Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(55)

Side by Side Diff: src/array.js

Issue 20416: Reverese attempted optimization of array sort. (Closed)
Patch Set: Created 11 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. 1 // Copyright 2006-2008 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 665 matching lines...) Expand 10 before | Expand all | Expand 10 after
676 return; 676 return;
677 } 677 }
678 var pivot_index = $floor($random() * (to - from)) + from; 678 var pivot_index = $floor($random() * (to - from)) + from;
679 var pivot = a[pivot_index]; 679 var pivot = a[pivot_index];
680 // Pre-convert the element to a string for comparison if we know 680 // Pre-convert the element to a string for comparison if we know
681 // it will happen on each compare anyway. 681 // it will happen on each compare anyway.
682 var pivot_key = 682 var pivot_key =
683 (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot); 683 (custom_compare || %_IsSmi(pivot)) ? pivot : ToString(pivot);
684 // Issue 95: Keep the pivot element out of the comparisons to avoid 684 // Issue 95: Keep the pivot element out of the comparisons to avoid
685 // infinite recursion if comparefn(pivot, pivot) != 0. 685 // infinite recursion if comparefn(pivot, pivot) != 0.
686 var low_end = from; // Upper bound of the elements lower than pivot. 686 a[pivot_index] = a[from];
687 var high_start = to; // Lower bound of the elements greater than pivot. 687 a[from] = pivot;
688 var eq_start = to - 1; // Lower bound of elements equal to pivot. 688 var low_end = from; // Upper bound of the elements lower than pivot.
689 a[pivot_index] = a[eq_start]; 689 var high_start = to; // Lower bound of the elements greater than pivot.
690 a[eq_start] = pivot; 690 // From low_end to i are elements equal to pivot.
691 // From eq_start to high_start are elements equal to the pivot 691 // From i to high_start are elements that haven't been compared yet.
692 // (including the pivot). 692 for (var i = from + 1; i < high_start; ) {
693 // From low_end to eq_start are elements that have not been compared yet. 693 var element = a[i];
694 while (low_end < eq_start) {
695 var element = a[low_end];
696 var order = Compare(element, pivot_key); 694 var order = Compare(element, pivot_key);
697 if (order < 0) { 695 if (order < 0) {
696 a[i] = a[low_end];
697 a[low_end] = element;
698 i++;
698 low_end++; 699 low_end++;
699 } else if (order > 0) { 700 } else if (order > 0) {
700 eq_start--;
701 high_start--; 701 high_start--;
702 a[low_end] = a[eq_start]; 702 a[i] = a[high_start];
703 a[eq_start] = a[high_start];
704 a[high_start] = element; 703 a[high_start] = element;
705 } else { // order == 0 704 } else { // order == 0
706 eq_start--; 705 i++;
707 a[low_end] = a[eq_start];
708 a[eq_start] = element;
709 } 706 }
710 } 707 }
711 QuickSort(a, from, low_end); 708 QuickSort(a, from, low_end);
712 QuickSort(a, high_start, to); 709 QuickSort(a, high_start, to);
713 } 710 }
714 711
715 var old_length = ToUint32(this.length); 712 var old_length = ToUint32(this.length);
716 if (old_length < 2) return this; 713 if (old_length < 2) return this;
717 714
718 %RemoveArrayHoles(this); 715 %RemoveArrayHoles(this);
(...skipping 213 matching lines...) Expand 10 before | Expand all | Expand 10 after
932 ArrayEvery: 1, 929 ArrayEvery: 1,
933 ArrayMap: 1, 930 ArrayMap: 1,
934 ArrayIndexOf: 1, 931 ArrayIndexOf: 1,
935 ArrayLastIndexOf: 1, 932 ArrayLastIndexOf: 1,
936 ArrayPush: 1 933 ArrayPush: 1
937 }); 934 });
938 } 935 }
939 936
940 937
941 SetupArray(); 938 SetupArray();
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698