Mercurial > hg > truffle
comparison src/share/vm/utilities/taskqueue.hpp @ 1638:b2a00dd3117c
6957084: simplify TaskQueue overflow handling
Reviewed-by: ysr, jmasa
author | jcoomes |
---|---|
date | Thu, 01 Jul 2010 21:40:45 -0700 |
parents | c18cbe5936b8 |
children | a93a9eda13f7 |
comparison
equal
deleted
inserted
replaced
1628:a00567c82f02 | 1638:b2a00dd3117c |
---|---|
1 /* | 1 /* |
2 * Copyright (c) 2001, 2009, Oracle and/or its affiliates. All rights reserved. | 2 * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * | 4 * |
5 * This code is free software; you can redistribute it and/or modify it | 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 | 6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. | 7 * published by the Free Software Foundation. |
107 } | 107 } |
108 | 108 |
109 public: | 109 public: |
110 TaskQueueSuper() : _bottom(0), _age() {} | 110 TaskQueueSuper() : _bottom(0), _age() {} |
111 | 111 |
112 // Return true if the TaskQueue contains any tasks. | 112 // Return true if the TaskQueue contains/does not contain any tasks. |
113 bool peek() { return _bottom != _age.top(); } | 113 bool peek() const { return _bottom != _age.top(); } |
114 bool is_empty() const { return size() == 0; } | |
114 | 115 |
115 // Return an estimate of the number of elements in the queue. | 116 // Return an estimate of the number of elements in the queue. |
116 // The "careful" version admits the possibility of pop_local/pop_global | 117 // The "careful" version admits the possibility of pop_local/pop_global |
117 // races. | 118 // races. |
118 uint size() const { | 119 uint size() const { |
163 // Initializes the queue to empty. | 164 // Initializes the queue to empty. |
164 GenericTaskQueue(); | 165 GenericTaskQueue(); |
165 | 166 |
166 void initialize(); | 167 void initialize(); |
167 | 168 |
168 // Push the task "t" on the queue. Returns "false" iff the queue is | 169 // Push the task "t" on the queue. Returns "false" iff the queue is full. |
169 // full. | |
170 inline bool push(E t); | 170 inline bool push(E t); |
171 | 171 |
172 // If succeeds in claiming a task (from the 'local' end, that is, the | 172 // Attempts to claim a task from the "local" end of the queue (the most |
173 // most recently pushed task), returns "true" and sets "t" to that task. | 173 // recently pushed). If successful, returns true and sets t to the task; |
174 // Otherwise, the queue is empty and returns false. | 174 // otherwise, returns false (the queue is empty). |
175 inline bool pop_local(E& t); | 175 inline bool pop_local(E& t); |
176 | 176 |
177 // If succeeds in claiming a task (from the 'global' end, that is, the | 177 // Like pop_local(), but uses the "global" end of the queue (the least |
178 // least recently pushed task), returns "true" and sets "t" to that task. | 178 // recently pushed). |
179 // Otherwise, the queue is empty and returns false. | |
180 bool pop_global(E& t); | 179 bool pop_global(E& t); |
181 | 180 |
182 // Delete any resource associated with the queue. | 181 // Delete any resource associated with the queue. |
183 ~GenericTaskQueue(); | 182 ~GenericTaskQueue(); |
184 | 183 |
196 } | 195 } |
197 | 196 |
198 template<class E, unsigned int N> | 197 template<class E, unsigned int N> |
199 void GenericTaskQueue<E, N>::initialize() { | 198 void GenericTaskQueue<E, N>::initialize() { |
200 _elems = NEW_C_HEAP_ARRAY(E, N); | 199 _elems = NEW_C_HEAP_ARRAY(E, N); |
201 guarantee(_elems != NULL, "Allocation failed."); | |
202 } | 200 } |
203 | 201 |
204 template<class E, unsigned int N> | 202 template<class E, unsigned int N> |
205 void GenericTaskQueue<E, N>::oops_do(OopClosure* f) { | 203 void GenericTaskQueue<E, N>::oops_do(OopClosure* f) { |
206 // tty->print_cr("START OopTaskQueue::oops_do"); | 204 // tty->print_cr("START OopTaskQueue::oops_do"); |
287 template<class E, unsigned int N> | 285 template<class E, unsigned int N> |
288 GenericTaskQueue<E, N>::~GenericTaskQueue() { | 286 GenericTaskQueue<E, N>::~GenericTaskQueue() { |
289 FREE_C_HEAP_ARRAY(E, _elems); | 287 FREE_C_HEAP_ARRAY(E, _elems); |
290 } | 288 } |
291 | 289 |
292 // Inherits the typedef of "Task" from above. | 290 // OverflowTaskQueue is a TaskQueue that also includes an overflow stack for |
291 // elements that do not fit in the TaskQueue. | |
292 // | |
293 // Three methods from super classes are overridden: | |
294 // | |
295 // initialize() - initialize the super classes and create the overflow stack | |
296 // push() - push onto the task queue or, if that fails, onto the overflow stack | |
297 // is_empty() - return true if both the TaskQueue and overflow stack are empty | |
298 // | |
299 // Note that size() is not overridden--it returns the number of elements in the | |
300 // TaskQueue, and does not include the size of the overflow stack. This | |
301 // simplifies replacement of GenericTaskQueues with OverflowTaskQueues. | |
302 template<class E, unsigned int N = TASKQUEUE_SIZE> | |
303 class OverflowTaskQueue: public GenericTaskQueue<E, N> | |
304 { | |
305 public: | |
306 typedef GrowableArray<E> overflow_t; | |
307 typedef GenericTaskQueue<E, N> taskqueue_t; | |
308 | |
309 OverflowTaskQueue(); | |
310 ~OverflowTaskQueue(); | |
311 void initialize(); | |
312 | |
313 inline overflow_t* overflow_stack() const { return _overflow_stack; } | |
314 | |
315 // Push task t onto the queue or onto the overflow stack. Return true. | |
316 inline bool push(E t); | |
317 | |
318 // Attempt to pop from the overflow stack; return true if anything was popped. | |
319 inline bool pop_overflow(E& t); | |
320 | |
321 inline bool taskqueue_empty() const { return taskqueue_t::is_empty(); } | |
322 inline bool overflow_empty() const { return overflow_stack()->is_empty(); } | |
323 inline bool is_empty() const { | |
324 return taskqueue_empty() && overflow_empty(); | |
325 } | |
326 | |
327 private: | |
328 overflow_t* _overflow_stack; | |
329 }; | |
330 | |
331 template <class E, unsigned int N> | |
332 OverflowTaskQueue<E, N>::OverflowTaskQueue() | |
333 { | |
334 _overflow_stack = NULL; | |
335 } | |
336 | |
337 template <class E, unsigned int N> | |
338 OverflowTaskQueue<E, N>::~OverflowTaskQueue() | |
339 { | |
340 if (_overflow_stack != NULL) { | |
341 delete _overflow_stack; | |
342 _overflow_stack = NULL; | |
343 } | |
344 } | |
345 | |
346 template <class E, unsigned int N> | |
347 void OverflowTaskQueue<E, N>::initialize() | |
348 { | |
349 taskqueue_t::initialize(); | |
350 assert(_overflow_stack == NULL, "memory leak"); | |
351 _overflow_stack = new (ResourceObj::C_HEAP) GrowableArray<E>(10, true); | |
352 } | |
353 | |
354 template <class E, unsigned int N> | |
355 bool OverflowTaskQueue<E, N>::push(E t) | |
356 { | |
357 if (!taskqueue_t::push(t)) { | |
358 overflow_stack()->push(t); | |
359 } | |
360 return true; | |
361 } | |
362 | |
363 template <class E, unsigned int N> | |
364 bool OverflowTaskQueue<E, N>::pop_overflow(E& t) | |
365 { | |
366 if (overflow_empty()) return false; | |
367 t = overflow_stack()->pop(); | |
368 return true; | |
369 } | |
370 | |
293 class TaskQueueSetSuper: public CHeapObj { | 371 class TaskQueueSetSuper: public CHeapObj { |
294 protected: | 372 protected: |
295 static int randomParkAndMiller(int* seed0); | 373 static int randomParkAndMiller(int* seed0); |
296 public: | 374 public: |
297 // Returns "true" if some TaskQueue in the set contains a task. | 375 // Returns "true" if some TaskQueue in the set contains a task. |
321 | 399 |
322 void register_queue(uint i, T* q); | 400 void register_queue(uint i, T* q); |
323 | 401 |
324 T* queue(uint n); | 402 T* queue(uint n); |
325 | 403 |
326 // The thread with queue number "queue_num" (and whose random number seed | 404 // The thread with queue number "queue_num" (and whose random number seed is |
327 // is at "seed") is trying to steal a task from some other queue. (It | 405 // at "seed") is trying to steal a task from some other queue. (It may try |
328 // may try several queues, according to some configuration parameter.) | 406 // several queues, according to some configuration parameter.) If some steal |
329 // If some steal succeeds, returns "true" and sets "t" the stolen task, | 407 // succeeds, returns "true" and sets "t" to the stolen task, otherwise returns |
330 // otherwise returns false. | 408 // false. |
331 bool steal(uint queue_num, int* seed, E& t); | 409 bool steal(uint queue_num, int* seed, E& t); |
332 | 410 |
333 bool peek(); | 411 bool peek(); |
334 }; | 412 }; |
335 | 413 |
505 template<class E, unsigned int N> inline bool | 583 template<class E, unsigned int N> inline bool |
506 GenericTaskQueue<E, N>::pop_local(E& t) { | 584 GenericTaskQueue<E, N>::pop_local(E& t) { |
507 uint localBot = _bottom; | 585 uint localBot = _bottom; |
508 // This value cannot be N-1. That can only occur as a result of | 586 // This value cannot be N-1. That can only occur as a result of |
509 // the assignment to bottom in this method. If it does, this method | 587 // the assignment to bottom in this method. If it does, this method |
510 // resets the size( to 0 before the next call (which is sequential, | 588 // resets the size to 0 before the next call (which is sequential, |
511 // since this is pop_local.) | 589 // since this is pop_local.) |
512 uint dirty_n_elems = dirty_size(localBot, _age.top()); | 590 uint dirty_n_elems = dirty_size(localBot, _age.top()); |
513 assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); | 591 assert(dirty_n_elems != N - 1, "Shouldn't be possible..."); |
514 if (dirty_n_elems == 0) return false; | 592 if (dirty_n_elems == 0) return false; |
515 localBot = decrement_index(localBot); | 593 localBot = decrement_index(localBot); |
531 // path. | 609 // path. |
532 return pop_local_slow(localBot, _age.get()); | 610 return pop_local_slow(localBot, _age.get()); |
533 } | 611 } |
534 } | 612 } |
535 | 613 |
536 typedef oop Task; | 614 typedef GenericTaskQueue<oop> OopTaskQueue; |
537 typedef GenericTaskQueue<Task> OopTaskQueue; | |
538 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet; | 615 typedef GenericTaskQueueSet<OopTaskQueue> OopTaskQueueSet; |
539 | 616 |
540 #ifdef _MSC_VER | 617 #ifdef _MSC_VER |
541 #pragma warning(push) | 618 #pragma warning(push) |
542 // warning C4522: multiple assignment operators specified | 619 // warning C4522: multiple assignment operators specified |
613 | 690 |
614 #ifdef _MSC_VER | 691 #ifdef _MSC_VER |
615 #pragma warning(pop) | 692 #pragma warning(pop) |
616 #endif | 693 #endif |
617 | 694 |
618 typedef GenericTaskQueue<StarTask> OopStarTaskQueue; | 695 typedef OverflowTaskQueue<StarTask> OopStarTaskQueue; |
619 typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet; | 696 typedef GenericTaskQueueSet<OopStarTaskQueue> OopStarTaskQueueSet; |
620 | 697 |
621 typedef size_t RegionTask; // index for region | 698 typedef OverflowTaskQueue<size_t> RegionTaskQueue; |
622 typedef GenericTaskQueue<RegionTask> RegionTaskQueue; | 699 typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet; |
623 typedef GenericTaskQueueSet<RegionTaskQueue> RegionTaskQueueSet; | |
624 | |
625 class RegionTaskQueueWithOverflow: public CHeapObj { | |
626 protected: | |
627 RegionTaskQueue _region_queue; | |
628 GrowableArray<RegionTask>* _overflow_stack; | |
629 | |
630 public: | |
631 RegionTaskQueueWithOverflow() : _overflow_stack(NULL) {} | |
632 // Initialize both stealable queue and overflow | |
633 void initialize(); | |
634 // Save first to stealable queue and then to overflow | |
635 void save(RegionTask t); | |
636 // Retrieve first from overflow and then from stealable queue | |
637 bool retrieve(RegionTask& region_index); | |
638 // Retrieve from stealable queue | |
639 bool retrieve_from_stealable_queue(RegionTask& region_index); | |
640 // Retrieve from overflow | |
641 bool retrieve_from_overflow(RegionTask& region_index); | |
642 bool is_empty(); | |
643 bool stealable_is_empty(); | |
644 bool overflow_is_empty(); | |
645 uint stealable_size() { return _region_queue.size(); } | |
646 RegionTaskQueue* task_queue() { return &_region_queue; } | |
647 }; | |
648 | |
649 #define USE_RegionTaskQueueWithOverflow |