annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 46475:75902cea18af

8166848: Performance bug: SystemDictionary - optimization Summary: Check instead that a bucket isn't 10x the average Reviewed-by: iklam, gziemski, sspitsyn
author coleenp
date Thu, 18 May 2017 08:17:52 -0400
parents 3f6cac9867d4
children 01c282163d38
rev   line source
duke@1 1 /*
coleenp@46475 2 * Copyright (c) 2003, 2017, Oracle and/or its affiliates. All rights reserved.
duke@1 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1 4 *
duke@1 5 * This code is free software; you can redistribute it and/or modify it
duke@1 6 * under the terms of the GNU General Public License version 2 only, as
duke@1 7 * published by the Free Software Foundation.
duke@1 8 *
duke@1 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@1 13 * accompanied this code).
duke@1 14 *
duke@1 15 * You should have received a copy of the GNU General Public License version
duke@1 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@1 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1 18 *
trims@5547 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@5547 20 * or visit www.oracle.com if you need additional information or have any
trims@5547 21 * questions.
duke@1 22 *
duke@1 23 */
duke@1 24
stefank@7397 25 #include "precompiled.hpp"
coleenp@13199 26 #include "classfile/altHashing.hpp"
coleenp@46475 27 #include "classfile/dictionary.hpp"
goetz@35498 28 #include "classfile/javaClasses.inline.hpp"
coleenp@46475 29 #include "classfile/moduleEntry.hpp"
coleenp@46475 30 #include "classfile/packageEntry.hpp"
coleenp@46475 31 #include "classfile/protectionDomainCache.hpp"
gziemski@24426 32 #include "classfile/stringTable.hpp"
stefank@7397 33 #include "memory/allocation.inline.hpp"
coleenp@13097 34 #include "memory/filemap.hpp"
stefank@7397 35 #include "memory/resourceArea.hpp"
stefank@7397 36 #include "oops/oop.inline.hpp"
stefank@7397 37 #include "runtime/safepoint.hpp"
stefank@7397 38 #include "utilities/dtrace.hpp"
stefank@7397 39 #include "utilities/hashtable.hpp"
stefank@7397 40 #include "utilities/hashtable.inline.hpp"
iklam@17610 41 #include "utilities/numberSeq.hpp"
duke@1 42
coleenp@8076 43
mgerdin@26421 44 // This hashtable is implemented as an open hash table with a fixed number of buckets.
duke@1 45
mgerdin@26421 46 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
mgerdin@26421 47 BasicHashtableEntry<F>* entry = NULL;
mgerdin@26421 48 if (_free_list != NULL) {
duke@1 49 entry = _free_list;
duke@1 50 _free_list = _free_list->next();
mgerdin@26421 51 }
mgerdin@26421 52 return entry;
mgerdin@26421 53 }
mgerdin@26421 54
mgerdin@26421 55 // HashtableEntrys are allocated in blocks to reduce the space overhead.
mgerdin@26421 56 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
mgerdin@26421 57 BasicHashtableEntry<F>* entry = new_entry_free_list();
mgerdin@26421 58
mgerdin@26421 59 if (entry == NULL) {
jrose@1551 60 if (_first_free_entry + _entry_size >= _end_block) {
jrose@1551 61 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
duke@1 62 int len = _entry_size * block_size;
jrose@1551 63 len = 1 << log2_intptr(len); // round down to power of 2
jrose@1551 64 assert(len >= _entry_size, "");
zgu@13195 65 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
duke@1 66 _end_block = _first_free_entry + len;
duke@1 67 }
zgu@13195 68 entry = (BasicHashtableEntry<F>*)_first_free_entry;
duke@1 69 _first_free_entry += _entry_size;
duke@1 70 }
duke@1 71
jrose@1551 72 assert(_entry_size % HeapWordSize == 0, "");
duke@1 73 entry->set_hash(hashValue);
duke@1 74 return entry;
duke@1 75 }
duke@1 76
duke@1 77
zgu@13195 78 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
zgu@13195 79 HashtableEntry<T, F>* entry;
duke@1 80
zgu@13195 81 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
coleenp@8076 82 entry->set_literal(obj);
duke@1 83 return entry;
duke@1 84 }
duke@1 85
coleenp@13087 86 // Check to see if the hashtable is unbalanced. The caller set a flag to
coleenp@13087 87 // rehash at the next safepoint. If this bucket is 60 times greater than the
coleenp@13087 88 // expected average bucket length, it's an unbalanced hashtable.
coleenp@13087 89 // This is somewhat an arbitrary heuristic but if one bucket gets to
coleenp@13087 90 // rehash_count which is currently 100, there's probably something wrong.
coleenp@13087 91
mgerdin@26421 92 template <class T, MEMFLAGS F> bool RehashableHashtable<T, F>::check_rehash_table(int count) {
mgerdin@26421 93 assert(this->table_size() != 0, "underflow");
mgerdin@26421 94 if (count > (((double)this->number_of_entries()/(double)this->table_size())*rehash_multiple)) {
coleenp@13087 95 // Set a flag for the next safepoint, which should be at some guaranteed
coleenp@13087 96 // safepoint interval.
coleenp@13087 97 return true;
coleenp@13087 98 }
coleenp@13087 99 return false;
coleenp@13087 100 }
coleenp@13087 101
mgerdin@26421 102 template <class T, MEMFLAGS F> juint RehashableHashtable<T, F>::_seed = 0;
coleenp@13199 103
coleenp@13087 104 // Create a new table and using alternate hash code, populate the new table
coleenp@13087 105 // with the existing elements. This can be used to change the hash code
coleenp@13087 106 // and could in the future change the size of the table.
coleenp@13087 107
mgerdin@26421 108 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::move_to(RehashableHashtable<T, F>* new_table) {
coleenp@13199 109
coleenp@13199 110 // Initialize the global seed for hashing.
coleenp@13199 111 _seed = AltHashing::compute_seed();
coleenp@13199 112 assert(seed() != 0, "shouldn't be zero");
coleenp@13199 113
coleenp@13199 114 int saved_entry_count = this->number_of_entries();
coleenp@13087 115
coleenp@13087 116 // Iterate through the table and create a new entry for the new table
coleenp@13087 117 for (int i = 0; i < new_table->table_size(); ++i) {
mgerdin@26421 118 for (HashtableEntry<T, F>* p = this->bucket(i); p != NULL; ) {
zgu@13195 119 HashtableEntry<T, F>* next = p->next();
coleenp@13087 120 T string = p->literal();
coleenp@13087 121 // Use alternate hashing algorithm on the symbol in the first table
coleenp@13728 122 unsigned int hashValue = string->new_hash(seed());
coleenp@13087 123 // Get a new index relative to the new table (can also change size)
coleenp@13087 124 int index = new_table->hash_to_index(hashValue);
coleenp@13087 125 p->set_hash(hashValue);
coleenp@13097 126 // Keep the shared bit in the Hashtable entry to indicate that this entry
coleenp@13097 127 // can't be deleted. The shared bit is the LSB in the _next field so
coleenp@13097 128 // walking the hashtable past these entries requires
coleenp@13097 129 // BasicHashtableEntry::make_ptr() call.
coleenp@13097 130 bool keep_shared = p->is_shared();
andrew@13342 131 this->unlink_entry(p);
coleenp@13087 132 new_table->add_entry(index, p);
coleenp@13097 133 if (keep_shared) {
coleenp@13097 134 p->set_shared();
coleenp@13097 135 }
coleenp@13087 136 p = next;
coleenp@13087 137 }
coleenp@13087 138 }
coleenp@13087 139 // give the new table the free list as well
coleenp@13087 140 new_table->copy_freelist(this);
coleenp@13087 141 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?");
coleenp@13087 142
coleenp@13087 143 // Destroy memory used by the buckets in the hashtable. The memory
coleenp@13087 144 // for the elements has been used in a new table and is not
coleenp@13087 145 // destroyed. The memory reuse will benefit resizing the SystemDictionary
coleenp@13087 146 // to avoid a memory allocation spike at safepoint.
zgu@13195 147 BasicHashtable<F>::free_buckets();
coleenp@13087 148 }
coleenp@13087 149
zgu@13195 150 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
coleenp@13097 151 if (NULL != _buckets) {
coleenp@13097 152 // Don't delete the buckets in the shared space. They aren't
coleenp@13097 153 // allocated by os::malloc
coleenp@13097 154 if (!UseSharedSpaces ||
coleenp@13097 155 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) {
coleenp@27880 156 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
coleenp@13097 157 }
coleenp@13097 158 _buckets = NULL;
coleenp@13097 159 }
coleenp@13097 160 }
coleenp@13097 161
coleenp@13097 162
duke@1 163 // Copy the table to the shared space.
duke@1 164
zgu@13195 165 template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) {
duke@1 166
duke@1 167 // Dump the hash table entries.
duke@1 168
duke@1 169 intptr_t *plen = (intptr_t*)(*top);
duke@1 170 *top += sizeof(*plen);
duke@1 171
duke@1 172 int i;
duke@1 173 for (i = 0; i < _table_size; ++i) {
zgu@13195 174 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr();
duke@1 175 *p != NULL;
duke@1 176 p = (*p)->next_addr()) {
duke@1 177 if (*top + entry_size() > end) {
coleenp@8076 178 report_out_of_shared_space(SharedMiscData);
duke@1 179 }
zgu@13195 180 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size());
duke@1 181 *top += entry_size();
duke@1 182 }
duke@1 183 }
duke@1 184 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 185
duke@1 186 // Set the shared bit.
duke@1 187
duke@1 188 for (i = 0; i < _table_size; ++i) {
zgu@13195 189 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) {
duke@1 190 p->set_shared();
duke@1 191 }
duke@1 192 }
duke@1 193 }
duke@1 194
duke@1 195
mgerdin@26421 196 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(Symbol *symbol) {
iklam@17610 197 return symbol->size() * HeapWordSize;
iklam@17610 198 }
iklam@17610 199
mgerdin@26421 200 template <class T, MEMFLAGS F> int RehashableHashtable<T, F>::literal_size(oop oop) {
iklam@17610 201 // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
iklam@17610 202 // and the String.value array is shared by several Strings. However, starting from JDK8,
iklam@17610 203 // the String.value array is not shared anymore.
iklam@17610 204 assert(oop != NULL && oop->klass() == SystemDictionary::String_klass(), "only strings are supported");
iklam@17610 205 return (oop->size() + java_lang_String::value(oop)->size()) * HeapWordSize;
iklam@17610 206 }
iklam@17610 207
iklam@17610 208 // Dump footprint and bucket length statistics
iklam@17610 209 //
iklam@17610 210 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
iklam@17610 211 // add a new function Hashtable<T, F>::literal_size(MyNewType lit)
iklam@17610 212
mgerdin@26421 213 template <class T, MEMFLAGS F> void RehashableHashtable<T, F>::dump_table(outputStream* st, const char *table_name) {
iklam@17610 214 NumberSeq summary;
iklam@17610 215 int literal_bytes = 0;
iklam@17610 216 for (int i = 0; i < this->table_size(); ++i) {
iklam@17610 217 int count = 0;
mgerdin@26421 218 for (HashtableEntry<T, F>* e = this->bucket(i);
iklam@17610 219 e != NULL; e = e->next()) {
iklam@17610 220 count++;
iklam@17610 221 literal_bytes += literal_size(e->literal());
iklam@17610 222 }
iklam@17610 223 summary.add((double)count);
iklam@17610 224 }
iklam@17610 225 double num_buckets = summary.num();
iklam@17610 226 double num_entries = summary.sum();
iklam@17610 227
mgerdin@26421 228 int bucket_bytes = (int)num_buckets * sizeof(HashtableBucket<F>);
iklam@17610 229 int entry_bytes = (int)num_entries * sizeof(HashtableEntry<T, F>);
iklam@17610 230 int total_bytes = literal_bytes + bucket_bytes + entry_bytes;
iklam@17610 231
iklam@17610 232 double bucket_avg = (num_buckets <= 0) ? 0 : (bucket_bytes / num_buckets);
iklam@17610 233 double entry_avg = (num_entries <= 0) ? 0 : (entry_bytes / num_entries);
iklam@17610 234 double literal_avg = (num_entries <= 0) ? 0 : (literal_bytes / num_entries);
iklam@17610 235
iklam@17610 236 st->print_cr("%s statistics:", table_name);
iklam@17610 237 st->print_cr("Number of buckets : %9d = %9d bytes, avg %7.3f", (int)num_buckets, bucket_bytes, bucket_avg);
iklam@17610 238 st->print_cr("Number of entries : %9d = %9d bytes, avg %7.3f", (int)num_entries, entry_bytes, entry_avg);
iklam@17610 239 st->print_cr("Number of literals : %9d = %9d bytes, avg %7.3f", (int)num_entries, literal_bytes, literal_avg);
iklam@17610 240 st->print_cr("Total footprint : %9s = %9d bytes", "", total_bytes);
iklam@17610 241 st->print_cr("Average bucket size : %9.3f", summary.avg());
iklam@17610 242 st->print_cr("Variance of bucket size : %9.3f", summary.variance());
iklam@17610 243 st->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
iklam@17610 244 st->print_cr("Maximum bucket size : %9d", (int)summary.maximum());
iklam@17610 245 }
iklam@17610 246
duke@1 247
duke@1 248 // Dump the hash table buckets.
duke@1 249
zgu@13195 250 template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) {
zgu@13195 251 intptr_t len = _table_size * sizeof(HashtableBucket<F>);
duke@1 252 *(intptr_t*)(*top) = len;
duke@1 253 *top += sizeof(intptr_t);
duke@1 254
duke@1 255 *(intptr_t*)(*top) = _number_of_entries;
duke@1 256 *top += sizeof(intptr_t);
duke@1 257
duke@1 258 if (*top + len > end) {
coleenp@8076 259 report_out_of_shared_space(SharedMiscData);
duke@1 260 }
zgu@13195 261 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len);
duke@1 262 *top += len;
duke@1 263 }
duke@1 264
duke@1 265
duke@1 266 #ifndef PRODUCT
duke@1 267
zgu@13195 268 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
duke@1 269 ResourceMark rm;
duke@1 270
zgu@13195 271 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
zgu@13195 272 HashtableEntry<T, F>* entry = bucket(i);
duke@1 273 while(entry != NULL) {
duke@1 274 tty->print("%d : ", i);
duke@1 275 entry->literal()->print();
duke@1 276 tty->cr();
duke@1 277 entry = entry->next();
duke@1 278 }
duke@1 279 }
duke@1 280 }
duke@1 281
duke@1 282
coleenp@46475 283 template <MEMFLAGS F>
coleenp@46475 284 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
coleenp@46475 285 int element_count = 0;
coleenp@46475 286 int max_bucket_count = 0;
coleenp@46475 287 for (int index = 0; index < table_size(); index++) {
coleenp@46475 288 int bucket_count = 0;
coleenp@46475 289 for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
coleenp@46475 290 probe->verify();
coleenp@46475 291 bucket_count++;
duke@1 292 }
coleenp@46475 293 element_count += bucket_count;
coleenp@46475 294 max_bucket_count = MAX2(max_bucket_count, bucket_count);
duke@1 295 }
coleenp@46475 296 guarantee(number_of_entries() == element_count,
coleenp@46475 297 "Verify of %s failed", table_name);
coleenp@46475 298 DEBUG_ONLY(verify_lookup_length(max_bucket_count, table_name));
duke@1 299 }
duke@1 300
duke@1 301
duke@1 302 #endif // PRODUCT
duke@1 303
duke@1 304 #ifdef ASSERT
duke@1 305
coleenp@46475 306 // Assert if the longest bucket is 10x longer than the average bucket size.
coleenp@46475 307 // Could change back to a warning, but warnings are not noticed.
coleenp@46475 308 template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(int max_bucket_count, const char *table_name) {
coleenp@46475 309 log_info(hashtables)("%s max bucket size %d element count %d table size %d", table_name,
coleenp@46475 310 max_bucket_count, _number_of_entries, _table_size);
coleenp@46475 311 assert (max_bucket_count < ((1 + number_of_entries()/table_size())*10), "Table is unbalanced");
duke@1 312 }
duke@1 313
duke@1 314 #endif
anoll@22921 315
anoll@22921 316
coleenp@8076 317 // Explicitly instantiate these types
mgerdin@26422 318 #if INCLUDE_ALL_GCS
mgerdin@26422 319 template class Hashtable<nmethod*, mtGC>;
mgerdin@26422 320 template class HashtableEntry<nmethod*, mtGC>;
mgerdin@26422 321 template class BasicHashtable<mtGC>;
mgerdin@26422 322 #endif
coleenp@13728 323 template class Hashtable<ConstantPool*, mtClass>;
mgerdin@26421 324 template class RehashableHashtable<Symbol*, mtSymbol>;
mgerdin@26421 325 template class RehashableHashtable<oopDesc*, mtSymbol>;
zgu@13195 326 template class Hashtable<Symbol*, mtSymbol>;
coleenp@13728 327 template class Hashtable<Klass*, mtClass>;
iklam@34257 328 template class Hashtable<InstanceKlass*, mtClass>;
zgu@13195 329 template class Hashtable<oop, mtClass>;
hseigel@20282 330 #if defined(SOLARIS) || defined(CHECK_UNHANDLED_OOPS)
zgu@13195 331 template class Hashtable<oop, mtSymbol>;
mgerdin@26421 332 template class RehashableHashtable<oop, mtSymbol>;
hseigel@20282 333 #endif // SOLARIS || CHECK_UNHANDLED_OOPS
zgu@13195 334 template class Hashtable<oopDesc*, mtSymbol>;
zgu@13195 335 template class Hashtable<Symbol*, mtClass>;
zgu@13195 336 template class HashtableEntry<Symbol*, mtSymbol>;
zgu@13195 337 template class HashtableEntry<Symbol*, mtClass>;
zgu@13195 338 template class HashtableEntry<oop, mtSymbol>;
zgu@13195 339 template class BasicHashtableEntry<mtSymbol>;
zgu@13195 340 template class BasicHashtableEntry<mtCode>;
zgu@13195 341 template class BasicHashtable<mtClass>;
iklam@34257 342 template class BasicHashtable<mtClassShared>;
zgu@13195 343 template class BasicHashtable<mtSymbol>;
zgu@13195 344 template class BasicHashtable<mtCode>;
zgu@13195 345 template class BasicHashtable<mtInternal>;
hseigel@38733 346 template class BasicHashtable<mtModule>;
mgronlun@36384 347 #if INCLUDE_TRACE
mgronlun@36384 348 template class Hashtable<Symbol*, mtTracing>;
mgronlun@36384 349 template class HashtableEntry<Symbol*, mtTracing>;
mgronlun@36384 350 template class BasicHashtable<mtTracing>;
mgronlun@36384 351 #endif
kvn@30593 352 template class BasicHashtable<mtCompiler>;
coleenp@46475 353
coleenp@46475 354 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
coleenp@46475 355 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
coleenp@46475 356 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
coleenp@46475 357 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);