Mercurial > hg > truffle
annotate src/share/vm/utilities/quickSort.cpp @ 20543:e7d0505c8a30
8059758: Footprint regressions with JDK-8038423
Summary: Changes in JDK-8038423 always initialize (zero out) virtual memory used for auxiliary data structures. This causes a footprint regression for G1 in startup benchmarks. This is because they do not touch that memory at all, so the operating system does not actually commit these pages. The fix is to, if the initialization value of the data structures matches the default value of just committed memory (=0), do not do anything.
Reviewed-by: jwilhelm, brutisso
| author | tschatzl |
|---|---|
| date | Fri, 10 Oct 2014 15:51:58 +0200 |
| parents | 78bbf4d43a14 |
| children | 52b4284cb496 |
| rev | line source |
|---|---|
| 3779 | 1 /* |
|
17937
78bbf4d43a14
8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents:
10283
diff
changeset
|
2 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. |
| 3779 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
| 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| 20 * or visit www.oracle.com if you need additional information or have any | |
| 21 * questions. | |
| 22 * | |
| 23 */ | |
| 24 | |
| 25 #include "precompiled.hpp" | |
|
4070
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
26 |
|
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
27 /////////////// Unit tests /////////////// |
| 3779 | 28 |
| 29 #ifndef PRODUCT | |
| 30 | |
| 31 #include "runtime/os.hpp" | |
|
4070
6fd81579526f
7102044: G1: VM crashes with assert(old_end != new_end) failed: don't call this otherwise
brutisso
parents:
3981
diff
changeset
|
32 #include "utilities/quickSort.hpp" |
|
10271
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
33 #include "memory/allocation.hpp" |
|
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
34 #include "memory/allocation.inline.hpp" |
| 3779 | 35 #include <stdlib.h> |
| 36 | |
| 10274 | 37 #ifdef ASSERT |
| 3779 | 38 static int test_comparator(int a, int b) { |
| 39 if (a == b) { | |
| 40 return 0; | |
| 41 } | |
| 42 if (a < b) { | |
| 43 return -1; | |
| 44 } | |
| 45 return 1; | |
| 46 } | |
| 10274 | 47 #endif // ASSERT |
| 3779 | 48 |
| 49 static int test_even_odd_comparator(int a, int b) { | |
| 50 bool a_is_odd = (a % 2) == 1; | |
| 51 bool b_is_odd = (b % 2) == 1; | |
| 52 if (a_is_odd == b_is_odd) { | |
| 53 return 0; | |
| 54 } | |
| 55 if (a_is_odd) { | |
| 56 return -1; | |
| 57 } | |
| 58 return 1; | |
| 59 } | |
| 60 | |
| 3981 | 61 extern "C" { |
| 62 static int test_stdlib_comparator(const void* a, const void* b) { | |
| 63 int ai = *(int*)a; | |
| 64 int bi = *(int*)b; | |
| 65 if (ai == bi) { | |
| 66 return 0; | |
| 67 } | |
| 68 if (ai < bi) { | |
| 69 return -1; | |
| 70 } | |
| 71 return 1; | |
| 3779 | 72 } |
| 73 } | |
| 74 | |
| 75 void QuickSort::print_array(const char* prefix, int* array, int length) { | |
| 76 tty->print("%s:", prefix); | |
| 77 for (int i = 0; i < length; i++) { | |
| 78 tty->print(" %d", array[i]); | |
| 79 } | |
|
17937
78bbf4d43a14
8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents:
10283
diff
changeset
|
80 tty->cr(); |
| 3779 | 81 } |
| 82 | |
| 83 bool QuickSort::compare_arrays(int* actual, int* expected, int length) { | |
| 84 for (int i = 0; i < length; i++) { | |
| 85 if (actual[i] != expected[i]) { | |
| 86 print_array("Sorted array ", actual, length); | |
| 87 print_array("Expected array", expected, length); | |
| 88 return false; | |
| 89 } | |
| 90 } | |
| 91 return true; | |
| 92 } | |
| 93 | |
| 94 template <class C> | |
| 95 bool QuickSort::sort_and_compare(int* arrayToSort, int* expectedResult, int length, C comparator, bool idempotent) { | |
| 96 sort<int, C>(arrayToSort, length, comparator, idempotent); | |
| 97 return compare_arrays(arrayToSort, expectedResult, length); | |
| 98 } | |
| 99 | |
| 4708 | 100 void QuickSort::test_quick_sort() { |
| 3779 | 101 { |
| 102 int* test_array = NULL; | |
| 103 int* expected_array = NULL; | |
| 104 assert(sort_and_compare(test_array, expected_array, 0, test_comparator), "Empty array not handled"); | |
| 105 } | |
| 106 { | |
| 107 int test_array[] = {3}; | |
| 108 int expected_array[] = {3}; | |
| 109 assert(sort_and_compare(test_array, expected_array, 1, test_comparator), "Single value array not handled"); | |
| 110 } | |
| 111 { | |
| 112 int test_array[] = {3,2}; | |
| 113 int expected_array[] = {2,3}; | |
| 114 assert(sort_and_compare(test_array, expected_array, 2, test_comparator), "Array with 2 values not correctly sorted"); | |
| 115 } | |
| 116 { | |
| 117 int test_array[] = {3,2,1}; | |
| 118 int expected_array[] = {1,2,3}; | |
| 119 assert(sort_and_compare(test_array, expected_array, 3, test_comparator), "Array with 3 values not correctly sorted"); | |
| 120 } | |
| 121 { | |
| 122 int test_array[] = {4,3,2,1}; | |
| 123 int expected_array[] = {1,2,3,4}; | |
| 124 assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "Array with 4 values not correctly sorted"); | |
| 125 } | |
| 126 { | |
| 127 int test_array[] = {7,1,5,3,6,9,8,2,4,0}; | |
| 128 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 129 assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Array with 10 values not correctly sorted"); | |
| 130 } | |
| 131 { | |
| 132 int test_array[] = {4,4,1,4}; | |
| 133 int expected_array[] = {1,4,4,4}; | |
| 134 assert(sort_and_compare(test_array, expected_array, 4, test_comparator), "3 duplicates not sorted correctly"); | |
| 135 } | |
| 136 { | |
| 137 int test_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 138 int expected_array[] = {0,1,2,3,4,5,6,7,8,9}; | |
| 139 assert(sort_and_compare(test_array, expected_array, 10, test_comparator), "Already sorted array not correctly sorted"); | |
| 140 } | |
| 141 { | |
| 142 // one of the random arrays that found an issue in the partion method. | |
| 143 int test_array[] = {76,46,81,8,64,56,75,11,51,55,11,71,59,27,9,64,69,75,21,25,39,40,44,32,7,8,40,41,24,78,24,74,9,65,28,6,40,31,22,13,27,82}; | |
| 144 int expected_array[] = {6,7,8,8,9,9,11,11,13,21,22,24,24,25,27,27,28,31,32,39,40,40,40,41,44,46,51,55,56,59,64,64,65,69,71,74,75,75,76,78,81,82}; | |
| 145 assert(sort_and_compare(test_array, expected_array, 42, test_comparator), "Not correctly sorted"); | |
| 146 } | |
| 147 { | |
| 148 int test_array[] = {2,8,1,4}; | |
| 149 int expected_array[] = {1,4,2,8}; | |
| 150 assert(sort_and_compare(test_array, expected_array, 4, test_even_odd_comparator), "Even/odd not sorted correctly"); | |
| 151 } | |
| 152 { // Some idempotent tests | |
| 153 { | |
| 154 // An array of lenght 3 is only sorted by find_pivot. Make sure that it is idempotent. | |
| 155 int test_array[] = {1,4,8}; | |
| 156 int expected_array[] = {1,4,8}; | |
| 157 assert(sort_and_compare(test_array, expected_array, 3, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 158 } | |
| 159 { | |
| 160 int test_array[] = {1,7,9,4,8,2}; | |
| 161 int expected_array[] = {1,7,9,4,8,2}; | |
| 162 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 163 } | |
| 164 { | |
| 165 int test_array[] = {1,9,7,4,2,8}; | |
| 166 int expected_array[] = {1,9,7,4,2,8}; | |
| 167 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 168 } | |
| 169 { | |
| 170 int test_array[] = {7,9,1,2,8,4}; | |
| 171 int expected_array[] = {7,9,1,2,8,4}; | |
| 172 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 173 } | |
| 174 { | |
| 175 int test_array[] = {7,1,9,2,4,8}; | |
| 176 int expected_array[] = {7,1,9,2,4,8}; | |
| 177 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 178 } | |
| 179 { | |
| 180 int test_array[] = {9,1,7,4,8,2}; | |
| 181 int expected_array[] = {9,1,7,4,8,2}; | |
| 182 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 183 } | |
| 184 { | |
| 185 int test_array[] = {9,7,1,4,2,8}; | |
| 186 int expected_array[] = {9,7,1,4,2,8}; | |
| 187 assert(sort_and_compare(test_array, expected_array, 6, test_even_odd_comparator, true), "Even/odd not idempotent"); | |
| 188 } | |
| 189 } | |
| 190 | |
| 191 // test sorting random arrays | |
| 192 for (int i = 0; i < 1000; i++) { | |
| 193 int length = os::random() % 100; | |
|
10271
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
194 int* test_array = NEW_C_HEAP_ARRAY(int, length, mtInternal); |
|
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
195 int* expected_array = NEW_C_HEAP_ARRAY(int, length, mtInternal); |
| 3779 | 196 for (int j = 0; j < length; j++) { |
| 197 // Choose random values, but get a chance of getting duplicates | |
| 198 test_array[j] = os::random() % (length * 2); | |
| 199 expected_array[j] = test_array[j]; | |
| 200 } | |
| 201 | |
| 202 // Compare sorting to stdlib::qsort() | |
| 203 qsort(expected_array, length, sizeof(int), test_stdlib_comparator); | |
| 204 assert(sort_and_compare(test_array, expected_array, length, test_comparator), "Random array not correctly sorted"); | |
| 205 | |
| 206 // Make sure sorting is idempotent. | |
| 207 // Both test_array and expected_array are sorted by the test_comparator. | |
| 208 // Now sort them once with the test_even_odd_comparator. Then sort the | |
| 209 // test_array one more time with test_even_odd_comparator and verify that | |
| 210 // it is idempotent. | |
| 211 sort(expected_array, length, test_even_odd_comparator, true); | |
| 212 sort(test_array, length, test_even_odd_comparator, true); | |
| 213 assert(compare_arrays(test_array, expected_array, length), "Sorting identical arrays rendered different results"); | |
| 214 sort(test_array, length, test_even_odd_comparator, true); | |
| 215 assert(compare_arrays(test_array, expected_array, length), "Sorting already sorted array changed order of elements - not idempotent"); | |
| 216 | |
|
10271
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
217 FREE_C_HEAP_ARRAY(int, test_array, mtInternal); |
|
f9be75d21404
8012902: remove use of global operator new - take 2
minqi
parents:
10135
diff
changeset
|
218 FREE_C_HEAP_ARRAY(int, expected_array, mtInternal); |
| 3779 | 219 } |
| 220 } | |
| 221 | |
| 222 #endif |