Mercurial > hg > truffle

comparison src/share/vm/utilities/hashtable.cpp @ 20804:7848fc12602b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge with jdk8u40-b25
author Gilles Duboscq <gilles.m.duboscq@oracle.com>
date Tue, 07 Apr 2015 14:58:49 +0200
parents 52b4284cb496 7baf47cb97cb
children
comparison
equal deleted inserted replaced
20184:84105dcdb05b 20804:7848fc12602b
34 #include "utilities/hashtable.hpp" 34 #include "utilities/hashtable.hpp"
35 #include "utilities/hashtable.inline.hpp" 35 #include "utilities/hashtable.inline.hpp"
36 #include "utilities/numberSeq.hpp" 36 #include "utilities/numberSeq.hpp"
37 37
38 38
39 // This is a generic hashtable, designed to be used for the symbol 39 // This hashtable is implemented as an open hash table with a fixed number of buckets.
40 // and string tables. 40
41 // 41 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
42 // It is implemented as an open hash table with a fixed number of buckets. 42 BasicHashtableEntry<F>* entry = NULL;
43 // 43 if (_free_list != NULL) {
44 // %note:
45 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
46
47 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
48 BasicHashtableEntry<F>* entry;
49
50 if (_free_list) {
51 entry = _free_list; 44 entry = _free_list;
52 _free_list = _free_list->next(); 45 _free_list = _free_list->next();
53 } else { 46 }
47 return entry;
48 }
49
50 // HashtableEntrys are allocated in blocks to reduce the space overhead.
51 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
52 BasicHashtableEntry<F>* entry = new_entry_free_list();
53
54 if (entry == NULL) {
54 if (_first_free_entry + _entry_size >= _end_block) { 55 if (_first_free_entry + _entry_size >= _end_block) {
55 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries)); 56 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
56 int len = _entry_size * block_size; 57 int len = _entry_size * block_size;
57 len = 1 << log2_intptr(len); // round down to power of 2 58 len = 1 << log2_intptr(len); // round down to power of 2
58 assert(len >= _entry_size, ""); 59 assert(len >= _entry_size, "");
81 // rehash at the next safepoint. If this bucket is 60 times greater than the 82 // rehash at the next safepoint. If this bucket is 60 times greater than the
82 // expected average bucket length, it's an unbalanced hashtable. 83 // expected average bucket length, it's an unbalanced hashtable.
83 // This is somewhat an arbitrary heuristic but if one bucket gets to 84 // This is somewhat an arbitrary heuristic but if one bucket gets to
84 // rehash_count which is currently 100, there's probably something wrong. 85 // rehash_count which is currently 100, there's probably something wrong.
85 86
86 template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) { 87 template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
87 assert(table_size() != 0, "underflow"); 88 assert(this->table_size() != 0, "underflow");
88 if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) { 89 if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
89 // Set a flag for the next safepoint, which should be at some guaranteed 90 // Set a flag for the next safepoint, which should be at some guaranteed
90 // safepoint interval. 91 // safepoint interval.
91 return true; 92 return true;
92 } 93 }
93 return false; 94 return false;
94 } 95 }
95 96
96 template <class T, MEMFLAGS F> juint Hashtable<T, F>::_seed = 0; 97 template <class T, MEMFLAGS F> juint RehashableHashtable<T, F>::_seed = 0;
97 98
98 // Create a new table and using alternate hash code, populate the new table 99 // Create a new table and using alternate hash code, populate the new table
99 // with the existing elements. This can be used to change the hash code 100 // with the existing elements. This can be used to change the hash code
100 // and could in the future change the size of the table. 101 // and could in the future change the size of the table.
101 102
102 template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) { 103 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
103 104
104 // Initialize the global seed for hashing. 105 // Initialize the global seed for hashing.
105 _seed = AltHashing::compute_seed(); 106 _seed = AltHashing::compute_seed();
106 assert(seed() != 0, "shouldn't be zero"); 107 assert(seed() != 0, "shouldn't be zero");
107 108
108 int saved_entry_count = this->number_of_entries(); 109 int saved_entry_count = this->number_of_entries();
109 110
110 // Iterate through the table and create a new entry for the new table 111 // Iterate through the table and create a new entry for the new table
111 for (int i = 0; i < new_table->table_size(); ++i) { 112 for (int i = 0; i < new_table->table_size(); ++i) {
112 for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) { 113 for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
113 HashtableEntry<T, F>* next = p->next(); 114 HashtableEntry<T, F>* next = p->next();
114 T string = p->literal(); 115 T string = p->literal();
115 // Use alternate hashing algorithm on the symbol in the first table 116 // Use alternate hashing algorithm on the symbol in the first table
116 unsigned int hashValue = string->new_hash(seed()); 117 unsigned int hashValue = string->new_hash(seed());
117 // Get a new index relative to the new table (can also change size) 118 // Get a new index relative to the new table (can also change size)
236 *bucket_addr(i) = high_list; 237 *bucket_addr(i) = high_list;
237 } 238 }
238 } 239 }
239 } 240 }
240 241
241 template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(Symbol *symbol) { 242 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
242 return symbol->size() * HeapWordSize; 243 return symbol->size() * HeapWordSize;
243 } 244 }
244 245
245 template <class T, MEMFLAGS F> int Hashtable<T, F>::literal_size(oop oop) { 246 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
246 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true, 247 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
247 // and the String.value array is shared by several Strings. However, starting from JDK8, 248 // and the String.value array is shared by several Strings. However, starting from JDK8,
248 // the String.value array is not shared anymore. 249 // the String.value array is not shared anymore.
249 assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported"); 250 assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
250 return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize; 251 return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
253 // Dump footprint and bucket length statistics 254 // Dump footprint and bucket length statistics
254 // 255 //
255 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to 256 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
256 // add a new function Hashtable<T, F>::literal_size(MyNewType lit) 257 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
257 258
258 template <class T, MEMFLAGS F> void Hashtable<T, F>::dump_table(outputStream* st, const char *table_name) { 259 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
259 NumberSeq summary; 260 NumberSeq summary;
260 int literal_bytes = 0; 261 int literal_bytes = 0;
261 for (int i = 0; i < this->table_size(); ++i) { 262 for (int i = 0; i < this->table_size(); ++i) {
262 int count = 0; 263 int count = 0;
263 for (HashtableEntry<T, F>* e = bucket(i); 264 for (HashtableEntry<T, F>* e = this->bucket(i);
264 e != NULL; e = e->next()) { 265 e != NULL; e = e->next()) {
265 count++; 266 count++;
266 literal_bytes += literal_size(e->literal()); 267 literal_bytes += literal_size(e->literal());
267 } 268 }
268 summary.add((double)count); 269 summary.add((double)count);
269 } 270 }
270 double num_buckets = summary.num(); 271 double num_buckets = summary.num();
271 double num_entries = summary.sum(); 272 double num_entries = summary.sum();
272 273
273 int bucket_bytes = (int)num_buckets * sizeof(bucket(0)); 274 int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
274 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>); 275 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>);
275 int total_bytes = literal_bytes + bucket_bytes + entry_bytes; 276 int total_bytes = literal_bytes + bucket_bytes + entry_bytes;
276 277
277 double bucket_avg = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets); 278 double bucket_avg = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
278 double entry_avg = (num_entries <= 0) ? 0 : (entry_bytes / num_entries); 279 double entry_avg = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
350 } 351 }
351 } 352 }
352 353
353 #endif 354 #endif
354 // Explicitly instantiate these types 355 // Explicitly instantiate these types
356 #if INCLUDE_ALL_GCS
357 template class Hashtable<nmethod*, mtGC>;
358 template class HashtableEntry<nmethod*, mtGC>;
359 template class BasicHashtable<mtGC>;
360 #endif
355 template class Hashtable<ConstantPool*, mtClass>; 361 template class Hashtable<ConstantPool*, mtClass>;
362 template class RehashableHashtable<Symbol*, mtSymbol>;
363 template class RehashableHashtable<oopDesc*, mtSymbol>;
356 template class Hashtable<Symbol*, mtSymbol>; 364 template class Hashtable<Symbol*, mtSymbol>;
357 template class Hashtable<Klass*, mtClass>; 365 template class Hashtable<Klass*, mtClass>;
358 template class Hashtable<oop, mtClass>; 366 template class Hashtable<oop, mtClass>;
359 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS) 367 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
360 template class Hashtable<oop, mtSymbol>; 368 template class Hashtable<oop, mtSymbol>;
369 template class RehashableHashtable<oop, mtSymbol>;
361 #endif // SOLARIS || CHECK_UNHANDLED_OOPS 370 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
362 template class Hashtable<oopDesc*, mtSymbol>; 371 template class Hashtable<oopDesc*, mtSymbol>;
363 template class Hashtable<Symbol*, mtClass>; 372 template class Hashtable<Symbol*, mtClass>;
364 template class HashtableEntry<Symbol*, mtSymbol>; 373 template class HashtableEntry<Symbol*, mtSymbol>;
365 template class HashtableEntry<Symbol*, mtClass>; 374 template class HashtableEntry<Symbol*, mtClass>;