Early specialize sorting functions depending if there is a custom comparator or not.

Early specialize sorting functions depending if there is a custom comparator or not.

Committed: http://code.google.com/p/v8/source/detail?r=4356

[antonm, 2010-04-07 12:10:42]

Mads, Ivan,

may you have a look?

It's not a huge boost, but hopefully it should enable more optimizations later.

But yes, code duplication is rather unfortunate so up to you if it's worth it.

[iegorov, 2010-04-07 12:27:57]

LGTM

http://codereview.chromium.org/1513020/diff/1/2
File src/array.js (right):

http://codereview.chromium.org/1513020/diff/1/2#newcode657
src/array.js:657: var order = (a[mid] === element) ? 0 : comparefn.call(null,
a[mid], element);
long line.

http://codereview.chromium.org/1513020/diff/1/2#newcode694
src/array.js:694: var order = (element === pivot) ? 0 : comparefn.call(null,
element, pivot);
long line.

[Mads Ager (chromium), 2010-04-07 12:41:57]

LGTM

I do find the duplication annoying though, so let's not make it a habit. :)

[antonm, 2010-04-07 13:10:12]

Thanks a lot, guys.

@Mads: wholeheartedly agree.

http://codereview.chromium.org/1513020/diff/1/2
File src/array.js (right):

http://codereview.chromium.org/1513020/diff/1/2#newcode657
src/array.js:657: var order = (a[mid] === element) ? 0 : comparefn.call(null,
a[mid], element);
On 2010/04/07 12:27:57, iegorov wrote:
> long line.

Done.

http://codereview.chromium.org/1513020/diff/1/2#newcode694
src/array.js:694: var order = (element === pivot) ? 0 : comparefn.call(null,
element, pivot);
On 2010/04/07 12:27:57, iegorov wrote:
> long line.

Done.

[Lasse Reichstein, 2010-04-07 17:43:27]

Well, LGTM, but I never liked the current solution anyway :)

http://codereview.chromium.org/1513020/diff/7001/8001
File src/array.js (right):

http://codereview.chromium.org/1513020/diff/7001/8001#newcode649
src/array.js:649: var element = a[i];
Come to think of it, using binary search seems overkill, since we are going to
read and write every element after the found position anyway when we place the
element. 
Just do a backwards search-and-copy until finding the correct location. I.e,
something like:

  for (var j = i - 1; j >= from; j--) {
    var tmp = a[j];
    var order = tmp === element ? 0 : comparefn.call(null,tmp,element);
    if (order > 0) {
      a[j + 1] = tmp;
    } else if (order == 0) {
      j--;
      break;
    }
  }
  a[j + 1] = element;

http://codereview.chromium.org/1513020/diff/7001/8001#newcode658
src/array.js:658: 0 : comparefn.call(null, a[mid], element);
Reading a[mid] twice. Maybe assign to temporary variable.

http://codereview.chromium.org/1513020/diff/7001/8001#newcode660
src/array.js:660: min = max = mid;
No need to assign to max.

http://codereview.chromium.org/1513020/diff/7001/8001#newcode716
src/array.js:716: // If it isn't, we are allowed arbitrary behavior by ECMA
15.4.4.11.
Comment doesn't make sense any more (not here, at least).

[antonm, 2010-04-07 17:47:27]

Thanks, Lasse.  I'll prepare a CL cleaning up all the stuff you mentioned and
run it through perfbots.

http://codereview.chromium.org/1513020/diff/7001/8001
File src/array.js (right):

http://codereview.chromium.org/1513020/diff/7001/8001#newcode649
src/array.js:649: var element = a[i];
On 2010/04/07 17:43:27, Lasse Reichstein wrote:
> Come to think of it, using binary search seems overkill, since we are going to
> read and write every element after the found position anyway when we place the
> element. 
> Just do a backwards search-and-copy until finding the correct location. I.e,
> something like:
> 
>   for (var j = i - 1; j >= from; j--) {
>     var tmp = a[j];
>     var order = tmp === element ? 0 : comparefn.call(null,tmp,element);
>     if (order > 0) {
>       a[j + 1] = tmp;
>     } else if (order == 0) {
>       j--;
>       break;
>     }
>   }
>   a[j + 1] = element;
> 

Agree.  That's the thing I implemented in C++, but calling JS from C++ is
expensive.  I'll give it a try, but for now it doesn't look like the main reason
for slowness.

http://codereview.chromium.org/1513020/diff/7001/8001#newcode658
src/array.js:658: 0 : comparefn.call(null, a[mid], element);
On 2010/04/07 17:43:27, Lasse Reichstein wrote:
> Reading a[mid] twice. Maybe assign to temporary variable.
> 

Thanks, will give it a try.

http://codereview.chromium.org/1513020/diff/7001/8001#newcode660
src/array.js:660: min = max = mid;
On 2010/04/07 17:43:27, Lasse Reichstein wrote:
> No need to assign to max.

Will give it a try as well.

http://codereview.chromium.org/1513020/diff/7001/8001#newcode716
src/array.js:716: // If it isn't, we are allowed arbitrary behavior by ECMA
15.4.4.11.
On 2010/04/07 17:43:27, Lasse Reichstein wrote:
> Comment doesn't make sense any more (not here, at least).

Agree.  Will remove.