Mercurial > hg > graal-jvmci-8
comparison 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 |
comparison
equal
deleted
inserted
replaced
1260:8859772195c6 | 1261:0414c1049f15 |
---|---|
25 #include "incls/_precompiled.incl" | 25 #include "incls/_precompiled.incl" |
26 #include "incls/_sparsePRT.cpp.incl" | 26 #include "incls/_sparsePRT.cpp.incl" |
27 | 27 |
28 #define SPARSE_PRT_VERBOSE 0 | 28 #define SPARSE_PRT_VERBOSE 0 |
29 | 29 |
30 #define UNROLL_CARD_LOOPS 1 | 30 #define UNROLL_CARD_LOOPS 1 |
31 | 31 |
32 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { | 32 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { |
33 sprt_iter->init(this); | 33 sprt_iter->init(this); |
34 } | 34 } |
35 | 35 |
36 void SparsePRTEntry::init(RegionIdx_t region_ind) { | 36 void SparsePRTEntry::init(RegionIdx_t region_ind) { |
37 _region_ind = region_ind; | 37 _region_ind = region_ind; |
38 _next_index = NullEntry; | 38 _next_index = NullEntry; |
39 | |
39 #if UNROLL_CARD_LOOPS | 40 #if UNROLL_CARD_LOOPS |
40 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); | 41 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
41 _cards[0] = NullEntry; | 42 for (int i = 0; i < cards_num(); i += UnrollFactor) { |
42 _cards[1] = NullEntry; | 43 _cards[i] = NullEntry; |
43 _cards[2] = NullEntry; | 44 _cards[i + 1] = NullEntry; |
44 _cards[3] = NullEntry; | 45 _cards[i + 2] = NullEntry; |
46 _cards[i + 3] = NullEntry; | |
47 } | |
45 #else | 48 #else |
46 for (int i = 0; i < CardsPerEntry; i++) | 49 for (int i = 0; i < cards_num(); i++) |
47 _cards[i] = NullEntry; | 50 _cards[i] = NullEntry; |
48 #endif | 51 #endif |
49 } | 52 } |
50 | 53 |
51 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const { | 54 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const { |
52 #if UNROLL_CARD_LOOPS | 55 #if UNROLL_CARD_LOOPS |
53 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); | 56 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
54 if (_cards[0] == card_index) return true; | 57 for (int i = 0; i < cards_num(); i += UnrollFactor) { |
55 if (_cards[1] == card_index) return true; | 58 if (_cards[i] == card_index || |
56 if (_cards[2] == card_index) return true; | 59 _cards[i + 1] == card_index || |
57 if (_cards[3] == card_index) return true; | 60 _cards[i + 2] == card_index || |
61 _cards[i + 3] == card_index) return true; | |
62 } | |
58 #else | 63 #else |
59 for (int i = 0; i < CardsPerEntry; i++) { | 64 for (int i = 0; i < cards_num(); i++) { |
60 if (_cards[i] == card_index) return true; | 65 if (_cards[i] == card_index) return true; |
61 } | 66 } |
62 #endif | 67 #endif |
63 // Otherwise, we're full. | 68 // Otherwise, we're full. |
64 return false; | 69 return false; |
65 } | 70 } |
66 | 71 |
67 int SparsePRTEntry::num_valid_cards() const { | 72 int SparsePRTEntry::num_valid_cards() const { |
68 int sum = 0; | 73 int sum = 0; |
69 #if UNROLL_CARD_LOOPS | 74 #if UNROLL_CARD_LOOPS |
70 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); | 75 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
71 if (_cards[0] != NullEntry) sum++; | 76 for (int i = 0; i < cards_num(); i += UnrollFactor) { |
72 if (_cards[1] != NullEntry) sum++; | 77 sum += (_cards[i] != NullEntry); |
73 if (_cards[2] != NullEntry) sum++; | 78 sum += (_cards[i + 1] != NullEntry); |
74 if (_cards[3] != NullEntry) sum++; | 79 sum += (_cards[i + 2] != NullEntry); |
80 sum += (_cards[i + 3] != NullEntry); | |
81 } | |
75 #else | 82 #else |
76 for (int i = 0; i < CardsPerEntry; i++) { | 83 for (int i = 0; i < cards_num(); i++) { |
77 if (_cards[i] != NulLEntry) sum++; | 84 sum += (_cards[i] != NullEntry); |
78 } | 85 } |
79 #endif | 86 #endif |
80 // Otherwise, we're full. | 87 // Otherwise, we're full. |
81 return sum; | 88 return sum; |
82 } | 89 } |
83 | 90 |
84 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) { | 91 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) { |
85 #if UNROLL_CARD_LOOPS | 92 #if UNROLL_CARD_LOOPS |
86 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); | 93 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
87 CardIdx_t c = _cards[0]; | 94 CardIdx_t c; |
88 if (c == card_index) return found; | 95 for (int i = 0; i < cards_num(); i += UnrollFactor) { |
89 if (c == NullEntry) { _cards[0] = card_index; return added; } | 96 c = _cards[i]; |
90 c = _cards[1]; | 97 if (c == card_index) return found; |
91 if (c == card_index) return found; | 98 if (c == NullEntry) { _cards[i] = card_index; return added; } |
92 if (c == NullEntry) { _cards[1] = card_index; return added; } | 99 c = _cards[i + 1]; |
93 c = _cards[2]; | 100 if (c == card_index) return found; |
94 if (c == card_index) return found; | 101 if (c == NullEntry) { _cards[i + 1] = card_index; return added; } |
95 if (c == NullEntry) { _cards[2] = card_index; return added; } | 102 c = _cards[i + 2]; |
96 c = _cards[3]; | 103 if (c == card_index) return found; |
97 if (c == card_index) return found; | 104 if (c == NullEntry) { _cards[i + 2] = card_index; return added; } |
98 if (c == NullEntry) { _cards[3] = card_index; return added; } | 105 c = _cards[i + 3]; |
106 if (c == card_index) return found; | |
107 if (c == NullEntry) { _cards[i + 3] = card_index; return added; } | |
108 } | |
99 #else | 109 #else |
100 for (int i = 0; i < CardsPerEntry; i++) { | 110 for (int i = 0; i < cards_num(); i++) { |
101 CardIdx_t c = _cards[i]; | 111 CardIdx_t c = _cards[i]; |
102 if (c == card_index) return found; | 112 if (c == card_index) return found; |
103 if (c == NullEntry) { | 113 if (c == NullEntry) { _cards[i] = card_index; return added; } |
104 _cards[i] = card_index; | |
105 return added; | |
106 } | |
107 } | 114 } |
108 #endif | 115 #endif |
109 // Otherwise, we're full. | 116 // Otherwise, we're full. |
110 return overflow; | 117 return overflow; |
111 } | 118 } |
112 | 119 |
113 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const { | 120 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const { |
114 #if UNROLL_CARD_LOOPS | 121 #if UNROLL_CARD_LOOPS |
115 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); | 122 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
116 cards[0] = _cards[0]; | 123 for (int i = 0; i < cards_num(); i += UnrollFactor) { |
117 cards[1] = _cards[1]; | 124 cards[i] = _cards[i]; |
118 cards[2] = _cards[2]; | 125 cards[i + 1] = _cards[i + 1]; |
119 cards[3] = _cards[3]; | 126 cards[i + 2] = _cards[i + 2]; |
127 cards[i + 3] = _cards[i + 3]; | |
128 } | |
120 #else | 129 #else |
121 for (int i = 0; i < CardsPerEntry; i++) { | 130 for (int i = 0; i < cards_num(); i++) { |
122 cards[i] = _cards[i]; | 131 cards[i] = _cards[i]; |
123 } | 132 } |
124 #endif | 133 #endif |
125 } | 134 } |
126 | 135 |
131 // ---------------------------------------------------------------------- | 140 // ---------------------------------------------------------------------- |
132 | 141 |
133 RSHashTable::RSHashTable(size_t capacity) : | 142 RSHashTable::RSHashTable(size_t capacity) : |
134 _capacity(capacity), _capacity_mask(capacity-1), | 143 _capacity(capacity), _capacity_mask(capacity-1), |
135 _occupied_entries(0), _occupied_cards(0), | 144 _occupied_entries(0), _occupied_cards(0), |
136 _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)), | 145 _entries((SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, SparsePRTEntry::size() * capacity)), |
137 _buckets(NEW_C_HEAP_ARRAY(int, capacity)), | 146 _buckets(NEW_C_HEAP_ARRAY(int, capacity)), |
138 _free_list(NullEntry), _free_region(0) | 147 _free_list(NullEntry), _free_region(0) |
139 { | 148 { |
140 clear(); | 149 clear(); |
141 } | 150 } |
159 | 168 |
160 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1, | 169 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1, |
161 "_capacity too large"); | 170 "_capacity too large"); |
162 | 171 |
163 // This will put -1 == NullEntry in the key field of all entries. | 172 // This will put -1 == NullEntry in the key field of all entries. |
164 memset(_entries, -1, _capacity * sizeof(SparsePRTEntry)); | 173 memset(_entries, NullEntry, _capacity * SparsePRTEntry::size()); |
165 memset(_buckets, -1, _capacity * sizeof(int)); | 174 memset(_buckets, NullEntry, _capacity * sizeof(int)); |
166 _free_list = NullEntry; | 175 _free_list = NullEntry; |
167 _free_region = 0; | 176 _free_region = 0; |
168 } | 177 } |
169 | 178 |
170 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) { | 179 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) { |
173 "Postcondition of call above."); | 182 "Postcondition of call above."); |
174 SparsePRTEntry::AddCardResult res = e->add_card(card_index); | 183 SparsePRTEntry::AddCardResult res = e->add_card(card_index); |
175 if (res == SparsePRTEntry::added) _occupied_cards++; | 184 if (res == SparsePRTEntry::added) _occupied_cards++; |
176 #if SPARSE_PRT_VERBOSE | 185 #if SPARSE_PRT_VERBOSE |
177 gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", | 186 gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", |
178 pointer_delta(e, _entries, sizeof(SparsePRTEntry)), | 187 pointer_delta(e, _entries, SparsePRTEntry::size()), |
179 e->num_valid_cards()); | 188 e->num_valid_cards()); |
180 #endif | 189 #endif |
181 assert(e->num_valid_cards() > 0, "Postcondition"); | 190 assert(e->num_valid_cards() > 0, "Postcondition"); |
182 return res != SparsePRTEntry::overflow; | 191 return res != SparsePRTEntry::overflow; |
183 } | 192 } |
184 | 193 |
195 // Otherwise... | 204 // Otherwise... |
196 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); | 205 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); |
197 assert(cur->num_valid_cards() > 0, "Inv"); | 206 assert(cur->num_valid_cards() > 0, "Inv"); |
198 cur->copy_cards(cards); | 207 cur->copy_cards(cards); |
199 return true; | 208 return true; |
209 } | |
210 | |
211 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) { | |
212 int ind = (int) (region_ind & capacity_mask()); | |
213 int cur_ind = _buckets[ind]; | |
214 SparsePRTEntry* cur; | |
215 while (cur_ind != NullEntry && | |
216 (cur = entry(cur_ind))->r_ind() != region_ind) { | |
217 cur_ind = cur->next_index(); | |
218 } | |
219 | |
220 if (cur_ind == NullEntry) return NULL; | |
221 // Otherwise... | |
222 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); | |
223 assert(cur->num_valid_cards() > 0, "Inv"); | |
224 return cur; | |
200 } | 225 } |
201 | 226 |
202 bool RSHashTable::delete_entry(RegionIdx_t region_ind) { | 227 bool RSHashTable::delete_entry(RegionIdx_t region_ind) { |
203 int ind = (int) (region_ind & capacity_mask()); | 228 int ind = (int) (region_ind & capacity_mask()); |
204 int* prev_loc = &_buckets[ind]; | 229 int* prev_loc = &_buckets[ind]; |
223 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const { | 248 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const { |
224 assert(occupied_entries() < capacity(), "Precondition"); | 249 assert(occupied_entries() < capacity(), "Precondition"); |
225 int ind = (int) (region_ind & capacity_mask()); | 250 int ind = (int) (region_ind & capacity_mask()); |
226 int cur_ind = _buckets[ind]; | 251 int cur_ind = _buckets[ind]; |
227 SparsePRTEntry* cur; | 252 SparsePRTEntry* cur; |
228 // XXX | |
229 // int k = 0; | |
230 while (cur_ind != NullEntry && | 253 while (cur_ind != NullEntry && |
231 (cur = entry(cur_ind))->r_ind() != region_ind) { | 254 (cur = entry(cur_ind))->r_ind() != region_ind) { |
232 /* | |
233 k++; | |
234 if (k > 10) { | |
235 gclog_or_tty->print_cr("RSHashTable::entry_for_region_ind(%d): " | |
236 "k = %d, cur_ind = %d.", region_ind, k, cur_ind); | |
237 if (k >= 1000) { | |
238 while (1) ; | |
239 } | |
240 } | |
241 */ | |
242 cur_ind = cur->next_index(); | 255 cur_ind = cur->next_index(); |
243 } | 256 } |
244 | 257 |
245 if (cur_ind != NullEntry) { | 258 if (cur_ind != NullEntry) { |
246 assert(cur->r_ind() == region_ind, "Loop postcondition + test"); | 259 assert(cur->r_ind() == region_ind, "Loop postcondition + test"); |
317 } | 330 } |
318 | 331 |
319 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { | 332 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { |
320 _card_ind++; | 333 _card_ind++; |
321 CardIdx_t ci; | 334 CardIdx_t ci; |
322 if (_card_ind < SparsePRTEntry::CardsPerEntry && | 335 if (_card_ind < SparsePRTEntry::cards_num() && |
323 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != | 336 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != |
324 SparsePRTEntry::NullEntry)) { | 337 SparsePRTEntry::NullEntry)) { |
325 card_index = compute_card_ind(ci); | 338 card_index = compute_card_ind(ci); |
326 return true; | 339 return true; |
327 } | 340 } |
357 return (e != NULL && e->contains_card(card_index)); | 370 return (e != NULL && e->contains_card(card_index)); |
358 } | 371 } |
359 | 372 |
360 size_t RSHashTable::mem_size() const { | 373 size_t RSHashTable::mem_size() const { |
361 return sizeof(this) + | 374 return sizeof(this) + |
362 capacity() * (sizeof(SparsePRTEntry) + sizeof(int)); | 375 capacity() * (SparsePRTEntry::size() + sizeof(int)); |
363 } | 376 } |
364 | 377 |
365 // ---------------------------------------------------------------------- | 378 // ---------------------------------------------------------------------- |
366 | 379 |
367 SparsePRT* SparsePRT::_head_expanded_list = NULL; | 380 SparsePRT* SparsePRT::_head_expanded_list = NULL; |
444 | 457 |
445 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { | 458 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { |
446 return _next->get_cards(region_id, cards); | 459 return _next->get_cards(region_id, cards); |
447 } | 460 } |
448 | 461 |
462 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { | |
463 return _next->get_entry(region_id); | |
464 } | |
465 | |
449 bool SparsePRT::delete_entry(RegionIdx_t region_id) { | 466 bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
450 return _next->delete_entry(region_id); | 467 return _next->delete_entry(region_id); |
451 } | 468 } |
452 | 469 |
453 void SparsePRT::clear() { | 470 void SparsePRT::clear() { |