Mercurial > hg > truffle
annotate src/share/vm/libadt/vectset.cpp @ 1994:6cd6d394f280
7001033: assert(gch->gc_cause() == GCCause::_scavenge_alot || !gch->incremental_collection_failed())
7002546: regression on SpecJbb2005 on 7b118 comparing to 7b117 on small heaps
Summary: Relaxed assertion checking related to incremental_collection_failed flag to allow for ExplicitGCInvokesConcurrent behaviour where we do not want a failing scavenge to bail to a stop-world collection. Parameterized incremental_collection_will_fail() so we can selectively use, or not use, as appropriate, the statistical prediction at specific use sites. This essentially reverts the scavenge bail-out logic to what it was prior to some recent changes that had inadvertently started using the statistical prediction which can be noisy in the presence of bursty loads. Added some associated verbose non-product debugging messages.
Reviewed-by: johnc, tonyp
author | ysr |
---|---|
date | Tue, 07 Dec 2010 21:55:53 -0800 |
parents | f95d63e2154a |
children | c760f78e0a53 |
rev | line source |
---|---|
0 | 1 /* |
1972 | 2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. |
0 | 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 * | |
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
0 | 22 * |
23 */ | |
24 | |
1972 | 25 #include "precompiled.hpp" |
26 #include "libadt/vectset.hpp" | |
27 #include "memory/allocation.inline.hpp" | |
0 | 28 |
1972 | 29 // Vector Sets - An Abstract Data Type |
0 | 30 |
31 // %%%%% includes not needed with AVM framework - Ungar | |
32 // #include "port.hpp" | |
33 //IMPLEMENTATION | |
34 // #include "vectset.hpp" | |
35 | |
36 // BitsInByte is a lookup table which tells the number of bits that | |
37 // are in the looked-up number. It is very useful in VectorSet_Size. | |
38 | |
39 uint8 bitsInByte[256] = { | |
40 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, | |
41 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
42 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
43 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
44 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
45 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
46 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
47 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
48 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, | |
49 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
50 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
51 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
52 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, | |
53 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
54 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, | |
55 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 | |
56 }; | |
57 | |
58 //------------------------------VectorSet-------------------------------------- | |
59 // Create a new, empty Set. | |
60 VectorSet::VectorSet(Arena *arena) : Set(arena) { | |
61 size = 2; // Small initial size | |
62 data = (uint32 *)_set_arena->Amalloc(size*sizeof(uint32)); | |
63 data[0] = 0; // No elements | |
64 data[1] = 0; | |
65 } | |
66 | |
67 //------------------------------Construct-------------------------------------- | |
68 Set &VectorSet_Construct(Arena *arena) | |
69 { | |
70 return *(new VectorSet(arena)); | |
71 } | |
72 | |
73 //------------------------------operator=-------------------------------------- | |
74 Set &VectorSet::operator = (const Set &set) | |
75 { | |
76 if( &set == this ) return *this; | |
77 FREE_FAST(data); | |
78 // The cast is a virtual function that checks that "set" is a VectorSet. | |
79 slamin(*(set.asVectorSet())); | |
80 return *this; | |
81 } | |
82 | |
83 //------------------------------slamin----------------------------------------- | |
84 // Initialize one set with another. No regard is made to the existing Set. | |
85 void VectorSet::slamin(const VectorSet& s) | |
86 { | |
87 size = s.size; // Use new size | |
88 data = (uint32*)s._set_arena->Amalloc(size*sizeof(uint32)); // Make array of required size | |
89 memcpy( data, s.data, size*sizeof(uint32) ); // Fill the array | |
90 } | |
91 | |
92 //------------------------------grow------------------------------------------- | |
93 // Expand the existing set to a bigger size | |
94 void VectorSet::grow( uint newsize ) | |
95 { | |
96 newsize = (newsize+31) >> 5; // Convert to longwords | |
97 uint x = size; | |
98 while( x < newsize ) x <<= 1; | |
99 data = (uint32 *)_set_arena->Arealloc(data, size*sizeof(uint32), x*sizeof(uint32)); | |
100 memset((char *)(data + size), 0, (x - size)*sizeof(uint32)); | |
101 size = x; | |
102 } | |
103 | |
104 //------------------------------operator<<=------------------------------------ | |
105 // Insert a member into an existing Set. | |
106 Set &VectorSet::operator <<= (uint elem) | |
107 { | |
108 register uint word = elem >> 5; // Get the longword offset | |
109 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
110 | |
111 if( word >= size ) // Need to grow set? | |
112 grow(elem+1); // Then grow it | |
113 data[word] |= mask; // Set new bit | |
114 return *this; | |
115 } | |
116 | |
117 //------------------------------operator>>=------------------------------------ | |
118 // Delete a member from an existing Set. | |
119 Set &VectorSet::operator >>= (uint elem) | |
120 { | |
121 register uint word = elem >> 5; // Get the longword offset | |
122 if( word >= size ) // Beyond the last? | |
123 return *this; // Then it's clear & return clear | |
124 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
125 data[word] &= ~mask; // Clear bit | |
126 return *this; | |
127 } | |
128 | |
129 //------------------------------operator&=------------------------------------- | |
130 // Intersect one set into another. | |
131 VectorSet &VectorSet::operator &= (const VectorSet &s) | |
132 { | |
133 // NOTE: The intersection is never any larger than the smallest set. | |
134 if( s.size < size ) size = s.size; // Get smaller size | |
135 register uint32 *u1 = data; // Pointer to the destination data | |
136 register uint32 *u2 = s.data; // Pointer to the source data | |
137 for( uint i=0; i<size; i++) // For data in set | |
138 *u1++ &= *u2++; // Copy and AND longwords | |
139 return *this; // Return set | |
140 } | |
141 | |
142 //------------------------------operator&=------------------------------------- | |
143 Set &VectorSet::operator &= (const Set &set) | |
144 { | |
145 // The cast is a virtual function that checks that "set" is a VectorSet. | |
146 return (*this) &= *(set.asVectorSet()); | |
147 } | |
148 | |
149 //------------------------------operator|=------------------------------------- | |
150 // Union one set into another. | |
151 VectorSet &VectorSet::operator |= (const VectorSet &s) | |
152 { | |
153 // This many words must be unioned | |
154 register uint cnt = ((size<s.size)?size:s.size); | |
155 register uint32 *u1 = data; // Pointer to the destination data | |
156 register uint32 *u2 = s.data; // Pointer to the source data | |
157 for( uint i=0; i<cnt; i++) // Copy and OR the two sets | |
158 *u1++ |= *u2++; | |
159 if( size < s.size ) { // Is set 2 larger than set 1? | |
160 // Extend result by larger set | |
161 grow(s.size*sizeof(uint32)*8); | |
162 memcpy(&data[cnt], u2, (s.size - cnt)*sizeof(uint32)); | |
163 } | |
164 return *this; // Return result set | |
165 } | |
166 | |
167 //------------------------------operator|=------------------------------------- | |
168 Set &VectorSet::operator |= (const Set &set) | |
169 { | |
170 // The cast is a virtual function that checks that "set" is a VectorSet. | |
171 return (*this) |= *(set.asVectorSet()); | |
172 } | |
173 | |
174 //------------------------------operator-=------------------------------------- | |
175 // Difference one set from another. | |
176 VectorSet &VectorSet::operator -= (const VectorSet &s) | |
177 { | |
178 // This many words must be unioned | |
179 register uint cnt = ((size<s.size)?size:s.size); | |
180 register uint32 *u1 = data; // Pointer to the destination data | |
181 register uint32 *u2 = s.data; // Pointer to the source data | |
182 for( uint i=0; i<cnt; i++ ) // For data in set | |
183 *u1++ &= ~(*u2++); // A <-- A & ~B with longwords | |
184 return *this; // Return new set | |
185 } | |
186 | |
187 //------------------------------operator-=------------------------------------- | |
188 Set &VectorSet::operator -= (const Set &set) | |
189 { | |
190 // The cast is a virtual function that checks that "set" is a VectorSet. | |
191 return (*this) -= *(set.asVectorSet()); | |
192 } | |
193 | |
194 //------------------------------compare---------------------------------------- | |
195 // Compute 2 booleans: bits in A not B, bits in B not A. | |
196 // Return X0 -- A is not a subset of B | |
197 // X1 -- A is a subset of B | |
198 // 0X -- B is not a subset of A | |
199 // 1X -- B is a subset of A | |
200 int VectorSet::compare (const VectorSet &s) const | |
201 { | |
202 register uint32 *u1 = data; // Pointer to the destination data | |
203 register uint32 *u2 = s.data; // Pointer to the source data | |
204 register uint32 AnotB = 0, BnotA = 0; | |
205 // This many words must be unioned | |
206 register uint cnt = ((size<s.size)?size:s.size); | |
207 | |
208 // Get bits for both sets | |
209 uint i; // Exit value of loop | |
210 for( i=0; i<cnt; i++ ) { // For data in BOTH sets | |
211 register uint32 A = *u1++; // Data from one guy | |
212 register uint32 B = *u2++; // Data from other guy | |
213 AnotB |= (A & ~B); // Compute bits in A not B | |
214 BnotA |= (B & ~A); // Compute bits in B not A | |
215 } | |
216 | |
217 // Get bits from bigger set | |
218 if( size < s.size ) { | |
219 for( ; i<s.size; i++ ) // For data in larger set | |
220 BnotA |= *u2++; // These bits are in B not A | |
221 } else { | |
222 for( ; i<size; i++ ) // For data in larger set | |
223 AnotB |= *u1++; // These bits are in A not B | |
224 } | |
225 | |
226 // Set & return boolean flags | |
227 return ((!BnotA)<<1) + (!AnotB); | |
228 } | |
229 | |
230 //------------------------------operator==------------------------------------- | |
231 // Test for set equality | |
232 int VectorSet::operator == (const VectorSet &s) const | |
233 { | |
234 return compare(s) == 3; // TRUE if A and B are mutual subsets | |
235 } | |
236 | |
237 //------------------------------operator==------------------------------------- | |
238 int VectorSet::operator == (const Set &set) const | |
239 { | |
240 // The cast is a virtual function that checks that "set" is a VectorSet. | |
241 return (*this) == *(set.asVectorSet()); | |
242 } | |
243 | |
244 //------------------------------disjoint--------------------------------------- | |
245 // Check for sets being disjoint. | |
246 int VectorSet::disjoint(const Set &set) const | |
247 { | |
248 // The cast is a virtual function that checks that "set" is a VectorSet. | |
249 const VectorSet &s = *(set.asVectorSet()); | |
250 | |
251 // NOTE: The intersection is never any larger than the smallest set. | |
252 register uint small = ((size<s.size)?size:s.size); | |
253 register uint32 *u1 = data; // Pointer to the destination data | |
254 register uint32 *u2 = s.data; // Pointer to the source data | |
255 for( uint i=0; i<small; i++) // For data in set | |
256 if( *u1++ & *u2++ ) // If any elements in common | |
257 return 0; // Then not disjoint | |
258 return 1; // Else disjoint | |
259 } | |
260 | |
261 //------------------------------operator<-------------------------------------- | |
262 // Test for strict subset | |
263 int VectorSet::operator < (const VectorSet &s) const | |
264 { | |
265 return compare(s) == 1; // A subset B, B not subset A | |
266 } | |
267 | |
268 //------------------------------operator<-------------------------------------- | |
269 int VectorSet::operator < (const Set &set) const | |
270 { | |
271 // The cast is a virtual function that checks that "set" is a VectorSet. | |
272 return (*this) < *(set.asVectorSet()); | |
273 } | |
274 | |
275 //------------------------------operator<=------------------------------------- | |
276 // Test for subset | |
277 int VectorSet::operator <= (const VectorSet &s) const | |
278 { | |
279 return compare(s) & 1; // A subset B | |
280 } | |
281 | |
282 //------------------------------operator<=------------------------------------- | |
283 int VectorSet::operator <= (const Set &set) const | |
284 { | |
285 // The cast is a virtual function that checks that "set" is a VectorSet. | |
286 return (*this) <= *(set.asVectorSet()); | |
287 } | |
288 | |
289 //------------------------------operator[]------------------------------------- | |
290 // Test for membership. A Zero/Non-Zero value is returned! | |
291 int VectorSet::operator[](uint elem) const | |
292 { | |
293 register uint word = elem >> 5; // Get the longword offset | |
294 if( word >= size ) // Beyond the last? | |
295 return 0; // Then it's clear | |
296 register uint32 mask = 1L << (elem & 31); // Get bit mask | |
297 return ((data[word] & mask))!=0; // Return the sense of the bit | |
298 } | |
299 | |
300 //------------------------------getelem---------------------------------------- | |
301 // Get any element from the set. | |
302 uint VectorSet::getelem(void) const | |
303 { | |
304 uint i; // Exit value of loop | |
305 for( i=0; i<size; i++ ) | |
306 if( data[i] ) | |
307 break; | |
308 uint32 word = data[i]; | |
309 int j; // Exit value of loop | |
310 for( j= -1; word; j++, word>>=1 ); | |
311 return (i<<5)+j; | |
312 } | |
313 | |
314 //------------------------------Clear------------------------------------------ | |
315 // Clear a set | |
316 void VectorSet::Clear(void) | |
317 { | |
318 if( size > 100 ) { // Reclaim storage only if huge | |
319 FREE_RESOURCE_ARRAY(uint32,data,size); | |
320 size = 2; // Small initial size | |
321 data = NEW_RESOURCE_ARRAY(uint32,size); | |
322 } | |
323 memset( data, 0, size*sizeof(uint32) ); | |
324 } | |
325 | |
326 //------------------------------Size------------------------------------------- | |
327 // Return number of elements in a Set | |
328 uint VectorSet::Size(void) const | |
329 { | |
330 uint sum = 0; // Cumulative size so far. | |
331 uint8 *currByte = (uint8*)data; | |
332 for( uint32 i = 0; i < (size<<2); i++) // While have bytes to process | |
333 sum += bitsInByte[*currByte++]; // Add bits in current byte to size. | |
334 return sum; | |
335 } | |
336 | |
337 //------------------------------Sort------------------------------------------- | |
338 // Sort the elements for the next forall statement | |
339 void VectorSet::Sort(void) | |
340 { | |
341 } | |
342 | |
343 //------------------------------hash------------------------------------------- | |
344 int VectorSet::hash() const | |
345 { | |
346 uint32 _xor = 0; | |
347 uint lim = ((size<4)?size:4); | |
348 for( uint i = 0; i < lim; i++ ) | |
349 _xor ^= data[i]; | |
350 return (int)_xor; | |
351 } | |
352 | |
353 //------------------------------iterate---------------------------------------- | |
354 SetI_ *VectorSet::iterate(uint &elem) const | |
355 { | |
356 VSetI_ *foo = (new(ResourceObj::C_HEAP) VSetI_(this)); | |
357 elem = foo->next(); | |
358 return foo; | |
359 } | |
360 | |
361 //============================================================================= | |
362 //------------------------------VSetI_----------------------------------------- | |
363 // Initialize the innards of a VectorSet iterator | |
364 VSetI_::VSetI_( const VectorSet *vset ) : s(vset) | |
365 { | |
366 i = (uint)-1L; | |
367 j = (uint)-1L; | |
368 mask = (unsigned)(1L<<31); | |
369 } | |
370 | |
371 //------------------------------next------------------------------------------- | |
372 // Find and return the next element of a vector set, or return garbage and | |
373 // make "VSetI_::test()" fail. | |
374 uint VSetI_::next(void) | |
375 { | |
376 j++; // Next element in word | |
377 mask = (mask & max_jint) << 1;// Next bit in word | |
378 do { // Do While still have words | |
379 while( mask ) { // While have bits in word | |
380 if( s->data[i] & mask ) { // If found a bit | |
381 return (i<<5)+j; // Return the bit address | |
382 } | |
383 j++; // Skip to next bit | |
384 mask = (mask & max_jint) << 1; | |
385 } | |
386 j = 0; // No more bits in word; setup for next word | |
387 mask = 1; | |
388 for( i++; (i<s->size) && (!s->data[i]); i++ ); // Skip to non-zero word | |
389 } while( i<s->size ); | |
390 return max_juint; // No element, iterated them all | |
391 } |