Mercurial > hg > graal-jvmci-8

comparison src/share/vm/utilities/taskqueue.hpp @ 12087:61521bd65100

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
8022784: TaskQueue misses minimal documentation and references for analysis Summary: Add appropriate documentation and references to publication to allow easier analysis of the TaskQueue implementation. Reviewed-by: dholmes, ehelin
author tschatzl
date Wed, 21 Aug 2013 10:32:02 +0200
parents cd25d3be91c5
children 190899198332 e2722a66aba7
comparison
equal deleted inserted replaced
12086:31f220c1f789 12087:61521bd65100
1 /* 1 /*
2 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. 2 * Copyright (c) 2001, 2013, 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.
130 void TaskQueueStats::reset() { 130 void TaskQueueStats::reset() {
131 memset(_stats, 0, sizeof(_stats)); 131 memset(_stats, 0, sizeof(_stats));
132 } 132 }
133 #endif // TASKQUEUE_STATS 133 #endif // TASKQUEUE_STATS
134 134
135 // TaskQueueSuper collects functionality common to all GenericTaskQueue instances.
136
135 template <unsigned int N, MEMFLAGS F> 137 template <unsigned int N, MEMFLAGS F>
136 class TaskQueueSuper: public CHeapObj<F> { 138 class TaskQueueSuper: public CHeapObj<F> {
137 protected: 139 protected:
138 // Internal type for indexing the queue; also used for the tag. 140 // Internal type for indexing the queue; also used for the tag.
139 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t; 141 typedef NOT_LP64(uint16_t) LP64_ONLY(uint32_t) idx_t;
247 static const uint total_size() { return N; } 249 static const uint total_size() { return N; }
248 250
249 TASKQUEUE_STATS_ONLY(TaskQueueStats stats;) 251 TASKQUEUE_STATS_ONLY(TaskQueueStats stats;)
250 }; 252 };
251 253
252 254 //
255 // GenericTaskQueue implements an ABP, Aurora-Blumofe-Plaxton, double-
256 // ended-queue (deque), intended for use in work stealing. Queue operations
257 // are non-blocking.
258 //
259 // A queue owner thread performs push() and pop_local() operations on one end
260 // of the queue, while other threads may steal work using the pop_global()
261 // method.
262 //
263 // The main difference to the original algorithm is that this
264 // implementation allows wrap-around at the end of its allocated
265 // storage, which is an array.
266 //
267 // The original paper is:
268 //
269 // Arora, N. S., Blumofe, R. D., and Plaxton, C. G.
270 // Thread scheduling for multiprogrammed multiprocessors.
271 // Theory of Computing Systems 34, 2 (2001), 115-144.
272 //
273 // The following paper provides an correctness proof and an
274 // implementation for weakly ordered memory models including (pseudo-)
275 // code containing memory barriers for a Chase-Lev deque. Chase-Lev is
276 // similar to ABP, with the main difference that it allows resizing of the
277 // underlying storage:
278 //
279 // Le, N. M., Pop, A., Cohen A., and Nardell, F. Z.
280 // Correct and efficient work-stealing for weak memory models
281 // Proceedings of the 18th ACM SIGPLAN symposium on Principles and
282 // practice of parallel programming (PPoPP 2013), 69-80
283 //
253 284
254 template <class E, MEMFLAGS F, unsigned int N = TASKQUEUE_SIZE> 285 template <class E, MEMFLAGS F, unsigned int N = TASKQUEUE_SIZE>
255 class GenericTaskQueue: public TaskQueueSuper<N, F> { 286 class GenericTaskQueue: public TaskQueueSuper<N, F> {
256 ArrayAllocator<E, F> _array_allocator; 287 ArrayAllocator<E, F> _array_allocator;
257 protected: 288 protected: