src/share/vm/gc_implementation/g1/sparsePRT.cpp

rev 6582 : 8047330: Remove unrolled card loops in G1 SparsePRTEntry
Summary: Removed unrolled card loops in sparsePRT.cpp
Reviewed-by:
Contributed-by: andreas.sjoberg@oracle.com
rev 6583 : 8047328: Change typedef CardIdx_t from int to uint16_t
Summary: Changed the typedef and made the necessary changes to code interacting with the SparsePRTEntry class.
Reviewed-by:
Contributed-by: andreas.sjoberg@oracle.com

@@ -33,48 +33,48 @@
 
 #define SPARSE_PRT_VERBOSE 0
 
 void SparsePRTEntry::init(RegionIdx_t region_ind) {
   _region_ind = region_ind;
-  _next_index = NullEntry;
+  _next_index = RSHashTable::NullEntry;
+  _next_null = 0;
 
-  for (int i = 0; i < cards_num(); i++) {
-    _cards[i] = NullEntry;
-  }
 }
 
 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
-  for (int i = 0; i < cards_num(); i++) {
+  for (int i = 0; i < _next_null; i++) {
     if (_cards[i] == card_index) return true;
   }
   return false;
 }
 
-int SparsePRTEntry::num_valid_cards() const {
-  int sum = 0;
-  for (int i = 0; i < cards_num(); i++) {
-    sum += (_cards[i] != NullEntry);
-  }
-  return sum;
-}
 
 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
-  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; }
+  for (int i = 0; i < _next_null; i++) {
+    CardIdx_t c = card(i);
+    if (c == card_index) {
+      return found;
+    }
+  }
+  if (_next_null < cards_num() -1) {
+    _cards[_next_null] = card_index;
+    _next_null++;
+    return added;
   }
   // Otherwise, we're full.
   return overflow;
 }
 
 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
-  memcpy(cards, _cards, cards_num() * sizeof(CardIdx_t));
+  memcpy(cards, _cards, _next_null * sizeof(CardIdx_t));
 }
 
 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
-  copy_cards(&e->_cards[0]);
+  copy_cards(e->_cards);
+  assert(_next_null >= 0, "invariant");
+  assert(_next_null <= cards_num(), "invariant");
+  e->_next_null = _next_null;
 }
 
 // ----------------------------------------------------------------------
 
 RSHashTable::RSHashTable(size_t capacity) :

@@ -218,54 +218,57 @@
   e->copy_cards(e2);
   _occupied_cards += e2->num_valid_cards();
   assert(e2->num_valid_cards() > 0, "Postcondition.");
 }
 
-CardIdx_t RSHashTableIter::find_first_card_in_list() {
-  CardIdx_t res;
+bool RSHashTableIter::find_first_card_in_list(CardIdx_t & res) {
   while (_bl_ind != RSHashTable::NullEntry) {
-    res = _rsht->entry(_bl_ind)->card(0);
-    if (res != SparsePRTEntry::NullEntry) {
-      return res;
+    SparsePRTEntry * sparse_entry = _rsht->entry(_bl_ind);
+    if (sparse_entry->num_valid_cards() > 0) {
+      res = sparse_entry->card(0);
+      return true;
     } else {
-      _bl_ind = _rsht->entry(_bl_ind)->next_index();
+      _bl_ind = sparse_entry->next_index();
     }
   }
   // Otherwise, none found:
-  return SparsePRTEntry::NullEntry;
+  return false;
 }
 
 size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) {
   return (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) + ci;
 }
 
 bool RSHashTableIter::has_next(size_t& card_index) {
   _card_ind++;
   CardIdx_t ci;
-  if (_card_ind < SparsePRTEntry::cards_num() &&
-      ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
-       SparsePRTEntry::NullEntry)) {
+  if (_bl_ind >= 0) {
+    SparsePRTEntry * e = _rsht->entry(_bl_ind);
+    if (_card_ind < e->num_valid_cards()) {
+      ci = e->card(_card_ind);
     card_index = compute_card_ind(ci);
     return true;
   }
+  }
+  
   // Otherwise, must find the next valid entry.
   _card_ind = 0;
 
   if (_bl_ind != RSHashTable::NullEntry) {
       _bl_ind = _rsht->entry(_bl_ind)->next_index();
-      ci = find_first_card_in_list();
-      if (ci != SparsePRTEntry::NullEntry) {
+      bool found = find_first_card_in_list(ci);
+      if (found) {
         card_index = compute_card_ind(ci);
         return true;
       }
   }
   // If we didn't return above, must go to the next non-null table index.
   _tbl_ind++;
   while ((size_t)_tbl_ind < _rsht->capacity()) {
     _bl_ind = _rsht->_buckets[_tbl_ind];
-    ci = find_first_card_in_list();
-    if (ci != SparsePRTEntry::NullEntry) {
+    bool found = find_first_card_in_list(ci);
+    if (found) {
       card_index = compute_card_ind(ci);
       return true;
     }
     // Otherwise, try next entry.
     _tbl_ind++;