I'm not convinced this is the way to go to make sorting faster. I'm not
sure I
like the "prepare for multiple writes" approach, although I can see the
advantage of not updating the write barrier for every step one takes during
a
permutation. It just seems ... fragile.
I do understand your concerns and would understand if you suggest to cancel
this
CL.
One argument in favour of this approach: that should be a common idiom to do
many writes into a single array. So we could benefit from this trick
currently
in several library functions and ideally even in compiler: if it can prove
we do
many writes into the same array, it could do the same trick.
Again, if you think that complexity and fragility added outweights
performance
benefit, that's fine.
In the easy cases (no element accessors, no inherited elements, etc.), >
maybe
we
should go to pure C++ code, and then leave a JavaScript version for the
cases
with complications (which never happens in practice).
The only problem with that approach is calling the compare function will
have
us
jumping in and out of JS all the time.
I started exactly with this approach. However it turned out the this
transitions from C++ to JS makes all the algorithms I tried roughly twice as
expensive (even after extensive caching of various stuff). Plus that won't
solve the problem of rset updates.
If you have some spare cycles, I could upload my CL in case if you could
spot
obvious optimization opportunity I missed.
Thanks a lot for first round of comments, Lasse.
http://codereview.chromium.org/1737007/diff/2001/3001
File src/array.js (right):
http://codereview.chromium.org/1737007/diff/2001/3001#newcode683
src/array.js:683: %_SwapElements(a, i, low_end);
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
It would seem this does one read more than the current code (a value
that we
already have in a variable).
Can't that be helped? Or is it faster anyway?
I didn't check if it's faster. Could we leave at for later if this CL
is a way too go?
http://codereview.chromium.org/1737007/diff/2001/3003
File src/heap-inl.h (right):
http://codereview.chromium.org/1737007/diff/2001/3003#newcode184
src/heap-inl.h:184: additional_scavenge_roots_.Add(object);
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
Why not just use a handle?
What kind of handle?
http://codereview.chromium.org/1737007/diff/2001/3006
File src/ia32/codegen-ia32.cc (right):
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6622
src/ia32/codegen-ia32.cc:6622: __ CallRuntime(Runtime::kSwapElements,
3);
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
So if the JSArray have index-accessors, we go to runtime for every
Swap (twice
per loop iteration of the sort function).
Wouldn't it be better to have two sort versions - one in pure
JavaScript, and
one optimized version for when we are sorting a plain Array with no
complications. Then we just need to test for complications once.
I think we go only once and we would go anyway as indexed interceptor
have to invoke runtime.
I do agree that lifting checks out of loop is a good idea, I just don't
want to double number of JS implementations (see below for native
implementation).
But I am planning to merge to implementations back soon, so it might be
an option.
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6630
src/ia32/codegen-ia32.cc:6630: // Note: object MUST have been prepared
for multiple writes!
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
Which object? Where do you test it?
Receiver. No, I don't test it. If you like I could probably add code
in debug mode to check that it's a top of additional roots stack.
Another approach might be to access the top directly, so protocol would
be you push the object and when use swaps on it.
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6661
src/ia32/codegen-ia32.cc:6661: // Check the object's elements are in
fast case.
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
You need to check that object is a JSObject.
This is a runtime-function, you must check arguments throughly.
Good catch, thanks a lot.
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6672
src/ia32/codegen-ia32.cc:6672: if (FLAG_debug_code) __
AbortIfNotSmi(index2.reg());
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
These tests should always be made. Don't trust parameters.
Those parameters are internal, so I kind of could trust them, but surely
I can have explicit checks here.
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6693
src/ia32/codegen-ia32.cc:6693: FixedArray::kHeaderSize), object.reg());
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
Swap the stores, so the value read first is also written first (I
guess it will
give it better time to resolve the load - even if it's writing to the
element
that is currently being read).
Good idea, done.
http://codereview.chromium.org/1737007/diff/2001/3006#newcode6695
src/ia32/codegen-ia32.cc:6695: // for multiple writes before.
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
You need to be able to test that. This code must not fail if a
non-prepared
object gets here.
See above
http://codereview.chromium.org/1737007/diff/2001/3009
File src/runtime.cc (right):
http://codereview.chromium.org/1737007/diff/2001/3009#newcode7769
src/runtime.cc:7769: // we properly updated remembered set on each swap.
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
What if the array changed to non-fast mode *during* sorting?
Remember we use this with a user-provided comparison function as well,
so it
might change any assumption at any time during sorting. Including
adding
accessors and changing the length of the array.
The latter per spec leads to undefined behaviour, but I agree with you,
let's play safe.
http://codereview.chromium.org/1737007/diff/2001/3009#newcode7785
src/runtime.cc:7785: Handle<Object> object = args.at<Object>(0);
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
Use
CONVERT_ARG_CHECKED(JSObject, object, 0);
That also throws the appropriate exception if conversion fails.
This is not so important if this function is never called directly
from JS code,
but then you need to check the arguments in the _SwapElements code.
Why I need JSObject here? Cannot Array.sort work on, say, strings?
http://codereview.chromium.org/1737007/diff/2001/3009#newcode7789
src/runtime.cc:7789: Handle<Object> tmp1 = GetProperty(object, key1);
On 2010/04/23 11:49:36, Lasse Reichstein wrote:
Shouldn't this be GetElement? Ditto for SetElement below.
Sure.
http://codereview.chromium.org/1737007/show
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
