Thu, 11 Feb 2010 15:52:19 -0800
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
duke@435 | 1 | /* |
xdono@905 | 2 | * Copyright 2000-2008 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | // correct linkage required to compile w/o warnings |
duke@435 | 26 | // (must be on file level - cannot be local) |
duke@435 | 27 | extern "C" { typedef int (*ftype)(const void*, const void*); } |
duke@435 | 28 | |
duke@435 | 29 | |
duke@435 | 30 | class ResourceArray: public ResourceObj { |
duke@435 | 31 | protected: |
duke@435 | 32 | int _length; // the number of array elements |
duke@435 | 33 | void* _data; // the array memory |
duke@435 | 34 | #ifdef ASSERT |
duke@435 | 35 | int _nesting; // the resource area nesting level |
duke@435 | 36 | #endif |
duke@435 | 37 | |
duke@435 | 38 | // creation |
duke@435 | 39 | ResourceArray() { |
duke@435 | 40 | _length = 0; |
duke@435 | 41 | _data = NULL; |
duke@435 | 42 | DEBUG_ONLY(init_nesting();) |
jrose@867 | 43 | // client may call initialize, at most once |
duke@435 | 44 | } |
duke@435 | 45 | |
duke@435 | 46 | |
duke@435 | 47 | ResourceArray(size_t esize, int length) { |
jrose@867 | 48 | DEBUG_ONLY(_data = NULL); |
jrose@867 | 49 | initialize(esize, length); |
jrose@867 | 50 | } |
jrose@867 | 51 | |
jrose@867 | 52 | void initialize(size_t esize, int length) { |
duke@435 | 53 | assert(length >= 0, "illegal length"); |
jrose@867 | 54 | assert(_data == NULL, "must be new object"); |
duke@435 | 55 | _length = length; |
duke@435 | 56 | _data = resource_allocate_bytes(esize * length); |
duke@435 | 57 | DEBUG_ONLY(init_nesting();) |
duke@435 | 58 | } |
duke@435 | 59 | |
duke@435 | 60 | #ifdef ASSERT |
duke@435 | 61 | void init_nesting(); |
duke@435 | 62 | #endif |
duke@435 | 63 | |
duke@435 | 64 | // helper functions |
duke@435 | 65 | void sort (size_t esize, ftype f); // sort the array |
duke@435 | 66 | void expand (size_t esize, int i, int& size);// expand the array to include slot i |
duke@435 | 67 | void remove_at(size_t esize, int i); // remove the element in slot i |
duke@435 | 68 | |
duke@435 | 69 | public: |
duke@435 | 70 | // standard operations |
duke@435 | 71 | int length() const { return _length; } |
duke@435 | 72 | bool is_empty() const { return length() == 0; } |
duke@435 | 73 | }; |
duke@435 | 74 | |
duke@435 | 75 | |
duke@435 | 76 | class CHeapArray: public CHeapObj { |
duke@435 | 77 | protected: |
duke@435 | 78 | int _length; // the number of array elements |
duke@435 | 79 | void* _data; // the array memory |
duke@435 | 80 | |
duke@435 | 81 | // creation |
duke@435 | 82 | CHeapArray() { |
duke@435 | 83 | _length = 0; |
duke@435 | 84 | _data = NULL; |
duke@435 | 85 | } |
duke@435 | 86 | |
duke@435 | 87 | |
duke@435 | 88 | CHeapArray(size_t esize, int length) { |
duke@435 | 89 | assert(length >= 0, "illegal length"); |
duke@435 | 90 | _length = length; |
duke@435 | 91 | _data = (void*) NEW_C_HEAP_ARRAY(char *, esize * length); |
duke@435 | 92 | } |
duke@435 | 93 | |
duke@435 | 94 | #ifdef ASSERT |
duke@435 | 95 | void init_nesting(); |
duke@435 | 96 | #endif |
duke@435 | 97 | |
duke@435 | 98 | // helper functions |
duke@435 | 99 | void sort (size_t esize, ftype f); // sort the array |
duke@435 | 100 | void expand (size_t esize, int i, int& size);// expand the array to include slot i |
duke@435 | 101 | void remove_at(size_t esize, int i); // remove the element in slot i |
duke@435 | 102 | |
duke@435 | 103 | public: |
duke@435 | 104 | // standard operations |
duke@435 | 105 | int length() const { return _length; } |
duke@435 | 106 | bool is_empty() const { return length() == 0; } |
duke@435 | 107 | }; |
duke@435 | 108 | |
duke@435 | 109 | #define define_generic_array(array_name,element_type, base_class) \ |
duke@435 | 110 | class array_name: public base_class { \ |
duke@435 | 111 | protected: \ |
duke@435 | 112 | typedef element_type etype; \ |
duke@435 | 113 | enum { esize = sizeof(etype) }; \ |
duke@435 | 114 | \ |
duke@435 | 115 | void base_remove_at(size_t size, int i) { base_class::remove_at(size, i); } \ |
duke@435 | 116 | \ |
duke@435 | 117 | public: \ |
duke@435 | 118 | /* creation */ \ |
duke@435 | 119 | array_name() : base_class() {} \ |
duke@435 | 120 | array_name(const int length) : base_class(esize, length) {} \ |
jrose@867 | 121 | array_name(const int length, const etype fx) { initialize(length, fx); } \ |
jrose@867 | 122 | void initialize(const int length) { base_class::initialize(esize, length); } \ |
jrose@867 | 123 | void initialize(const int length, const etype fx) { \ |
jrose@867 | 124 | initialize(length); \ |
duke@435 | 125 | for (int i = 0; i < length; i++) ((etype*)_data)[i] = fx; \ |
duke@435 | 126 | } \ |
duke@435 | 127 | \ |
duke@435 | 128 | /* standard operations */ \ |
duke@435 | 129 | etype& operator [] (const int i) const { \ |
duke@435 | 130 | assert(0 <= i && i < length(), "index out of bounds"); \ |
duke@435 | 131 | return ((etype*)_data)[i]; \ |
duke@435 | 132 | } \ |
duke@435 | 133 | \ |
duke@435 | 134 | int index_of(const etype x) const { \ |
duke@435 | 135 | int i = length(); \ |
duke@435 | 136 | while (i-- > 0 && ((etype*)_data)[i] != x) ; \ |
duke@435 | 137 | /* i < 0 || ((etype*)_data)_data[i] == x */ \ |
duke@435 | 138 | return i; \ |
duke@435 | 139 | } \ |
duke@435 | 140 | \ |
duke@435 | 141 | void sort(int f(etype*, etype*)) { base_class::sort(esize, (ftype)f); } \ |
duke@435 | 142 | bool contains(const etype x) const { return index_of(x) >= 0; } \ |
duke@435 | 143 | \ |
duke@435 | 144 | /* deprecated operations - for compatibility with GrowableArray only */ \ |
duke@435 | 145 | etype at(const int i) const { return (*this)[i]; } \ |
duke@435 | 146 | void at_put(const int i, const etype x) { (*this)[i] = x; } \ |
duke@435 | 147 | etype* adr_at(const int i) { return &(*this)[i]; } \ |
duke@435 | 148 | int find(const etype x) { return index_of(x); } \ |
duke@435 | 149 | }; \ |
duke@435 | 150 | |
duke@435 | 151 | |
duke@435 | 152 | #define define_array(array_name,element_type) \ |
duke@435 | 153 | define_generic_array(array_name, element_type, ResourceArray) |
duke@435 | 154 | |
duke@435 | 155 | |
duke@435 | 156 | #define define_stack(stack_name,array_name) \ |
duke@435 | 157 | class stack_name: public array_name { \ |
duke@435 | 158 | protected: \ |
duke@435 | 159 | int _size; \ |
duke@435 | 160 | \ |
duke@435 | 161 | void grow(const int i, const etype fx) { \ |
duke@435 | 162 | assert(i >= length(), "index too small"); \ |
duke@435 | 163 | if (i >= size()) expand(esize, i, _size); \ |
duke@435 | 164 | for (int j = length(); j <= i; j++) ((etype*)_data)[j] = fx; \ |
duke@435 | 165 | _length = i+1; \ |
duke@435 | 166 | } \ |
duke@435 | 167 | \ |
duke@435 | 168 | public: \ |
duke@435 | 169 | /* creation */ \ |
jrose@867 | 170 | stack_name() : array_name() { _size = 0; } \ |
jrose@867 | 171 | stack_name(const int size) { initialize(size); } \ |
jrose@867 | 172 | stack_name(const int size, const etype fx) { initialize(size, fx); } \ |
jrose@867 | 173 | void initialize(const int size, const etype fx) { \ |
jrose@867 | 174 | _size = size; \ |
jrose@867 | 175 | array_name::initialize(size, fx); \ |
jrose@867 | 176 | /* _length == size, allocation and size are the same */ \ |
jrose@867 | 177 | } \ |
jrose@867 | 178 | void initialize(const int size) { \ |
jrose@867 | 179 | _size = size; \ |
jrose@867 | 180 | array_name::initialize(size); \ |
jrose@867 | 181 | _length = 0; /* reset length to zero; _size records the allocation */ \ |
jrose@867 | 182 | } \ |
duke@435 | 183 | \ |
duke@435 | 184 | /* standard operations */ \ |
duke@435 | 185 | int size() const { return _size; } \ |
duke@435 | 186 | \ |
jrose@867 | 187 | int push(const etype x) { \ |
jrose@867 | 188 | int len = length(); \ |
jrose@867 | 189 | if (len >= size()) expand(esize, len, _size); \ |
jrose@867 | 190 | ((etype*)_data)[len] = x; \ |
jrose@867 | 191 | _length = len+1; \ |
jrose@867 | 192 | return len; \ |
duke@435 | 193 | } \ |
duke@435 | 194 | \ |
duke@435 | 195 | etype pop() { \ |
duke@435 | 196 | assert(!is_empty(), "stack is empty"); \ |
duke@435 | 197 | return ((etype*)_data)[--_length]; \ |
duke@435 | 198 | } \ |
duke@435 | 199 | \ |
duke@435 | 200 | etype top() const { \ |
duke@435 | 201 | assert(!is_empty(), "stack is empty"); \ |
duke@435 | 202 | return ((etype*)_data)[length() - 1]; \ |
duke@435 | 203 | } \ |
duke@435 | 204 | \ |
duke@435 | 205 | void push_all(const stack_name* stack) { \ |
duke@435 | 206 | const int l = stack->length(); \ |
duke@435 | 207 | for (int i = 0; i < l; i++) push(((etype*)(stack->_data))[i]); \ |
duke@435 | 208 | } \ |
duke@435 | 209 | \ |
duke@435 | 210 | etype at_grow(const int i, const etype fx) { \ |
duke@435 | 211 | if (i >= length()) grow(i, fx); \ |
duke@435 | 212 | return ((etype*)_data)[i]; \ |
duke@435 | 213 | } \ |
duke@435 | 214 | \ |
duke@435 | 215 | void at_put_grow(const int i, const etype x, const etype fx) { \ |
duke@435 | 216 | if (i >= length()) grow(i, fx); \ |
duke@435 | 217 | ((etype*)_data)[i] = x; \ |
duke@435 | 218 | } \ |
duke@435 | 219 | \ |
duke@435 | 220 | void truncate(const int length) { \ |
duke@435 | 221 | assert(0 <= length && length <= this->length(), "illegal length"); \ |
duke@435 | 222 | _length = length; \ |
duke@435 | 223 | } \ |
duke@435 | 224 | \ |
duke@435 | 225 | void remove_at(int i) { base_remove_at(esize, i); } \ |
duke@435 | 226 | void remove(etype x) { remove_at(index_of(x)); } \ |
duke@435 | 227 | \ |
duke@435 | 228 | /* inserts the given element before the element at index i */ \ |
duke@435 | 229 | void insert_before(const int i, const etype el) { \ |
duke@435 | 230 | int len = length(); \ |
duke@435 | 231 | int new_length = len + 1; \ |
duke@435 | 232 | if (new_length >= size()) expand(esize, new_length, _size); \ |
duke@435 | 233 | for (int j = len - 1; j >= i; j--) { \ |
duke@435 | 234 | ((etype*)_data)[j + 1] = ((etype*)_data)[j]; \ |
duke@435 | 235 | } \ |
duke@435 | 236 | _length = new_length; \ |
duke@435 | 237 | at_put(i, el); \ |
duke@435 | 238 | } \ |
duke@435 | 239 | \ |
duke@435 | 240 | /* inserts contents of the given stack before the element at index i */ \ |
duke@435 | 241 | void insert_before(const int i, const stack_name *st) { \ |
duke@435 | 242 | if (st->length() == 0) return; \ |
duke@435 | 243 | int len = length(); \ |
duke@435 | 244 | int st_len = st->length(); \ |
duke@435 | 245 | int new_length = len + st_len; \ |
duke@435 | 246 | if (new_length >= size()) expand(esize, new_length, _size); \ |
duke@435 | 247 | int j; \ |
duke@435 | 248 | for (j = len - 1; j >= i; j--) { \ |
duke@435 | 249 | ((etype*)_data)[j + st_len] = ((etype*)_data)[j]; \ |
duke@435 | 250 | } \ |
duke@435 | 251 | for (j = 0; j < st_len; j++) { \ |
duke@435 | 252 | ((etype*)_data)[i + j] = ((etype*)st->_data)[j]; \ |
duke@435 | 253 | } \ |
duke@435 | 254 | _length = new_length; \ |
duke@435 | 255 | } \ |
duke@435 | 256 | \ |
duke@435 | 257 | /* deprecated operations - for compatibility with GrowableArray only */ \ |
duke@435 | 258 | int capacity() const { return size(); } \ |
duke@435 | 259 | void clear() { truncate(0); } \ |
duke@435 | 260 | void trunc_to(const int length) { truncate(length); } \ |
jrose@867 | 261 | int append(const etype x) { return push(x); } \ |
duke@435 | 262 | void appendAll(const stack_name* stack) { push_all(stack); } \ |
duke@435 | 263 | etype last() const { return top(); } \ |
duke@435 | 264 | }; \ |
duke@435 | 265 | |
duke@435 | 266 | |
duke@435 | 267 | #define define_resource_list(element_type) \ |
duke@435 | 268 | define_generic_array(element_type##Array, element_type, ResourceArray) \ |
duke@435 | 269 | define_stack(element_type##List, element_type##Array) |
duke@435 | 270 | |
duke@435 | 271 | #define define_resource_pointer_list(element_type) \ |
duke@435 | 272 | define_generic_array(element_type##Array, element_type *, ResourceArray) \ |
duke@435 | 273 | define_stack(element_type##List, element_type##Array) |
duke@435 | 274 | |
duke@435 | 275 | #define define_c_heap_list(element_type) \ |
duke@435 | 276 | define_generic_array(element_type##Array, element_type, CHeapArray) \ |
duke@435 | 277 | define_stack(element_type##List, element_type##Array) |
duke@435 | 278 | |
duke@435 | 279 | #define define_c_heap_pointer_list(element_type) \ |
duke@435 | 280 | define_generic_array(element_type##Array, element_type *, CHeapArray) \ |
duke@435 | 281 | define_stack(element_type##List, element_type##Array) |
duke@435 | 282 | |
duke@435 | 283 | |
duke@435 | 284 | // Arrays for basic types |
duke@435 | 285 | |
duke@435 | 286 | define_array(boolArray, bool) define_stack(boolStack, boolArray) |
duke@435 | 287 | define_array(intArray , int ) define_stack(intStack , intArray ) |