Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1892033003:
TaskScheduler [10] SchedulerWorkerThreadStack (Closed)
DescriptionTaskScheduler [10] SchedulerWorkerThreadStack
A stack of SchedulerWorkerThreads. Supports removal of arbitrary
SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted
multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is
amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n).
Removal of arbitrary elements is required to be able to remove a worker
thread from the stack when it is woken up to run single-threaded tasks.
BUG=553459
Committed: https://crrev.com/e7839991aabb3d5e79e971177e78640ed88d940f
Cr-Commit-Position: refs/heads/master@{#389382}
Patch Set 1 #Patch Set 2 : use bitfield to determine whether an element is on the stack #
Total comments: 8
Patch Set 3 : self review #Patch Set 4 : self review #
Total comments: 6
Patch Set 5 : CR robliao #19 #Patch Set 6 : rebase #Patch Set 7 : stop using a bitfield #
Total comments: 6
Patch Set 8 : CR robliao #24 (SchedulerUniqueStack + nit) #
Total comments: 2
Patch Set 9 : CR robliao #26 (simplify a comment) #Patch Set 10 : rebase #Patch Set 11 : use SchedulerUniqueStack in STP #
Total comments: 6
Patch Set 12 : CR gab (improve comment) #
Total comments: 4
Patch Set 13 : CR danakj #41 (no template) #Patch Set 14 : remove old file #
Total comments: 4
Patch Set 15 : fix typo #Patch Set 16 : CR danakj #44 (Empty -> IsEmpty) #
Dependent Patchsets: Messages
Total messages: 60 (23 generated)
fdoray@chromium.org changed reviewers: + gab@chromium.org, robliao@chromium.org
Can you review this CL? See how this will be used in https://codereview.chromium.org/1895513002/. Thanks!
On 2016/04/15 18:48:47, fdoray wrote: > Can you review this CL? See how this will be used in > https://codereview.chromium.org/1895513002/. Thanks! Can we use a std::vector to get this behavior? I don't think we have so many idle threads that removals will be slow.
On 2016/04/15 20:04:17, robliao wrote: > On 2016/04/15 18:48:47, fdoray wrote: > > Can you review this CL? See how this will be used in > > https://codereview.chromium.org/1895513002/. Thanks! > > Can we use a std::vector to get this behavior? I don't think we have so many > idle threads that removals will be slow. Yes, we could use an std::vector. Combined with an std::unordered_set to be able to verify quickly whether an element is on the stack? That way, Push() stays O(1) and Remove() is O(1) when the element to remove is not on the stack. SchedulerStack::Remove will be called each time that a Sequence is returned by GetWork https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... I could improve the code to avoid the unnecessary calls (when the worker thread is already not on the stack).
On 2016/04/15 22:03:08, fdoray wrote: > On 2016/04/15 20:04:17, robliao wrote: > > On 2016/04/15 18:48:47, fdoray wrote: > > > Can you review this CL? See how this will be used in > > > https://codereview.chromium.org/1895513002/. Thanks! > > > > Can we use a std::vector to get this behavior? I don't think we have so many > > idle threads that removals will be slow. > > Yes, we could use an std::vector. Combined with an std::unordered_set to be able > to verify quickly whether an element is on the stack? That way, Push() stays > O(1) and Remove() is O(1) when the element to remove is not on the stack. > > SchedulerStack::Remove will be called each time that a Sequence is returned by > GetWork > https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... > I could improve the code to avoid the unnecessary calls (when the worker thread > is already not on the stack).
On 2016/04/15 22:07:23, robliao wrote: > On 2016/04/15 22:03:08, fdoray wrote: > > On 2016/04/15 20:04:17, robliao wrote: > > > On 2016/04/15 18:48:47, fdoray wrote: > > > > Can you review this CL? See how this will be used in > > > > https://codereview.chromium.org/1895513002/. Thanks! > > > > > > Can we use a std::vector to get this behavior? I don't think we have so many > > > idle threads that removals will be slow. > > > > Yes, we could use an std::vector. Combined with an std::unordered_set to be > able > > to verify quickly whether an element is on the stack? That way, Push() stays > > O(1) and Remove() is O(1) when the element to remove is not on the stack. > > > > SchedulerStack::Remove will be called each time that a Sequence is returned by > > GetWork > > > https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... > > I could improve the code to avoid the unnecessary calls (when the worker > thread > > is already not on the stack). Ahh, rietveld. Is an O(n) for small n demonstrably slower than a lookup in std::unordered_set? The nice part about std::vector is that all of the elements stay together. For unordered_set, you may have to traverse.
On 2016/04/15 22:10:06, robliao wrote: > On 2016/04/15 22:07:23, robliao wrote: > > On 2016/04/15 22:03:08, fdoray wrote: > > > On 2016/04/15 20:04:17, robliao wrote: > > > > On 2016/04/15 18:48:47, fdoray wrote: > > > > > Can you review this CL? See how this will be used in > > > > > https://codereview.chromium.org/1895513002/. Thanks! > > > > > > > > Can we use a std::vector to get this behavior? I don't think we have so > many > > > > idle threads that removals will be slow. > > > > > > Yes, we could use an std::vector. Combined with an std::unordered_set to be > > able > > > to verify quickly whether an element is on the stack? That way, Push() stays > > > O(1) and Remove() is O(1) when the element to remove is not on the stack. > > > > > > SchedulerStack::Remove will be called each time that a Sequence is returned > by > > > GetWork > > > > > > https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... > > > I could improve the code to avoid the unnecessary calls (when the worker > > thread > > > is already not on the stack). > > Ahh, rietveld. > > Is an O(n) for small n demonstrably slower than a lookup in std::unordered_set? > The nice part about std::vector is that all of the elements stay together. For > unordered_set, you may have to traverse. You're right, lookup in an std::vector with std::find is faster than lookup in an std::unordered_set when n <= 16. Lookup in a bitfield is even faster. We could use that solution if we decide that the number of threads per thread pool is always <= 64 and we assign and index to each thread. Benchmarks with Visual Studio builds on a Z840. The containers contain all elements in [1, n]. 500 million lookups for elements that are in the container. n=1 n=2 n=4 n=8 n=16 n=64 vector 625 1187 1699 1980 2004 9446 (milliseconds) unordered_set 3625 3699 3910 4360 4752 4420 (milliseconds) uint64_t bitfield 504 500 500 560 579 580 (milliseconds)
On 2016/04/18 14:06:32, fdoray wrote: > On 2016/04/15 22:10:06, robliao wrote: > > On 2016/04/15 22:07:23, robliao wrote: > > > On 2016/04/15 22:03:08, fdoray wrote: > > > > On 2016/04/15 20:04:17, robliao wrote: > > > > > On 2016/04/15 18:48:47, fdoray wrote: > > > > > > Can you review this CL? See how this will be used in > > > > > > https://codereview.chromium.org/1895513002/. Thanks! > > > > > > > > > > Can we use a std::vector to get this behavior? I don't think we have so > > many > > > > > idle threads that removals will be slow. > > > > > > > > Yes, we could use an std::vector. Combined with an std::unordered_set to > be > > > able > > > > to verify quickly whether an element is on the stack? That way, Push() > stays > > > > O(1) and Remove() is O(1) when the element to remove is not on the stack. > > > > > > > > SchedulerStack::Remove will be called each time that a Sequence is > returned > > by > > > > GetWork > > > > > > > > > > https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... > > > > I could improve the code to avoid the unnecessary calls (when the worker > > > thread > > > > is already not on the stack). > > > > Ahh, rietveld. > > > > Is an O(n) for small n demonstrably slower than a lookup in > std::unordered_set? > > The nice part about std::vector is that all of the elements stay together. For > > unordered_set, you may have to traverse. You're right, lookup in an std::vector with std::find is faster than lookup in an std::unordered_set when n <= 16. Lookup in a bitfield is even faster. We could use that solution if we decide that the number of threads per thread pool is always <= 64 and we assign and index to each thread. Benchmarks with Visual Studio builds on a Z840. The containers contain all elements in [1, n]. 500 million lookups for elements that are in the container. n=1 n=2 n=4 n=8 n=16 n=32 n=64 vector 625 1187 1699 1980 2004 5412 9446 (milliseconds) unordered_set 3625 3699 3910 4360 4752 4522 4420 (milliseconds) uint64_t bitfield 504 500 500 560 579 583 580 (milliseconds)
On 2016/04/18 14:10:01, fdoray wrote: > On 2016/04/18 14:06:32, fdoray wrote: > > On 2016/04/15 22:10:06, robliao wrote: > > > On 2016/04/15 22:07:23, robliao wrote: > > > > On 2016/04/15 22:03:08, fdoray wrote: > > > > > On 2016/04/15 20:04:17, robliao wrote: > > > > > > On 2016/04/15 18:48:47, fdoray wrote: > > > > > > > Can you review this CL? See how this will be used in > > > > > > > https://codereview.chromium.org/1895513002/. Thanks! > > > > > > > > > > > > Can we use a std::vector to get this behavior? I don't think we have > so > > > many > > > > > > idle threads that removals will be slow. > > > > > > > > > > Yes, we could use an std::vector. Combined with an std::unordered_set to > > be > > > > able > > > > > to verify quickly whether an element is on the stack? That way, Push() > > stays > > > > > O(1) and Remove() is O(1) when the element to remove is not on the > stack. > > > > > > > > > > SchedulerStack::Remove will be called each time that a Sequence is > > returned > > > by > > > > > GetWork > > > > > > > > > > > > > > > https://codereview.chromium.org/1895513002/diff/1/base/task_scheduler/schedul... > > > > > I could improve the code to avoid the unnecessary calls (when the worker > > > > thread > > > > > is already not on the stack). > > > > > > Ahh, rietveld. > > > > > > Is an O(n) for small n demonstrably slower than a lookup in > > std::unordered_set? > > > The nice part about std::vector is that all of the elements stay together. > For > > > unordered_set, you may have to traverse. > > You're right, lookup in an std::vector with std::find is faster than lookup in > an std::unordered_set when n <= 16. > > Lookup in a bitfield is even faster. We could use that solution if we decide > that the number of threads per thread pool is always <= 64 and we assign and > index to each thread. > > Benchmarks with Visual Studio builds on a Z840. The containers contain all > elements in [1, n]. 500 million lookups for elements that are in the container. > > n=1 n=2 n=4 n=8 n=16 n=32 n=64 > vector 625 1187 1699 1980 2004 5412 9446 (milliseconds) > unordered_set 3625 3699 3910 4360 4752 4522 4420 (milliseconds) > uint64_t bitfield 504 500 500 560 579 583 580 (milliseconds) If a bitfeld doesn't complicate the solution too much, sounds like we should use that!
Description was changed from ========== TaskScheduler [12] SchedulerStack A stack that supports removal of arbitrary elements in amortized constant time and doesn't allow multiple insertions of the same element. Will be used for the stack of idle threads in SchedulerThreadPool. BUG=553459 ========== to ========== TaskScheduler [12] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. BUG=553459 ==========
Description was changed from ========== TaskScheduler [12] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. BUG=553459 ==========
Can you take another look? Thanks.
bitfield approach sgtm, please augment CL description with reasoning behind current approach. Also please add a mention in CL desc of how it will be used (not just where) -- I assume it will be used to store indices of worker threads in another vector? https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.cc (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:24: bit_field_ |= 1ULL << val; Don't think it's guaranteed that ULL will always be a uint64_t, how about a static_cast<uint64_t>(1U)? Or even "constexpr uint64_t bit = 1U; bit_field |= bit << val;" https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:43: stack_.erase(it); Lines 41+43 are O(2n) :-(. Can we make Remove() constant by simply invalidating the |bit_field_| and then Pop() becomes amortized-O(1) instead of pure-O(1) but that's okay (could also make a purge pass if push is invoked when stack_.size() == 64). https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.h (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.h:19: // allow multiple insertions of the same value. This class is NOT thread-safe. Add a note about what makes this special (performance wise and why it's only [0,63])? https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack_unittest.cc (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack_unittest.cc:109: for (int i = 63; i >= 0; --i) { Remove in increasing order to test that it works in non-stack order.
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. This allows Remove() to run in constant time when the value to remove is not on the stack. Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread on top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. This allows Remove() to run in constant time when the value to remove is not on the stack. Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread on top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. Remove() just updates the bit field and thus runs in constant time. Pop() pops values from a vector until it finds one whose bit is set in the bit field. It runs in amortized constant time. Push() pushes a value at the end of a vector. If the size of the vector becomes greater than 64, it removes all values whose bit isn't set in the bit field to prevent it from growing indefinitely. Push() runs in amortized constant time. Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. Remove() just updates the bit field and thus runs in constant time. Pop() pops values from a vector until it finds one whose bit is set in the bit field. It runs in amortized constant time. Push() pushes a value at the end of a vector. If the size of the vector becomes greater than 64, it removes all values whose bit isn't set in the bit field to prevent it from growing indefinitely. Push() runs in amortized constant time. Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. Remove() just updates the bit field and thus runs in O(1). Pop() pops values from a vector until it finds one whose bit is set in the bit field. It runs in O(1 + x) where x is the number of values removed from the stack since the last Pop(). Push() pushes a value at the end of a vector. If the size of the vector becomes greater than 64, it removes all values whose bit isn't set in the bit field to prevent it from growing indefinitely. Push() runs in amortized O(1). Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ==========
Can you take another look? Thanks. https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.cc (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:24: bit_field_ |= 1ULL << val; On 2016/04/18 18:35:40, gab wrote: > Don't think it's guaranteed that ULL will always be a uint64_t, how about a > static_cast<uint64_t>(1U)? Or even "constexpr uint64_t bit = 1U; bit_field |= > bit << val;" Done. https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:43: stack_.erase(it); On 2016/04/18 18:35:40, gab wrote: > Lines 41+43 are O(2n) :-(. Can we make Remove() constant by simply invalidating > the |bit_field_| and then Pop() becomes amortized-O(1) instead of pure-O(1) but > that's okay (could also make a purge pass if push is invoked when stack_.size() > == 64). Done. https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.h (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.h:19: // allow multiple insertions of the same value. This class is NOT thread-safe. On 2016/04/18 18:35:40, gab wrote: > Add a note about what makes this special (performance wise and why it's only > [0,63])? Done. https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack_unittest.cc (right): https://codereview.chromium.org/1892033003/diff/20001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack_unittest.cc:109: for (int i = 63; i >= 0; --i) { On 2016/04/18 18:35:40, gab wrote: > Remove in increasing order to test that it works in non-stack order. Done.
To use this stack, we'll need to associate an index with each worker thread. I plan to add an |index| argument to the constructor of SWT. That index would be stored in a member of SWT and accessible via a public accessor. Having a map SWT*->index in STP wouldn't make sense; the reason why we use a bit field and indexes is to avoid an std::unordered_set lookup. Other use for the index: naming threads (e.g. "HighPriorityFileIO/1").
Nice! https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.cc (right): https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:42: DCHECK(!BitIsSet(bit_field_, val)); Let's add a message: DCHECK(..) << "Value already on stack". https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:49: BitIsSetPredicate(bit_field_)), Instead of predicate, this may be clearer as a lambda. https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:79: --size_; It's worthwhile to note somewhere that an index on the stack doesn't necessarily mean the bit is set.
robliao@/gab@: Done. Can you take another look? https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... File base/task_scheduler/scheduler_stack.cc (right): https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:42: DCHECK(!BitIsSet(bit_field_, val)); On 2016/04/19 00:41:16, robliao wrote: > Let's add a message: DCHECK(..) << "Value already on stack". Done. https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:49: BitIsSetPredicate(bit_field_)), On 2016/04/19 00:41:16, robliao wrote: > Instead of predicate, this may be clearer as a lambda. Done. https://codereview.chromium.org/1892033003/diff/60001/base/task_scheduler/sch... base/task_scheduler/scheduler_stack.cc:79: --size_; On 2016/04/19 00:41:16, robliao wrote: > It's worthwhile to note somewhere that an index on the stack doesn't necessarily > mean the bit is set. Done, in scheduler_stack.h above |stack_|.
We discussed offline with Francois: The speed benefits being in nanoseconds, being "4X faster" doesn't change anything when compared to running the next task. To avoid the complexity of having to keep WorkerThread indices around in the user of SchedulerStack we decided to go with a simpler version (i.e. using std::vector). Will block my review on the upload of that, thanks!
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack of integers in [0, 63]. Supports removal of arbitrary values. Doesn't allow multiple insertions of the same value. Maintains a bit field that indicates whether a value is on the stack. Remove() just updates the bit field and thus runs in O(1). Pop() pops values from a vector until it finds one whose bit is set in the bit field. It runs in O(1 + x) where x is the number of values removed from the stack since the last Pop(). Push() pushes a value at the end of a vector. If the size of the vector becomes greater than 64, it removes all values whose bit isn't set in the bit field to prevent it from growing indefinitely. Push() runs in amortized O(1). Will be used for the stack of idle threads in SchedulerThreadPool. The values on the stack will be indexes in |worker_threads_|. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, its index is pushed on the stack. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, it will be pushed on the stack. BUG=553459 ==========
robliao@/gab@: Can you review this CL? Thanks. I used a template because it allows SchedulerStack to be tested without creating real SchedulerWorkerThreads.
https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... File base/task_scheduler/scheduler_stack.h (right): https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:21: Remove extra linebreak. https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:24: class SchedulerStack { Given that this doesn't allow multiple insertions of the same value, maybe SchedulerUniqueStack? https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:35: T Pop(); Would peek be a useful operation that we may use in the future?
robliao@: Done. Can you take another look? gab@: Can you review this CL? https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... File base/task_scheduler/scheduler_stack.h (right): https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:21: On 2016/04/20 20:54:58, robliao wrote: > Remove extra linebreak. Done. https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:24: class SchedulerStack { On 2016/04/20 20:54:58, robliao wrote: > Given that this doesn't allow multiple insertions of the same value, maybe > SchedulerUniqueStack? Done. https://codereview.chromium.org/1892033003/diff/120001/base/task_scheduler/sc... base/task_scheduler/scheduler_stack.h:35: T Pop(); On 2016/04/20 20:54:58, robliao wrote: > Would peek be a useful operation that we may use in the future? We don't need it currently. With this API, we can do stack.Pop()->WakeUp() I prefer not to add methods that aren't used.
lgtm https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:35: // Removes |val| from the stack if it was on it. Nit: // Removes |val| form the stack. is sufficient.
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, a thread will be popped from the stack and woken up. When single-threaded work is posted, the appropriate thread will be removed from the stack and woken up (it's not necessarily the thread at the top of the stack). When a thread stops getting work from its delegate, it will be pushed on the stack. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, the thread at the top of the stack is popped and woken up. When single-threaded work is posted, the appropriate thread is removed from the stack and woken up (it's not necessarily at the top of the stack). BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, the thread at the top of the stack is popped and woken up. When single-threaded work is posted, the appropriate thread is removed from the stack and woken up (it's not necessarily at the top of the stack). BUG=553459 ========== to ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, the thread at the top of the stack is popped and woken up. When single-threaded work is posted, the appropriate thread is removed from the stack and woken up (it's not necessarily at the top of the stack). BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Will be used for the stack of idle threads in SchedulerThreadPool. When shared work is posted, the thread at the top of the stack is popped and woken up. When single-threaded work is posted, the appropriate thread is removed from the stack and woken up (it's not necessarily at the top of the stack). BUG=553459 ========== to ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-thread tasks. BUG=553459 ==========
Description was changed from ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-thread tasks. BUG=553459 ========== to ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ==========
https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:35: // Removes |val| from the stack if it was on it. On 2016/04/20 21:18:40, robliao wrote: > Nit: // Removes |val| form the stack. > is sufficient. Done.
On 2016/04/21 15:34:11, fdoray wrote: > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > File base/task_scheduler/scheduler_unique_stack.h (right): > > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > base/task_scheduler/scheduler_unique_stack.h:35: // Removes |val| from the stack > if it was on it. > On 2016/04/20 21:18:40, robliao wrote: > > Nit: // Removes |val| form the stack. > > is sufficient. > > Done. Is the STP addition intentional for this CL?
On 2016/04/21 17:20:57, robliao wrote: > On 2016/04/21 15:34:11, fdoray wrote: > > > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > > File base/task_scheduler/scheduler_unique_stack.h (right): > > > > > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > > base/task_scheduler/scheduler_unique_stack.h:35: // Removes |val| from the > stack > > if it was on it. > > On 2016/04/20 21:18:40, robliao wrote: > > > Nit: // Removes |val| form the stack. > > > is sufficient. > > > > Done. > > Is the STP addition intentional for this CL? Yes. danakj@ prefers when I use the new components that I introduce.
On 2016/04/21 17:22:04, fdoray wrote: > On 2016/04/21 17:20:57, robliao wrote: > > On 2016/04/21 15:34:11, fdoray wrote: > > > > > > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > > > File base/task_scheduler/scheduler_unique_stack.h (right): > > > > > > > > > https://codereview.chromium.org/1892033003/diff/140001/base/task_scheduler/sc... > > > base/task_scheduler/scheduler_unique_stack.h:35: // Removes |val| from the > > stack > > > if it was on it. > > > On 2016/04/20 21:18:40, robliao wrote: > > > > Nit: // Removes |val| form the stack. > > > > is sufficient. > > > > > > Done. > > > > Is the STP addition intentional for this CL? > > Yes. danakj@ prefers when I use the new components that I introduce. Gotcha. For future changelists, let's keep the usage up front/call out in the publish mail when new functionality is added. It's unexpected to introduce new things after a l-g-t-m.
Description was changed from ========== TaskScheduler [11] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ========== to ========== TaskScheduler [10] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ==========
lgtm
lgtm w/ comment requests, thanks! https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:8: #include <stddef.h> Was that for int64 or is it still required? https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:20: // insertions of the same value. This class is NOT thread-safe. "doesn't allow multiple insertions of the same value" makes it sound like adding the same value twice will be ignored whereas it's a mere DCHECK+proceed. So the "unique" property of the stack is not algorithmic, it's merely a contract, can this comment reflect that better? https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:20: // insertions of the same value. This class is NOT thread-safe. Expand this comment to explain the performance characteristics of this stack.
fdoray@chromium.org changed reviewers: + danakj@chromium.org
danakj@: Can you review this CL? We have a more efficient implementation (see patch set 6), but we prefer to land simple code and optimize later if we find that this is a real performance bottleneck. Thanks! CLs to review (in order): - https://codereview.chromium.org/1892033003/ SchedulerUniqueStack - https://codereview.chromium.org/1906083002/ Remove base/task_scheduler/utils.h/.cc - https://codereview.chromium.org/1903103007/ Make SchedulerWorkerThread own its delegate. - https://codereview.chromium.org/1906813003/ TimeDelta instead of TimeTicks in Task's constructor. - https://codereview.chromium.org/1876363004/ Support ExecutionMode::SINGLE_THREADED. https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:8: #include <stddef.h> On 2016/04/22 17:07:04, gab wrote: > Was that for int64 or is it still required? It's required for size_t. http://en.cppreference.com/w/cpp/types/size_t https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:20: // insertions of the same value. This class is NOT thread-safe. On 2016/04/22 17:07:04, gab wrote: > Expand this comment to explain the performance characteristics of this stack. Done. https://codereview.chromium.org/1892033003/diff/200001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:20: // insertions of the same value. This class is NOT thread-safe. On 2016/04/22 17:07:04, gab wrote: > "doesn't allow multiple insertions of the same value" makes it sound like adding > the same value twice will be ignored whereas it's a mere DCHECK+proceed. > > So the "unique" property of the stack is not algorithmic, it's merely a > contract, can this comment reflect that better? Done.
https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:22: template <typename T> Are you going to use this for more than worker threads? Don't template it if not, and move the implementation to a .cc file https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:67: const T val = stack_.back(); std::move, tho that may not make sense once this isnt templated
Description was changed from ========== TaskScheduler [10] SchedulerUniqueStack A stack that supports removal of arbitrary values and doesn't allow multiple insertions of the same value. Removal of arbitrary values is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ========== to ========== TaskScheduler [10] SchedulerWorkerThreadStack A stack of SchedulerWorkerThreads. Supports removal of arbitrary SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n). Removal of arbitrary elements is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ==========
danakj@: Can you take another look? Thanks. https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... File base/task_scheduler/scheduler_unique_stack.h (right): https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:22: template <typename T> On 2016/04/22 18:44:47, danakj wrote: > Are you going to use this for more than worker threads? Don't template it if > not, and move the implementation to a .cc file Done. Template was nice to test without instantiating SchedulerWorkerThreads. https://codereview.chromium.org/1892033003/diff/220001/base/task_scheduler/sc... base/task_scheduler/scheduler_unique_stack.h:67: const T val = stack_.back(); On 2016/04/22 18:44:47, danakj wrote: > std::move, tho that may not make sense once this isnt templated Doesn't make sense now that this isn't templated.
LGTM https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... File base/task_scheduler/scheduler_worker_thread_stack.cc (right): https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... base/task_scheduler/scheduler_worker_thread_stack.cc:25: if (Empty()) nit: usually contains DCHECK this and expect the caller to check IsEmpty() instead, this is ok too tho if you prefer https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... File base/task_scheduler/scheduler_worker_thread_stack.h (right): https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... base/task_scheduler/scheduler_worker_thread_stack.h:45: bool Empty() const { return stack_.empty(); } IsEmpty
https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... File base/task_scheduler/scheduler_worker_thread_stack.cc (right): https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... base/task_scheduler/scheduler_worker_thread_stack.cc:25: if (Empty()) On 2016/04/22 21:08:12, danakj wrote: > nit: usually contains DCHECK this and expect the caller to check IsEmpty() > instead, this is ok too tho if you prefer I prefer keeping this as-is because it requires less code at the call site. https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... File base/task_scheduler/scheduler_worker_thread_stack.h (right): https://codereview.chromium.org/1892033003/diff/260001/base/task_scheduler/sc... base/task_scheduler/scheduler_worker_thread_stack.h:45: bool Empty() const { return stack_.empty(); } On 2016/04/22 21:08:12, danakj wrote: > IsEmpty Done.
The CQ bit was checked by fdoray@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from robliao@chromium.org, gab@chromium.org, danakj@chromium.org Link to the patchset: https://codereview.chromium.org/1892033003/#ps300001 (title: "CR danakj #44 (Empty -> IsEmpty)")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1892033003/300001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1892033003/300001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: win_chromium_x64_rel_ng on tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)
The CQ bit was checked by fdoray@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1892033003/300001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1892033003/300001
The CQ bit was unchecked by commit-bot@chromium.org
Try jobs failed on following builders: win_chromium_x64_rel_ng on tryserver.chromium.win (JOB_FAILED, http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)
The CQ bit was checked by fdoray@chromium.org
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1892033003/300001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1892033003/300001
Message was sent while issue was closed.
Description was changed from ========== TaskScheduler [10] SchedulerWorkerThreadStack A stack of SchedulerWorkerThreads. Supports removal of arbitrary SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n). Removal of arbitrary elements is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ========== to ========== TaskScheduler [10] SchedulerWorkerThreadStack A stack of SchedulerWorkerThreads. Supports removal of arbitrary SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n). Removal of arbitrary elements is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ==========
Message was sent while issue was closed.
Committed patchset #16 (id:300001)
Message was sent while issue was closed.
Description was changed from ========== TaskScheduler [10] SchedulerWorkerThreadStack A stack of SchedulerWorkerThreads. Supports removal of arbitrary SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n). Removal of arbitrary elements is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 ========== to ========== TaskScheduler [10] SchedulerWorkerThreadStack A stack of SchedulerWorkerThreads. Supports removal of arbitrary SchedulerWorkerThreads. DCHECKs when a SchedulerWorkerThread is inserted multiple times. SchedulerWorkerThreads are not owned by the stack. Push() is amortized O(1). Pop(), Size() and Empty() are O(1). Remove is O(n). Removal of arbitrary elements is required to be able to remove a worker thread from the stack when it is woken up to run single-threaded tasks. BUG=553459 Committed: https://crrev.com/e7839991aabb3d5e79e971177e78640ed88d940f Cr-Commit-Position: refs/heads/master@{#389382} ==========
Message was sent while issue was closed.
Patchset 16 (id:??) landed as https://crrev.com/e7839991aabb3d5e79e971177e78640ed88d940f Cr-Commit-Position: refs/heads/master@{#389382} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
