Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
1709713002:
TaskScheduler [4/9] Priority Queue (Closed)
DescriptionTaskScheduler [4/9] Priority Queue
This change is a subset of https://codereview.chromium.org/1698183005/
A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and
Peek operations through a Transaction object.
A SequenceSortKey must be provided to push a Sequence into a
PriorityQueue. Sequences are sorted according to their SequenceSortKey.
The SequenceSortKey of a Sequence never changes while it is in the
PriorityQueue (even if Tasks are pushed/popped from the Sequence).
BUG=553459
Committed: https://crrev.com/6477fbded94522e26875bbf405710060d01ea971
Cr-Commit-Position: refs/heads/master@{#382115}
Patch Set 1 #
Total comments: 3
Patch Set 2 : format #Patch Set 3 : self review. #
Total comments: 33
Patch Set 4 : address comments from robliao/gab #5-6 #Patch Set 5 : self review. #
Total comments: 27
Patch Set 6 : address comments from robliao/gab #8-9 #Patch Set 7 : fix indentation and comment. #
Total comments: 2
Patch Set 8 : simplify test #Patch Set 9 : self review #
Total comments: 51
Patch Set 10 : CR from robliao #21 #Patch Set 11 : add missing file #Patch Set 12 : CR danakj #26 #Patch Set 13 : self review #Patch Set 14 : self review #
Total comments: 9
Patch Set 15 : CR danakj #31 #
Messages
Total messages: 40 (10 generated)
Description was changed from ========== TaskScheduler [4/8] Priority Queue R=gab@chromium.org, robliao@chromium.org ========== to ========== TaskScheduler [4/8] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ As documented in https://docs.google.com/a/chromium.org/document/d/1S2AAeoo1xa_vsLbDYBsDHCqhrk... BUG=553459 ==========
Description was changed from ========== TaskScheduler [4/8] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ As documented in https://docs.google.com/a/chromium.org/document/d/1S2AAeoo1xa_vsLbDYBsDHCqhrk... BUG=553459 ========== to ========== TaskScheduler [4/8] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ BUG=553459 ==========
https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... base/task_scheduler/priority_queue.h:96: using ContainerType = std::priority_queue<SequenceAndSortKeyPair, Looked into details of std::priority_queue and pretty convinced we want to store SequenceSortKeyPair* in it. Then we avoid copies (potential unnecessary refcount bumps for Sequence and allows making SequenceSortKey's members const as discussed on other CL)
https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:26: : lock_(&predecessor_priority_queue->lock_), Won't this line crash since predecessor_priority_queue == nullptr with the one-arg constructor? https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:39: // |predecessor_priority_queue| is a PriorityQueue for which a thread is Let's separate this comment and have one per constructor, even though they are indeed similar. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:42: PriorityQueue(const Closure& sequence_inserted_callback); Add explicit constructor keyword https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:54: void PushSequence(scoped_refptr<Sequence> sequence, Should this be a SequenceAndSortKey? https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:74: scoped_ptr<AutoSchedulerLock> auto_lock_; Worth noting why we're using a scoped_ptr rather than a regular AutoSchedulerLock instance (destruction mechanics). At that point it isn't really the lifetime since it's gone before the constructor concludes. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:92: SchedulerLock lock_; Move below the type definitions. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:27: TaskTraits().WithPriority(TaskPriority::USER_VISIBLE)))); Maybe we should get some BACKGROUND tasks for completeness.
lvg, only a couple of things + Rob's comments, will make another pass after that. Thanks! https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... base/task_scheduler/priority_queue.h:40: // returned result can be invalidated at any time by sequences being pushed or [old comment from my initial review -- looks like this is gone now?] How about this for last sentence: This can only be used as a heuristic, the returned result can be invalidated at any time by sequences being pushed or popped from the priority queue in parallel. (and then I think putting the memory barrier sentence last, after that one, actually reads better) https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:27: sequence_inserted_callback_(sequence_inserted_callback) { Same order for initializer list, parameter order, and member order in header. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:35: auto_lock_.reset(); Add a comment about what's happening here (unlock + invoke call back outside of lock). https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:57: TimeTicks::FromInternalValue(std::numeric_limits<int64_t>::max()))); Should SequenceAndSortKey instead have a default constructor and an is_null() method to check when it is null instead of forging extreme values which AFAIK our algorithm wouldn't rely on anyways? https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:71: PriorityQueue* const priority_queue_; s/priority_queue_/outer_/ (I tend to prefer using "outer_" for inner-classes' pointer to their outer class, WDYT? Up to you, looks like the two main places this is done in the codebase are in code I wrote so... :-)) https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:74: scoped_ptr<AutoSchedulerLock> auto_lock_; On 2016/02/23 02:10:58, robliao wrote: > Worth noting why we're using a scoped_ptr rather than a regular > AutoSchedulerLock instance (destruction mechanics). At that point it isn't > really the lifetime since it's gone before the constructor concludes. Right, something like appending "Using a scoped_ptr allows a few internal operations to be performed after releasing the lock on destruction." ? https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:99: std::priority_queue<SequenceAndSortKey, s/SequenceAndSortKey/scoped_ptr<SequenceAndSortKey>/ ? According to http://en.cppreference.com/w/cpp/container/priority_queue this should be the same T as the next param's std::vector<T> https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:25: sequence_a_->PushTask(make_scoped_ptr( make_scoped_ptr is for scoped_ptr not scoped_refptr, I'm surprised this even compiles https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:41: MOCK_METHOD0(SequenceInsertedInPriorityQueue, void()); Unused I think (seems to be using PriorityQueueCallbackMock's instead) https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:75: PriorityQueueCallbackMock mock; I think you can make this verify precisely what you want even more with a StrictMock. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:109: EXPECT_EQ(nullptr, transaction->PeekSequence().sequence.get()); PeekSequence().is_null() would be nicer here if above recommendation is adopted :-)
Can you take another look? Thanks. https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/1/base/task_scheduler/priorit... base/task_scheduler/priority_queue.h:40: // returned result can be invalidated at any time by sequences being pushed or On 2016/02/23 03:02:10, gab wrote: > [old comment from my initial review -- looks like this is gone now?] > > > How about this for last sentence: > > This can only be used as a heuristic, the returned result can be invalidated at > any time by sequences being pushed or popped from the priority queue in > parallel. > > (and then I think putting the memory barrier sentence last, after that one, > actually reads better) I removed the method because I have a version of WorkerThread which doesn't require it. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:26: : lock_(&predecessor_priority_queue->lock_), On 2016/02/23 02:10:58, robliao wrote: > Won't this line crash since predecessor_priority_queue == nullptr with the > one-arg constructor? Done. It didn't crash but it was definitely wrong. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:27: sequence_inserted_callback_(sequence_inserted_callback) { On 2016/02/23 03:02:10, gab wrote: > Same order for initializer list, parameter order, and member order in header. Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:35: auto_lock_.reset(); On 2016/02/23 03:02:10, gab wrote: > Add a comment about what's happening here (unlock + invoke call back outside of > lock). Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:57: TimeTicks::FromInternalValue(std::numeric_limits<int64_t>::max()))); On 2016/02/23 03:02:10, gab wrote: > Should SequenceAndSortKey instead have a default constructor and an is_null() > method to check when it is null instead of forging extreme values which AFAIK > our algorithm wouldn't rely on anyways? Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:39: // |predecessor_priority_queue| is a PriorityQueue for which a thread is On 2016/02/23 02:10:58, robliao wrote: > Let's separate this comment and have one per constructor, even though they are > indeed similar. Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:42: PriorityQueue(const Closure& sequence_inserted_callback); On 2016/02/23 02:10:58, robliao wrote: > Add explicit constructor keyword Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:54: void PushSequence(scoped_refptr<Sequence> sequence, On 2016/02/23 02:10:58, robliao wrote: > Should this be a SequenceAndSortKey? Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:71: PriorityQueue* const priority_queue_; On 2016/02/23 03:02:10, gab wrote: > s/priority_queue_/outer_/ > > (I tend to prefer using "outer_" for inner-classes' pointer to their outer > class, WDYT? Up to you, looks like the two main places this is done in the > codebase are in code I wrote so... :-)) Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:74: scoped_ptr<AutoSchedulerLock> auto_lock_; On 2016/02/23 03:02:10, gab wrote: > On 2016/02/23 02:10:58, robliao wrote: > > Worth noting why we're using a scoped_ptr rather than a regular > > AutoSchedulerLock instance (destruction mechanics). At that point it isn't > > really the lifetime since it's gone before the constructor concludes. > > Right, something like appending "Using a scoped_ptr allows a few internal > operations to be performed after releasing the lock on destruction." ? Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:92: SchedulerLock lock_; On 2016/02/23 02:10:58, robliao wrote: > Move below the type definitions. Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:99: std::priority_queue<SequenceAndSortKey, On 2016/02/23 03:02:10, gab wrote: > s/SequenceAndSortKey/scoped_ptr<SequenceAndSortKey>/ ? According to > http://en.cppreference.com/w/cpp/container/priority_queue this should be the > same T as the next param's std::vector<T> Done. I'm surprised that the code compiled with the wrong type... https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:25: sequence_a_->PushTask(make_scoped_ptr( On 2016/02/23 03:02:10, gab wrote: > make_scoped_ptr is for scoped_ptr not scoped_refptr, I'm surprised this even > compiles PushTask expects a scoped_ptr<Task>, not a scoped_refptr. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:27: TaskTraits().WithPriority(TaskPriority::USER_VISIBLE)))); On 2016/02/23 02:10:58, robliao wrote: > Maybe we should get some BACKGROUND tasks for completeness. Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:41: MOCK_METHOD0(SequenceInsertedInPriorityQueue, void()); On 2016/02/23 03:02:10, gab wrote: > Unused I think (seems to be using PriorityQueueCallbackMock's instead) Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:75: PriorityQueueCallbackMock mock; On 2016/02/23 03:02:10, gab wrote: > I think you can make this verify precisely what you want even more with a > StrictMock. Done. https://codereview.chromium.org/1709713002/diff/40001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:109: EXPECT_EQ(nullptr, transaction->PeekSequence().sequence.get()); On 2016/02/23 03:02:10, gab wrote: > PeekSequence().is_null() would be nicer here if above recommendation is adopted > :-) Done.
lgtm w/ comments Thanks! https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:49: // callback to avoid holding multiple locks at the same time. s/to avoid holding multiple locks at the same time/to avoid imposing an unnecessary lock dependency on |sequence_inserted_callback_|'s destination/ (i.e. this component's comment shouldn't assume anything about where this callback lands in practice today) https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:53: // inserted in the PriorityQueue during the lifetime of this Transaction. Actually I'd say append [1] to this comment and fold |auto_lock_.reset()| below as it really goes together. [1] "Perform this outside the scope of PriorityQueue's lock to avoid imposing an unnecessary lock dependency on |sequence_inserted_callback_|'s destination." https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:35: static SequenceAndSortKey Null(); I meant to have a default constructor instead, just like Time(). https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:41: SequenceSortKey sort_key; Should these be const? (and this class be marked "immutable" in its meta comment?) https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:81: // performing internal operations which don't require synchronization. s/don't require synchronization/have to be done outside of its scope/ (i.e. it's not just adding this complexity to free ASAP when synchronized work is done but rather because it is required for the cleanup work to be unsynchronized) https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:39: EXPECT_EQ(expected.is_null(), actual.is_null()); Don't think this is necessary. Since is_null() is const and the above verifies all other state, it's impossible for any state to be equivalent above but not result in the same is_null(). https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:44: // Check the behavior of the Push, Pop and Peek methods of s/Check/Verifies/ (and overall I think the test being named "PushPopPeek" is enough and a comment isn't necessary) https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:135: PriorityQueue pq_a(Bind(&DoNothing)); s/Bind(&DoNothing)/Closure()/ here and below? I guess you're doing this because the compiler doesn't allow a Closure which is_null(). Not sure this strict requirement is required. If you think it is, add to the API comment that the param must be non-null.
lgtm + comments, feel free to proceed to the next stage when you wish. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); Remove DCHECK(predecessory_priorit_queue) since we'll crash before this line (initializer list). https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:35: static SequenceAndSortKey Null(); Could this instead be the default constructor? https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:132: // Check that creating Transactions on the same thread for 2 unrelated It would also be interesting to create two transactions on different threads for the same PQ to make sure that doesn't crash as well. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:139: { Follow the lambda expressions style for this block: https://google.github.io/styleguide/cppguide.html#Lambda_expressions EXPECT_DEBUG_DEATH({ // Body 2 Space Indent }, "");
all done. I'll wait until I get a first round of comments from Nico on "TaskScheduler [3/8] Task and Sequence" to send this CL. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); On 2016/02/23 21:00:35, robliao wrote: > Remove DCHECK(predecessory_priorit_queue) since we'll crash before this line > (initializer list). On my machine, there is no crash when the address of predecessor_priority_queue->lock_ is taken with predecessor_priority_queue_ == nullptr. The DCHECK is useful to guarantee a crash. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:49: // callback to avoid holding multiple locks at the same time. On 2016/02/23 20:58:42, gab wrote: > s/to avoid holding multiple locks at the same time/to avoid imposing an > unnecessary lock dependency on |sequence_inserted_callback_|'s destination/ > > (i.e. this component's comment shouldn't assume anything about where this > callback lands in practice today) I did what you suggest in your next comment instead. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:53: // inserted in the PriorityQueue during the lifetime of this Transaction. On 2016/02/23 20:58:42, gab wrote: > Actually I'd say append [1] to this comment and fold |auto_lock_.reset()| below > as it really goes together. > > [1] "Perform this outside the scope of PriorityQueue's lock to avoid imposing an > unnecessary lock dependency on |sequence_inserted_callback_|'s destination." Done. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:35: static SequenceAndSortKey Null(); On 2016/02/23 21:00:35, robliao wrote: > Could this instead be the default constructor? Done. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:41: SequenceSortKey sort_key; On 2016/02/23 20:58:42, gab wrote: > Should these be const? (and this class be marked "immutable" in its meta > comment?) Done. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.h:81: // performing internal operations which don't require synchronization. On 2016/02/23 20:58:42, gab wrote: > s/don't require synchronization/have to be done outside of its scope/ > > (i.e. it's not just adding this complexity to free ASAP when synchronized work > is done but rather because it is required for the cleanup work to be > unsynchronized) Done. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:39: EXPECT_EQ(expected.is_null(), actual.is_null()); On 2016/02/23 20:58:42, gab wrote: > Don't think this is necessary. Since is_null() is const and the above verifies > all other state, it's impossible for any state to be equivalent above but not > result in the same is_null(). It tested the implementation of is_null(). I created a separate test for this instead. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:44: // Check the behavior of the Push, Pop and Peek methods of On 2016/02/23 20:58:42, gab wrote: > s/Check/Verifies/ > > (and overall I think the test being named "PushPopPeek" is enough and a comment > isn't necessary) Done. Removed the comment. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:132: // Check that creating Transactions on the same thread for 2 unrelated On 2016/02/23 21:00:35, robliao wrote: > It would also be interesting to create two transactions on different threads for > the same PQ to make sure that doesn't crash as well. Done. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:135: PriorityQueue pq_a(Bind(&DoNothing)); On 2016/02/23 20:58:42, gab wrote: > s/Bind(&DoNothing)/Closure()/ > > here and below? I guess you're doing this because the compiler doesn't allow a > Closure which is_null(). Not sure this strict requirement is required. If you > think it is, add to the API comment that the param must be non-null. Done. Added comment in PriorityQueue to say that the callback can't be null. https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue_unittest.cc:139: { On 2016/02/23 21:00:35, robliao wrote: > Follow the lambda expressions style for this block: > https://google.github.io/styleguide/cppguide.html#Lambda_expressions > > EXPECT_DEBUG_DEATH({ > // Body 2 Space Indent > }, ""); Done.
lgtm++ https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); On 2016/02/24 15:03:53, fdoray wrote: > On 2016/02/23 21:00:35, robliao wrote: > > Remove DCHECK(predecessory_priorit_queue) since we'll crash before this line > > (initializer list). > > On my machine, there is no crash when the address of > predecessor_priority_queue->lock_ is taken with predecessor_priority_queue_ == > nullptr. The DCHECK is useful to guarantee a crash. Interesting, @ Rob maybe this goes to show that explicit DCHECKs are good to have even when a deref implicitly documents expectation of pointer being non-null (ref. discussion on other CL). DCHECK will always fire, but perhaps deref may not based on some weird compiler optimizations I don't understand? https://codereview.chromium.org/1709713002/diff/120001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/120001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:214: TaskTraits().WithPriority(TaskPriority::USER_VISIBLE)))); Does the sequence need to have a task in it for this test to be valid? If not I'd vote for keeping it minimalistic.
https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); On 2016/02/24 18:07:38, gab wrote: > On 2016/02/24 15:03:53, fdoray wrote: > > On 2016/02/23 21:00:35, robliao wrote: > > > Remove DCHECK(predecessory_priorit_queue) since we'll crash before this line > > > (initializer list). > > > > On my machine, there is no crash when the address of > > predecessor_priority_queue->lock_ is taken with predecessor_priority_queue_ == > > nullptr. The DCHECK is useful to guarantee a crash. > > Interesting, @ Rob maybe this goes to show that explicit DCHECKs are good to > have even when a deref implicitly documents expectation of pointer being > non-null (ref. discussion on other CL). > > DCHECK will always fire, but perhaps deref may not based on some weird compiler > optimizations I don't understand? explanation from etienneb@: It doesn't crash because the pointer isn't dereferenced. We take the address of predecessor_priority_queue->lock_ but we don't try to read its value. https://codereview.chromium.org/1709713002/diff/120001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/120001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:214: TaskTraits().WithPriority(TaskPriority::USER_VISIBLE)))); On 2016/02/24 18:07:38, gab wrote: > Does the sequence need to have a task in it for this test to be valid? If not > I'd vote for keeping it minimalistic. Done.
https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); On 2016/02/24 18:18:42, fdoray wrote: > On 2016/02/24 18:07:38, gab wrote: > > On 2016/02/24 15:03:53, fdoray wrote: > > > On 2016/02/23 21:00:35, robliao wrote: > > > > Remove DCHECK(predecessory_priorit_queue) since we'll crash before this > line > > > > (initializer list). > > > > > > On my machine, there is no crash when the address of > > > predecessor_priority_queue->lock_ is taken with predecessor_priority_queue_ > == > > > nullptr. The DCHECK is useful to guarantee a crash. > > > > Interesting, @ Rob maybe this goes to show that explicit DCHECKs are good to > > have even when a deref implicitly documents expectation of pointer being > > non-null (ref. discussion on other CL). > > > > DCHECK will always fire, but perhaps deref may not based on some weird > compiler > > optimizations I don't understand? > > explanation from etienneb@: It doesn't crash because the pointer isn't > dereferenced. We take the address of predecessor_priority_queue->lock_ but we > don't try to read its value. This sounds wrong to me. We are dereferencing the predecessor_priority_queue on a nullptr. That should immediately cause a crash, since predecessor_priority_queue->lock_ = (*predecessor_priority_queue)->lock For example, this results in an immediate access violation for me: int main(int argc, char* argv[]) { class A { public: A() : value_(42) {} A(int placeholder, A* outer) : value_(outer->value_) {} private: int value_; }; A instance1; A instance2(0, &instance1); A instance3(0, nullptr); <----- AV on this line } Do you have exceptions suppressed on your machine by any chance?
https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/80001/base/task_scheduler/pri... base/task_scheduler/priority_queue.cc:40: DCHECK(predecessor_priority_queue); On 2016/02/24 18:46:33, robliao wrote: > On 2016/02/24 18:18:42, fdoray wrote: > > On 2016/02/24 18:07:38, gab wrote: > > > On 2016/02/24 15:03:53, fdoray wrote: > > > > On 2016/02/23 21:00:35, robliao wrote: > > > > > Remove DCHECK(predecessory_priorit_queue) since we'll crash before this > > line > > > > > (initializer list). > > > > > > > > On my machine, there is no crash when the address of > > > > predecessor_priority_queue->lock_ is taken with > predecessor_priority_queue_ > > == > > > > nullptr. The DCHECK is useful to guarantee a crash. > > > > > > Interesting, @ Rob maybe this goes to show that explicit DCHECKs are good to > > > have even when a deref implicitly documents expectation of pointer being > > > non-null (ref. discussion on other CL). > > > > > > DCHECK will always fire, but perhaps deref may not based on some weird > > compiler > > > optimizations I don't understand? > > > > explanation from etienneb@: It doesn't crash because the pointer isn't > > dereferenced. We take the address of predecessor_priority_queue->lock_ but we > > don't try to read its value. > > This sounds wrong to me. We are dereferencing the predecessor_priority_queue on > a nullptr. That should immediately cause a crash, since > predecessor_priority_queue->lock_ = (*predecessor_priority_queue)->lock > > For example, this results in an immediate access violation for me: > > int main(int argc, char* argv[]) { > class A { > public: > A() : value_(42) {} > A(int placeholder, A* outer) : value_(outer->value_) {} > > private: > int value_; > }; > > A instance1; > A instance2(0, &instance1); > A instance3(0, nullptr); <----- AV on this line > } > > Do you have exceptions suppressed on your machine by any chance? Alright. Looks like I get to stand corrected here :-) and learned something new. tl;dr - Because of some subtle dereferencing rules, the DCHECK stands. New snippet! class Copyable { public: Copyable() = default; Copyable(const Copyable* other) {} void Print() {} }; class A { public: A() = default; A(int placeholder, A* outer) : copyable_(&outer->copyable_) { outer->copyable_.Print(); } A(float placeholder, A* outer) : pointer_(outer->pointer_) {} private: Copyable copyable_; Copyable* pointer_; }; int main(int argc, char* argv[]) { A instance3(0, nullptr); A instance4(0.0f, nullptr); } So why doesn't instance3 crash? Turns out, MSVC treats &outer->copyable_ as well as outer->copyable_.Print() as a whole when it's a class and does not generate a dereference of |outer| to get the value. Instead, it jumps straight to the location regardless of the base address: mov eax,dword ptr [ebp+0Ch] eax = other = 0 mov ecx,dword ptr [ebp-8] ecx = this = instance3's Copyable call Sandbox!Copyable::Copyable mov ecx,dword ptr [ebp+0Ch] ecx = this = 0 call Sandbox!Copyable::Print However, if we have a piece of plain old data, then we run into trouble like in instance4 as it generates mov ecx,dword ptr [ebp+0Ch] <-- Code Example, ecx = 0 mov edx,dword ptr [ecx+4] <-- Dereferencing 4 to get the pointer value For the code in question, SchedulerLock never dereferences the predecessor lock, so that's why we continue without a crash.
fdoray@chromium.org changed reviewers: + thakis@chromium.org
thakis@: Can you review this CL when you are done reviewing these: - TaskScheduler [2/8] Scheduler Lock https://codereview.chromium.org/1706123002/ - TaskScheduler [3/8] Task and Sequence https://codereview.chromium.org/1705253002/ Thanks! cc: jam@
gab@chromium.org changed reviewers: + danakj@chromium.org
On 2016/02/25 19:14:23, fdoray wrote: > thakis@: Can you review this CL when you are done reviewing these: > - TaskScheduler [2/8] Scheduler Lock https://codereview.chromium.org/1706123002/ > - TaskScheduler [3/8] Task and Sequence > https://codereview.chromium.org/1705253002/ > Thanks! +Dana as just discussed, thanks!
Description was changed from ========== TaskScheduler [4/8] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ BUG=553459 ========== to ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ BUG=553459 ==========
danakj@: Can you review this CL for the new task scheduler? Thanks!
Some small nits on an update scan. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:59: class BASE_EXPORT Transaction : public NonThreadSafe { Move this after SequenceAndSortKey's definition. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:172: EXPECT_DEBUG_DEATH({ We'll want to start using EXPECT_DCHECK_DEATH here.
Can you give this a more detailed CL description to say what it's doing on its own?
Description was changed from ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ BUG=553459 ========== to ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and Peek operations through a Transaction object. A SequenceSortKey must be provided to push a Sequence into a PriorityQueue. Sequences are sorted according to their SequenceSortKey. The SequenceSortKey of a Sequence never changes while it is in the PriorityQueue (even if Tasks are pushed/popped from the Sequence). BUG=553459 ==========
danakj@: I updated the CL's description. robliao@: I addressed your 2 comments. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:59: class BASE_EXPORT Transaction : public NonThreadSafe { On 2016/03/17 17:48:10, robliao wrote: > Move this after SequenceAndSortKey's definition. Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:172: EXPECT_DEBUG_DEATH({ On 2016/03/17 17:48:10, robliao wrote: > We'll want to start using EXPECT_DCHECK_DEATH here. Done.
On 2016/03/17 19:12:02, fdoray wrote: > danakj@: I updated the CL's description. > robliao@: I addressed your 2 comments. > > https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... > File base/task_scheduler/priority_queue.h (right): > > https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... > base/task_scheduler/priority_queue.h:59: class BASE_EXPORT Transaction : public > NonThreadSafe { > On 2016/03/17 17:48:10, robliao wrote: > > Move this after SequenceAndSortKey's definition. > > Done. > > https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... > File base/task_scheduler/priority_queue_unittest.cc (right): > > https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... > base/task_scheduler/priority_queue_unittest.cc:172: EXPECT_DEBUG_DEATH({ > On 2016/03/17 17:48:10, robliao wrote: > > We'll want to start using EXPECT_DCHECK_DEATH here. > > Done. Still lgtm. We may want to move some PrintTo's to test_utils, but we can definitely do that later.
https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:20: : sequence(sequence), sort_key(sort_key) {} move the sequence https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:24: bool PriorityQueue::SequenceAndSortKey::is_null() const { hacker_style methods should be inline. otherwise it's IsNull. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:25: return sequence.get() == nullptr; fwiw, return !!sequence also works, either way. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:64: PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const { why not return a const reference? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:79: PriorityQueue::Transaction::Transaction(PriorityQueue* outer) can you put this constructor above the destructor in this file? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:91: return left->sort_key < right->sort_key; i think you could inline this in the header https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:35: SequenceSortKey sort_key); const& https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:47: // is added to the PriorityQueue. Can you document this happens when the transaction is done? You could push/pop then the closure runs and it's like what the queue is empty?? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:59: class BASE_EXPORT Transaction : public NonThreadSafe { Put a comment on this class, what is it? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:79: PriorityQueue* const outer_; outer_queue_? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. usually locks sit right above the things they lock in the class defn https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. Why is it okay that while a Transaction is alive the queue is locked? It will prevent it from scheduling tasks also won't it? I don't remember this from your overview of stuff, can you explain the reasoning? And why not just lock when you Push or Peek etc? Is it a requirement that pushing N tasks is an atomic operation? How come? Maybe you can document this all on the top of the Transaction class? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:112: SchedulerLock lock_; container_lock_? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:69: scoped_refptr<Sequence> sequence_a = new Sequence; use the constructor rather than assigning a raw pointer, for all of these. ie scoped_refptr<T> t(new T); https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:99: ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(), You can use a SCOPED_TRACE() to make errors show which call to ExpectSequenceAndSortKey failed. If you want, you could macro this #define EXPECT_SEQUENCE_AND_SORT_KEY_EQ(e, a) { \ TRACE_SCOPED(""); \ ExpectS...(e, a); \ } https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:161: // Transaction is destroyed. Can you VerifyAndClearExpectations(); before the EXPECT_CALL, so we can tell that these come from the reset() and not from the Pushes above? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:208: // thread should stil not have returned. "still", though the word is superfluous here. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:210: EXPECT_FALSE(thread_beginning_transaction.transaction_began()); This is a data race. You need a lock to access this variable on multiple threads. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:217: EXPECT_TRUE(thread_beginning_transaction.transaction_began()); ditto https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:223: new Sequence, make_scoped_refptr https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:225: .is_null()); consider making the key outside of the EXPECT statement so this reads better
danakj@: All done. Can you take another look and respond to my questions at https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... ? Thanks. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:20: : sequence(sequence), sort_key(sort_key) {} On 2016/03/17 21:32:14, danakj wrote: > move the sequence Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:24: bool PriorityQueue::SequenceAndSortKey::is_null() const { On 2016/03/17 21:32:14, danakj wrote: > hacker_style methods should be inline. otherwise it's IsNull. Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:25: return sequence.get() == nullptr; On 2016/03/17 21:32:14, danakj wrote: > fwiw, return !!sequence also works, either way. Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:64: PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const { On 2016/03/17 21:32:14, danakj wrote: > why not return a const reference? I changed the code to return a const reference. However, I don't think it's a good idea because we'll have to be extremely careful not to use the reference after it has been popped from the pq (see code below). Alternative solutions (I prefer solution 3): 1. Return by value. No questions about lifetime. 2. Return a pointer. Same questions about lifetime, but we can return nullptr instead of |empty_sequence_and_sort_key_| to indicate that the pq is empty. 3. Change the API to return a "SequenceSortKey" (instead of SequenceAndSortKey) in Peek and a scoped_refptr<Sequence> in Pop(). SequenceSortKey is a struct with TaskPriority+TimeTicks so it is less costly to copy than a SequenceAndSortKey with a scoped_refptr<Sequence>. With solution 3, the WorkerThread::GetWork code would look like this: scoped_refptr<Sequence> GetWork() { auto single_thread_transaction = single_thread_pq_->BeginTransaction(); auto shared_transaction = shared_pq_->BeginTransaction(); auto single_thread_key = single_thread_transaction->Peek(); auto shared_key = shared_transaction->Peek(); // Make sure that Peek() returns a key which compares less than any other // key when the pq is empty. if (single_thread_key > shared_key) return single_thread_transaction->Pop(); return shared_transaction->Pop(); } instead of like this with the current API (solution 1): scoped_refptr<Sequence> GetWork() { auto single_thread_transaction = single_thread_pq_->BeginTransaction(); auto shared_transaction = shared_pq_->BeginTransaction(); auto single_thread_seq_and_key = single_thread_transaction->Peek(); auto shared_key_seq_and_key = shared_transaction->Peek(); if (single_thread_seq_and_key.is_null() && single_thread_seq_and_key.is_null()) return scoped_ref_ptr<Sequence>(); if (single_thread_seq_and_key.key > shared_seq_and_key.key) { single_thread_transaction->Pop(); // If |single_thread_seq_and_key| was a reference, it couldn't be used after // the Pop(). return single_thread_seq_and_key.seq; } shared_transaction->Pop(); return shared_seq_and_key.seq; } WDYT? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:79: PriorityQueue::Transaction::Transaction(PriorityQueue* outer) On 2016/03/17 21:32:14, danakj wrote: > can you put this constructor above the destructor in this file? Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:91: return left->sort_key < right->sort_key; On 2016/03/17 21:32:14, danakj wrote: > i think you could inline this in the header Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:35: SequenceSortKey sort_key); On 2016/03/17 21:32:14, danakj wrote: > const& Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:47: // is added to the PriorityQueue. On 2016/03/17 21:32:14, danakj wrote: > Can you document this happens when the transaction is done? You could push/pop > then the closure runs and it's like what the queue is empty?? Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:59: class BASE_EXPORT Transaction : public NonThreadSafe { On 2016/03/17 21:32:15, danakj wrote: > Put a comment on this class, what is it? Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:79: PriorityQueue* const outer_; On 2016/03/17 21:32:15, danakj wrote: > outer_queue_? Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. On 2016/03/17 21:32:14, danakj wrote: > usually locks sit right above the things they lock in the class defn This is not a lock. It's an auto-lock to hold outer_queue_->container_lock_ for the lifetime of the Transaction. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. On 2016/03/17 21:32:14, danakj wrote: > Why is it okay that while a Transaction is alive the queue is locked? It will > prevent it from scheduling tasks also won't it? I don't remember this from your > overview of stuff, can you explain the reasoning? > > And why not just lock when you Push or Peek etc? Is it a requirement that > pushing N tasks is an atomic operation? How come? Maybe you can document this > all on the top of the Transaction class? Done. Added an explanation above the declaration of Transaction. Note that we only need the Transaction to perform an atomic Peek+Pop. Push doesn't have to be in Transaction. It could be a method of PriorityQueue that locks the container itself. However, we think that it is more consistent to have all operations at the same place. WorkerThread pseudo-code: scoped_refptr<Sequence> GetWork() { auto single_thread_transaction = single_thread_pq_->BeginTransaction(); auto shared_transaction = shared_pq_->BeginTransaction(); auto single_thread_seq_and_key = single_thread_transaction->Peek(); auto shared_key_seq_and_key = shared_transaction->Peek(); if (single_thread_seq_and_key.is_null() && single_thread_seq_and_key.is_null()) return scoped_ref_ptr<Sequence>(); if (single_thread_seq_and_key.key > shared_seq_and_key.key) { single_thread_transaction->Pop(); return single_thread_seq_and_key.seq; } shared_transaction->Pop(); return shared_seq_and_key.seq; } https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:112: SchedulerLock lock_; On 2016/03/17 21:32:14, danakj wrote: > container_lock_? Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:69: scoped_refptr<Sequence> sequence_a = new Sequence; On 2016/03/17 21:32:15, danakj wrote: > use the constructor rather than assigning a raw pointer, for all of these. ie > scoped_refptr<T> t(new T); Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:99: ExpectSequenceAndSortKey(PriorityQueue::SequenceAndSortKey(), On 2016/03/17 21:32:15, danakj wrote: > You can use a SCOPED_TRACE() to make errors show which call to > ExpectSequenceAndSortKey failed. > > If you want, you could macro this > > #define EXPECT_SEQUENCE_AND_SORT_KEY_EQ(e, a) { \ > TRACE_SCOPED(""); \ > ExpectS...(e, a); \ > } > Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:161: // Transaction is destroyed. On 2016/03/17 21:32:15, danakj wrote: > Can you VerifyAndClearExpectations(); before the EXPECT_CALL, so we can tell > that these come from the reset() and not from the Pushes above? This is already covered by using a StrictMock: the test fails if there are calls to the mock function before EXPECT_CALL. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:208: // thread should stil not have returned. On 2016/03/17 21:32:15, danakj wrote: > "still", though the word is superfluous here. Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:210: EXPECT_FALSE(thread_beginning_transaction.transaction_began()); On 2016/03/17 21:32:15, danakj wrote: > This is a data race. You need a lock to access this variable on multiple > threads. I used a WaitableEvent to fix the data race because IMO transaction_began_.Signal() is simpler than lock+set boolean. WDYT? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:217: EXPECT_TRUE(thread_beginning_transaction.transaction_began()); On 2016/03/17 21:32:15, danakj wrote: > ditto Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:223: new Sequence, On 2016/03/17 21:32:15, danakj wrote: > make_scoped_refptr Done. https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:225: .is_null()); On 2016/03/17 21:32:15, danakj wrote: > consider making the key outside of the EXPECT statement so this reads better Done.
https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:64: PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const { On 2016/03/18 16:06:55, fdoray wrote: > On 2016/03/17 21:32:14, danakj wrote: > > why not return a const reference? > > I changed the code to return a const reference. However, I don't think it's a > good idea because we'll have to be extremely careful not to use the reference > after it has been popped from the pq (see code below). > > Alternative solutions (I prefer solution 3): > 1. Return by value. No questions about lifetime. > 2. Return a pointer. Same questions about lifetime, but we can return nullptr > instead of |empty_sequence_and_sort_key_| to indicate that the pq is empty. > 3. Change the API to return a "SequenceSortKey" (instead of SequenceAndSortKey) > in Peek and a scoped_refptr<Sequence> in Pop(). SequenceSortKey is a struct with > TaskPriority+TimeTicks so it is less costly to copy than a SequenceAndSortKey > with a scoped_refptr<Sequence>. > > With solution 3, the WorkerThread::GetWork code would look like this: > > scoped_refptr<Sequence> GetWork() { > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > auto shared_transaction = shared_pq_->BeginTransaction(); > auto single_thread_key = single_thread_transaction->Peek(); > auto shared_key = shared_transaction->Peek(); > > // Make sure that Peek() returns a key which compares less than any other > // key when the pq is empty. > > if (single_thread_key > shared_key) > return single_thread_transaction->Pop(); > return shared_transaction->Pop(); > } > > instead of like this with the current API (solution 1): > > scoped_refptr<Sequence> GetWork() { > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > auto shared_transaction = shared_pq_->BeginTransaction(); > auto single_thread_seq_and_key = single_thread_transaction->Peek(); > auto shared_key_seq_and_key = shared_transaction->Peek(); > > if (single_thread_seq_and_key.is_null() && > single_thread_seq_and_key.is_null()) > return scoped_ref_ptr<Sequence>(); > > if (single_thread_seq_and_key.key > shared_seq_and_key.key) { > single_thread_transaction->Pop(); > > // If |single_thread_seq_and_key| was a reference, it couldn't be used after > // the Pop(). > return single_thread_seq_and_key.seq; > } > > shared_transaction->Pop(); > return shared_seq_and_key.seq; > } > > WDYT? Is the cost of having the Sequence with the sort key that high? It was nice to have these two elements logically grouped.
https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:64: PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const { On 2016/03/18 16:06:55, fdoray wrote: > On 2016/03/17 21:32:14, danakj wrote: > > why not return a const reference? > > I changed the code to return a const reference. However, I don't think it's a > good idea because we'll have to be extremely careful not to use the reference > after it has been popped from the pq (see code below). > > Alternative solutions (I prefer solution 3): > 1. Return by value. No questions about lifetime. > 2. Return a pointer. Same questions about lifetime, but we can return nullptr > instead of |empty_sequence_and_sort_key_| to indicate that the pq is empty. > 3. Change the API to return a "SequenceSortKey" (instead of SequenceAndSortKey) > in Peek and a scoped_refptr<Sequence> in Pop(). SequenceSortKey is a struct with > TaskPriority+TimeTicks so it is less costly to copy than a SequenceAndSortKey > with a scoped_refptr<Sequence>. > > With solution 3, the WorkerThread::GetWork code would look like this: > > scoped_refptr<Sequence> GetWork() { > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > auto shared_transaction = shared_pq_->BeginTransaction(); > auto single_thread_key = single_thread_transaction->Peek(); > auto shared_key = shared_transaction->Peek(); > > // Make sure that Peek() returns a key which compares less than any other > // key when the pq is empty. > > if (single_thread_key > shared_key) > return single_thread_transaction->Pop(); > return shared_transaction->Pop(); > } > > instead of like this with the current API (solution 1): > > scoped_refptr<Sequence> GetWork() { > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > auto shared_transaction = shared_pq_->BeginTransaction(); > auto single_thread_seq_and_key = single_thread_transaction->Peek(); > auto shared_key_seq_and_key = shared_transaction->Peek(); > > if (single_thread_seq_and_key.is_null() && > single_thread_seq_and_key.is_null()) > return scoped_ref_ptr<Sequence>(); > > if (single_thread_seq_and_key.key > shared_seq_and_key.key) { > single_thread_transaction->Pop(); > > // If |single_thread_seq_and_key| was a reference, it couldn't be used after > // the Pop(). > return single_thread_seq_and_key.seq; > } > > shared_transaction->Pop(); > return shared_seq_and_key.seq; > } > > WDYT? If you look at container_.top(), it returns a const reference. It's normal for methods like this to do so. If you remove it from the container you can't use the reference, yeah, but that seems okay to me. You need to think about that whenever you store a reference. Normally you wouldn't store a ref, but it's nice for code like Peek().foo(). Now you didn't need to copy the result of Peek() just to call foo() on it.
danakj@: Can you take another look at the CL? https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:64: PriorityQueue::SequenceAndSortKey PriorityQueue::Transaction::Peek() const { On 2016/03/18 17:44:17, danakj wrote: > On 2016/03/18 16:06:55, fdoray wrote: > > On 2016/03/17 21:32:14, danakj wrote: > > > why not return a const reference? > > > > I changed the code to return a const reference. However, I don't think it's a > > good idea because we'll have to be extremely careful not to use the reference > > after it has been popped from the pq (see code below). > > > > Alternative solutions (I prefer solution 3): > > 1. Return by value. No questions about lifetime. > > 2. Return a pointer. Same questions about lifetime, but we can return nullptr > > instead of |empty_sequence_and_sort_key_| to indicate that the pq is empty. > > 3. Change the API to return a "SequenceSortKey" (instead of > SequenceAndSortKey) > > in Peek and a scoped_refptr<Sequence> in Pop(). SequenceSortKey is a struct > with > > TaskPriority+TimeTicks so it is less costly to copy than a SequenceAndSortKey > > with a scoped_refptr<Sequence>. > > > > With solution 3, the WorkerThread::GetWork code would look like this: > > > > scoped_refptr<Sequence> GetWork() { > > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > > auto shared_transaction = shared_pq_->BeginTransaction(); > > auto single_thread_key = single_thread_transaction->Peek(); > > auto shared_key = shared_transaction->Peek(); > > > > // Make sure that Peek() returns a key which compares less than any other > > // key when the pq is empty. > > > > if (single_thread_key > shared_key) > > return single_thread_transaction->Pop(); > > return shared_transaction->Pop(); > > } > > > > instead of like this with the current API (solution 1): > > > > scoped_refptr<Sequence> GetWork() { > > auto single_thread_transaction = single_thread_pq_->BeginTransaction(); > > auto shared_transaction = shared_pq_->BeginTransaction(); > > auto single_thread_seq_and_key = single_thread_transaction->Peek(); > > auto shared_key_seq_and_key = shared_transaction->Peek(); > > > > if (single_thread_seq_and_key.is_null() && > > single_thread_seq_and_key.is_null()) > > return scoped_ref_ptr<Sequence>(); > > > > if (single_thread_seq_and_key.key > shared_seq_and_key.key) { > > single_thread_transaction->Pop(); > > > > // If |single_thread_seq_and_key| was a reference, it couldn't be used > after > > // the Pop(). > > return single_thread_seq_and_key.seq; > > } > > > > shared_transaction->Pop(); > > return shared_seq_and_key.seq; > > } > > > > WDYT? > > If you look at container_.top(), it returns a const reference. It's normal for > methods like this to do so. If you remove it from the container you can't use > the reference, yeah, but that seems okay to me. You need to think about that > whenever you store a reference. > > Normally you wouldn't store a ref, but it's nice for code like Peek().foo(). Now > you didn't need to copy the result of Peek() just to call foo() on it. OK, makes sense. In the latest patch set, Peek() returns a const ref as you suggested.
LGTM https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. On 2016/03/18 16:06:55, fdoray wrote: > On 2016/03/17 21:32:14, danakj wrote: > > usually locks sit right above the things they lock in the class defn > > This is not a lock. It's an auto-lock to hold outer_queue_->container_lock_ for > the lifetime of the Transaction. Yeah, but it's holding a lock in the auto lock. What I mean to say is that I'd be nice to have this above the things it's used for locking. In this case its used for locking stuff in outer_queue_. https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:56: return outer_queue_->empty_sequence_and_sort_key_; Maybe consider an IsEmpty() instead of returning empty on Peek, and require Peek to be non-empty? I think that would be nicer. This CL's gone on enough, so perhaps a TODO and a followup? https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:132: const SequenceAndSortKey empty_sequence_and_sort_key_; static? you could probably put this in an anon namespace in the cc file? https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:70: { \ oh, I remembered another common trick, you can do: #define M(...) \ do { ... } while (false) And then this will force the user of the macro to put a semicolon on the end of the line. https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:220: EXPECT_FALSE(thread_beginning_transaction.transaction_began()); Instead of a Sleep you could use TimedWait() on the WaitableEvent, but I guess it's roughly the same thing at that point.
https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/160001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:81: // Holds the lock of |outer_| for most of the lifetime of this Transaction. On 2016/03/18 20:24:05, danakj wrote: > On 2016/03/18 16:06:55, fdoray wrote: > > On 2016/03/17 21:32:14, danakj wrote: > > > usually locks sit right above the things they lock in the class defn > > > > This is not a lock. It's an auto-lock to hold outer_queue_->container_lock_ > for > > the lifetime of the Transaction. > > Yeah, but it's holding a lock in the auto lock. What I mean to say is that I'd > be nice to have this above the things it's used for locking. In this case its > used for locking stuff in outer_queue_. Ah ok! Done. https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.cc (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue.cc:56: return outer_queue_->empty_sequence_and_sort_key_; On 2016/03/18 20:24:05, danakj wrote: > Maybe consider an IsEmpty() instead of returning empty on Peek, and require Peek > to be non-empty? I think that would be nicer. This CL's gone on enough, so > perhaps a TODO and a followup? Done. https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:132: const SequenceAndSortKey empty_sequence_and_sort_key_; On 2016/03/18 20:24:05, danakj wrote: > static? > > you could probably put this in an anon namespace in the cc file? I believe that the style guide doesn't allow non-POD static member. Is that right? https://google.github.io/styleguide/cppguide.html#Static_and_Global_Variables https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue_unittest.cc (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:70: { \ On 2016/03/18 20:24:05, danakj wrote: > oh, I remembered another common trick, you can do: > > #define M(...) \ > do { > ... > } while (false) > > And then this will force the user of the macro to put a semicolon on the end of > the line. Done. https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue_unittest.cc:220: EXPECT_FALSE(thread_beginning_transaction.transaction_began()); On 2016/03/18 20:24:05, danakj wrote: > Instead of a Sleep you could use TimedWait() on the WaitableEvent, but I guess > it's roughly the same thing at that point. Done.
The CQ bit was checked by fdoray@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from gab@chromium.org, robliao@chromium.org, danakj@chromium.org Link to the patchset: https://codereview.chromium.org/1709713002/#ps280001 (title: "CR danakj #31")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/patch-status/1709713002/280001 View timeline at https://chromium-cq-status.appspot.com/patch-timeline/1709713002/280001
https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... File base/task_scheduler/priority_queue.h (right): https://codereview.chromium.org/1709713002/diff/260001/base/task_scheduler/pr... base/task_scheduler/priority_queue.h:132: const SequenceAndSortKey empty_sequence_and_sort_key_; On 2016/03/18 21:22:18, fdoray wrote: > On 2016/03/18 20:24:05, danakj wrote: > > static? > > > > you could probably put this in an anon namespace in the cc file? > > I believe that the style guide doesn't allow non-POD static member. Is that > right? > https://google.github.io/styleguide/cppguide.html#Static_and_Global_Variables Oops, ya that's right.
Message was sent while issue was closed.
Description was changed from ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and Peek operations through a Transaction object. A SequenceSortKey must be provided to push a Sequence into a PriorityQueue. Sequences are sorted according to their SequenceSortKey. The SequenceSortKey of a Sequence never changes while it is in the PriorityQueue (even if Tasks are pushed/popped from the Sequence). BUG=553459 ========== to ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and Peek operations through a Transaction object. A SequenceSortKey must be provided to push a Sequence into a PriorityQueue. Sequences are sorted according to their SequenceSortKey. The SequenceSortKey of a Sequence never changes while it is in the PriorityQueue (even if Tasks are pushed/popped from the Sequence). BUG=553459 ==========
Message was sent while issue was closed.
Committed patchset #15 (id:280001)
Message was sent while issue was closed.
Description was changed from ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and Peek operations through a Transaction object. A SequenceSortKey must be provided to push a Sequence into a PriorityQueue. Sequences are sorted according to their SequenceSortKey. The SequenceSortKey of a Sequence never changes while it is in the PriorityQueue (even if Tasks are pushed/popped from the Sequence). BUG=553459 ========== to ========== TaskScheduler [4/9] Priority Queue This change is a subset of https://codereview.chromium.org/1698183005/ A PriorityQueue holds Sequences of Tasks. It supports Push, Pop and Peek operations through a Transaction object. A SequenceSortKey must be provided to push a Sequence into a PriorityQueue. Sequences are sorted according to their SequenceSortKey. The SequenceSortKey of a Sequence never changes while it is in the PriorityQueue (even if Tasks are pushed/popped from the Sequence). BUG=553459 Committed: https://crrev.com/6477fbded94522e26875bbf405710060d01ea971 Cr-Commit-Position: refs/heads/master@{#382115} ==========
Message was sent while issue was closed.
Patchset 15 (id:??) landed as https://crrev.com/6477fbded94522e26875bbf405710060d01ea971 Cr-Commit-Position: refs/heads/master@{#382115} |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
