Mercurial > hg > truffle
annotate src/share/vm/utilities/bitMap.inline.hpp @ 8733:9def4075da6d
8008079: G1: Add nextObject routine to CMBitMapRO and replace nextWord
Summary: Update the task local finger to the start of the next object when marking aborts, in order to avoid the redundant scanning of all 0's when the marking task restarts, if otherwise updating to the next word. In addition, reuse the routine nextObject() in routine iterate().
Reviewed-by: johnc, ysr
Contributed-by: tamao <tao.mao@oracle.com>
| author | tamao |
|---|---|
| date | Tue, 05 Mar 2013 15:36:56 -0800 |
| parents | 2e966d967c5c |
| children | 17deed6716af |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
4827
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
2 * Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved. |
| 0 | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
844
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_UTILITIES_BITMAP_INLINE_HPP |
| 26 #define SHARE_VM_UTILITIES_BITMAP_INLINE_HPP | |
| 27 | |
| 28 #include "runtime/atomic.hpp" | |
| 29 #include "utilities/bitMap.hpp" | |
| 30 | |
|
809
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
31 #ifdef ASSERT |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
32 inline void BitMap::verify_index(idx_t index) const { |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
33 assert(index < _size, "BitMap index out of bounds"); |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
34 } |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
35 |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
36 inline void BitMap::verify_range(idx_t beg_index, idx_t end_index) const { |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
37 assert(beg_index <= end_index, "BitMap range error"); |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
38 // Note that [0,0) and [size,size) are both valid ranges. |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
39 if (end_index != _size) verify_index(end_index); |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
40 } |
|
6e2afda171db
6849716: BitMap - performance regression introduced with G1
jcoomes
parents:
342
diff
changeset
|
41 #endif // #ifdef ASSERT |
| 342 | 42 |
| 43 inline void BitMap::set_bit(idx_t bit) { | |
| 44 verify_index(bit); | |
| 45 *word_addr(bit) |= bit_mask(bit); | |
| 46 } | |
| 47 | |
| 48 inline void BitMap::clear_bit(idx_t bit) { | |
| 49 verify_index(bit); | |
| 50 *word_addr(bit) &= ~bit_mask(bit); | |
| 51 } | |
| 52 | |
| 0 | 53 inline bool BitMap::par_set_bit(idx_t bit) { |
| 54 verify_index(bit); | |
| 55 volatile idx_t* const addr = word_addr(bit); | |
| 56 const idx_t mask = bit_mask(bit); | |
| 57 idx_t old_val = *addr; | |
| 58 | |
| 59 do { | |
| 60 const idx_t new_val = old_val | mask; | |
| 61 if (new_val == old_val) { | |
| 62 return false; // Someone else beat us to it. | |
| 63 } | |
| 64 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val, | |
| 65 (volatile void*) addr, | |
| 66 (void*) old_val); | |
| 67 if (cur_val == old_val) { | |
| 68 return true; // Success. | |
| 69 } | |
| 70 old_val = cur_val; // The value changed, try again. | |
| 71 } while (true); | |
| 72 } | |
| 73 | |
| 74 inline bool BitMap::par_clear_bit(idx_t bit) { | |
| 75 verify_index(bit); | |
| 76 volatile idx_t* const addr = word_addr(bit); | |
| 77 const idx_t mask = ~bit_mask(bit); | |
| 78 idx_t old_val = *addr; | |
| 79 | |
| 80 do { | |
| 81 const idx_t new_val = old_val & mask; | |
| 82 if (new_val == old_val) { | |
| 83 return false; // Someone else beat us to it. | |
| 84 } | |
| 85 const idx_t cur_val = (idx_t) Atomic::cmpxchg_ptr((void*) new_val, | |
| 86 (volatile void*) addr, | |
| 87 (void*) old_val); | |
| 88 if (cur_val == old_val) { | |
| 89 return true; // Success. | |
| 90 } | |
| 91 old_val = cur_val; // The value changed, try again. | |
| 92 } while (true); | |
| 93 } | |
| 94 | |
| 342 | 95 inline void BitMap::set_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
| 96 if (hint == small_range && end - beg == 1) { | |
| 97 set_bit(beg); | |
| 98 } else { | |
| 99 if (hint == large_range) { | |
| 100 set_large_range(beg, end); | |
| 101 } else { | |
| 102 set_range(beg, end); | |
| 103 } | |
| 104 } | |
| 105 } | |
| 106 | |
| 107 inline void BitMap::clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { | |
| 108 if (hint == small_range && end - beg == 1) { | |
| 109 clear_bit(beg); | |
| 110 } else { | |
| 111 if (hint == large_range) { | |
| 112 clear_large_range(beg, end); | |
| 113 } else { | |
| 114 clear_range(beg, end); | |
| 115 } | |
| 116 } | |
| 117 } | |
| 118 | |
| 119 inline void BitMap::par_set_range(idx_t beg, idx_t end, RangeSizeHint hint) { | |
| 120 if (hint == small_range && end - beg == 1) { | |
| 121 par_at_put(beg, true); | |
| 122 } else { | |
| 123 if (hint == large_range) { | |
| 124 par_at_put_large_range(beg, end, true); | |
| 125 } else { | |
| 126 par_at_put_range(beg, end, true); | |
| 127 } | |
| 128 } | |
| 129 } | |
| 0 | 130 |
| 342 | 131 inline void BitMap::set_range_of_words(idx_t beg, idx_t end) { |
| 132 bm_word_t* map = _map; | |
| 133 for (idx_t i = beg; i < end; ++i) map[i] = ~(uintptr_t)0; | |
| 134 } | |
| 135 | |
| 136 | |
| 137 inline void BitMap::clear_range_of_words(idx_t beg, idx_t end) { | |
| 138 bm_word_t* map = _map; | |
| 139 for (idx_t i = beg; i < end; ++i) map[i] = 0; | |
| 140 } | |
| 141 | |
| 142 | |
| 143 inline void BitMap::clear() { | |
| 144 clear_range_of_words(0, size_in_words()); | |
| 145 } | |
| 146 | |
| 0 | 147 |
| 342 | 148 inline void BitMap::par_clear_range(idx_t beg, idx_t end, RangeSizeHint hint) { |
| 149 if (hint == small_range && end - beg == 1) { | |
| 150 par_at_put(beg, false); | |
| 151 } else { | |
| 152 if (hint == large_range) { | |
| 153 par_at_put_large_range(beg, end, false); | |
| 154 } else { | |
| 155 par_at_put_range(beg, end, false); | |
| 156 } | |
| 157 } | |
| 158 } | |
| 159 | |
| 160 inline BitMap::idx_t | |
| 161 BitMap::get_next_one_offset_inline(idx_t l_offset, idx_t r_offset) const { | |
| 162 assert(l_offset <= size(), "BitMap index out of bounds"); | |
| 163 assert(r_offset <= size(), "BitMap index out of bounds"); | |
| 164 assert(l_offset <= r_offset, "l_offset > r_offset ?"); | |
| 165 | |
| 166 if (l_offset == r_offset) { | |
| 167 return l_offset; | |
| 168 } | |
| 169 idx_t index = word_index(l_offset); | |
| 170 idx_t r_index = word_index(r_offset-1) + 1; | |
| 171 idx_t res_offset = l_offset; | |
| 0 | 172 |
| 173 // check bits including and to the _left_ of offset's position | |
| 342 | 174 idx_t pos = bit_in_word(res_offset); |
| 175 idx_t res = map(index) >> pos; | |
| 176 if (res != (uintptr_t)NoBits) { | |
| 0 | 177 // find the position of the 1-bit |
| 342 | 178 for (; !(res & 1); res_offset++) { |
| 0 | 179 res = res >> 1; |
| 180 } | |
|
4827
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
181 |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
182 #ifdef ASSERT |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
183 // In the following assert, if r_offset is not bitamp word aligned, |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
184 // checking that res_offset is strictly less than r_offset is too |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
185 // strong and will trip the assert. |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
186 // |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
187 // Consider the case where l_offset is bit 15 and r_offset is bit 17 |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
188 // of the same map word, and where bits [15:16:17:18] == [00:00:00:01]. |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
189 // All the bits in the range [l_offset:r_offset) are 0. |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
190 // The loop that calculates res_offset, above, would yield the offset |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
191 // of bit 18 because it's in the same map word as l_offset and there |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
192 // is a set bit in that map word above l_offset (i.e. res != NoBits). |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
193 // |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
194 // In this case, however, we can assert is that res_offset is strictly |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
195 // less than size() since we know that there is at least one set bit |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
196 // at an offset above, but in the same map word as, r_offset. |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
197 // Otherwise, if r_offset is word aligned then it will not be in the |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
198 // same map word as l_offset (unless it equals l_offset). So either |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
199 // there won't be a set bit between l_offset and the end of it's map |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
200 // word (i.e. res == NoBits), or res_offset will be less than r_offset. |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
201 |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
202 idx_t limit = is_word_aligned(r_offset) ? r_offset : size(); |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
203 assert(res_offset >= l_offset && res_offset < limit, "just checking"); |
|
2e966d967c5c
7121547: G1: High number mispredicted branches while iterating over the marking bitmap
johnc
parents:
1972
diff
changeset
|
204 #endif // ASSERT |
| 342 | 205 return MIN2(res_offset, r_offset); |
| 0 | 206 } |
| 207 // skip over all word length 0-bit runs | |
| 208 for (index++; index < r_index; index++) { | |
| 209 res = map(index); | |
| 342 | 210 if (res != (uintptr_t)NoBits) { |
| 0 | 211 // found a 1, return the offset |
| 342 | 212 for (res_offset = bit_index(index); !(res & 1); res_offset++) { |
| 0 | 213 res = res >> 1; |
| 214 } | |
| 215 assert(res & 1, "tautology; see loop condition"); | |
| 342 | 216 assert(res_offset >= l_offset, "just checking"); |
| 217 return MIN2(res_offset, r_offset); | |
| 218 } | |
| 219 } | |
| 220 return r_offset; | |
| 221 } | |
| 222 | |
| 223 inline BitMap::idx_t | |
| 224 BitMap::get_next_zero_offset_inline(idx_t l_offset, idx_t r_offset) const { | |
| 225 assert(l_offset <= size(), "BitMap index out of bounds"); | |
| 226 assert(r_offset <= size(), "BitMap index out of bounds"); | |
| 227 assert(l_offset <= r_offset, "l_offset > r_offset ?"); | |
| 228 | |
| 229 if (l_offset == r_offset) { | |
| 230 return l_offset; | |
| 231 } | |
| 232 idx_t index = word_index(l_offset); | |
| 233 idx_t r_index = word_index(r_offset-1) + 1; | |
| 234 idx_t res_offset = l_offset; | |
| 235 | |
| 236 // check bits including and to the _left_ of offset's position | |
| 237 idx_t pos = res_offset & (BitsPerWord - 1); | |
| 238 idx_t res = (map(index) >> pos) | left_n_bits((int)pos); | |
| 239 | |
| 240 if (res != (uintptr_t)AllBits) { | |
| 241 // find the position of the 0-bit | |
| 242 for (; res & 1; res_offset++) { | |
| 243 res = res >> 1; | |
| 244 } | |
| 245 assert(res_offset >= l_offset, "just checking"); | |
| 246 return MIN2(res_offset, r_offset); | |
| 247 } | |
| 248 // skip over all word length 1-bit runs | |
| 249 for (index++; index < r_index; index++) { | |
| 250 res = map(index); | |
| 251 if (res != (uintptr_t)AllBits) { | |
| 252 // found a 0, return the offset | |
| 253 for (res_offset = index << LogBitsPerWord; res & 1; | |
| 254 res_offset++) { | |
| 255 res = res >> 1; | |
| 256 } | |
| 257 assert(!(res & 1), "tautology; see loop condition"); | |
| 258 assert(res_offset >= l_offset, "just checking"); | |
| 259 return MIN2(res_offset, r_offset); | |
| 0 | 260 } |
| 261 } | |
| 342 | 262 return r_offset; |
| 263 } | |
| 264 | |
| 265 inline BitMap::idx_t | |
| 266 BitMap::get_next_one_offset_inline_aligned_right(idx_t l_offset, | |
| 267 idx_t r_offset) const | |
| 268 { | |
| 269 verify_range(l_offset, r_offset); | |
| 270 assert(bit_in_word(r_offset) == 0, "r_offset not word-aligned"); | |
| 271 | |
| 272 if (l_offset == r_offset) { | |
| 273 return l_offset; | |
| 274 } | |
| 275 idx_t index = word_index(l_offset); | |
| 276 idx_t r_index = word_index(r_offset); | |
| 277 idx_t res_offset = l_offset; | |
| 278 | |
| 279 // check bits including and to the _left_ of offset's position | |
| 280 idx_t res = map(index) >> bit_in_word(res_offset); | |
| 281 if (res != (uintptr_t)NoBits) { | |
| 282 // find the position of the 1-bit | |
| 283 for (; !(res & 1); res_offset++) { | |
| 284 res = res >> 1; | |
| 285 } | |
| 286 assert(res_offset >= l_offset && | |
| 287 res_offset < r_offset, "just checking"); | |
| 288 return res_offset; | |
| 289 } | |
| 290 // skip over all word length 0-bit runs | |
| 291 for (index++; index < r_index; index++) { | |
| 292 res = map(index); | |
| 293 if (res != (uintptr_t)NoBits) { | |
| 294 // found a 1, return the offset | |
| 295 for (res_offset = bit_index(index); !(res & 1); res_offset++) { | |
| 296 res = res >> 1; | |
| 297 } | |
| 298 assert(res & 1, "tautology; see loop condition"); | |
| 299 assert(res_offset >= l_offset && res_offset < r_offset, "just checking"); | |
| 300 return res_offset; | |
| 301 } | |
| 302 } | |
| 303 return r_offset; | |
| 0 | 304 } |
| 342 | 305 |
| 306 | |
| 307 // Returns a bit mask for a range of bits [beg, end) within a single word. Each | |
| 308 // bit in the mask is 0 if the bit is in the range, 1 if not in the range. The | |
| 309 // returned mask can be used directly to clear the range, or inverted to set the | |
| 310 // range. Note: end must not be 0. | |
| 311 inline BitMap::bm_word_t | |
| 312 BitMap::inverted_bit_mask_for_range(idx_t beg, idx_t end) const { | |
| 313 assert(end != 0, "does not work when end == 0"); | |
| 314 assert(beg == end || word_index(beg) == word_index(end - 1), | |
| 315 "must be a single-word range"); | |
| 316 bm_word_t mask = bit_mask(beg) - 1; // low (right) bits | |
| 317 if (bit_in_word(end) != 0) { | |
| 318 mask |= ~(bit_mask(end) - 1); // high (left) bits | |
| 319 } | |
| 320 return mask; | |
| 321 } | |
| 322 | |
| 323 inline void BitMap::set_large_range_of_words(idx_t beg, idx_t end) { | |
| 324 memset(_map + beg, ~(unsigned char)0, (end - beg) * sizeof(uintptr_t)); | |
| 325 } | |
| 326 | |
| 327 inline void BitMap::clear_large_range_of_words(idx_t beg, idx_t end) { | |
| 328 memset(_map + beg, 0, (end - beg) * sizeof(uintptr_t)); | |
| 329 } | |
| 330 | |
| 331 inline BitMap::idx_t BitMap::word_index_round_up(idx_t bit) const { | |
| 332 idx_t bit_rounded_up = bit + (BitsPerWord - 1); | |
| 333 // Check for integer arithmetic overflow. | |
| 334 return bit_rounded_up > bit ? word_index(bit_rounded_up) : size_in_words(); | |
| 335 } | |
| 336 | |
| 337 inline BitMap::idx_t BitMap::get_next_one_offset(idx_t l_offset, | |
| 338 idx_t r_offset) const { | |
| 339 return get_next_one_offset_inline(l_offset, r_offset); | |
| 340 } | |
| 341 | |
| 342 inline BitMap::idx_t BitMap::get_next_zero_offset(idx_t l_offset, | |
| 343 idx_t r_offset) const { | |
| 344 return get_next_zero_offset_inline(l_offset, r_offset); | |
| 345 } | |
| 346 | |
| 347 inline void BitMap2D::clear() { | |
| 348 _map.clear(); | |
| 349 } | |
| 1972 | 350 |
| 351 #endif // SHARE_VM_UTILITIES_BITMAP_INLINE_HPP |