Mercurial > hg > truffle
diff src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 1261:0414c1049f15
6923991: G1: improve scalability of RSet scanning
Summary: Implemented block-based work stealing. Moved copying during the rset scanning phase to the main copying phase. Made the size of rset table depend on the region size.
Reviewed-by: apetrusenko, tonyp
author | iveresov |
---|---|
date | Thu, 11 Feb 2010 15:52:19 -0800 |
parents | fa2f65ebeb08 |
children | c18cbe5936b8 |
line wrap: on
line diff
--- a/src/share/vm/gc_implementation/g1/sparsePRT.cpp Tue Feb 09 13:56:09 2010 -0800 +++ b/src/share/vm/gc_implementation/g1/sparsePRT.cpp Thu Feb 11 15:52:19 2010 -0800 @@ -27,7 +27,7 @@ #define SPARSE_PRT_VERBOSE 0 -#define UNROLL_CARD_LOOPS 1 +#define UNROLL_CARD_LOOPS 1 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { sprt_iter->init(this); @@ -36,27 +36,32 @@ void SparsePRTEntry::init(RegionIdx_t region_ind) { _region_ind = region_ind; _next_index = NullEntry; + #if UNROLL_CARD_LOOPS - assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); - _cards[0] = NullEntry; - _cards[1] = NullEntry; - _cards[2] = NullEntry; - _cards[3] = NullEntry; + assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); + for (int i = 0; i < cards_num(); i += UnrollFactor) { + _cards[i] = NullEntry; + _cards[i + 1] = NullEntry; + _cards[i + 2] = NullEntry; + _cards[i + 3] = NullEntry; + } #else - for (int i = 0; i < CardsPerEntry; i++) + for (int i = 0; i < cards_num(); i++) _cards[i] = NullEntry; #endif } bool SparsePRTEntry::contains_card(CardIdx_t card_index) const { #if UNROLL_CARD_LOOPS - assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); - if (_cards[0] == card_index) return true; - if (_cards[1] == card_index) return true; - if (_cards[2] == card_index) return true; - if (_cards[3] == card_index) return true; + assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); + for (int i = 0; i < cards_num(); i += UnrollFactor) { + if (_cards[i] == card_index || + _cards[i + 1] == card_index || + _cards[i + 2] == card_index || + _cards[i + 3] == card_index) return true; + } #else - for (int i = 0; i < CardsPerEntry; i++) { + for (int i = 0; i < cards_num(); i++) { if (_cards[i] == card_index) return true; } #endif @@ -67,14 +72,16 @@ int SparsePRTEntry::num_valid_cards() const { int sum = 0; #if UNROLL_CARD_LOOPS - assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); - if (_cards[0] != NullEntry) sum++; - if (_cards[1] != NullEntry) sum++; - if (_cards[2] != NullEntry) sum++; - if (_cards[3] != NullEntry) sum++; + assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); + for (int i = 0; i < cards_num(); i += UnrollFactor) { + sum += (_cards[i] != NullEntry); + sum += (_cards[i + 1] != NullEntry); + sum += (_cards[i + 2] != NullEntry); + sum += (_cards[i + 3] != NullEntry); + } #else - for (int i = 0; i < CardsPerEntry; i++) { - if (_cards[i] != NulLEntry) sum++; + for (int i = 0; i < cards_num(); i++) { + sum += (_cards[i] != NullEntry); } #endif // Otherwise, we're full. @@ -83,27 +90,27 @@ SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) { #if UNROLL_CARD_LOOPS - assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); - CardIdx_t c = _cards[0]; - if (c == card_index) return found; - if (c == NullEntry) { _cards[0] = card_index; return added; } - c = _cards[1]; - if (c == card_index) return found; - if (c == NullEntry) { _cards[1] = card_index; return added; } - c = _cards[2]; - if (c == card_index) return found; - if (c == NullEntry) { _cards[2] = card_index; return added; } - c = _cards[3]; - if (c == card_index) return found; - if (c == NullEntry) { _cards[3] = card_index; return added; } + assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); + CardIdx_t c; + for (int i = 0; i < cards_num(); i += UnrollFactor) { + c = _cards[i]; + if (c == card_index) return found; + if (c == NullEntry) { _cards[i] = card_index; return added; } + c = _cards[i + 1]; + if (c == card_index) return found; + if (c == NullEntry) { _cards[i + 1] = card_index; return added; } + c = _cards[i + 2]; + if (c == card_index) return found; + if (c == NullEntry) { _cards[i + 2] = card_index; return added; } + c = _cards[i + 3]; + if (c == card_index) return found; + if (c == NullEntry) { _cards[i + 3] = card_index; return added; } + } #else - for (int i = 0; i < CardsPerEntry; i++) { + for (int i = 0; i < cards_num(); i++) { CardIdx_t c = _cards[i]; if (c == card_index) return found; - if (c == NullEntry) { - _cards[i] = card_index; - return added; - } + if (c == NullEntry) { _cards[i] = card_index; return added; } } #endif // Otherwise, we're full. @@ -112,13 +119,15 @@ void SparsePRTEntry::copy_cards(CardIdx_t* cards) const { #if UNROLL_CARD_LOOPS - assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); - cards[0] = _cards[0]; - cards[1] = _cards[1]; - cards[2] = _cards[2]; - cards[3] = _cards[3]; + assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); + for (int i = 0; i < cards_num(); i += UnrollFactor) { + cards[i] = _cards[i]; + cards[i + 1] = _cards[i + 1]; + cards[i + 2] = _cards[i + 2]; + cards[i + 3] = _cards[i + 3]; + } #else - for (int i = 0; i < CardsPerEntry; i++) { + for (int i = 0; i < cards_num(); i++) { cards[i] = _cards[i]; } #endif @@ -133,7 +142,7 @@ RSHashTable::RSHashTable(size_t capacity) : _capacity(capacity), _capacity_mask(capacity-1), _occupied_entries(0), _occupied_cards(0), - _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)), + _entries((SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, SparsePRTEntry::size() * capacity)), _buckets(NEW_C_HEAP_ARRAY(int, capacity)), _free_list(NullEntry), _free_region(0) { @@ -161,8 +170,8 @@ "_capacity too large"); // This will put -1 == NullEntry in the key field of all entries. - memset(_entries, -1, _capacity * sizeof(SparsePRTEntry)); - memset(_buckets, -1, _capacity * sizeof(int)); + memset(_entries, NullEntry, _capacity * SparsePRTEntry::size()); + memset(_buckets, NullEntry, _capacity * sizeof(int)); _free_list = NullEntry; _free_region = 0; } @@ -175,8 +184,8 @@ if (res == SparsePRTEntry::added) _occupied_cards++; #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", - pointer_delta(e, _entries, sizeof(SparsePRTEntry)), - e->num_valid_cards()); + pointer_delta(e, _entries, SparsePRTEntry::size()), + e->num_valid_cards()); #endif assert(e->num_valid_cards() > 0, "Postcondition"); return res != SparsePRTEntry::overflow; @@ -199,6 +208,22 @@ return true; } +SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) { + int ind = (int) (region_ind & capacity_mask()); + int cur_ind = _buckets[ind]; + SparsePRTEntry* cur; + while (cur_ind != NullEntry && + (cur = entry(cur_ind))->r_ind() != region_ind) { + cur_ind = cur->next_index(); + } + + if (cur_ind == NullEntry) return NULL; + // Otherwise... + assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); + assert(cur->num_valid_cards() > 0, "Inv"); + return cur; +} + bool RSHashTable::delete_entry(RegionIdx_t region_ind) { int ind = (int) (region_ind & capacity_mask()); int* prev_loc = &_buckets[ind]; @@ -225,20 +250,8 @@ int ind = (int) (region_ind & capacity_mask()); int cur_ind = _buckets[ind]; SparsePRTEntry* cur; - // XXX - // int k = 0; while (cur_ind != NullEntry && (cur = entry(cur_ind))->r_ind() != region_ind) { - /* - k++; - if (k > 10) { - gclog_or_tty->print_cr("RSHashTable::entry_for_region_ind(%d): " - "k = %d, cur_ind = %d.", region_ind, k, cur_ind); - if (k >= 1000) { - while (1) ; - } - } - */ cur_ind = cur->next_index(); } @@ -319,7 +332,7 @@ bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { _card_ind++; CardIdx_t ci; - if (_card_ind < SparsePRTEntry::CardsPerEntry && + if (_card_ind < SparsePRTEntry::cards_num() && ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != SparsePRTEntry::NullEntry)) { card_index = compute_card_ind(ci); @@ -359,7 +372,7 @@ size_t RSHashTable::mem_size() const { return sizeof(this) + - capacity() * (sizeof(SparsePRTEntry) + sizeof(int)); + capacity() * (SparsePRTEntry::size() + sizeof(int)); } // ---------------------------------------------------------------------- @@ -446,6 +459,10 @@ return _next->get_cards(region_id, cards); } +SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { + return _next->get_entry(region_id); +} + bool SparsePRT::delete_entry(RegionIdx_t region_id) { return _next->delete_entry(region_id); }