Description
tav
2009-06-13 23:17:56 PDT
*** Bug 32243 has been marked as a duplicate of this bug. *** Would be great to have this. And here's a similar Mozilla ticket for reference — https://bugzilla.mozilla.org/show_bug.cgi?id=429507 Created attachment 53992 [details]
Attempt to implement Function.prototype.bind()
Created attachment 54158 [details]
Attempt 2 to implement Function.prototype.bind()
This clean up some minor issues, adds tests and more build systems support. The implementation for a very simple case (just binding 'this' in a small function without parameters), is around 4 times slower than using JS directly. When there's complexity, this difference is smaller: taking around 50% more time in more complex cases (with curried parameter and a larger function). Talking to Oliver Hunt, if I understood correctly this overhead might be due the re-entering the VM.
I don't think we should land a version of Function.prototype.bind() if it is slower than a JS-implemented version. We should look into ways to make this faster, or find a way to implement fully or partially in JS but still look native in the required ways. The fastest implementation of `bind` I was able to come up with back in the days was the one with load-time + run-time forking (to avoid unnecessary arguments concatenation). Does native `bind` perform better than this "optimized" version? Function.prototype.bind = (function(){ var _slice = Array.prototype.slice; return function(context) { var fn = this, args = _slice.call(arguments, 1); if (args.length) { return function() { return arguments.length ? fn.apply(context, args.concat(_slice.call(arguments))) : fn.apply(context, args); } } return function() { return arguments.length ? fn.apply(context, arguments) : fn.call(context); }; } })(); There are also some tests in this thread: https://prototype.lighthouseapp.com/projects/8886/tickets/215-optimize-bind-bindaseventlistener Thanks for looking into it. For the record, the simplest case (and the one with worst performance) I was testing was comparing 'g' and 'h' g = function() { return obj.f(); } h = obj.f.bind(obj); // using the native implementation Agreed that we should land a solution only if it is not slower. So, I'll look into Maciej's suggestions to improve the performance and report back here. There's a benchmark for the bind() function, which includes both Prototype.js trunk implementation and the one pointed out by kangax: http://www.broofa.com/Tools/JSLitmus/tests/PrototypeBind.html I've changed my patch to rename the native bind to 'bindNative' (so no collisions with any other implementation), and added a case for it. My conclusion is that the situation isn't as bad as we thought. The difference between my previous tests is that real world 'bind()' implementations perform worse than special tuned functions that I was using. Results in the following chart -> http://chart.apis.google.com/chart?chtt=Prototype%20bind()%20Performance|Ops/sec%20(Safari%20533.7%20on%20Linux)&chts=000000,10&cht=bhg&chd=t:8258481,7556237,6140297,1255825,873981,641343,1546185,981289,788777,20532293,966813,778470,20099368,2898464,2094766,4424939,3588929,509668,4555667,2904887,2065063&chds=0,20532293&chxt=x&chxl=0:|0|20.5M&chsp=0,1&chm=tnative%20bind(obj)(8.3M),000000,0,0,10|tnative%20bind(obj\,1\,2)(7.6M),000000,0,1,10|tnative%20bind(obj\,1\,2[\,3\,4])(6.1M),000000,0,2,10|t1.6.0.3%20bind(obj)(1.3M),000000,0,3,10|t1.6.0.3%20bind(obj\,1\,2)(874K),000000,0,4,10|t1.6.0.3%20bind(obj\,1\,2[\,3\,4])(641.3K),000000,0,5,10|ttrunk%20bind(obj)(1.5M),000000,0,6,10|ttrunk%20bind(obj\,1\,2)(981.3K),000000,0,7,10|ttrunk%20bind(obj\,1\,2[\,3\,4])(788.8K),000000,0,8,10|tTobie's%20bind(obj)(20.5M),000000,0,9,10|tTobie's%20bind(obj\,1\,2)(966.8K),000000,0,10,10|tTobie's%20bind(obj\,1\,2[\,3\,4])(778.5K),000000,0,11,10|tBroofa's%20bind(obj)(20.1M),000000,0,12,10|tBroofa's%20bind(obj\,1\,2)(2.9M),000000,0,13,10|tBroofa's%20bind(obj\,1\,2[\,3\,4])(2.1M),000000,0,14,10|tKangax's%20bind(obj)(4.4M),000000,0,15,10|tKangax's%20bind(obj\,1\,2)(3.6M),000000,0,16,10|tKangax's%20bind(obj\,1\,2[\,3\,4])(509.7K),000000,0,17,10|tImproved%20bind(obj)(4.6M),000000,0,18,10|tImproved%20bind(obj\,1\,2)(2.9M),000000,0,19,10|tImproved%20bind(obj\,1\,2[\,3\,4])(2.1M),000000,0,20,10&chbh=15,0,5&chs=250x490 Okay, here's my thought for getting a non-reentrant version of bind, it only works for non-partially applied bound functions (but according to Caio's numbers the native impl of partially applied bind is faster than the js version). Basically we do this: DEFINE_OPCODE(op_call) { ... call_start: JSValue v = callFrame->r(func).jsValue(); CallData callData; CallType callType = v.getCallData(callData); if (callType == CallTypeJS) { ... if (callType == CallTypeHost) { if (callData.boundFunction) { callFrame->r(func) = callData.boundFunction; // we actually need to work out what thisRegister is :D callFrame->r(thisRegister) = static_cast<JSBoundFunction*>(v.asCell())->thisArgument(); goto call_start; } ... That should save the reentry cost -- in the jit we'd probably just want to do the handling on return from host call stub. Created attachment 54243 [details]
Native implementation of Function.prototype.bind()
Same as before, just fixes order of functions.
Created attachment 54245 [details] Optimization for bind() used just for binding 'this' (non JIT case) This patch follows the suggestion of Oliver Hunt in the bug comments. For the non-JIT case, this will make the native implementation win all the other JavaScript-only implementations we found out. In my local tests it even gets a better result than the explicit 'function() { obj.method(); }' call. We are using http://www.broofa.com/Tools/JSLitmus/tests/PrototypeBind.html as the benchmark. Created attachment 54896 [details]
Native implementation of Function.prototype.bind(), v4
Use Cell space available, and avoid allocating space for holding arguments if they are not used.
Created attachment 54897 [details]
Optimization for bind() used just for binding 'this' (non JIT case)
Updated because of changes in previous patch.
Created attachment 54898 [details]
Optimization for bind() used just for binding 'this' (JIT case)
Uses same idea from previous optimization in the JIT context. With this patch, in the linked benchmark, the native is faster all the three scenarios.
Created attachment 54900 [details]
Optimization for bind() used just for binding 'this' (non JIT case)
After some discussion with Oliver and testing, it isn't always safe to rewrite the 'callee' register, since it might be reused by the bytecode. For the non-JIT case the fix is simple, just change the local variable used instead of the call frame.
The JIT version is already correct in this case, but suffer other problem: that slow cases can look at the callee register again (ex.: compileOpCallSlowCase() when OPTIMIZED_CALL is disabled).
Created attachment 55158 [details]
Native implementation of Function.prototype.bind(), v5
Adds a missing 'OverridesMarkChildren' to the StructureFlags of JSBoundFunction. This is needed because JSBoundFunction implements markChildren method.
Also added new test cases to guarantee that CallFrame rewriting done by possible optimizations will not break the code.
Created attachment 55161 [details]
Optimization for bind() used just for binding 'this' (JIT case), v2
This an improvement of earlier implementation of the JIT rewriting optimization.
Functionally it should be complete, still have a FIXME to check and possibly removing a redundant information passed to the stub. Note that I'm still working only in one case of Call until we settle in a solution.
After some tests and discussion with Oliver, we understood that it was not always safe to rewrite the register containing the 'callee' since it could be a non-temporary register. The solution in this patch is to force every call emitted to use a temporary for 'callee'. This causes impact on the size of bytecode generated, but guarantee that it's safe to rewrite the call frame, making the optimization correct.
I still want to give a different take on optimizing this case, and try to save/restore the 'callee' instead of guarantee that it is always a temporary. Then compare both solutions.
Created attachment 55852 [details]
Native implementation of Function.prototype.bind(), v6
Fixes building in 64bits: JSBoundFunction was too large to fit in the cell, so moved other members inside the private data. Tested that on MacOSX.
Also cached the CallData information of target function, this gave a small boost in performance.
I'd really prefer that we didn't add overhead to normal calls in order to make bind faster. We're working really hard right now to remove overhead from normal calls, and it's paying off in terms of performance. (In reply to comment #20) > I'd really prefer that we didn't add overhead to normal calls in order to make bind faster. We're working really hard right now to remove overhead from normal calls, and it's paying off in terms of performance. Geoff actually pointed out that the new specialised thunk stuff i added would potentially make the jit code much easier. I think a better solution would be for the binding function to fix up callframe[callee] and callframe[this], and then jump to the bound function. ping The lack of this is starting to cause compat issue. (In reply to comment #23) > ping > > The lack of this is starting to cause compat issue. Given that JS can be used to make a reasonably performant implementation and most sites that use Function.prototype.bind do actually start of with an existence check and then add the js impl this is not high priority. (In reply to comment #24) > (In reply to comment #23) > > ping > > > > The lack of this is starting to cause compat issue. > > Given that JS can be used to make a reasonably performant implementation and most sites that use Function.prototype.bind do actually start of with an existence check and then add the js impl this is not high priority. JS can reasonably emulate the [[Call]] behavior of .bind() but not its [[Construct]] behavior. This is important because the [[Construct]] behavior of .bind() is the only way to implement a correct var-args construction (new) operation in ES5. another ping The lack of this is starting to cause compatibility issues in some of the browser-based tooling being done at Eclipse. (In reply to comment #26) > The lack of this is starting to cause compatibility issues in some of the browser-based tooling being done at Eclipse. To be clear the shim is fine for our case. Just comes as a surprise that we need it for JSC given that all other current VMs provide support. Despite our best effort to inform we get folk using Function.bind and testing in other browsers and then have failing unit tests during our nightly builds. Hello Geoffrey, (In reply to comment #22) > I think a better solution would be for the binding function to fix up callframe[callee] and callframe[this], and then jump to the bound function. Is this still valid? Can you elaborate a bit on that? (In reply to comment #25) > > JS can reasonably emulate the [[Call]] behavior of .bind() but not > its [[Construct]] behavior. This is important because the [[Construct]] > behavior of .bind() is the only way to implement a correct var-args > construction (new) operation in ES5. To expand on that, given the ES5 specified Function.prototype.bind, one can implement a "construct(f, args)" operation as follows: > function construct(f, args) { > var bound = Function.prototype.bind.apply(f, [null].concat(args)); > return new bound(); > } > construct(Date, [1957, 5, 27]) Thu Jun 27 1957 00:00:00 GMT-0700 (PDT) Without the specified primitive implementation of bind, I know of no way for a pure JavaScript shim to correctly emulate this behavior, and therefore no way for an ES-next to ES5 compiler to correctly compile "new f(...args)" to ES5. Created attachment 108382 [details]
New patch, reentrant implementation.
A fresh implementation. This has three interesting features:
* Based on ToT!
* Subclasses JSFunction (this allows the JIT to make fast calls to bound functions)
* Cell size is no longer restricted (doesn't need a data object).
Attachment 108382 [details] did not pass style-queue:
Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
Source/JavaScriptCore/runtime/ConstructData.h:33: Alphabetical sorting problem. [build/include_order] [4]
Source/JavaScriptCore/runtime/JSFunction.h:47: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:47: The parameter name "descriptor" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "globalObject" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "nativeFunction" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "globalObject" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "nativeExecutable" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:134: The parameter name "mode" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSBoundFunction.h:45: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSBoundFunction.h:45: The parameter name "value" adds no information, so it should be removed. [readability/parameter_name] [5]
Total errors found: 12 in 57 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Comment on attachment 108382 [details] New patch, reentrant implementation. View in context: https://bugs.webkit.org/attachment.cgi?id=108382&action=review > Source/JavaScriptCore/runtime/JSBoundFunction.cpp:92 > + // FIXME: our instanceof implementation will have already (incorrectly) performed > + // a [[Get]] of .prototype from the bound function object, which is incorrect! > + proto = m_targetFunction->get(exec, exec->propertyNames().prototype); You should add a test showing this is incorrect. > Source/JavaScriptCore/runtime/JSBoundFunction.h:66 > + WriteBarrier<JSObject> m_targetFunction; > + WriteBarrier<Unknown> m_boundThis; > + WriteBarrier<Unknown> m_boundArgs; How are these marked? Comment on attachment 108382 [details] New patch, reentrant implementation. Attachment 108382 [details] did not pass qt-ews (qt): Output: http://queues.webkit.org/results/9798358 Comment on attachment 108382 [details] New patch, reentrant implementation. Attachment 108382 [details] did not pass efl-ews (efl): Output: http://queues.webkit.org/results/9792455 Created attachment 108399 [details]
Build fixes, GC fixes, added more test cases, fix for recursive hasInstance
Attachment 108399 [details] did not pass style-queue:
Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
Source/JavaScriptCore/runtime/ConstructData.h:33: Alphabetical sorting problem. [build/include_order] [4]
Source/JavaScriptCore/runtime/JSFunction.h:47: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:47: The parameter name "descriptor" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "globalObject" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:57: The parameter name "nativeFunction" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "globalObject" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:58: The parameter name "nativeExecutable" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSFunction.h:135: The parameter name "mode" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSBoundFunction.h:45: The parameter name "exec" adds no information, so it should be removed. [readability/parameter_name] [5]
Source/JavaScriptCore/runtime/JSBoundFunction.h:45: The parameter name "value" adds no information, so it should be removed. [readability/parameter_name] [5]
Total errors found: 12 in 63 files
If any of these errors are false positives, please file a bug against check-webkit-style.
Fixed in r95751. Comment on attachment 108399 [details] Build fixes, GC fixes, added more test cases, fix for recursive hasInstance View in context: https://bugs.webkit.org/attachment.cgi?id=108399&action=review > LayoutTests/fast/js/Object-getOwnPropertyNames-expected.txt:46 > -PASS getSortedOwnPropertyNames(Function.prototype) is ['apply', 'call', 'constructor', 'length', 'name', 'toString'] > +FAIL getSortedOwnPropertyNames(Function.prototype) should be apply,call,constructor,length,name,toString. Was apply,bind,call,constructor,length,name,toString. Shouldn't we update the test to expect the bind property? (In reply to comment #38) > (From update of attachment 108399 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=108399&action=review > > > LayoutTests/fast/js/Object-getOwnPropertyNames-expected.txt:46 > > -PASS getSortedOwnPropertyNames(Function.prototype) is ['apply', 'call', 'constructor', 'length', 'name', 'toString'] > > +FAIL getSortedOwnPropertyNames(Function.prototype) should be apply,call,constructor,length,name,toString. Was apply,bind,call,constructor,length,name,toString. > > Shouldn't we update the test to expect the bind property? Ooops, yes, meant to do so, clearly forgot to. Will do. |