Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
390983010:
Fix Deque.swap for deques with inline capacity
|
Created:
6 years, 5 months ago by Erik Corry Modified:
4 years, 9 months ago CC:
blink-reviews, Mads Ager (chromium), abarth-chromium, haraken, blink-reviews-wtf_chromium.org, kouhei+heap_chromium.org, Mikhail Base URL:
svn://svn.chromium.org/blink/trunk Project:
blink Visibility:
Public. |
DescriptionFix Deque.swap for deques with inline capacity
R=kbr@chromium.org, mikhail.pozdnyakov@gmail.com
BUG=360572
Patch Set 1 #Patch Set 2 : Remove unneeded CRTP #Patch Set 3 : Fix comment #Patch Set 4 : Make accidentally-public method private. #
Total comments: 6
Patch Set 5 : Fix test and bugs spotted by kbr #Patch Set 6 : Add more tests of Vector and Deque swap #
Total comments: 2
Patch Set 7 : Use more fullnesses in test to improve coverage #
Total comments: 19
Patch Set 8 : Address comments from Ken and Mads, and simplify #
Total comments: 14
Messages
Total messages: 18 (0 generated)
PTAL Deque and Vector both use the VectorBuffer, but Vector uses a size field, where Deque is a circular buffer and uses start and end fields. This change moves the size field from the VectorBuffer to the Vector where it makes sense (reducing the size of the Deque by a word) and fixes the swap method on VectorBuffer to be able to cope with multiple in-use ranges of inlineBuffer usage (the range in use for a deque can be split across the start and end of the inline buffer).
This change is pretty involved. Are you confident that the existing tests (and the parameterization changes you've made to DequeTest) sufficiently test both the Deque and Vector classes? I'm not particularly confident that the changes to swapVectorBuffer -- which seems to be the core change -- are sufficiently tested. Will Mikhail provide a domain expert's review? https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Deque.h#newco... Source/wtf/Deque.h:287: Range otherRange = (other.m_start != other.m_end && other.m_end == 0) ? Range(other.m_start, capacity()) : Range(other.m_start, other.m_end); It's legal to use capacity() with other because inlineCapacity is a template argument to both and must be equal for both? https://codereview.chromium.org/390983010/diff/60001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/DequeTest.cpp... Source/wtf/DequeTest.cpp:366: EXPECT_EQ(i - j, LivenessCounter::s_live); How does this work? It looks to me like in the nested loops above, j is greater than or equal to i. Won't that cause removeFirst() to be called too many times? https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Vector.h#newc... Source/wtf/Vector.h:493: void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, Range thisRange, Range otherRange) Are the changes to this method tested sufficiently? I see no changes to any Vector-related tests. All code paths should be exercised for a CL as involved as this one.
https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Deque.h#newco... Source/wtf/Deque.h:287: Range otherRange = (other.m_start != other.m_end && other.m_end == 0) ? Range(other.m_start, capacity()) : Range(other.m_start, other.m_end); On 2014/07/16 07:38:42, Ken Russell wrote: > It's legal to use capacity() with other because inlineCapacity is a template > argument to both and must be equal for both? No that was wrong, nice catch, poor tests! https://codereview.chromium.org/390983010/diff/60001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/DequeTest.cpp... Source/wtf/DequeTest.cpp:366: EXPECT_EQ(i - j, LivenessCounter::s_live); On 2014/07/16 07:38:42, Ken Russell wrote: > How does this work? It looks to me like in the nested loops above, j is greater > than or equal to i. Won't that cause removeFirst() to be called too many times? It doesn't work, but the fairlyPrime test that was supposed to make the test run faster by skipping some boring cases accidentally disabled most of the test. Ooops!
https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/60001/Source/wtf/Vector.h#newc... Source/wtf/Vector.h:493: void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, Range thisRange, Range otherRange) On 2014/07/16 07:38:42, Ken Russell wrote: > Are the changes to this method tested sufficiently? I see no changes to any > Vector-related tests. All code paths should be exercised for a CL as involved as > this one. More tests added
https://codereview.chromium.org/390983010/diff/100001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/100001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:115: Deque<int, inlineCapacity> intDeque2; Throughout this file and VectorTest.cpp, it seems to me that the following boundary conditions need to be tested: - deque or vector 1's inline capacity = 0, deque 2's inline capacity = 0 - deque or vector 1's inline capacity = 0, deque 2's inline capacity > 0 - deque or vector 1's inline capacity > 0, deque 2's inline capacity = 0 - deque or vector 1's inline capacity > 0 and == deque 2's inline capacity - deque or vector 1's inline capacity > 0 and > than deque 2's inline capacity, also > 0 - deque or vector 1's inline capacity > 0 and < than deque 2's inline capacity, also > 0 Could you please either argue why these conditions don't all need to be tested, or modify the tests to add these? Thanks.
https://codereview.chromium.org/390983010/diff/100001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/100001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:115: Deque<int, inlineCapacity> intDeque2; On 2014/07/17 18:39:58, Ken Russell wrote: > Throughout this file and VectorTest.cpp, it seems to me that the following > boundary conditions need to be tested: > > - deque or vector 1's inline capacity = 0, deque 2's inline capacity = 0 > - deque or vector 1's inline capacity = 0, deque 2's inline capacity > 0 > - deque or vector 1's inline capacity > 0, deque 2's inline capacity = 0 > - deque or vector 1's inline capacity > 0 and == deque 2's inline capacity > - deque or vector 1's inline capacity > 0 and > than deque 2's inline capacity, > also > 0 > - deque or vector 1's inline capacity > 0 and < than deque 2's inline capacity, > also > 0 > > Could you please either argue why these conditions don't all need to be tested, > or modify the tests to add these? Thanks. The template system doesn't allow you to swap if the inlineCapacity does not match, and you can't swap a vector with a deque or vice versa. So the tests that hit inline capacities of 0, 2 and 10 with up to 11 elements in the collections should be sufficient. I'll modify the tests to use more different fullnesses.
I put a breakpoint in every 'if' statement body in swapVectorBuffer and verified that they were all hit by wtf_unittests On Fri, Jul 18, 2014 at 9:16 AM, <erik.corry@gmail.com> wrote: > > https://codereview.chromium.org/390983010/diff/100001/ > Source/wtf/DequeTest.cpp > File Source/wtf/DequeTest.cpp (right): > > https://codereview.chromium.org/390983010/diff/100001/ > Source/wtf/DequeTest.cpp#newcode115 > Source/wtf/DequeTest.cpp:115: Deque<int, inlineCapacity> intDeque2; > On 2014/07/17 18:39:58, Ken Russell wrote: > >> Throughout this file and VectorTest.cpp, it seems to me that the >> > following > >> boundary conditions need to be tested: >> > > - deque or vector 1's inline capacity = 0, deque 2's inline capacity >> > = 0 > >> - deque or vector 1's inline capacity = 0, deque 2's inline capacity >> 0 >> - deque or vector 1's inline capacity > 0, deque 2's inline capacity >> > = 0 > >> - deque or vector 1's inline capacity > 0 and == deque 2's inline >> > capacity > >> - deque or vector 1's inline capacity > 0 and > than deque 2's inline >> > capacity, > >> also > 0 >> - deque or vector 1's inline capacity > 0 and < than deque 2's inline >> > capacity, > >> also > 0 >> > > Could you please either argue why these conditions don't all need to >> > be tested, > >> or modify the tests to add these? Thanks. >> > > The template system doesn't allow you to swap if the inlineCapacity does > not match, and you can't swap a vector with a deque or vice versa. So > the tests that hit inline capacities of 0, 2 and 10 with up to 11 > elements in the collections should be sufficient. > > I'll modify the tests to use more different fullnesses. > > https://codereview.chromium.org/390983010/ > To unsubscribe from this group and stop receiving emails from it, send an email to blink-reviews+unsubscribe@chromium.org.
Drive-by nits. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:49: private: Remove this line. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:112: friend class VectorBuffer<T, inlineCapacity, Allocator>; Is this needed? When is the VectorBuffer super class accessing private parts of the subclass? https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:314: static const size_t sizeFieldSize = sizeof(unsigned) * 2 > sizeof(double) ? sizeof(unsigned) * 2 : sizeof(double); I can't find any usages of this? https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:824: friend class VectorBuffer<T, inlineCapacity, Allocator>; Do you need this friend declaration?
Oh, and LGTM
I apologize for the delay re-reviewing this. Please see comments below. If you can find another reviewer willing to sign off on this code, please feel free; but I can't in good faith give a thumbs up to this change. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:283: template<typename T, size_t inlineCapacity, typename Allocator> Throughout this class, member function templates are used. I believe this is an error. The template parameters T, inlineCapacity, and Allocator should be re-used from the template parameters of the class. Otherwise it isn't apparent that they must match the values used at construction time, and I think it may be possible to subvert the type checking you intend. Basically, I think you should remove the template<typename T, size_t inlineCapacity, typename Allocator> lines throughout this class. The Deque<T, inlineCapacity, Allocator> scoping is redundant as well. If I'm correct about this issue, please send out a revised CL. Thanks. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:341: void theBigSwapTest() Please consider using a more descriptive name for this test and/or splitting up the test into multiple smaller ones. Someone coming in fresh to this code will have a hard time understanding what it does. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:411: void swapValuesTest() Same comment applies to this test name. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:493: void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, Range thisRange, Range otherRange) What are the invariants of this method? What does it mean if thisRange and otherRange specify differing numbers of elements? https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:505: } else { I can't in good faith review this method. It isn't apparent to me from reading the code that the algorithm is correct nor that the tests cover all of the code paths. Is there any way to rewrite this to be simpler? Perhaps having a couple of common fast paths, and then a more general but slow loop that actually allocates temporary storage using TypeOperations and does moves in order to visibly get a correct answer? https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:545: *otherRangePtr++ = Range(otherRange.start, thisRange.start); Where is the guarantee that the new range being pushed back for processing has the correct relationship to the last range in thisRanges so that the correct elements will be swapped? Same question regarding the additions to otherRanges and thisRanges below.
https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:112: friend class VectorBuffer<T, inlineCapacity, Allocator>; On 2014/07/18 11:03:14, Mads Ager (chromium) wrote: > Is this needed? When is the VectorBuffer super class accessing private parts of > the subclass? Not needed yet, removed. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:283: template<typename T, size_t inlineCapacity, typename Allocator> On 2014/07/21 20:44:09, Ken Russell wrote: > Throughout this class, member function templates are used. I believe this is an > error. The template parameters T, inlineCapacity, and Allocator should be > re-used from the template parameters of the class. Otherwise it isn't apparent > that they must match the values used at construction time, and I think it may be > possible to subvert the type checking you intend. Basically, I think you should > remove the template<typename T, size_t inlineCapacity, typename Allocator> lines > throughout this class. The Deque<T, inlineCapacity, Allocator> scoping is > redundant as well. > > If I'm correct about this issue, please send out a revised CL. Thanks. This is just because they are defined out of line. I am using the class template parameters. For a reduced example that hopefully makes it more clear, the template situation with bar and bar2 is identical, it's just that in the second case I am defining bar2 out of line, and so I have to write template<typename T> template <typename T> class Foo { bool bar(T* t) { return !!t; } bool bar2(T* t); } template <typename T> Foo<T>::bar2(T* t) { return !!t; } https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cpp File Source/wtf/DequeTest.cpp (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:341: void theBigSwapTest() On 2014/07/21 20:44:09, Ken Russell wrote: > Please consider using a more descriptive name for this test and/or splitting up > the test into multiple smaller ones. Someone coming in fresh to this code will > have a hard time understanding what it does. Renamed, and comment added. I saw no way to split up the test, since the point is to swap deques that have different histories, resulting in different patterns of use in the inline buffers. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/DequeTest.cp... Source/wtf/DequeTest.cpp:411: void swapValuesTest() On 2014/07/21 20:44:09, Ken Russell wrote: > Same comment applies to this test name. Acknowledged. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:314: static const size_t sizeFieldSize = sizeof(unsigned) * 2 > sizeof(double) ? sizeof(unsigned) * 2 : sizeof(double); On 2014/07/18 11:03:14, Mads Ager (chromium) wrote: > I can't find any usages of this? Removed. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:493: void swapVectorBuffer(VectorBuffer<T, inlineCapacity, Allocator>& other, Range thisRange, Range otherRange) On 2014/07/21 20:44:09, Ken Russell wrote: > What are the invariants of this method? What does it mean if thisRange and > otherRange specify differing numbers of elements? There's no problem with the ranges having a different number of elements. If the other vector buffer has more elements than this vector buffer then after the swap, things will be reversed, and this vector buffer will have more elements than the other vector buffer. I added a comment to explain this. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:505: } else { On 2014/07/21 20:44:09, Ken Russell wrote: > I can't in good faith review this method. It isn't apparent to me from reading > the code that the algorithm is correct nor that the tests cover all of the code > paths. Is there any way to rewrite this to be simpler? Perhaps having a couple > of common fast paths, and then a more general but slow loop that actually > allocates temporary storage using TypeOperations and does moves in order to > visibly get a correct answer? I managed to simplify this function quite a bit, without having to allocate and deallocate storage for a swap operation, or use three moves, where a swap would do. Hope it is more understandable now. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:545: *otherRangePtr++ = Range(otherRange.start, thisRange.start); On 2014/07/21 20:44:09, Ken Russell wrote: > Where is the guarantee that the new range being pushed back for processing has > the correct relationship to the last range in thisRanges so that the correct > elements will be swapped? Same question regarding the additions to otherRanges > and thisRanges below. There's no restriction on the ranges pushed on the two different stacks relative to each other, it's enough that each stack is internally ordered with the left range at the low index and the right range at the high index, which is definitely the case. Hopefully this is clearer in the new version. https://codereview.chromium.org/390983010/diff/120001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:824: friend class VectorBuffer<T, inlineCapacity, Allocator>; On 2014/07/18 11:03:14, Mads Ager (chromium) wrote: > Do you need this friend declaration? Removed.
Thanks for making the test case names more descriptive. https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:549: while (thisRangePtr >= thisRanges || otherRangePtr >= otherRanges) { Thanks for giving this more thought. This does look a lot clearer than the last version. As far as I can tell there are roughly six overlap relationships between thisRange and otherRange that have to be considered and I verified three by hand. I don't have time right now to verify the other three. Could you please do an over-the-shoulder review with Mads or someone else in your office and have them give a thumbs up on this code? I'll give my own thumbs up in response.
I'm a bit worried that WTF::Vector/VectorBuffer is getting more and more complex, but I do not have a simpler solution on top of my head. https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:46: class Deque : private VectorBuffer<T, inlineCapacity, Allocator>, public VectorDestructorBase<Deque<T, inlineCapacity, Allocator>, T, (inlineCapacity > 0), Allocator::isGarbageCollected> { Off topic: VectorBuffer sounds really vector-specific :) maybe give it more generic name LinearBuffer or so.. https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:314: static const size_t sizeFieldSize = sizeof(unsigned) * 2 > sizeof(double) ? sizeof(unsigned) * 2 : sizeof(double); I do not see 'sizeFieldSize' being used anywhere, could you pls tell why it is needed? https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:332: struct Range { Would be nice to see also the comment how these ranges are used (what are they for?) https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:333: Range(unsigned s = 0, unsigned e = 0) better 'start' and 'end' https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:339: bool IsEmpty() { return start == end; } nit: const method https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:348: Range* findRanges(Range* buffer, const Range in, unsigned capacity) this function does not use any of class members, so shouldn't it be just a free function? https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:348: Range* findRanges(Range* buffer, const Range in, unsigned capacity) const Range& in https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:1039: inline void Vector<T, inlineCapacity, Allocator>::resize(size_t sizeArg) AFAIK 'Arg' postfix is mostly used for template arguments in WTF, maybe 'newSize'?
https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:549: while (thisRangePtr >= thisRanges || otherRangePtr >= otherRanges) { On 2014/07/23 06:27:57, Ken Russell wrote: > Thanks for giving this more thought. This does look a lot clearer than the last > version. As far as I can tell there are roughly six overlap relationships > between thisRange and otherRange that have to be considered and I verified three > by hand. I don't have time right now to verify the other three. Could you please > do an over-the-shoulder review with Mads or someone else in your office and have > them give a thumbs up on this code? I'll give my own thumbs up in response. Ping. Any progress on an over-the-shoulder review in your office?
LGTM https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Deque.h File Source/wtf/Deque.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Deque.h#newc... Source/wtf/Deque.h:49: private: Remove this duplicate private: line. https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h File Source/wtf/Vector.h (right): https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:505: // The ranges Rewrap the lines. https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:510: // capacity is always the same size. same size -> same https://codereview.chromium.org/390983010/diff/140001/Source/wtf/Vector.h#new... Source/wtf/Vector.h:549: while (thisRangePtr >= thisRanges || otherRangePtr >= otherRanges) { On 2014/07/29 00:15:32, Ken Russell wrote: > On 2014/07/23 06:27:57, Ken Russell wrote: > > Thanks for giving this more thought. This does look a lot clearer than the > last > > version. As far as I can tell there are roughly six overlap relationships > > between thisRange and otherRange that have to be considered and I verified > three > > by hand. I don't have time right now to verify the other three. Could you > please > > do an over-the-shoulder review with Mads or someone else in your office and > have > > them give a thumbs up on this code? I'll give my own thumbs up in response. > > Ping. Any progress on an over-the-shoulder review in your office? Overlapping vacations at play. ;-) Erik and I discussed the old version of this code face to face. This looks simpler and I went through all the cases by hand and they look correct to me.
LGTM then. Erik, sorry for the delay on this review. Thanks for persisting with it and for the simplifications in the current version.
Can we land this?
My work needs this bug to be fixed, so let me take over this patch. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
