< prev index next >
src/hotspot/share/gc/shared/stringdedup/stringDedupTable.cpp
Print this page
*** 23,76 ****
*/
#include "precompiled.hpp"
#include "classfile/altHashing.hpp"
#include "classfile/javaClasses.inline.hpp"
! #include "gc/g1/g1BarrierSet.hpp"
! #include "gc/g1/g1CollectedHeap.inline.hpp"
! #include "gc/g1/g1StringDedup.hpp"
! #include "gc/g1/g1StringDedupTable.hpp"
#include "logging/log.hpp"
#include "memory/padded.inline.hpp"
#include "oops/arrayOop.inline.hpp"
#include "oops/oop.inline.hpp"
#include "oops/typeArrayOop.hpp"
#include "runtime/mutexLocker.hpp"
#include "runtime/safepointVerifiers.hpp"
//
// List of deduplication table entries. Links table
// entries together using their _next fields.
//
! class G1StringDedupEntryList : public CHeapObj<mtGC> {
private:
! G1StringDedupEntry* _list;
size_t _length;
public:
! G1StringDedupEntryList() :
_list(NULL),
_length(0) {
}
! void add(G1StringDedupEntry* entry) {
entry->set_next(_list);
_list = entry;
_length++;
}
! G1StringDedupEntry* remove() {
! G1StringDedupEntry* entry = _list;
if (entry != NULL) {
_list = entry->next();
_length--;
}
return entry;
}
! G1StringDedupEntry* remove_all() {
! G1StringDedupEntry* list = _list;
_list = NULL;
return list;
}
size_t length() {
--- 23,76 ----
*/
#include "precompiled.hpp"
#include "classfile/altHashing.hpp"
#include "classfile/javaClasses.inline.hpp"
! #include "gc/shared/stringdedup/stringDedup.hpp"
! #include "gc/shared/stringdedup/stringDedupTable.hpp"
! #include "gc/shared/suspendibleThreadSet.hpp"
#include "logging/log.hpp"
#include "memory/padded.inline.hpp"
+ #include "oops/access.inline.hpp"
#include "oops/arrayOop.inline.hpp"
#include "oops/oop.inline.hpp"
#include "oops/typeArrayOop.hpp"
#include "runtime/mutexLocker.hpp"
#include "runtime/safepointVerifiers.hpp"
//
// List of deduplication table entries. Links table
// entries together using their _next fields.
//
! class StringDedupEntryList : public CHeapObj<mtGC> {
private:
! StringDedupEntry* _list;
size_t _length;
public:
! StringDedupEntryList() :
_list(NULL),
_length(0) {
}
! void add(StringDedupEntry* entry) {
entry->set_next(_list);
_list = entry;
_length++;
}
! StringDedupEntry* remove() {
! StringDedupEntry* entry = _list;
if (entry != NULL) {
_list = entry->next();
_length--;
}
return entry;
}
! StringDedupEntry* remove_all() {
! StringDedupEntry* list = _list;
_list = NULL;
return list;
}
size_t length() {
*** 90,156 ****
//
// The cache allows for single-threaded allocations and multi-threaded frees.
// Allocations are synchronized by StringDedupTable_lock as part of a table
// modification.
//
! class G1StringDedupEntryCache : public CHeapObj<mtGC> {
private:
// One cache/overflow list per GC worker to allow lock less freeing of
// entries while doing a parallel scan of the table. Using PaddedEnd to
// avoid false sharing.
size_t _nlists;
size_t _max_list_length;
! PaddedEnd<G1StringDedupEntryList>* _cached;
! PaddedEnd<G1StringDedupEntryList>* _overflowed;
public:
! G1StringDedupEntryCache(size_t max_size);
! ~G1StringDedupEntryCache();
// Set max number of table entries to cache.
void set_max_size(size_t max_size);
// Get a table entry from the cache, or allocate a new entry if the cache is empty.
! G1StringDedupEntry* alloc();
// Insert a table entry into the cache.
! void free(G1StringDedupEntry* entry, uint worker_id);
// Returns current number of entries in the cache.
size_t size();
// Deletes overflowed entries.
void delete_overflowed();
};
! G1StringDedupEntryCache::G1StringDedupEntryCache(size_t max_size) :
_nlists(ParallelGCThreads),
_max_list_length(0),
! _cached(PaddedArray<G1StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)),
! _overflowed(PaddedArray<G1StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)) {
set_max_size(max_size);
}
! G1StringDedupEntryCache::~G1StringDedupEntryCache() {
ShouldNotReachHere();
}
! void G1StringDedupEntryCache::set_max_size(size_t size) {
_max_list_length = size / _nlists;
}
! G1StringDedupEntry* G1StringDedupEntryCache::alloc() {
for (size_t i = 0; i < _nlists; i++) {
! G1StringDedupEntry* entry = _cached[i].remove();
if (entry != NULL) {
return entry;
}
}
! return new G1StringDedupEntry();
}
! void G1StringDedupEntryCache::free(G1StringDedupEntry* entry, uint worker_id) {
assert(entry->obj() != NULL, "Double free");
assert(worker_id < _nlists, "Invalid worker id");
entry->set_obj(NULL);
entry->set_hash(0);
--- 90,156 ----
//
// The cache allows for single-threaded allocations and multi-threaded frees.
// Allocations are synchronized by StringDedupTable_lock as part of a table
// modification.
//
! class StringDedupEntryCache : public CHeapObj<mtGC> {
private:
// One cache/overflow list per GC worker to allow lock less freeing of
// entries while doing a parallel scan of the table. Using PaddedEnd to
// avoid false sharing.
size_t _nlists;
size_t _max_list_length;
! PaddedEnd<StringDedupEntryList>* _cached;
! PaddedEnd<StringDedupEntryList>* _overflowed;
public:
! StringDedupEntryCache(size_t max_size);
! ~StringDedupEntryCache();
// Set max number of table entries to cache.
void set_max_size(size_t max_size);
// Get a table entry from the cache, or allocate a new entry if the cache is empty.
! StringDedupEntry* alloc();
// Insert a table entry into the cache.
! void free(StringDedupEntry* entry, uint worker_id);
// Returns current number of entries in the cache.
size_t size();
// Deletes overflowed entries.
void delete_overflowed();
};
! StringDedupEntryCache::StringDedupEntryCache(size_t max_size) :
_nlists(ParallelGCThreads),
_max_list_length(0),
! _cached(PaddedArray<StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)),
! _overflowed(PaddedArray<StringDedupEntryList, mtGC>::create_unfreeable((uint)_nlists)) {
set_max_size(max_size);
}
! StringDedupEntryCache::~StringDedupEntryCache() {
ShouldNotReachHere();
}
! void StringDedupEntryCache::set_max_size(size_t size) {
_max_list_length = size / _nlists;
}
! StringDedupEntry* StringDedupEntryCache::alloc() {
for (size_t i = 0; i < _nlists; i++) {
! StringDedupEntry* entry = _cached[i].remove();
if (entry != NULL) {
return entry;
}
}
! return new StringDedupEntry();
}
! void StringDedupEntryCache::free(StringDedupEntry* entry, uint worker_id) {
assert(entry->obj() != NULL, "Double free");
assert(worker_id < _nlists, "Invalid worker id");
entry->set_obj(NULL);
entry->set_hash(0);
*** 162,185 ****
// Cache is full, add to overflow list for later deletion
_overflowed[worker_id].add(entry);
}
}
! size_t G1StringDedupEntryCache::size() {
size_t size = 0;
for (size_t i = 0; i < _nlists; i++) {
size += _cached[i].length();
}
return size;
}
! void G1StringDedupEntryCache::delete_overflowed() {
double start = os::elapsedTime();
uintx count = 0;
for (size_t i = 0; i < _nlists; i++) {
! G1StringDedupEntry* entry;
{
// The overflow list can be modified during safepoints, therefore
// we temporarily join the suspendible thread set while removing
// all entries from the list.
--- 162,185 ----
// Cache is full, add to overflow list for later deletion
_overflowed[worker_id].add(entry);
}
}
! size_t StringDedupEntryCache::size() {
size_t size = 0;
for (size_t i = 0; i < _nlists; i++) {
size += _cached[i].length();
}
return size;
}
! void StringDedupEntryCache::delete_overflowed() {
double start = os::elapsedTime();
uintx count = 0;
for (size_t i = 0; i < _nlists; i++) {
! StringDedupEntry* entry;
{
// The overflow list can be modified during safepoints, therefore
// we temporarily join the suspendible thread set while removing
// all entries from the list.
*** 187,300 ****
entry = _overflowed[i].remove_all();
}
// Delete all entries
while (entry != NULL) {
! G1StringDedupEntry* next = entry->next();
delete entry;
entry = next;
count++;
}
}
double end = os::elapsedTime();
! log_trace(gc, stringdedup)("Deleted " UINTX_FORMAT " entries, " G1_STRDEDUP_TIME_FORMAT_MS,
! count, G1_STRDEDUP_TIME_PARAM_MS(end - start));
}
! G1StringDedupTable* G1StringDedupTable::_table = NULL;
! G1StringDedupEntryCache* G1StringDedupTable::_entry_cache = NULL;
! const size_t G1StringDedupTable::_min_size = (1 << 10); // 1024
! const size_t G1StringDedupTable::_max_size = (1 << 24); // 16777216
! const double G1StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
! const double G1StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
! const double G1StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
! const uintx G1StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
! const uintx G1StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
!
! uintx G1StringDedupTable::_entries_added = 0;
! uintx G1StringDedupTable::_entries_removed = 0;
! uintx G1StringDedupTable::_resize_count = 0;
! uintx G1StringDedupTable::_rehash_count = 0;
! G1StringDedupTable::G1StringDedupTable(size_t size, jint hash_seed) :
_size(size),
_entries(0),
_grow_threshold((uintx)(size * _grow_load_factor)),
_shrink_threshold((uintx)(size * _shrink_load_factor)),
_rehash_needed(false),
_hash_seed(hash_seed) {
assert(is_power_of_2(size), "Table size must be a power of 2");
! _buckets = NEW_C_HEAP_ARRAY(G1StringDedupEntry*, _size, mtGC);
! memset(_buckets, 0, _size * sizeof(G1StringDedupEntry*));
}
! G1StringDedupTable::~G1StringDedupTable() {
FREE_C_HEAP_ARRAY(G1StringDedupEntry*, _buckets);
}
! void G1StringDedupTable::create() {
assert(_table == NULL, "One string deduplication table allowed");
! _entry_cache = new G1StringDedupEntryCache(_min_size * _max_cache_factor);
! _table = new G1StringDedupTable(_min_size);
}
! void G1StringDedupTable::add(typeArrayOop value, bool latin1, unsigned int hash, G1StringDedupEntry** list) {
! G1StringDedupEntry* entry = _entry_cache->alloc();
entry->set_obj(value);
entry->set_hash(hash);
entry->set_latin1(latin1);
entry->set_next(*list);
*list = entry;
_entries++;
}
! void G1StringDedupTable::remove(G1StringDedupEntry** pentry, uint worker_id) {
! G1StringDedupEntry* entry = *pentry;
*pentry = entry->next();
_entry_cache->free(entry, worker_id);
}
! void G1StringDedupTable::transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest) {
! G1StringDedupEntry* entry = *pentry;
*pentry = entry->next();
unsigned int hash = entry->hash();
size_t index = dest->hash_to_index(hash);
! G1StringDedupEntry** list = dest->bucket(index);
entry->set_next(*list);
*list = entry;
}
! bool G1StringDedupTable::equals(typeArrayOop value1, typeArrayOop value2) {
! return (value1 == value2 ||
(value1->length() == value2->length() &&
(!memcmp(value1->base(T_BYTE),
value2->base(T_BYTE),
value1->length() * sizeof(jbyte)))));
}
! typeArrayOop G1StringDedupTable::lookup(typeArrayOop value, bool latin1, unsigned int hash,
! G1StringDedupEntry** list, uintx &count) {
! for (G1StringDedupEntry* entry = *list; entry != NULL; entry = entry->next()) {
if (entry->hash() == hash && entry->latin1() == latin1) {
typeArrayOop existing_value = entry->obj();
if (equals(value, existing_value)) {
! // Match found
! return existing_value;
}
}
count++;
}
// Not found
return NULL;
}
! typeArrayOop G1StringDedupTable::lookup_or_add_inner(typeArrayOop value, bool latin1, unsigned int hash) {
size_t index = hash_to_index(hash);
! G1StringDedupEntry** list = bucket(index);
uintx count = 0;
// Lookup in list
typeArrayOop existing_value = lookup(value, latin1, hash, list, count);
--- 187,307 ----
entry = _overflowed[i].remove_all();
}
// Delete all entries
while (entry != NULL) {
! StringDedupEntry* next = entry->next();
delete entry;
entry = next;
count++;
}
}
double end = os::elapsedTime();
! log_trace(gc, stringdedup)("Deleted " UINTX_FORMAT " entries, " STRDEDUP_TIME_FORMAT_MS,
! count, STRDEDUP_TIME_PARAM_MS(end - start));
}
! StringDedupTable* StringDedupTable::_table = NULL;
! StringDedupEntryCache* StringDedupTable::_entry_cache = NULL;
! const size_t StringDedupTable::_min_size = (1 << 10); // 1024
! const size_t StringDedupTable::_max_size = (1 << 24); // 16777216
! const double StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
! const double StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
! const double StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
! const uintx StringDedupTable::_rehash_multiple = 60; // Hash bucket has 60 times more collisions than expected
! const uintx StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
!
! uintx StringDedupTable::_entries_added = 0;
! uintx StringDedupTable::_entries_removed = 0;
! uintx StringDedupTable::_resize_count = 0;
! uintx StringDedupTable::_rehash_count = 0;
!
! StringDedupTable* StringDedupTable::_resized_table = NULL;
! StringDedupTable* StringDedupTable::_rehashed_table = NULL;
! volatile size_t StringDedupTable::_claimed_index = 0;
! StringDedupTable::StringDedupTable(size_t size, jint hash_seed) :
_size(size),
_entries(0),
_grow_threshold((uintx)(size * _grow_load_factor)),
_shrink_threshold((uintx)(size * _shrink_load_factor)),
_rehash_needed(false),
_hash_seed(hash_seed) {
assert(is_power_of_2(size), "Table size must be a power of 2");
! _buckets = NEW_C_HEAP_ARRAY(StringDedupEntry*, _size, mtGC);
! memset(_buckets, 0, _size * sizeof(StringDedupEntry*));
}
! StringDedupTable::~StringDedupTable() {
FREE_C_HEAP_ARRAY(G1StringDedupEntry*, _buckets);
}
! void StringDedupTable::create() {
assert(_table == NULL, "One string deduplication table allowed");
! _entry_cache = new StringDedupEntryCache(_min_size * _max_cache_factor);
! _table = new StringDedupTable(_min_size);
}
! void StringDedupTable::add(typeArrayOop value, bool latin1, unsigned int hash, StringDedupEntry** list) {
! StringDedupEntry* entry = _entry_cache->alloc();
entry->set_obj(value);
entry->set_hash(hash);
entry->set_latin1(latin1);
entry->set_next(*list);
*list = entry;
_entries++;
}
! void StringDedupTable::remove(StringDedupEntry** pentry, uint worker_id) {
! StringDedupEntry* entry = *pentry;
*pentry = entry->next();
_entry_cache->free(entry, worker_id);
}
! void StringDedupTable::transfer(StringDedupEntry** pentry, StringDedupTable* dest) {
! StringDedupEntry* entry = *pentry;
*pentry = entry->next();
unsigned int hash = entry->hash();
size_t index = dest->hash_to_index(hash);
! StringDedupEntry** list = dest->bucket(index);
entry->set_next(*list);
*list = entry;
}
! bool StringDedupTable::equals(typeArrayOop value1, typeArrayOop value2) {
! return (oopDesc::equals(value1, value2) ||
(value1->length() == value2->length() &&
(!memcmp(value1->base(T_BYTE),
value2->base(T_BYTE),
value1->length() * sizeof(jbyte)))));
}
! typeArrayOop StringDedupTable::lookup(typeArrayOop value, bool latin1, unsigned int hash,
! StringDedupEntry** list, uintx &count) {
! for (StringDedupEntry* entry = *list; entry != NULL; entry = entry->next()) {
if (entry->hash() == hash && entry->latin1() == latin1) {
typeArrayOop existing_value = entry->obj();
if (equals(value, existing_value)) {
! // Apply proper barrier to make sure it is kept alive. Concurrent mark might
! // otherwise declare it dead if there are no other strong references to this object.
! oop* obj_addr = (oop*)entry->obj_addr();
! oop obj = RootAccess<IN_CONCURRENT_ROOT>::oop_load(obj_addr);
! return typeArrayOop(obj);
}
}
count++;
}
// Not found
return NULL;
}
! typeArrayOop StringDedupTable::lookup_or_add_inner(typeArrayOop value, bool latin1, unsigned int hash) {
size_t index = hash_to_index(hash);
! StringDedupEntry** list = bucket(index);
uintx count = 0;
// Lookup in list
typeArrayOop existing_value = lookup(value, latin1, hash, list, count);
*** 312,322 ****
}
return existing_value;
}
! unsigned int G1StringDedupTable::hash_code(typeArrayOop value, bool latin1) {
unsigned int hash;
int length = value->length();
if (latin1) {
const jbyte* data = (jbyte*)value->base(T_BYTE);
if (use_java_hash()) {
--- 319,329 ----
}
return existing_value;
}
! unsigned int StringDedupTable::hash_code(typeArrayOop value, bool latin1) {
unsigned int hash;
int length = value->length();
if (latin1) {
const jbyte* data = (jbyte*)value->base(T_BYTE);
if (use_java_hash()) {
*** 335,354 ****
}
return hash;
}
! void G1StringDedupTable::deduplicate(oop java_string, G1StringDedupStat& stat) {
assert(java_lang_String::is_instance(java_string), "Must be a string");
NoSafepointVerifier nsv;
! stat.inc_inspected();
typeArrayOop value = java_lang_String::value(java_string);
if (value == NULL) {
// String has no value
! stat.inc_skipped();
return;
}
bool latin1 = java_lang_String::is_latin1(java_string);
unsigned int hash = 0;
--- 342,361 ----
}
return hash;
}
! void StringDedupTable::deduplicate(oop java_string, StringDedupStat* stat) {
assert(java_lang_String::is_instance(java_string), "Must be a string");
NoSafepointVerifier nsv;
! stat->inc_inspected();
typeArrayOop value = java_lang_String::value(java_string);
if (value == NULL) {
// String has no value
! stat->inc_skipped();
return;
}
bool latin1 = java_lang_String::is_latin1(java_string);
unsigned int hash = 0;
*** 359,404 ****
}
if (hash == 0) {
// Compute hash
hash = hash_code(value, latin1);
! stat.inc_hashed();
if (use_java_hash() && hash != 0) {
// Store hash code in cache
java_lang_String::set_hash(java_string, hash);
}
}
typeArrayOop existing_value = lookup_or_add(value, latin1, hash);
if (existing_value == value) {
// Same value, already known
! stat.inc_known();
return;
}
// Get size of value array
uintx size_in_bytes = value->size() * HeapWordSize;
! stat.inc_new(size_in_bytes);
if (existing_value != NULL) {
- // Enqueue the reference to make sure it is kept alive. Concurrent mark might
- // otherwise declare it dead if there are no other strong references to this object.
- G1BarrierSet::enqueue(existing_value);
-
// Existing value found, deduplicate string
java_lang_String::set_value(java_string, existing_value);
!
! if (G1CollectedHeap::heap()->is_in_young(value)) {
! stat.inc_deduped_young(size_in_bytes);
! } else {
! stat.inc_deduped_old(size_in_bytes);
! }
}
}
! G1StringDedupTable* G1StringDedupTable::prepare_resize() {
size_t size = _table->_size;
// Check if the hashtable needs to be resized
if (_table->_entries > _table->_grow_threshold) {
// Grow table, double the size
--- 366,410 ----
}
if (hash == 0) {
// Compute hash
hash = hash_code(value, latin1);
! stat->inc_hashed();
if (use_java_hash() && hash != 0) {
// Store hash code in cache
java_lang_String::set_hash(java_string, hash);
}
}
typeArrayOop existing_value = lookup_or_add(value, latin1, hash);
if (existing_value == value) {
// Same value, already known
! stat->inc_known();
return;
}
// Get size of value array
uintx size_in_bytes = value->size() * HeapWordSize;
! stat->inc_new(size_in_bytes);
if (existing_value != NULL) {
// Existing value found, deduplicate string
java_lang_String::set_value(java_string, existing_value);
! stat->deduped(value, size_in_bytes);
}
}
! bool StringDedupTable::is_resizing() {
! return _resized_table != NULL;
! }
!
! bool StringDedupTable::is_rehashing() {
! return _rehashed_table != NULL;
! }
!
! StringDedupTable* StringDedupTable::prepare_resize() {
size_t size = _table->_size;
// Check if the hashtable needs to be resized
if (_table->_entries > _table->_grow_threshold) {
// Grow table, double the size
*** 432,445 ****
// Update max cache size
_entry_cache->set_max_size(size * _max_cache_factor);
// Allocate the new table. The new table will be populated by workers
// calling unlink_or_oops_do() and finally installed by finish_resize().
! return new G1StringDedupTable(size, _table->_hash_seed);
}
! void G1StringDedupTable::finish_resize(G1StringDedupTable* resized_table) {
assert(resized_table != NULL, "Invalid table");
resized_table->_entries = _table->_entries;
// Free old table
--- 438,451 ----
// Update max cache size
_entry_cache->set_max_size(size * _max_cache_factor);
// Allocate the new table. The new table will be populated by workers
// calling unlink_or_oops_do() and finally installed by finish_resize().
! return new StringDedupTable(size, _table->_hash_seed);
}
! void StringDedupTable::finish_resize(StringDedupTable* resized_table) {
assert(resized_table != NULL, "Invalid table");
resized_table->_entries = _table->_entries;
// Free old table
*** 447,457 ****
// Install new table
_table = resized_table;
}
! void G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id) {
// The table is divided into partitions to allow lock-less parallel processing by
// multiple worker threads. A worker thread first claims a partition, which ensures
// exclusive access to that part of the table, then continues to process it. To allow
// shrinking of the table in parallel we also need to make sure that the same worker
// thread processes all partitions where entries will hash to the same destination
--- 453,463 ----
// Install new table
_table = resized_table;
}
! void StringDedupTable::unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id) {
// The table is divided into partitions to allow lock-less parallel processing by
// multiple worker threads. A worker thread first claims a partition, which ensures
// exclusive access to that part of the table, then continues to process it. To allow
// shrinking of the table in parallel we also need to make sure that the same worker
// thread processes all partitions where entries will hash to the same destination
*** 462,480 ****
// For example, if the table is divided into 8 partitions, the sibling of partition 0
// is partition 4, the sibling of partition 1 is partition 5, etc.
size_t table_half = _table->_size / 2;
// Let each partition be one page worth of buckets
! size_t partition_size = MIN2(table_half, os::vm_page_size() / sizeof(G1StringDedupEntry*));
assert(table_half % partition_size == 0, "Invalid partition size");
// Number of entries removed during the scan
uintx removed = 0;
for (;;) {
// Grab next partition to scan
! size_t partition_begin = cl->claim_table_partition(partition_size);
size_t partition_end = partition_begin + partition_size;
if (partition_begin >= table_half) {
// End of table
break;
}
--- 468,486 ----
// For example, if the table is divided into 8 partitions, the sibling of partition 0
// is partition 4, the sibling of partition 1 is partition 5, etc.
size_t table_half = _table->_size / 2;
// Let each partition be one page worth of buckets
! size_t partition_size = MIN2(table_half, os::vm_page_size() / sizeof(StringDedupEntry*));
assert(table_half % partition_size == 0, "Invalid partition size");
// Number of entries removed during the scan
uintx removed = 0;
for (;;) {
// Grab next partition to scan
! size_t partition_begin = claim_table_partition(partition_size);
size_t partition_end = partition_begin + partition_size;
if (partition_begin >= table_half) {
// End of table
break;
}
*** 490,515 ****
_table->_entries -= removed;
_entries_removed += removed;
}
}
! uintx G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,
size_t partition_begin,
size_t partition_end,
uint worker_id) {
uintx removed = 0;
for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
! G1StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
oop* p = (oop*)(*entry)->obj_addr();
if (cl->is_alive(*p)) {
cl->keep_alive(p);
! if (cl->is_resizing()) {
// We are resizing the table, transfer entry to the new table
! _table->transfer(entry, cl->resized_table());
} else {
! if (cl->is_rehashing()) {
// We are rehashing the table, rehash the entry but keep it
// in the table. We can't transfer entries into the new table
// at this point since we don't have exclusive access to all
// destination partitions. finish_rehash() will do a single
// threaded transfer of all entries.
--- 496,521 ----
_table->_entries -= removed;
_entries_removed += removed;
}
}
! uintx StringDedupTable::unlink_or_oops_do(StringDedupUnlinkOrOopsDoClosure* cl,
size_t partition_begin,
size_t partition_end,
uint worker_id) {
uintx removed = 0;
for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
! StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
oop* p = (oop*)(*entry)->obj_addr();
if (cl->is_alive(*p)) {
cl->keep_alive(p);
! if (is_resizing()) {
// We are resizing the table, transfer entry to the new table
! _table->transfer(entry, _resized_table);
} else {
! if (is_rehashing()) {
// We are rehashing the table, rehash the entry but keep it
// in the table. We can't transfer entries into the new table
// at this point since we don't have exclusive access to all
// destination partitions. finish_rehash() will do a single
// threaded transfer of all entries.
*** 531,541 ****
}
return removed;
}
! G1StringDedupTable* G1StringDedupTable::prepare_rehash() {
if (!_table->_rehash_needed && !StringDeduplicationRehashALot) {
// Rehash not needed
return NULL;
}
--- 537,574 ----
}
return removed;
}
! void StringDedupTable::gc_prologue(bool resize_and_rehash_table) {
! assert(!is_resizing() && !is_rehashing(), "Already in progress?");
!
! _claimed_index = 0;
! if (resize_and_rehash_table) {
! // If both resize and rehash is needed, only do resize. Rehash of
! // the table will eventually happen if the situation persists.
! _resized_table = StringDedupTable::prepare_resize();
! if (!is_resizing()) {
! _rehashed_table = StringDedupTable::prepare_rehash();
! }
! }
! }
!
! void StringDedupTable::gc_epilogue() {
! assert(!is_resizing() || !is_rehashing(), "Can not both resize and rehash");
! assert(_claimed_index >= _table->_size / 2 || _claimed_index == 0, "All or nothing");
!
! if (is_resizing()) {
! StringDedupTable::finish_resize(_resized_table);
! _resized_table = NULL;
! } else if (is_rehashing()) {
! StringDedupTable::finish_rehash(_rehashed_table);
! _rehashed_table = NULL;
! }
! }
!
! StringDedupTable* StringDedupTable::prepare_rehash() {
if (!_table->_rehash_needed && !StringDeduplicationRehashALot) {
// Rehash not needed
return NULL;
}
*** 544,562 ****
// Compute new hash seed
_table->_hash_seed = AltHashing::compute_seed();
// Allocate the new table, same size and hash seed
! return new G1StringDedupTable(_table->_size, _table->_hash_seed);
}
! void G1StringDedupTable::finish_rehash(G1StringDedupTable* rehashed_table) {
assert(rehashed_table != NULL, "Invalid table");
// Move all newly rehashed entries into the correct buckets in the new table
for (size_t bucket = 0; bucket < _table->_size; bucket++) {
! G1StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
_table->transfer(entry, rehashed_table);
}
}
--- 577,595 ----
// Compute new hash seed
_table->_hash_seed = AltHashing::compute_seed();
// Allocate the new table, same size and hash seed
! return new StringDedupTable(_table->_size, _table->_hash_seed);
}
! void StringDedupTable::finish_rehash(StringDedupTable* rehashed_table) {
assert(rehashed_table != NULL, "Invalid table");
// Move all newly rehashed entries into the correct buckets in the new table
for (size_t bucket = 0; bucket < _table->_size; bucket++) {
! StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
_table->transfer(entry, rehashed_table);
}
}
*** 567,584 ****
// Install new table
_table = rehashed_table;
}
! void G1StringDedupTable::verify() {
for (size_t bucket = 0; bucket < _table->_size; bucket++) {
// Verify entries
! G1StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
typeArrayOop value = (*entry)->obj();
guarantee(value != NULL, "Object must not be NULL");
! guarantee(G1CollectedHeap::heap()->is_in_reserved(value), "Object must be on the heap");
guarantee(!value->is_forwarded(), "Object must not be forwarded");
guarantee(value->is_typeArray(), "Object must be a typeArrayOop");
bool latin1 = (*entry)->latin1();
unsigned int hash = hash_code(value, latin1);
guarantee((*entry)->hash() == hash, "Table entry has inorrect hash");
--- 600,621 ----
// Install new table
_table = rehashed_table;
}
! size_t StringDedupTable::claim_table_partition(size_t partition_size) {
! return Atomic::add(partition_size, &_claimed_index) - partition_size;
! }
!
! void StringDedupTable::verify() {
for (size_t bucket = 0; bucket < _table->_size; bucket++) {
// Verify entries
! StringDedupEntry** entry = _table->bucket(bucket);
while (*entry != NULL) {
typeArrayOop value = (*entry)->obj();
guarantee(value != NULL, "Object must not be NULL");
! guarantee(Universe::heap()->is_in_reserved(value), "Object must be on the heap");
guarantee(!value->is_forwarded(), "Object must not be forwarded");
guarantee(value->is_typeArray(), "Object must be a typeArrayOop");
bool latin1 = (*entry)->latin1();
unsigned int hash = hash_code(value, latin1);
guarantee((*entry)->hash() == hash, "Table entry has inorrect hash");
*** 588,602 ****
// Verify that we do not have entries with identical oops or identical arrays.
// We only need to compare entries in the same bucket. If the same oop or an
// identical array has been inserted more than once into different/incorrect
// buckets the verification step above will catch that.
! G1StringDedupEntry** entry1 = _table->bucket(bucket);
while (*entry1 != NULL) {
typeArrayOop value1 = (*entry1)->obj();
bool latin1_1 = (*entry1)->latin1();
! G1StringDedupEntry** entry2 = (*entry1)->next_addr();
while (*entry2 != NULL) {
typeArrayOop value2 = (*entry2)->obj();
bool latin1_2 = (*entry2)->latin1();
guarantee(latin1_1 != latin1_2 || !equals(value1, value2), "Table entries must not have identical arrays");
entry2 = (*entry2)->next_addr();
--- 625,639 ----
// Verify that we do not have entries with identical oops or identical arrays.
// We only need to compare entries in the same bucket. If the same oop or an
// identical array has been inserted more than once into different/incorrect
// buckets the verification step above will catch that.
! StringDedupEntry** entry1 = _table->bucket(bucket);
while (*entry1 != NULL) {
typeArrayOop value1 = (*entry1)->obj();
bool latin1_1 = (*entry1)->latin1();
! StringDedupEntry** entry2 = (*entry1)->next_addr();
while (*entry2 != NULL) {
typeArrayOop value2 = (*entry2)->obj();
bool latin1_2 = (*entry2)->latin1();
guarantee(latin1_1 != latin1_2 || !equals(value1, value2), "Table entries must not have identical arrays");
entry2 = (*entry2)->next_addr();
*** 604,625 ****
entry1 = (*entry1)->next_addr();
}
}
}
! void G1StringDedupTable::clean_entry_cache() {
_entry_cache->delete_overflowed();
}
! void G1StringDedupTable::print_statistics() {
Log(gc, stringdedup) log;
log.debug(" Table");
! log.debug(" Memory Usage: " G1_STRDEDUP_BYTES_FORMAT_NS,
! G1_STRDEDUP_BYTES_PARAM(_table->_size * sizeof(G1StringDedupEntry*) + (_table->_entries + _entry_cache->size()) * sizeof(G1StringDedupEntry)));
log.debug(" Size: " SIZE_FORMAT ", Min: " SIZE_FORMAT ", Max: " SIZE_FORMAT, _table->_size, _min_size, _max_size);
! log.debug(" Entries: " UINTX_FORMAT ", Load: " G1_STRDEDUP_PERCENT_FORMAT_NS ", Cached: " UINTX_FORMAT ", Added: " UINTX_FORMAT ", Removed: " UINTX_FORMAT,
_table->_entries, percent_of(_table->_entries, _table->_size), _entry_cache->size(), _entries_added, _entries_removed);
! log.debug(" Resize Count: " UINTX_FORMAT ", Shrink Threshold: " UINTX_FORMAT "(" G1_STRDEDUP_PERCENT_FORMAT_NS "), Grow Threshold: " UINTX_FORMAT "(" G1_STRDEDUP_PERCENT_FORMAT_NS ")",
_resize_count, _table->_shrink_threshold, _shrink_load_factor * 100.0, _table->_grow_threshold, _grow_load_factor * 100.0);
log.debug(" Rehash Count: " UINTX_FORMAT ", Rehash Threshold: " UINTX_FORMAT ", Hash Seed: 0x%x", _rehash_count, _rehash_threshold, _table->_hash_seed);
log.debug(" Age Threshold: " UINTX_FORMAT, StringDeduplicationAgeThreshold);
}
--- 641,662 ----
entry1 = (*entry1)->next_addr();
}
}
}
! void StringDedupTable::clean_entry_cache() {
_entry_cache->delete_overflowed();
}
! void StringDedupTable::print_statistics() {
Log(gc, stringdedup) log;
log.debug(" Table");
! log.debug(" Memory Usage: " STRDEDUP_BYTES_FORMAT_NS,
! STRDEDUP_BYTES_PARAM(_table->_size * sizeof(StringDedupEntry*) + (_table->_entries + _entry_cache->size()) * sizeof(StringDedupEntry)));
log.debug(" Size: " SIZE_FORMAT ", Min: " SIZE_FORMAT ", Max: " SIZE_FORMAT, _table->_size, _min_size, _max_size);
! log.debug(" Entries: " UINTX_FORMAT ", Load: " STRDEDUP_PERCENT_FORMAT_NS ", Cached: " UINTX_FORMAT ", Added: " UINTX_FORMAT ", Removed: " UINTX_FORMAT,
_table->_entries, percent_of(_table->_entries, _table->_size), _entry_cache->size(), _entries_added, _entries_removed);
! log.debug(" Resize Count: " UINTX_FORMAT ", Shrink Threshold: " UINTX_FORMAT "(" STRDEDUP_PERCENT_FORMAT_NS "), Grow Threshold: " UINTX_FORMAT "(" STRDEDUP_PERCENT_FORMAT_NS ")",
_resize_count, _table->_shrink_threshold, _shrink_load_factor * 100.0, _table->_grow_threshold, _grow_load_factor * 100.0);
log.debug(" Rehash Count: " UINTX_FORMAT ", Rehash Threshold: " UINTX_FORMAT ", Hash Seed: 0x%x", _rehash_count, _rehash_threshold, _table->_hash_seed);
log.debug(" Age Threshold: " UINTX_FORMAT, StringDeduplicationAgeThreshold);
}
< prev index next >