Skip to content

Commit e7efa1b

Browse files
ConstellationConstellation
committed
[JSC] Define Array#sort's implementation functions as globalPrivate
https://bugs.webkit.org/show_bug.cgi?id=217168 Reviewed by Ross Kirsling. Now, these Array#sort's implementation functions are not capturing any heap variables. So we can make them @GlobalPrivate, this avoids function allocations in LLInt / Baseline / DFG in Array#sort. * builtins/ArrayPrototype.js: (globalPrivate.sortMin): (globalPrivate.sortStringComparator): (globalPrivate.sortCompact): (globalPrivate.sortCommit): (globalPrivate.sortMerge): (globalPrivate.sortMergeSort): (globalPrivate.sortBucketSort): (sort): (sort.min): Deleted. (sort.stringComparator): Deleted. (sort.compact): Deleted. (sort.commit): Deleted. (sort.merge): Deleted. (sort.mergeSort): Deleted. (sort.bucketSort): Deleted. Canonical link: https://commits.webkit.org/229946@main git-svn-id: https://svn.webkit.org/repository/webkit/trunk@267827 268f45cc-cd09-0410-ab3c-d52691b4dbfc
1 parent 4ed991f commit e7efa1b

2 files changed

Lines changed: 171 additions & 121 deletions

File tree

‎Source/JavaScriptCore/ChangeLog‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,30 @@
1+
2020-10-01 Yusuke Suzuki <ysuzuki@apple.com>
2+
3+
[JSC] Define Array#sort's implementation functions as globalPrivate
4+
https://bugs.webkit.org/show_bug.cgi?id=217168
5+
6+
Reviewed by Ross Kirsling.
7+
8+
Now, these Array#sort's implementation functions are not capturing any heap variables. So we can make them @globalPrivate,
9+
this avoids function allocations in LLInt / Baseline / DFG in Array#sort.
10+
11+
* builtins/ArrayPrototype.js:
12+
(globalPrivate.sortMin):
13+
(globalPrivate.sortStringComparator):
14+
(globalPrivate.sortCompact):
15+
(globalPrivate.sortCommit):
16+
(globalPrivate.sortMerge):
17+
(globalPrivate.sortMergeSort):
18+
(globalPrivate.sortBucketSort):
19+
(sort):
20+
(sort.min): Deleted.
21+
(sort.stringComparator): Deleted.
22+
(sort.compact): Deleted.
23+
(sort.commit): Deleted.
24+
(sort.merge): Deleted.
25+
(sort.mergeSort): Deleted.
26+
(sort.bucketSort): Deleted.
27+
128
2020-10-01 Yusuke Suzuki <ysuzuki@apple.com>
229

330
[JSC] Do not use std::function in setPrivateField and definePrivateField

‎Source/JavaScriptCore/builtins/ArrayPrototype.js‎

Lines changed: 144 additions & 121 deletions
Original file line numberDiff line numberDiff line change
@@ -306,157 +306,180 @@ function includes(searchElement /*, fromIndex*/)
306306
return false;
307307
}
308308

309-
function sort(comparator)
309+
@globalPrivate
310+
function sortMin(a, b)
310311
{
311312
"use strict";
312313

313-
function min(a, b)
314-
{
315-
return a < b ? a : b;
316-
}
314+
return a < b ? a : b;
315+
}
317316

