Mercurial > hg > truffle
annotate src/share/vm/libadt/dict.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 |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
17937
78bbf4d43a14
8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents:
1972
diff
changeset
|
2 * Copyright (c) 1997, 2014, 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:
628
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
628
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:
628
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
| 26 #include "libadt/dict.hpp" | |
| 27 #include "memory/allocation.inline.hpp" | |
| 28 #include "memory/resourceArea.hpp" | |
| 29 #include "runtime/thread.hpp" | |
| 0 | 30 |
| 1972 | 31 // Dictionaries - An Abstract Data Type |
| 0 | 32 |
| 33 // %%%%% includes not needed with AVM framework - Ungar | |
| 34 | |
| 35 // #include "port.hpp" | |
| 36 //IMPLEMENTATION | |
| 37 // #include "dict.hpp" | |
| 38 | |
| 39 #include <assert.h> | |
| 40 | |
|
17937
78bbf4d43a14
8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents:
1972
diff
changeset
|
41 PRAGMA_FORMAT_MUTE_WARNINGS_FOR_GCC |
|
78bbf4d43a14
8037816: Fix for 8036122 breaks build with Xcode5/clang
drchase
parents:
1972
diff
changeset
|
42 |
| 0 | 43 // The iostream is not needed and it gets confused for gcc by the |
| 44 // define of bool. | |
| 45 // | |
| 46 // #include <iostream.h> | |
| 47 | |
| 48 //------------------------------data----------------------------------------- | |
| 49 // String hash tables | |
| 50 #define MAXID 20 | |
| 51 static byte initflag = 0; // True after 1st initialization | |
| 52 static const char shft[MAXID] = {1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6}; | |
| 53 static short xsum[MAXID]; | |
| 54 | |
| 55 //------------------------------bucket--------------------------------------- | |
| 56 class bucket : public ResourceObj { | |
| 57 public: | |
| 58 uint _cnt, _max; // Size of bucket | |
| 59 void **_keyvals; // Array of keys and values | |
| 60 }; | |
| 61 | |
| 62 //------------------------------Dict----------------------------------------- | |
| 63 // The dictionary is kept has a hash table. The hash table is a even power | |
| 64 // of two, for nice modulo operations. Each bucket in the hash table points | |
| 65 // to a linear list of key-value pairs; each key & value is just a (void *). | |
| 66 // The list starts with a count. A hash lookup finds the list head, then a | |
| 67 // simple linear scan finds the key. If the table gets too full, it's | |
| 68 // doubled in size; the total amount of EXTRA times all hash functions are | |
| 69 // computed for the doubling is no more than the current size - thus the | |
| 70 // doubling in size costs no more than a constant factor in speed. | |
| 71 Dict::Dict(CmpKey initcmp, Hash inithash) : _hash(inithash), _cmp(initcmp), | |
| 72 _arena(Thread::current()->resource_area()) { | |
| 73 int i; | |
| 74 | |
| 75 // Precompute table of null character hashes | |
| 76 if( !initflag ) { // Not initializated yet? | |
| 77 xsum[0] = (1<<shft[0])+1; // Initialize | |
| 78 for(i=1; i<MAXID; i++) { | |
| 79 xsum[i] = (1<<shft[i])+1+xsum[i-1]; | |
| 80 } | |
| 81 initflag = 1; // Never again | |
| 82 } | |
| 83 | |
| 84 _size = 16; // Size is a power of 2 | |
| 85 _cnt = 0; // Dictionary is empty | |
| 86 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size); | |
| 87 memset(_bin,0,sizeof(bucket)*_size); | |
| 88 } | |
| 89 | |
| 90 Dict::Dict(CmpKey initcmp, Hash inithash, Arena *arena, int size) | |
| 91 : _hash(inithash), _cmp(initcmp), _arena(arena) { | |
| 92 int i; | |
| 93 | |
| 94 // Precompute table of null character hashes | |
| 95 if( !initflag ) { // Not initializated yet? | |
| 96 xsum[0] = (1<<shft[0])+1; // Initialize | |
| 97 for(i=1; i<MAXID; i++) { | |
| 98 xsum[i] = (1<<shft[i])+1+xsum[i-1]; | |
| 99 } | |
| 100 initflag = 1; // Never again | |
| 101 } | |
| 102 | |
| 103 i=16; | |
| 104 while( i < size ) i <<= 1; | |
| 105 _size = i; // Size is a power of 2 | |
| 106 _cnt = 0; // Dictionary is empty | |
| 107 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size); | |
| 108 memset(_bin,0,sizeof(bucket)*_size); | |
| 109 } | |
| 110 | |
| 111 //------------------------------~Dict------------------------------------------ | |
| 112 // Delete an existing dictionary. | |
| 113 Dict::~Dict() { | |
| 114 /* | |
| 115 tty->print("~Dict %d/%d: ",_cnt,_size); | |
| 116 for( uint i=0; i < _size; i++) // For complete new table do | |
| 117 tty->print("%d ",_bin[i]._cnt); | |
| 118 tty->print("\n");*/ | |
| 119 /*for( uint i=0; i<_size; i++ ) { | |
| 120 FREE_FAST( _bin[i]._keyvals ); | |
| 121 } */ | |
| 122 } | |
| 123 | |
| 124 //------------------------------Clear---------------------------------------- | |
| 125 // Zap to empty; ready for re-use | |
| 126 void Dict::Clear() { | |
| 127 _cnt = 0; // Empty contents | |
| 128 for( uint i=0; i<_size; i++ ) | |
| 129 _bin[i]._cnt = 0; // Empty buckets, but leave allocated | |
| 130 // Leave _size & _bin alone, under the assumption that dictionary will | |
| 131 // grow to this size again. | |
| 132 } | |
| 133 | |
| 134 //------------------------------doubhash--------------------------------------- | |
| 135 // Double hash table size. If can't do so, just suffer. If can, then run | |
| 136 // thru old hash table, moving things to new table. Note that since hash | |
| 137 // table doubled, exactly 1 new bit is exposed in the mask - so everything | |
| 138 // in the old table ends up on 1 of two lists in the new table; a hi and a | |
| 139 // lo list depending on the value of the bit. | |
| 140 void Dict::doubhash(void) { | |
| 141 uint oldsize = _size; | |
| 142 _size <<= 1; // Double in size | |
| 143 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*oldsize, sizeof(bucket)*_size ); | |
| 144 memset( &_bin[oldsize], 0, oldsize*sizeof(bucket) ); | |
| 145 // Rehash things to spread into new table | |
| 146 for( uint i=0; i < oldsize; i++) { // For complete OLD table do | |
| 147 bucket *b = &_bin[i]; // Handy shortcut for _bin[i] | |
| 148 if( !b->_keyvals ) continue; // Skip empties fast | |
| 149 | |
| 150 bucket *nb = &_bin[i+oldsize]; // New bucket shortcut | |
| 151 uint j = b->_max; // Trim new bucket to nearest power of 2 | |
| 152 while( j > b->_cnt ) j >>= 1; // above old bucket _cnt | |
| 153 if( !j ) j = 1; // Handle zero-sized buckets | |
| 154 nb->_max = j<<1; | |
| 155 // Allocate worst case space for key-value pairs | |
| 156 nb->_keyvals = (void**)_arena->Amalloc_4( sizeof(void *)*nb->_max*2 ); | |
| 157 uint nbcnt = 0; | |
| 158 | |
| 159 for( j=0; j<b->_cnt; j++ ) { // Rehash all keys in this bucket | |
| 160 void *key = b->_keyvals[j+j]; | |
| 161 if( (_hash( key ) & (_size-1)) != i ) { // Moving to hi bucket? | |
| 162 nb->_keyvals[nbcnt+nbcnt] = key; | |
| 163 nb->_keyvals[nbcnt+nbcnt+1] = b->_keyvals[j+j+1]; | |
| 164 nb->_cnt = nbcnt = nbcnt+1; | |
| 165 b->_cnt--; // Remove key/value from lo bucket | |
| 166 b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ]; | |
| 167 b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1]; | |
| 168 j--; // Hash compacted element also | |
| 169 } | |
| 170 } // End of for all key-value pairs in bucket | |
| 171 } // End of for all buckets | |
| 172 | |
| 173 | |
| 174 } | |
| 175 | |
| 176 //------------------------------Dict----------------------------------------- | |
| 177 // Deep copy a dictionary. | |
| 178 Dict::Dict( const Dict &d ) : _size(d._size), _cnt(d._cnt), _hash(d._hash),_cmp(d._cmp), _arena(d._arena) { | |
| 179 _bin = (bucket*)_arena->Amalloc_4(sizeof(bucket)*_size); | |
| 180 memcpy( _bin, d._bin, sizeof(bucket)*_size ); | |
| 181 for( uint i=0; i<_size; i++ ) { | |
| 182 if( !_bin[i]._keyvals ) continue; | |
| 183 _bin[i]._keyvals=(void**)_arena->Amalloc_4( sizeof(void *)*_bin[i]._max*2); | |
| 184 memcpy( _bin[i]._keyvals, d._bin[i]._keyvals,_bin[i]._cnt*2*sizeof(void*)); | |
| 185 } | |
| 186 } | |
| 187 | |
| 188 //------------------------------Dict----------------------------------------- | |
| 189 // Deep copy a dictionary. | |
| 190 Dict &Dict::operator =( const Dict &d ) { | |
| 191 if( _size < d._size ) { // If must have more buckets | |
| 192 _arena = d._arena; | |
| 193 _bin = (bucket*)_arena->Arealloc( _bin, sizeof(bucket)*_size, sizeof(bucket)*d._size ); | |
| 194 memset( &_bin[_size], 0, (d._size-_size)*sizeof(bucket) ); | |
| 195 _size = d._size; | |
| 196 } | |
| 197 uint i; | |
| 198 for( i=0; i<_size; i++ ) // All buckets are empty | |
| 199 _bin[i]._cnt = 0; // But leave bucket allocations alone | |
| 200 _cnt = d._cnt; | |
| 201 *(Hash*)(&_hash) = d._hash; | |
| 202 *(CmpKey*)(&_cmp) = d._cmp; | |
| 203 for( i=0; i<_size; i++ ) { | |
| 204 bucket *b = &d._bin[i]; // Shortcut to source bucket | |
| 205 for( uint j=0; j<b->_cnt; j++ ) | |
| 206 Insert( b->_keyvals[j+j], b->_keyvals[j+j+1] ); | |
| 207 } | |
| 208 return *this; | |
| 209 } | |
| 210 | |
| 211 //------------------------------Insert---------------------------------------- | |
| 212 // Insert or replace a key/value pair in the given dictionary. If the | |
| 213 // dictionary is too full, it's size is doubled. The prior value being | |
| 214 // replaced is returned (NULL if this is a 1st insertion of that key). If | |
| 215 // an old value is found, it's swapped with the prior key-value pair on the | |
| 216 // list. This moves a commonly searched-for value towards the list head. | |
| 217 void *Dict::Insert(void *key, void *val, bool replace) { | |
| 218 uint hash = _hash( key ); // Get hash key | |
| 219 uint i = hash & (_size-1); // Get hash key, corrected for size | |
| 220 bucket *b = &_bin[i]; // Handy shortcut | |
| 221 for( uint j=0; j<b->_cnt; j++ ) { | |
| 222 if( !_cmp(key,b->_keyvals[j+j]) ) { | |
| 223 if (!replace) { | |
| 224 return b->_keyvals[j+j+1]; | |
| 225 } else { | |
| 226 void *prior = b->_keyvals[j+j+1]; | |
| 227 b->_keyvals[j+j ] = key; // Insert current key-value | |
| 228 b->_keyvals[j+j+1] = val; | |
| 229 return prior; // Return prior | |
| 230 } | |
| 231 } | |
| 232 } | |
| 233 if( ++_cnt > _size ) { // Hash table is full | |
| 234 doubhash(); // Grow whole table if too full | |
| 235 i = hash & (_size-1); // Rehash | |
| 236 b = &_bin[i]; // Handy shortcut | |
| 237 } | |
| 238 if( b->_cnt == b->_max ) { // Must grow bucket? | |
| 239 if( !b->_keyvals ) { | |
| 240 b->_max = 2; // Initial bucket size | |
| 241 b->_keyvals = (void**)_arena->Amalloc_4(sizeof(void*) * b->_max * 2); | |
| 242 } else { | |
| 243 b->_keyvals = (void**)_arena->Arealloc(b->_keyvals, sizeof(void*) * b->_max * 2, sizeof(void*) * b->_max * 4); | |
| 244 b->_max <<= 1; // Double bucket | |
| 245 } | |
| 246 } | |
| 247 b->_keyvals[b->_cnt+b->_cnt ] = key; | |
| 248 b->_keyvals[b->_cnt+b->_cnt+1] = val; | |
| 249 b->_cnt++; | |
| 250 return NULL; // Nothing found prior | |
| 251 } | |
| 252 | |
| 253 //------------------------------Delete--------------------------------------- | |
| 254 // Find & remove a value from dictionary. Return old value. | |
| 255 void *Dict::Delete(void *key) { | |
| 256 uint i = _hash( key ) & (_size-1); // Get hash key, corrected for size | |
| 257 bucket *b = &_bin[i]; // Handy shortcut | |
| 258 for( uint j=0; j<b->_cnt; j++ ) | |
| 259 if( !_cmp(key,b->_keyvals[j+j]) ) { | |
| 260 void *prior = b->_keyvals[j+j+1]; | |
| 261 b->_cnt--; // Remove key/value from lo bucket | |
| 262 b->_keyvals[j+j ] = b->_keyvals[b->_cnt+b->_cnt ]; | |
| 263 b->_keyvals[j+j+1] = b->_keyvals[b->_cnt+b->_cnt+1]; | |
| 264 _cnt--; // One less thing in table | |
| 265 return prior; | |
| 266 } | |
| 267 return NULL; | |
| 268 } | |
| 269 | |
| 270 //------------------------------FindDict------------------------------------- | |
| 271 // Find a key-value pair in the given dictionary. If not found, return NULL. | |
| 272 // If found, move key-value pair towards head of list. | |
| 273 void *Dict::operator [](const void *key) const { | |
| 274 uint i = _hash( key ) & (_size-1); // Get hash key, corrected for size | |
| 275 bucket *b = &_bin[i]; // Handy shortcut | |
| 276 for( uint j=0; j<b->_cnt; j++ ) | |
| 277 if( !_cmp(key,b->_keyvals[j+j]) ) | |
| 278 return b->_keyvals[j+j+1]; | |
| 279 return NULL; | |
| 280 } | |
| 281 | |
| 282 //------------------------------CmpDict-------------------------------------- | |
| 283 // CmpDict compares two dictionaries; they must have the same keys (their | |
| 284 // keys must match using CmpKey) and they must have the same values (pointer | |
| 285 // comparison). If so 1 is returned, if not 0 is returned. | |
| 286 int32 Dict::operator ==(const Dict &d2) const { | |
| 287 if( _cnt != d2._cnt ) return 0; | |
| 288 if( _hash != d2._hash ) return 0; | |
| 289 if( _cmp != d2._cmp ) return 0; | |
| 290 for( uint i=0; i < _size; i++) { // For complete hash table do | |
| 291 bucket *b = &_bin[i]; // Handy shortcut | |
| 292 if( b->_cnt != d2._bin[i]._cnt ) return 0; | |
| 293 if( memcmp(b->_keyvals, d2._bin[i]._keyvals, b->_cnt*2*sizeof(void*) ) ) | |
| 294 return 0; // Key-value pairs must match | |
| 295 } | |
| 296 return 1; // All match, is OK | |
| 297 } | |
| 298 | |
| 299 //------------------------------print------------------------------------------ | |
| 300 // Handier print routine | |
| 301 void Dict::print() { | |
| 302 DictI i(this); // Moved definition in iterator here because of g++. | |
| 303 tty->print("Dict@0x%lx[%d] = {", this, _cnt); | |
| 304 for( ; i.test(); ++i ) { | |
| 305 tty->print("(0x%lx,0x%lx),", i._key, i._value); | |
| 306 } | |
| 307 tty->print_cr("}"); | |
| 308 } | |
| 309 | |
| 310 //------------------------------Hashing Functions---------------------------- | |
| 311 // Convert string to hash key. This algorithm implements a universal hash | |
| 312 // function with the multipliers frozen (ok, so it's not universal). The | |
| 313 // multipliers (and allowable characters) are all odd, so the resultant sum | |
| 605 | 314 // is odd - guaranteed not divisible by any power of two, so the hash tables |
| 0 | 315 // can be any power of two with good results. Also, I choose multipliers |
| 316 // that have only 2 bits set (the low is always set to be odd) so | |
| 317 // multiplication requires only shifts and adds. Characters are required to | |
| 318 // be in the range 0-127 (I double & add 1 to force oddness). Keys are | |
| 319 // limited to MAXID characters in length. Experimental evidence on 150K of | |
| 320 // C text shows excellent spreading of values for any size hash table. | |
| 321 int hashstr(const void *t) { | |
| 322 register char c, k = 0; | |
| 323 register int32 sum = 0; | |
| 324 register const char *s = (const char *)t; | |
| 325 | |
| 326 while( ((c = *s++) != '\0') && (k < MAXID-1) ) { // Get characters till null or MAXID-1 | |
| 327 c = (c<<1)+1; // Characters are always odd! | |
| 328 sum += c + (c<<shft[k++]); // Universal hash function | |
| 329 } | |
| 330 return (int)((sum+xsum[k]) >> 1); // Hash key, un-modulo'd table size | |
| 331 } | |
| 332 | |
| 333 //------------------------------hashptr-------------------------------------- | |
| 605 | 334 // Slimey cheap hash function; no guaranteed performance. Better than the |
| 0 | 335 // default for pointers, especially on MS-DOS machines. |
| 336 int hashptr(const void *key) { | |
| 337 #ifdef __TURBOC__ | |
| 338 return ((intptr_t)key >> 16); | |
| 339 #else // __TURBOC__ | |
| 340 return ((intptr_t)key >> 2); | |
| 341 #endif | |
| 342 } | |
| 343 | |
| 605 | 344 // Slimey cheap hash function; no guaranteed performance. |
| 0 | 345 int hashkey(const void *key) { |
| 346 return (intptr_t)key; | |
| 347 } | |
| 348 | |
| 349 //------------------------------Key Comparator Functions--------------------- | |
| 350 int32 cmpstr(const void *k1, const void *k2) { | |
| 351 return strcmp((const char *)k1,(const char *)k2); | |
| 352 } | |
| 353 | |
|
562
1580954e694c
6798785: Crash in OopFlow::build_oop_map: incorrect comparison of 64bit pointers
never
parents:
0
diff
changeset
|
354 // Cheap key comparator. |
| 0 | 355 int32 cmpkey(const void *key1, const void *key2) { |
|
562
1580954e694c
6798785: Crash in OopFlow::build_oop_map: incorrect comparison of 64bit pointers
never
parents:
0
diff
changeset
|
356 if (key1 == key2) return 0; |
|
1580954e694c
6798785: Crash in OopFlow::build_oop_map: incorrect comparison of 64bit pointers
never
parents:
0
diff
changeset
|
357 intptr_t delta = (intptr_t)key1 - (intptr_t)key2; |
|
1580954e694c
6798785: Crash in OopFlow::build_oop_map: incorrect comparison of 64bit pointers
never
parents:
0
diff
changeset
|
358 if (delta > 0) return 1; |
|
1580954e694c
6798785: Crash in OopFlow::build_oop_map: incorrect comparison of 64bit pointers
never
parents:
0
diff
changeset
|
359 return -1; |
| 0 | 360 } |
| 361 | |
| 362 //============================================================================= | |
| 363 //------------------------------reset------------------------------------------ | |
| 364 // Create an iterator and initialize the first variables. | |
| 365 void DictI::reset( const Dict *dict ) { | |
| 366 _d = dict; // The dictionary | |
| 367 _i = (uint)-1; // Before the first bin | |
| 368 _j = 0; // Nothing left in the current bin | |
| 369 ++(*this); // Step to first real value | |
| 370 } | |
| 371 | |
| 372 //------------------------------next------------------------------------------- | |
| 373 // Find the next key-value pair in the dictionary, or return a NULL key and | |
| 374 // value. | |
| 375 void DictI::operator ++(void) { | |
| 376 if( _j-- ) { // Still working in current bin? | |
| 377 _key = _d->_bin[_i]._keyvals[_j+_j]; | |
| 378 _value = _d->_bin[_i]._keyvals[_j+_j+1]; | |
| 379 return; | |
| 380 } | |
| 381 | |
| 382 while( ++_i < _d->_size ) { // Else scan for non-zero bucket | |
| 383 _j = _d->_bin[_i]._cnt; | |
| 384 if( !_j ) continue; | |
| 385 _j--; | |
| 386 _key = _d->_bin[_i]._keyvals[_j+_j]; | |
| 387 _value = _d->_bin[_i]._keyvals[_j+_j+1]; | |
| 388 return; | |
| 389 } | |
| 390 _key = _value = NULL; | |
| 391 } |