Wed, 23 Sep 2020 15:18:53 +0300
8240124: Better VM Interning
Reviewed-by: mbalao, andrew
aoqi@0 | 1 | /* |
vkempik@8452 | 2 | * Copyright (c) 2014, 2016, Oracle and/or its affiliates. All rights reserved. |
aoqi@0 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
aoqi@0 | 4 | * |
aoqi@0 | 5 | * This code is free software; you can redistribute it and/or modify it |
aoqi@0 | 6 | * under the terms of the GNU General Public License version 2 only, as |
aoqi@0 | 7 | * published by the Free Software Foundation. |
aoqi@0 | 8 | * |
aoqi@0 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
aoqi@0 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
aoqi@0 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
aoqi@0 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
aoqi@0 | 13 | * accompanied this code). |
aoqi@0 | 14 | * |
aoqi@0 | 15 | * You should have received a copy of the GNU General Public License version |
aoqi@0 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
aoqi@0 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
aoqi@0 | 18 | * |
aoqi@0 | 19 | * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
aoqi@0 | 20 | * or visit www.oracle.com if you need additional information or have any |
aoqi@0 | 21 | * questions. |
aoqi@0 | 22 | * |
aoqi@0 | 23 | */ |
aoqi@0 | 24 | |
aoqi@0 | 25 | #include "precompiled.hpp" |
aoqi@0 | 26 | #include "classfile/altHashing.hpp" |
aoqi@0 | 27 | #include "classfile/javaClasses.hpp" |
aoqi@0 | 28 | #include "gc_implementation/g1/g1CollectedHeap.inline.hpp" |
aoqi@0 | 29 | #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp" |
aoqi@0 | 30 | #include "gc_implementation/g1/g1StringDedupTable.hpp" |
vkempik@8452 | 31 | #include "gc_implementation/shared/concurrentGCThread.hpp" |
aoqi@0 | 32 | #include "memory/gcLocker.hpp" |
aoqi@0 | 33 | #include "memory/padded.inline.hpp" |
aoqi@0 | 34 | #include "oops/typeArrayOop.hpp" |
aoqi@0 | 35 | #include "runtime/mutexLocker.hpp" |
aoqi@0 | 36 | |
aoqi@0 | 37 | // |
vkempik@8452 | 38 | // List of deduplication table entries. Links table |
aoqi@0 | 39 | // entries together using their _next fields. |
aoqi@0 | 40 | // |
vkempik@8452 | 41 | class G1StringDedupEntryList : public CHeapObj<mtGC> { |
aoqi@0 | 42 | private: |
aoqi@0 | 43 | G1StringDedupEntry* _list; |
aoqi@0 | 44 | size_t _length; |
aoqi@0 | 45 | |
aoqi@0 | 46 | public: |
vkempik@8452 | 47 | G1StringDedupEntryList() : |
aoqi@0 | 48 | _list(NULL), |
aoqi@0 | 49 | _length(0) { |
aoqi@0 | 50 | } |
aoqi@0 | 51 | |
aoqi@0 | 52 | void add(G1StringDedupEntry* entry) { |
aoqi@0 | 53 | entry->set_next(_list); |
aoqi@0 | 54 | _list = entry; |
aoqi@0 | 55 | _length++; |
aoqi@0 | 56 | } |
aoqi@0 | 57 | |
aoqi@0 | 58 | G1StringDedupEntry* remove() { |
aoqi@0 | 59 | G1StringDedupEntry* entry = _list; |
aoqi@0 | 60 | if (entry != NULL) { |
aoqi@0 | 61 | _list = entry->next(); |
aoqi@0 | 62 | _length--; |
aoqi@0 | 63 | } |
aoqi@0 | 64 | return entry; |
aoqi@0 | 65 | } |
aoqi@0 | 66 | |
vkempik@8452 | 67 | G1StringDedupEntry* remove_all() { |
vkempik@8452 | 68 | G1StringDedupEntry* list = _list; |
vkempik@8452 | 69 | _list = NULL; |
vkempik@8452 | 70 | return list; |
vkempik@8452 | 71 | } |
vkempik@8452 | 72 | |
aoqi@0 | 73 | size_t length() { |
aoqi@0 | 74 | return _length; |
aoqi@0 | 75 | } |
aoqi@0 | 76 | }; |
aoqi@0 | 77 | |
aoqi@0 | 78 | // |
aoqi@0 | 79 | // Cache of deduplication table entries. This cache provides fast allocation and |
aoqi@0 | 80 | // reuse of table entries to lower the pressure on the underlying allocator. |
aoqi@0 | 81 | // But more importantly, it provides fast/deferred freeing of table entries. This |
aoqi@0 | 82 | // is important because freeing of table entries is done during stop-the-world |
aoqi@0 | 83 | // phases and it is not uncommon for large number of entries to be freed at once. |
aoqi@0 | 84 | // Tables entries that are freed during these phases are placed onto a freelist in |
aoqi@0 | 85 | // the cache. The deduplication thread, which executes in a concurrent phase, will |
aoqi@0 | 86 | // later reuse or free the underlying memory for these entries. |
aoqi@0 | 87 | // |
aoqi@0 | 88 | // The cache allows for single-threaded allocations and multi-threaded frees. |
aoqi@0 | 89 | // Allocations are synchronized by StringDedupTable_lock as part of a table |
aoqi@0 | 90 | // modification. |
aoqi@0 | 91 | // |
aoqi@0 | 92 | class G1StringDedupEntryCache : public CHeapObj<mtGC> { |
aoqi@0 | 93 | private: |
vkempik@8452 | 94 | // One cache/overflow list per GC worker to allow lock less freeing of |
vkempik@8452 | 95 | // entries while doing a parallel scan of the table. Using PaddedEnd to |
vkempik@8452 | 96 | // avoid false sharing. |
vkempik@8452 | 97 | size_t _nlists; |
vkempik@8452 | 98 | size_t _max_list_length; |
vkempik@8452 | 99 | PaddedEnd<G1StringDedupEntryList>* _cached; |
vkempik@8452 | 100 | PaddedEnd<G1StringDedupEntryList>* _overflowed; |
aoqi@0 | 101 | |
aoqi@0 | 102 | public: |
vkempik@8452 | 103 | G1StringDedupEntryCache(size_t max_size); |
aoqi@0 | 104 | ~G1StringDedupEntryCache(); |
aoqi@0 | 105 | |
vkempik@8452 | 106 | // Set max number of table entries to cache. |
vkempik@8452 | 107 | void set_max_size(size_t max_size); |
vkempik@8452 | 108 | |
vkempik@8452 | 109 | // Get a table entry from the cache, or allocate a new entry if the cache is empty. |
aoqi@0 | 110 | G1StringDedupEntry* alloc(); |
aoqi@0 | 111 | |
vkempik@8452 | 112 | // Insert a table entry into the cache. |
aoqi@0 | 113 | void free(G1StringDedupEntry* entry, uint worker_id); |
aoqi@0 | 114 | |
aoqi@0 | 115 | // Returns current number of entries in the cache. |
aoqi@0 | 116 | size_t size(); |
aoqi@0 | 117 | |
vkempik@8452 | 118 | // Deletes overflowed entries. |
vkempik@8452 | 119 | void delete_overflowed(); |
aoqi@0 | 120 | }; |
aoqi@0 | 121 | |
vkempik@8452 | 122 | G1StringDedupEntryCache::G1StringDedupEntryCache(size_t max_size) : |
vkempik@8452 | 123 | _nlists(MAX2(ParallelGCThreads, (size_t)1)), |
vkempik@8452 | 124 | _max_list_length(0), |
vkempik@8452 | 125 | _cached(PaddedArray<G1StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)), |
vkempik@8452 | 126 | _overflowed(PaddedArray<G1StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)) { |
vkempik@8452 | 127 | set_max_size(max_size); |
aoqi@0 | 128 | } |
aoqi@0 | 129 | |
aoqi@0 | 130 | G1StringDedupEntryCache::~G1StringDedupEntryCache() { |
aoqi@0 | 131 | ShouldNotReachHere(); |
aoqi@0 | 132 | } |
aoqi@0 | 133 | |
vkempik@8452 | 134 | void G1StringDedupEntryCache::set_max_size(size_t size) { |
vkempik@8452 | 135 | _max_list_length = size / _nlists; |
vkempik@8452 | 136 | } |
vkempik@8452 | 137 | |
aoqi@0 | 138 | G1StringDedupEntry* G1StringDedupEntryCache::alloc() { |
aoqi@0 | 139 | for (size_t i = 0; i < _nlists; i++) { |
vkempik@8452 | 140 | G1StringDedupEntry* entry = _cached[i].remove(); |
aoqi@0 | 141 | if (entry != NULL) { |
aoqi@0 | 142 | return entry; |
aoqi@0 | 143 | } |
aoqi@0 | 144 | } |
aoqi@0 | 145 | return new G1StringDedupEntry(); |
aoqi@0 | 146 | } |
aoqi@0 | 147 | |
aoqi@0 | 148 | void G1StringDedupEntryCache::free(G1StringDedupEntry* entry, uint worker_id) { |
aoqi@0 | 149 | assert(entry->obj() != NULL, "Double free"); |
aoqi@0 | 150 | assert(worker_id < _nlists, "Invalid worker id"); |
vkempik@8452 | 151 | |
aoqi@0 | 152 | entry->set_obj(NULL); |
vkempik@10008 | 153 | entry->set_java_hash(0); |
vkempik@8452 | 154 | |
vkempik@8452 | 155 | if (_cached[worker_id].length() < _max_list_length) { |
vkempik@8452 | 156 | // Cache is not full |
vkempik@8452 | 157 | _cached[worker_id].add(entry); |
vkempik@8452 | 158 | } else { |
vkempik@8452 | 159 | // Cache is full, add to overflow list for later deletion |
vkempik@8452 | 160 | _overflowed[worker_id].add(entry); |
vkempik@8452 | 161 | } |
aoqi@0 | 162 | } |
aoqi@0 | 163 | |
aoqi@0 | 164 | size_t G1StringDedupEntryCache::size() { |
aoqi@0 | 165 | size_t size = 0; |
aoqi@0 | 166 | for (size_t i = 0; i < _nlists; i++) { |
vkempik@8452 | 167 | size += _cached[i].length(); |
aoqi@0 | 168 | } |
aoqi@0 | 169 | return size; |
aoqi@0 | 170 | } |
aoqi@0 | 171 | |
vkempik@8452 | 172 | void G1StringDedupEntryCache::delete_overflowed() { |
vkempik@8452 | 173 | double start = os::elapsedTime(); |
vkempik@8452 | 174 | uintx count = 0; |
vkempik@8452 | 175 | |
aoqi@0 | 176 | for (size_t i = 0; i < _nlists; i++) { |
vkempik@8452 | 177 | G1StringDedupEntry* entry; |
vkempik@8452 | 178 | |
vkempik@8452 | 179 | { |
vkempik@8452 | 180 | // The overflow list can be modified during safepoints, therefore |
vkempik@8452 | 181 | // we temporarily join the suspendible thread set while removing |
vkempik@8452 | 182 | // all entries from the list. |
vkempik@8452 | 183 | SuspendibleThreadSetJoiner sts_join; |
vkempik@8452 | 184 | entry = _overflowed[i].remove_all(); |
vkempik@8452 | 185 | } |
vkempik@8452 | 186 | |
vkempik@8452 | 187 | // Delete all entries |
vkempik@8452 | 188 | while (entry != NULL) { |
vkempik@8452 | 189 | G1StringDedupEntry* next = entry->next(); |
aoqi@0 | 190 | delete entry; |
vkempik@8452 | 191 | entry = next; |
vkempik@8452 | 192 | count++; |
aoqi@0 | 193 | } |
aoqi@0 | 194 | } |
vkempik@8452 | 195 | |
vkempik@8452 | 196 | double end = os::elapsedTime(); |
vkempik@8452 | 197 | if (PrintStringDeduplicationStatistics) { |
vkempik@8452 | 198 | gclog_or_tty->print_cr("[GC concurrent-string-deduplication, deleted " UINTX_FORMAT " entries, " G1_STRDEDUP_TIME_FORMAT "]", count, end - start); |
vkempik@8452 | 199 | } |
aoqi@0 | 200 | } |
aoqi@0 | 201 | |
aoqi@0 | 202 | G1StringDedupTable* G1StringDedupTable::_table = NULL; |
aoqi@0 | 203 | G1StringDedupEntryCache* G1StringDedupTable::_entry_cache = NULL; |
aoqi@0 | 204 | |
aoqi@0 | 205 | const size_t G1StringDedupTable::_min_size = (1 << 10); // 1024 |
aoqi@0 | 206 | const size_t G1StringDedupTable::_max_size = (1 << 24); // 16777216 |
aoqi@0 | 207 | const double G1StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load |
aoqi@0 | 208 | const double G1StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load |
aoqi@0 | 209 | const double G1StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size |
aoqi@0 | 210 | const uintx G1StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected |
aoqi@0 | 211 | const uintx G1StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor); |
aoqi@0 | 212 | |
aoqi@0 | 213 | uintx G1StringDedupTable::_entries_added = 0; |
aoqi@0 | 214 | uintx G1StringDedupTable::_entries_removed = 0; |
aoqi@0 | 215 | uintx G1StringDedupTable::_resize_count = 0; |
aoqi@0 | 216 | uintx G1StringDedupTable::_rehash_count = 0; |
aoqi@0 | 217 | |
vkempik@10008 | 218 | G1StringDedupTable::G1StringDedupTable(size_t size, uint64_t hash_seed) : |
aoqi@0 | 219 | _size(size), |
aoqi@0 | 220 | _entries(0), |
aoqi@0 | 221 | _grow_threshold((uintx)(size * _grow_load_factor)), |
aoqi@0 | 222 | _shrink_threshold((uintx)(size * _shrink_load_factor)), |
aoqi@0 | 223 | _rehash_needed(false), |
aoqi@0 | 224 | _hash_seed(hash_seed) { |
aoqi@0 | 225 | assert(is_power_of_2(size), "Table size must be a power of 2"); |
aoqi@0 | 226 | _buckets = NEW_C_HEAP_ARRAY(G1StringDedupEntry*, _size, mtGC); |
aoqi@0 | 227 | memset(_buckets, 0, _size * sizeof(G1StringDedupEntry*)); |
aoqi@0 | 228 | } |
aoqi@0 | 229 | |
aoqi@0 | 230 | G1StringDedupTable::~G1StringDedupTable() { |
aoqi@0 | 231 | FREE_C_HEAP_ARRAY(G1StringDedupEntry*, _buckets, mtGC); |
aoqi@0 | 232 | } |
aoqi@0 | 233 | |
aoqi@0 | 234 | void G1StringDedupTable::create() { |
aoqi@0 | 235 | assert(_table == NULL, "One string deduplication table allowed"); |
vkempik@8452 | 236 | _entry_cache = new G1StringDedupEntryCache((size_t)(_min_size * _max_cache_factor)); |
aoqi@0 | 237 | _table = new G1StringDedupTable(_min_size); |
aoqi@0 | 238 | } |
aoqi@0 | 239 | |
vkempik@10008 | 240 | void G1StringDedupTable::add(typeArrayOop value, uint64_t hash, G1StringDedupEntry** list) { |
aoqi@0 | 241 | G1StringDedupEntry* entry = _entry_cache->alloc(); |
aoqi@0 | 242 | entry->set_obj(value); |
vkempik@10008 | 243 | if (use_java_hash()) { |
vkempik@10008 | 244 | entry->set_java_hash((unsigned int)hash); |
vkempik@10008 | 245 | } else { |
vkempik@10008 | 246 | entry->set_alt_hash(hash); |
vkempik@10008 | 247 | } |
aoqi@0 | 248 | entry->set_next(*list); |
aoqi@0 | 249 | *list = entry; |
aoqi@0 | 250 | _entries++; |
aoqi@0 | 251 | } |
aoqi@0 | 252 | |
aoqi@0 | 253 | void G1StringDedupTable::remove(G1StringDedupEntry** pentry, uint worker_id) { |
aoqi@0 | 254 | G1StringDedupEntry* entry = *pentry; |
aoqi@0 | 255 | *pentry = entry->next(); |
aoqi@0 | 256 | _entry_cache->free(entry, worker_id); |
aoqi@0 | 257 | } |
aoqi@0 | 258 | |
aoqi@0 | 259 | void G1StringDedupTable::transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest) { |
aoqi@0 | 260 | G1StringDedupEntry* entry = *pentry; |
aoqi@0 | 261 | *pentry = entry->next(); |
vkempik@10008 | 262 | uint64_t hash = use_java_hash() ? entry->java_hash() : entry->alt_hash(); |
aoqi@0 | 263 | size_t index = dest->hash_to_index(hash); |
aoqi@0 | 264 | G1StringDedupEntry** list = dest->bucket(index); |
aoqi@0 | 265 | entry->set_next(*list); |
aoqi@0 | 266 | *list = entry; |
aoqi@0 | 267 | } |
aoqi@0 | 268 | |
aoqi@0 | 269 | bool G1StringDedupTable::equals(typeArrayOop value1, typeArrayOop value2) { |
aoqi@0 | 270 | return (value1 == value2 || |
aoqi@0 | 271 | (value1->length() == value2->length() && |
aoqi@0 | 272 | (!memcmp(value1->base(T_CHAR), |
aoqi@0 | 273 | value2->base(T_CHAR), |
aoqi@0 | 274 | value1->length() * sizeof(jchar))))); |
aoqi@0 | 275 | } |
aoqi@0 | 276 | |
vkempik@10008 | 277 | typeArrayOop G1StringDedupTable::lookup(typeArrayOop value, uint64_t hash, |
aoqi@0 | 278 | G1StringDedupEntry** list, uintx &count) { |
aoqi@0 | 279 | for (G1StringDedupEntry* entry = *list; entry != NULL; entry = entry->next()) { |
vkempik@10008 | 280 | if ((use_java_hash() ? entry->java_hash() : entry->alt_hash()) == hash) { |
aoqi@0 | 281 | typeArrayOop existing_value = entry->obj(); |
aoqi@0 | 282 | if (equals(value, existing_value)) { |
aoqi@0 | 283 | // Match found |
aoqi@0 | 284 | return existing_value; |
aoqi@0 | 285 | } |
aoqi@0 | 286 | } |
aoqi@0 | 287 | count++; |
aoqi@0 | 288 | } |
aoqi@0 | 289 | |
aoqi@0 | 290 | // Not found |
aoqi@0 | 291 | return NULL; |
aoqi@0 | 292 | } |
aoqi@0 | 293 | |
vkempik@10008 | 294 | typeArrayOop G1StringDedupTable::lookup_or_add_inner(typeArrayOop value, uint64_t hash) { |
aoqi@0 | 295 | size_t index = hash_to_index(hash); |
aoqi@0 | 296 | G1StringDedupEntry** list = bucket(index); |
aoqi@0 | 297 | uintx count = 0; |
aoqi@0 | 298 | |
aoqi@0 | 299 | // Lookup in list |
aoqi@0 | 300 | typeArrayOop existing_value = lookup(value, hash, list, count); |
aoqi@0 | 301 | |
aoqi@0 | 302 | // Check if rehash is needed |
aoqi@0 | 303 | if (count > _rehash_threshold) { |
aoqi@0 | 304 | _rehash_needed = true; |
aoqi@0 | 305 | } |
aoqi@0 | 306 | |
aoqi@0 | 307 | if (existing_value == NULL) { |
aoqi@0 | 308 | // Not found, add new entry |
aoqi@0 | 309 | add(value, hash, list); |
aoqi@0 | 310 | |
aoqi@0 | 311 | // Update statistics |
aoqi@0 | 312 | _entries_added++; |
aoqi@0 | 313 | } |
aoqi@0 | 314 | |
aoqi@0 | 315 | return existing_value; |
aoqi@0 | 316 | } |
aoqi@0 | 317 | |
vkempik@10008 | 318 | unsigned int G1StringDedupTable::java_hash_code(typeArrayOop value) { |
vkempik@10008 | 319 | assert(use_java_hash(), "Should not use java hash code"); |
aoqi@0 | 320 | unsigned int hash; |
aoqi@0 | 321 | int length = value->length(); |
aoqi@0 | 322 | const jchar* data = (jchar*)value->base(T_CHAR); |
aoqi@0 | 323 | |
vkempik@10008 | 324 | hash = java_lang_String::hash_code(data, length); |
aoqi@0 | 325 | |
aoqi@0 | 326 | return hash; |
aoqi@0 | 327 | } |
aoqi@0 | 328 | |
vkempik@10008 | 329 | uint64_t G1StringDedupTable::alt_hash_code(typeArrayOop value) { |
vkempik@10008 | 330 | assert(!use_java_hash(), "Should not use alt hash code"); |
vkempik@10008 | 331 | |
vkempik@10008 | 332 | int length = value->length(); |
vkempik@10008 | 333 | const jbyte* data = (jbyte*)value->base(T_BYTE); |
vkempik@10008 | 334 | return AltHashing::halfsiphash_64(_table->_hash_seed, (const int8_t*)data, length); |
vkempik@10008 | 335 | } |
vkempik@10008 | 336 | |
aoqi@0 | 337 | void G1StringDedupTable::deduplicate(oop java_string, G1StringDedupStat& stat) { |
aoqi@0 | 338 | assert(java_lang_String::is_instance(java_string), "Must be a string"); |
aoqi@0 | 339 | No_Safepoint_Verifier nsv; |
aoqi@0 | 340 | |
aoqi@0 | 341 | stat.inc_inspected(); |
aoqi@0 | 342 | |
aoqi@0 | 343 | typeArrayOop value = java_lang_String::value(java_string); |
aoqi@0 | 344 | if (value == NULL) { |
aoqi@0 | 345 | // String has no value |
aoqi@0 | 346 | stat.inc_skipped(); |
aoqi@0 | 347 | return; |
aoqi@0 | 348 | } |
aoqi@0 | 349 | |
vkempik@10008 | 350 | uint64_t hash = 0; |
aoqi@0 | 351 | |
aoqi@0 | 352 | if (use_java_hash()) { |
aoqi@0 | 353 | // Get hash code from cache |
aoqi@0 | 354 | hash = java_lang_String::hash(java_string); |
aoqi@0 | 355 | } |
aoqi@0 | 356 | |
aoqi@0 | 357 | if (hash == 0) { |
aoqi@0 | 358 | // Compute hash |
vkempik@10008 | 359 | hash = alt_hash_code(value); |
aoqi@0 | 360 | stat.inc_hashed(); |
aoqi@0 | 361 | } |
aoqi@0 | 362 | |
aoqi@0 | 363 | if (use_java_hash() && hash != 0) { |
aoqi@0 | 364 | // Store hash code in cache |
aoqi@0 | 365 | java_lang_String::set_hash(java_string, hash); |
aoqi@0 | 366 | } |
aoqi@0 | 367 | |
aoqi@0 | 368 | typeArrayOop existing_value = lookup_or_add(value, hash); |
aoqi@0 | 369 | if (existing_value == value) { |
aoqi@0 | 370 | // Same value, already known |
aoqi@0 | 371 | stat.inc_known(); |
aoqi@0 | 372 | return; |
aoqi@0 | 373 | } |
aoqi@0 | 374 | |
aoqi@0 | 375 | // Get size of value array |
aoqi@0 | 376 | uintx size_in_bytes = value->size() * HeapWordSize; |
aoqi@0 | 377 | stat.inc_new(size_in_bytes); |
aoqi@0 | 378 | |
aoqi@0 | 379 | if (existing_value != NULL) { |
aoqi@0 | 380 | // Enqueue the reference to make sure it is kept alive. Concurrent mark might |
aoqi@0 | 381 | // otherwise declare it dead if there are no other strong references to this object. |
aoqi@0 | 382 | G1SATBCardTableModRefBS::enqueue(existing_value); |
aoqi@0 | 383 | |
aoqi@0 | 384 | // Existing value found, deduplicate string |
aoqi@0 | 385 | java_lang_String::set_value(java_string, existing_value); |
aoqi@0 | 386 | |
aoqi@0 | 387 | if (G1CollectedHeap::heap()->is_in_young(value)) { |
aoqi@0 | 388 | stat.inc_deduped_young(size_in_bytes); |
aoqi@0 | 389 | } else { |
aoqi@0 | 390 | stat.inc_deduped_old(size_in_bytes); |
aoqi@0 | 391 | } |
aoqi@0 | 392 | } |
aoqi@0 | 393 | } |
aoqi@0 | 394 | |
aoqi@0 | 395 | G1StringDedupTable* G1StringDedupTable::prepare_resize() { |
aoqi@0 | 396 | size_t size = _table->_size; |
aoqi@0 | 397 | |
aoqi@0 | 398 | // Check if the hashtable needs to be resized |
aoqi@0 | 399 | if (_table->_entries > _table->_grow_threshold) { |
aoqi@0 | 400 | // Grow table, double the size |
aoqi@0 | 401 | size *= 2; |
aoqi@0 | 402 | if (size > _max_size) { |
aoqi@0 | 403 | // Too big, don't resize |
aoqi@0 | 404 | return NULL; |
aoqi@0 | 405 | } |
aoqi@0 | 406 | } else if (_table->_entries < _table->_shrink_threshold) { |
aoqi@0 | 407 | // Shrink table, half the size |
aoqi@0 | 408 | size /= 2; |
aoqi@0 | 409 | if (size < _min_size) { |
aoqi@0 | 410 | // Too small, don't resize |
aoqi@0 | 411 | return NULL; |
aoqi@0 | 412 | } |
aoqi@0 | 413 | } else if (StringDeduplicationResizeALot) { |
aoqi@0 | 414 | // Force grow |
aoqi@0 | 415 | size *= 2; |
aoqi@0 | 416 | if (size > _max_size) { |
aoqi@0 | 417 | // Too big, force shrink instead |
aoqi@0 | 418 | size /= 4; |
aoqi@0 | 419 | } |
aoqi@0 | 420 | } else { |
aoqi@0 | 421 | // Resize not needed |
aoqi@0 | 422 | return NULL; |
aoqi@0 | 423 | } |
aoqi@0 | 424 | |
aoqi@0 | 425 | // Update statistics |
aoqi@0 | 426 | _resize_count++; |
aoqi@0 | 427 | |
vkempik@8452 | 428 | // Update max cache size |
vkempik@8452 | 429 | _entry_cache->set_max_size((size_t)(size * _max_cache_factor)); |
vkempik@8452 | 430 | |
aoqi@0 | 431 | // Allocate the new table. The new table will be populated by workers |
aoqi@0 | 432 | // calling unlink_or_oops_do() and finally installed by finish_resize(). |
aoqi@0 | 433 | return new G1StringDedupTable(size, _table->_hash_seed); |
aoqi@0 | 434 | } |
aoqi@0 | 435 | |
aoqi@0 | 436 | void G1StringDedupTable::finish_resize(G1StringDedupTable* resized_table) { |
aoqi@0 | 437 | assert(resized_table != NULL, "Invalid table"); |
aoqi@0 | 438 | |
aoqi@0 | 439 | resized_table->_entries = _table->_entries; |
aoqi@0 | 440 | |
aoqi@0 | 441 | // Free old table |
aoqi@0 | 442 | delete _table; |
aoqi@0 | 443 | |
aoqi@0 | 444 | // Install new table |
aoqi@0 | 445 | _table = resized_table; |
aoqi@0 | 446 | } |
aoqi@0 | 447 | |
aoqi@0 | 448 | void G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id) { |
aoqi@0 | 449 | // The table is divided into partitions to allow lock-less parallel processing by |
aoqi@0 | 450 | // multiple worker threads. A worker thread first claims a partition, which ensures |
aoqi@0 | 451 | // exclusive access to that part of the table, then continues to process it. To allow |
aoqi@0 | 452 | // shrinking of the table in parallel we also need to make sure that the same worker |
aoqi@0 | 453 | // thread processes all partitions where entries will hash to the same destination |
aoqi@0 | 454 | // partition. Since the table size is always a power of two and we always shrink by |
aoqi@0 | 455 | // dividing the table in half, we know that for a given partition there is only one |
aoqi@0 | 456 | // other partition whoes entries will hash to the same destination partition. That |
aoqi@0 | 457 | // other partition is always the sibling partition in the second half of the table. |
aoqi@0 | 458 | // For example, if the table is divided into 8 partitions, the sibling of partition 0 |
aoqi@0 | 459 | // is partition 4, the sibling of partition 1 is partition 5, etc. |
aoqi@0 | 460 | size_t table_half = _table->_size / 2; |
aoqi@0 | 461 | |
aoqi@0 | 462 | // Let each partition be one page worth of buckets |
aoqi@0 | 463 | size_t partition_size = MIN2(table_half, os::vm_page_size() / sizeof(G1StringDedupEntry*)); |
aoqi@0 | 464 | assert(table_half % partition_size == 0, "Invalid partition size"); |
aoqi@0 | 465 | |
aoqi@0 | 466 | // Number of entries removed during the scan |
aoqi@0 | 467 | uintx removed = 0; |
aoqi@0 | 468 | |
aoqi@0 | 469 | for (;;) { |
aoqi@0 | 470 | // Grab next partition to scan |
aoqi@0 | 471 | size_t partition_begin = cl->claim_table_partition(partition_size); |
aoqi@0 | 472 | size_t partition_end = partition_begin + partition_size; |
aoqi@0 | 473 | if (partition_begin >= table_half) { |
aoqi@0 | 474 | // End of table |
aoqi@0 | 475 | break; |
aoqi@0 | 476 | } |
aoqi@0 | 477 | |
aoqi@0 | 478 | // Scan the partition followed by the sibling partition in the second half of the table |
aoqi@0 | 479 | removed += unlink_or_oops_do(cl, partition_begin, partition_end, worker_id); |
aoqi@0 | 480 | removed += unlink_or_oops_do(cl, table_half + partition_begin, table_half + partition_end, worker_id); |
aoqi@0 | 481 | } |
aoqi@0 | 482 | |
vkempik@8452 | 483 | // Delayed update to avoid contention on the table lock |
aoqi@0 | 484 | if (removed > 0) { |
aoqi@0 | 485 | MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag); |
aoqi@0 | 486 | _table->_entries -= removed; |
aoqi@0 | 487 | _entries_removed += removed; |
aoqi@0 | 488 | } |
aoqi@0 | 489 | } |
aoqi@0 | 490 | |
aoqi@0 | 491 | uintx G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, |
aoqi@0 | 492 | size_t partition_begin, |
aoqi@0 | 493 | size_t partition_end, |
aoqi@0 | 494 | uint worker_id) { |
aoqi@0 | 495 | uintx removed = 0; |
aoqi@0 | 496 | for (size_t bucket = partition_begin; bucket < partition_end; bucket++) { |
aoqi@0 | 497 | G1StringDedupEntry** entry = _table->bucket(bucket); |
aoqi@0 | 498 | while (*entry != NULL) { |
aoqi@0 | 499 | oop* p = (oop*)(*entry)->obj_addr(); |
aoqi@0 | 500 | if (cl->is_alive(*p)) { |
aoqi@0 | 501 | cl->keep_alive(p); |
aoqi@0 | 502 | if (cl->is_resizing()) { |
aoqi@0 | 503 | // We are resizing the table, transfer entry to the new table |
aoqi@0 | 504 | _table->transfer(entry, cl->resized_table()); |
aoqi@0 | 505 | } else { |
aoqi@0 | 506 | if (cl->is_rehashing()) { |
aoqi@0 | 507 | // We are rehashing the table, rehash the entry but keep it |
aoqi@0 | 508 | // in the table. We can't transfer entries into the new table |
aoqi@0 | 509 | // at this point since we don't have exclusive access to all |
aoqi@0 | 510 | // destination partitions. finish_rehash() will do a single |
aoqi@0 | 511 | // threaded transfer of all entries. |
aoqi@0 | 512 | typeArrayOop value = (typeArrayOop)*p; |
vkempik@10008 | 513 | assert(!use_java_hash(), "Should not be using Java hash"); |
vkempik@10008 | 514 | uint64_t hash = alt_hash_code(value); |
vkempik@10008 | 515 | (*entry)->set_alt_hash(hash); |
aoqi@0 | 516 | } |
aoqi@0 | 517 | |
aoqi@0 | 518 | // Move to next entry |
aoqi@0 | 519 | entry = (*entry)->next_addr(); |
aoqi@0 | 520 | } |
aoqi@0 | 521 | } else { |
aoqi@0 | 522 | // Not alive, remove entry from table |
aoqi@0 | 523 | _table->remove(entry, worker_id); |
aoqi@0 | 524 | removed++; |
aoqi@0 | 525 | } |
aoqi@0 | 526 | } |
aoqi@0 | 527 | } |
aoqi@0 | 528 | |
aoqi@0 | 529 | return removed; |
aoqi@0 | 530 | } |
aoqi@0 | 531 | |
aoqi@0 | 532 | G1StringDedupTable* G1StringDedupTable::prepare_rehash() { |
aoqi@0 | 533 | if (!_table->_rehash_needed && !StringDeduplicationRehashALot) { |
aoqi@0 | 534 | // Rehash not needed |
aoqi@0 | 535 | return NULL; |
aoqi@0 | 536 | } |
aoqi@0 | 537 | |
aoqi@0 | 538 | // Update statistics |
aoqi@0 | 539 | _rehash_count++; |
aoqi@0 | 540 | |
aoqi@0 | 541 | // Compute new hash seed |
aoqi@0 | 542 | _table->_hash_seed = AltHashing::compute_seed(); |
aoqi@0 | 543 | |
aoqi@0 | 544 | // Allocate the new table, same size and hash seed |
aoqi@0 | 545 | return new G1StringDedupTable(_table->_size, _table->_hash_seed); |
aoqi@0 | 546 | } |
aoqi@0 | 547 | |
aoqi@0 | 548 | void G1StringDedupTable::finish_rehash(G1StringDedupTable* rehashed_table) { |
aoqi@0 | 549 | assert(rehashed_table != NULL, "Invalid table"); |
aoqi@0 | 550 | |
aoqi@0 | 551 | // Move all newly rehashed entries into the correct buckets in the new table |
aoqi@0 | 552 | for (size_t bucket = 0; bucket < _table->_size; bucket++) { |
aoqi@0 | 553 | G1StringDedupEntry** entry = _table->bucket(bucket); |
aoqi@0 | 554 | while (*entry != NULL) { |
aoqi@0 | 555 | _table->transfer(entry, rehashed_table); |
aoqi@0 | 556 | } |
aoqi@0 | 557 | } |
aoqi@0 | 558 | |
aoqi@0 | 559 | rehashed_table->_entries = _table->_entries; |
aoqi@0 | 560 | |
aoqi@0 | 561 | // Free old table |
aoqi@0 | 562 | delete _table; |
aoqi@0 | 563 | |
aoqi@0 | 564 | // Install new table |
aoqi@0 | 565 | _table = rehashed_table; |
aoqi@0 | 566 | } |
aoqi@0 | 567 | |
aoqi@0 | 568 | void G1StringDedupTable::verify() { |
aoqi@0 | 569 | for (size_t bucket = 0; bucket < _table->_size; bucket++) { |
aoqi@0 | 570 | // Verify entries |
aoqi@0 | 571 | G1StringDedupEntry** entry = _table->bucket(bucket); |
aoqi@0 | 572 | while (*entry != NULL) { |
aoqi@0 | 573 | typeArrayOop value = (*entry)->obj(); |
aoqi@0 | 574 | guarantee(value != NULL, "Object must not be NULL"); |
aoqi@0 | 575 | guarantee(Universe::heap()->is_in_reserved(value), "Object must be on the heap"); |
aoqi@0 | 576 | guarantee(!value->is_forwarded(), "Object must not be forwarded"); |
aoqi@0 | 577 | guarantee(value->is_typeArray(), "Object must be a typeArrayOop"); |
vkempik@10008 | 578 | uint64_t hash; |
vkempik@10008 | 579 | if (use_java_hash()) { |
vkempik@10008 | 580 | hash = (*entry)->java_hash(); |
vkempik@10008 | 581 | guarantee(java_hash_code(value) == hash, "Table entry has incorrect hash"); |
vkempik@10008 | 582 | } else { |
vkempik@10008 | 583 | hash = (*entry)->alt_hash(); |
vkempik@10008 | 584 | guarantee(alt_hash_code(value) == hash, "Table entry has incorrect hash"); |
vkempik@10008 | 585 | } |
aoqi@0 | 586 | guarantee(_table->hash_to_index(hash) == bucket, "Table entry has incorrect index"); |
aoqi@0 | 587 | entry = (*entry)->next_addr(); |
aoqi@0 | 588 | } |
aoqi@0 | 589 | |
aoqi@0 | 590 | // Verify that we do not have entries with identical oops or identical arrays. |
aoqi@0 | 591 | // We only need to compare entries in the same bucket. If the same oop or an |
aoqi@0 | 592 | // identical array has been inserted more than once into different/incorrect |
aoqi@0 | 593 | // buckets the verification step above will catch that. |
aoqi@0 | 594 | G1StringDedupEntry** entry1 = _table->bucket(bucket); |
aoqi@0 | 595 | while (*entry1 != NULL) { |
aoqi@0 | 596 | typeArrayOop value1 = (*entry1)->obj(); |
aoqi@0 | 597 | G1StringDedupEntry** entry2 = (*entry1)->next_addr(); |
aoqi@0 | 598 | while (*entry2 != NULL) { |
aoqi@0 | 599 | typeArrayOop value2 = (*entry2)->obj(); |
vkempik@10008 | 600 | guarantee(value1 != value2, "Table entries must not have the same array"); |
vkempik@10008 | 601 | if (use_java_hash()) { |
vkempik@10008 | 602 | guarantee(!equals(value1, value2), "Table entries must not have identical arrays"); |
vkempik@10008 | 603 | } |
aoqi@0 | 604 | entry2 = (*entry2)->next_addr(); |
aoqi@0 | 605 | } |
aoqi@0 | 606 | entry1 = (*entry1)->next_addr(); |
aoqi@0 | 607 | } |
aoqi@0 | 608 | } |
aoqi@0 | 609 | } |
aoqi@0 | 610 | |
vkempik@8452 | 611 | void G1StringDedupTable::clean_entry_cache() { |
vkempik@8452 | 612 | _entry_cache->delete_overflowed(); |
aoqi@0 | 613 | } |
aoqi@0 | 614 | |
aoqi@0 | 615 | void G1StringDedupTable::print_statistics(outputStream* st) { |
aoqi@0 | 616 | st->print_cr( |
aoqi@0 | 617 | " [Table]\n" |
kevinw@9327 | 618 | " [Memory Usage: " G1_STRDEDUP_BYTES_FORMAT_NS "]\n" |
kevinw@9327 | 619 | " [Size: " SIZE_FORMAT ", Min: " SIZE_FORMAT ", Max: " SIZE_FORMAT "]\n" |
kevinw@9327 | 620 | " [Entries: " UINTX_FORMAT ", Load: " G1_STRDEDUP_PERCENT_FORMAT_NS ", Cached: " UINTX_FORMAT ", Added: " UINTX_FORMAT ", Removed: " UINTX_FORMAT "]\n" |
kevinw@9327 | 621 | " [Resize Count: " UINTX_FORMAT ", Shrink Threshold: " UINTX_FORMAT "(" G1_STRDEDUP_PERCENT_FORMAT_NS "), Grow Threshold: " UINTX_FORMAT "(" G1_STRDEDUP_PERCENT_FORMAT_NS ")]\n" |
vkempik@10008 | 622 | " [Rehash Count: " UINTX_FORMAT ", Rehash Threshold: " UINTX_FORMAT ", Hash Seed: " UINT64_FORMAT_X "]\n" |
kevinw@9327 | 623 | " [Age Threshold: " UINTX_FORMAT "]", |
aoqi@0 | 624 | G1_STRDEDUP_BYTES_PARAM(_table->_size * sizeof(G1StringDedupEntry*) + (_table->_entries + _entry_cache->size()) * sizeof(G1StringDedupEntry)), |
aoqi@0 | 625 | _table->_size, _min_size, _max_size, |
aoqi@0 | 626 | _table->_entries, (double)_table->_entries / (double)_table->_size * 100.0, _entry_cache->size(), _entries_added, _entries_removed, |
aoqi@0 | 627 | _resize_count, _table->_shrink_threshold, _shrink_load_factor * 100.0, _table->_grow_threshold, _grow_load_factor * 100.0, |
aoqi@0 | 628 | _rehash_count, _rehash_threshold, _table->_hash_seed, |
aoqi@0 | 629 | StringDeduplicationAgeThreshold); |
aoqi@0 | 630 | } |