318-
function stringComparator(a, b)
319-
{
320-
var aString = a.string;
321-
var bString = b.string;
317+
@globalPrivate
318+
function sortStringComparator(a, b)
319+
{
320+
"use strict";
322321

323-
if (aString === bString)
324-
return 0;
322+
var aString = a.string;
323+
var bString = b.string;
325324

326-
return aString > bString ? 1 : -1;
327-
}
325+
if (aString === bString)
326+
return 0;
328327

329-
function compact(receiver, receiverLength, compacted, isStringSort)
330-
{
331-
var undefinedCount = 0;
332-
var compactedIndex = 0;
333-
334-
for (var i = 0; i < receiverLength; ++i) {
335-
if (i in receiver) {
336-
var value = receiver[i];
337-
if (value === @undefined)
338-
++undefinedCount;
339-
else {
340-
@putByValDirect(compacted, compactedIndex,
341-
isStringSort ? {string: @toString(value), value} : value);
342-
++compactedIndex;
343-
}
328+
return aString > bString ? 1 : -1;
329+
}
330+
331+
@globalPrivate
332+
function sortCompact(receiver, receiverLength, compacted, isStringSort)
333+
{
334+
"use strict";
335+
336+
var undefinedCount = 0;
337+
var compactedIndex = 0;
338+
339+
for (var i = 0; i < receiverLength; ++i) {
340+
if (i in receiver) {
341+
var value = receiver[i];
342+
if (value === @undefined)
343+
++undefinedCount;
344+
else {
345+
@putByValDirect(compacted, compactedIndex,
346+
isStringSort ? {string: @toString(value), value} : value);
347+
++compactedIndex;
344348
}
345349
}
346-
347-
return undefinedCount;
348350
}
349351

352+
return undefinedCount;
353+
}
354+
355+
@globalPrivate
356+
function sortCommit(receiver, receiverLength, sorted, undefinedCount)
357+
{
358+
"use strict";
359+
350360
// Move undefineds and holes to the end of an array. Result is [values..., undefineds..., holes...].
351-
function commit(receiver, receiverLength, sorted, undefinedCount)
352-
{
353-
@assert(@isJSArray(sorted));
354-
var sortedLength = sorted.length;
355-
@assert(sortedLength + undefinedCount <= receiverLength);
356-
357-
var i = 0;
358-
if (@isJSArray(receiver) && sortedLength >= 64 && typeof sorted[0] !== "number") { // heuristic
359-
@appendMemcpy(receiver, sorted, 0);
360-
i = sortedLength;
361-
} else {
362-
for (; i < sortedLength; ++i)
363-
receiver[i] = sorted[i];
364-
}
365361

366-
for (; i < sortedLength + undefinedCount; ++i)
367-
receiver[i] = @undefined;
362+
@assert(@isJSArray(sorted));
363+
var sortedLength = sorted.length;
364+
@assert(sortedLength + undefinedCount <= receiverLength);
368365

369-
for (; i < receiverLength; ++i)
370-
delete receiver[i];
366+
var i = 0;
367+
if (@isJSArray(receiver) && sortedLength >= 64 && typeof sorted[0] !== "number") { // heuristic
368+
@appendMemcpy(receiver, sorted, 0);
369+
i = sortedLength;
370+
} else {
371+
for (; i < sortedLength; ++i)
372+
receiver[i] = sorted[i];
371373
}
372374

373-
function merge(dst, src, srcIndex, srcEnd, width, comparator)
374-
{
375-
var left = srcIndex;
376-
var leftEnd = min(left + width, srcEnd);
377-
var right = leftEnd;
378-
var rightEnd = min(right + width, srcEnd);
379-
380-
for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
381-
if (right < rightEnd) {
382-
if (left >= leftEnd) {
383-
@putByValDirect(dst, dstIndex, src[right]);
384-
++right;
385-
continue;
386-
}
375+
for (; i < sortedLength + undefinedCount; ++i)
376+
receiver[i] = @undefined;
387377

388-
// See https://bugs.webkit.org/show_bug.cgi?id=47825 on boolean special-casing
389-
var comparisonResult = comparator(src[right], src[left]);
390-
if (comparisonResult === false || comparisonResult < 0) {
391-
@putByValDirect(dst, dstIndex, src[right]);
392-
++right;
393-
continue;
394-
}
378+
for (; i < receiverLength; ++i)
379+
delete receiver[i];
380+
}
381+
382+
383+
@globalPrivate
384+
function sortMerge(dst, src, srcIndex, srcEnd, width, comparator)
385+
{
386+
"use strict";
387+
388+
var left = srcIndex;
389+
var leftEnd = @sortMin(left + width, srcEnd);
390+
var right = leftEnd;
391+
var rightEnd = @sortMin(right + width, srcEnd);
392+
393+
for (var dstIndex = left; dstIndex < rightEnd; ++dstIndex) {
394+
if (right < rightEnd) {
395+
if (left >= leftEnd) {
396+
@putByValDirect(dst, dstIndex, src[right]);
397+
++right;
398+
continue;
399+
}
395400

401+
// See https://bugs.webkit.org/show_bug.cgi?id=47825 on boolean special-casing
402+
var comparisonResult = comparator(src[right], src[left]);
403+
if (comparisonResult === false || comparisonResult < 0) {
404+
@putByValDirect(dst, dstIndex, src[right]);
405+
++right;
406+
continue;
396407
}
397408

398-
@putByValDirect(dst, dstIndex, src[left]);
399-
++left;
400409
}
410+
411+
@putByValDirect(dst, dstIndex, src[left]);
412+
++left;
401413
}
414+
}
402415

403-
function mergeSort(array, comparator)
404-
{
405-
var valueCount = array.length;
406-
var buffer = @newArrayWithSize(valueCount);
407-
408-
var dst = buffer;
409-
var src = array;
410-
for (var width = 1; width < valueCount; width *= 2) {
411-
for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
412-
merge(dst, src, srcIndex, valueCount, width, comparator);
413-
414-
var tmp = src;
415-
src = dst;
416-
dst = tmp;
417-
}
416+
@globalPrivate
417+
function sortMergeSort(array, comparator)
418+
{
419+
"use strict";
420+
421+
var valueCount = array.length;
422+
var buffer = @newArrayWithSize(valueCount);
423+
424+
var dst = buffer;
425+
var src = array;
426+
for (var width = 1; width < valueCount; width *= 2) {
427+
for (var srcIndex = 0; srcIndex < valueCount; srcIndex += 2 * width)
428+
@sortMerge(dst, src, srcIndex, valueCount, width, comparator);
418429

419-
return src;
430+
var tmp = src;
431+
src = dst;
432+
dst = tmp;
420433
}
421434

422-
function bucketSort(array, dst, bucket, depth)
423-
{
424-
if (bucket.length < 32 || depth > 32) {
425-
var sorted = mergeSort(bucket, stringComparator);
426-
for (var i = 0; i < sorted.length; ++i) {
427-
@putByValDirect(array, dst, sorted[i].value);
428-
++dst;
429-
}
430-
return dst;
431-
}
435+
return src;
436+
}
432437

433-
var buckets = [ ];
434-
for (var i = 0; i < bucket.length; ++i) {
435-
var entry = bucket[i];
436-
var string = entry.string;
437-
if (string.length == depth) {
438-
@putByValDirect(array, dst, entry.value);
439-
++dst;
440-
continue;
441-
}
438+
@globalPrivate
439+
function sortBucketSort(array, dst, bucket, depth)
440+
{
441+
"use strict";
442442

443-
var c = string.@charCodeAt(depth);
444-
var cBucket = buckets[c];
445-
if (cBucket)
446-
@putByValDirect(cBucket, cBucket.length, entry);
447-
else
448-
@putByValDirect(buckets, c, [ entry ]);
443+
if (bucket.length < 32 || depth > 32) {
444+
var sorted = @sortMergeSort(bucket, @sortStringComparator);
445+
for (var i = 0; i < sorted.length; ++i) {
446+
@putByValDirect(array, dst, sorted[i].value);
447+
++dst;
449448
}
449+
return dst;
450+
}
450451

451-
for (var i = 0; i < buckets.length; ++i) {
452-
if (!buckets[i])
453-
continue;
454-
dst = bucketSort(array, dst, buckets[i], depth + 1);
452+
var buckets = [ ];
453+
for (var i = 0; i < bucket.length; ++i) {
454+
var entry = bucket[i];
455+
var string = entry.string;
456+
if (string.length == depth) {
457+
@putByValDirect(array, dst, entry.value);
458+
++dst;
459+
continue;
455460
}
456461

457-
return dst;
462+
var c = string.@charCodeAt(depth);
463+
var cBucket = buckets[c];
464+
if (cBucket)
465+
@putByValDirect(cBucket, cBucket.length, entry);
466+
else
467+
@putByValDirect(buckets, c, [ entry ]);
458468
}
459469

470+
for (var i = 0; i < buckets.length; ++i) {
471+
if (!buckets[i])
472+
continue;
473+
dst = @sortBucketSort(array, dst, buckets[i], depth + 1);
474+
}
475+
476+
return dst;
477+
}
478+
479+
function sort(comparator)
480+
{
481+
"use strict";
482+
460483
var isStringSort = false;
461484
if (comparator === @undefined)
462485
isStringSort = true;
@@ -473,15 +496,15 @@ function sort(comparator)
473496

474497
var compacted = [ ];
475498
var sorted = null;
476-
var undefinedCount = compact(receiver, receiverLength, compacted, isStringSort);
499+
var undefinedCount = @sortCompact(receiver, receiverLength, compacted, isStringSort);
477500

478501
if (isStringSort) {
479502
sorted = @newArrayWithSize(compacted.length);
480-
bucketSort(sorted, 0, compacted, 0);
503+
@sortBucketSort(sorted, 0, compacted, 0);
481504
} else
482-
sorted = mergeSort(compacted, comparator);
505+
sorted = @sortMergeSort(compacted, comparator);
483506

484-
commit(receiver, receiverLength, sorted, undefinedCount);
507+
@sortCommit(receiver, receiverLength, sorted, undefinedCount);
485508
return receiver;
486509
}
487510

0 commit comments

Comments
 (0)