Bug 128864 – Vector with inline capacity should work with non-PODs

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

Created attachment 224279 [details]
the patch

[Filip Pizlo]

Created attachment 224280 [details]
the patch

With some fixes.

[Filip Pizlo]

Comment on attachment 224280 [details]
the patch

Clearing r? because I have another fix on the way.  I'll actually test this before r?'ing again.

[Filip Pizlo]

Created attachment 224281 [details]
the patch

I'm still going to write a test for this, but it would be good to get a review for the approach.

[Filip Pizlo]

Looks like teh build is broken because Deque uses VectorBuffer.  Making that work with VectorBuffer now that VectorBuffer needs to know the size would be cumbersome.  But, luckily, *nobody* uses Deque with a non-zero inline capacity, except for the DFG::Worklist.  I know for a fact that the DFG::Worklist doesn't need to use a non-zero inline capacity.

[Filip Pizlo]

(In reply to comment #5)
> Looks like teh build is broken because Deque uses VectorBuffer.  Making that work with VectorBuffer now that VectorBuffer needs to know the size would be cumbersome.  But, luckily, *nobody* uses Deque with a non-zero inline capacity, except for the DFG::Worklist.  I know for a fact that the DFG::Worklist doesn't need to use a non-zero inline capacity.

WheelEventDeltaTracker also uses inline capacity.  However, I think that only EventHandler allocates it, and EventHandler is sufficiently fat that losing that inline capacity ought not be a big deal.

[Benjamin Poulain]

Comment on attachment 224281 [details]
the patch

View in context: https://bugs.webkit.org/attachment.cgi?id=224281&action=review

I would reeaaaallly like a test, even only on OS X. That will take 5 minutes and will avoid any stupid mistakes like this in future refactoring.

> Source/WTF/wtf/Vector.h:480
> -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> +            swapInlineBuffer(other, mySize, otherSize);
>              std::swap(m_capacity, other.m_capacity);
>          } else if (other.buffer() == other.inlineBuffer()) {
>              other.m_buffer = m_buffer;
>              m_buffer = inlineBuffer();
> -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> +            swapInlineBuffer(other, mySize, otherSize);

I am not sure I like swapInlineBuffer() in those cases though.

On remove, we just call the destructor. So it is basically garbage in one or the other of the inlineBuffer and we will swap valid values with garbage.

In these two cases, I would instead do a moveOperation from the buffer to the inline_buffer, followed by a call to the destructors on the unused inlineBuffer.

> Source/WTF/wtf/Vector.h:535
> +        for (unsigned i = swapBound; i--;)
> +            std::swap(left[i], right[i]);

Why do you go from swapBound to zero instead of zero to swapBound-1?

> Source/WTF/wtf/Vector.h:715
> +        Base::swap(other, m_size, other.m_size);

m_size is on VectorBufferBase, not sure you need to pass it here.

We could even have Base::swap() do the m_size swap to make things clearer.

[Filip Pizlo]

(In reply to comment #7)
> (From update of attachment 224281 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=224281&action=review
> 
> I would reeaaaallly like a test, even only on OS X. That will take 5 minutes and will avoid any stupid mistakes like this in future refactoring.

I will add one.  As I said in an earlier comment, I was using r? to get feedback on an incomplete patch.  The final patch will have to include changes to Deque and a test.  If you prefer, I can wait with requesting feedback until the patch is complete.  However, you just found a bug, so I think it's a good thing.

> 
> > Source/WTF/wtf/Vector.h:480
> > -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> > +            swapInlineBuffer(other, mySize, otherSize);
> >              std::swap(m_capacity, other.m_capacity);
> >          } else if (other.buffer() == other.inlineBuffer()) {
> >              other.m_buffer = m_buffer;
> >              m_buffer = inlineBuffer();
> > -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> > +            swapInlineBuffer(other, mySize, otherSize);
> 
> I am not sure I like swapInlineBuffer() in those cases though.
> 
> On remove, we just call the destructor. So it is basically garbage in one or the other of the inlineBuffer and we will swap valid values with garbage.
> 
> In these two cases, I would instead do a moveOperation from the buffer to the inline_buffer, followed by a call to the destructors on the unused inlineBuffer.

You're right, this is borked.  It's not just inelegant, it's plain broken: the size arguments to swapInlineBuffer() are meant to denote the size in the inline buffer, but in the case where one Vector is using an out-of-line buffer and the other is using an inline buffer, it's incorrect to say that the size used in the out-of-line buffer is the size used in the inline buffer - in fact that size used in the inline buffer is zero.

I *believe* that the cleanest way to write this is to have these cases call:

swapInlineBuffer(other, mySize, 0);

and:

swapInlineBuffer(other, 0, otherSize);

respectively.  It also means that these statements in swapInlineBuffers:

        leftSize = std::min(leftSize, inlineCapacity);
        rightSize = std::min(rightSize, inlineCapacity);

are unnecessary; we can instead assert that leftSize <= inlineCapacity and rightSize <= inlineCapacity.

I'll try this out and upload another patch...

> 
> > Source/WTF/wtf/Vector.h:535
> > +        for (unsigned i = swapBound; i--;)
> > +            std::swap(left[i], right[i]);
> 
> Why do you go from swapBound to zero instead of zero to swapBound-1?

This goes from swapBound - 1 to 0.  I prefer downward loops because they tend to be slightly cheaper in hardware (loop condition compares against zero, a constant, rather than the length, a non-constant that needs to be kept in a register or somewhere else).  This style of downward loop is particularly robust; it works with both unsigned and signed indices.

> 
> > Source/WTF/wtf/Vector.h:715
> > +        Base::swap(other, m_size, other.m_size);
> 
> m_size is on VectorBufferBase, not sure you need to pass it here.

I need to pass it because other subclasses of VectorBufferBase either don't use m_size at all or use it to mean something different.  The field was moved there not because it is semantically part of VectorBufferBase but because we are optimizing padding for Vector (at the expense of everyone else, FWIW).

> 
> We could even have Base::swap() do the m_size swap to make things clearer.

For example, Deque uses swap() but not m_size.  So, this would break Deque since m_size would have some irrelevant value.

[Filip Pizlo]

(In reply to comment #7)
> (From update of attachment 224281 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=224281&action=review
> 
> I would reeaaaallly like a test, even only on OS X. That will take 5 minutes and will avoid any stupid mistakes like this in future refactoring.
> 
> > Source/WTF/wtf/Vector.h:480
> > -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> > +            swapInlineBuffer(other, mySize, otherSize);
> >              std::swap(m_capacity, other.m_capacity);
> >          } else if (other.buffer() == other.inlineBuffer()) {
> >              other.m_buffer = m_buffer;
> >              m_buffer = inlineBuffer();
> > -            std::swap(m_inlineBuffer, other.m_inlineBuffer);
> > +            swapInlineBuffer(other, mySize, otherSize);
> 
> I am not sure I like swapInlineBuffer() in those cases though.
> 
> On remove, we just call the destructor. So it is basically garbage in one or the other of the inlineBuffer and we will swap valid values with garbage.
> 
> In these two cases, I would instead do a moveOperation from the buffer to the inline_buffer, followed by a call to the destructors on the unused inlineBuffer.

I could do this, but VectorTypeOperatins<T>::move() should do all of the right things, obviating the need to call destructors.

> 
> > Source/WTF/wtf/Vector.h:535
> > +        for (unsigned i = swapBound; i--;)
> > +            std::swap(left[i], right[i]);
> 
> Why do you go from swapBound to zero instead of zero to swapBound-1?
> 
> > Source/WTF/wtf/Vector.h:715
> > +        Base::swap(other, m_size, other.m_size);
> 
> m_size is on VectorBufferBase, not sure you need to pass it here.
> 
> We could even have Base::swap() do the m_size swap to make things clearer.

[Benjamin Poulain]

(In reply to comment #8)
> I will add one.  As I said in an earlier comment, I was using r? to get feedback on an incomplete patch.  The final patch will have to include changes to Deque and a test.  If you prefer, I can wait with requesting feedback until the patch is complete.  However, you just found a bug, so I think it's a good thing.

My bad. I thought you needed a quick review to unblock your FTL patches.

> > > Source/WTF/wtf/Vector.h:535
> > > +        for (unsigned i = swapBound; i--;)
> > > +            std::swap(left[i], right[i]);
> > 
> > Why do you go from swapBound to zero instead of zero to swapBound-1?
> 
> This goes from swapBound - 1 to 0.  I prefer downward loops because they tend to be slightly cheaper in hardware (loop condition compares against zero, a constant, rather than the length, a non-constant that needs to be kept in a register or somewhere else).  This style of downward loop is particularly robust; it works with both unsigned and signed indices.

I gotta love your way of thinking there :)

You can use a forward loop with clang. It optimizes it to either indexed forward loop or a downward loop depending on what is best for the memory access on the particular platform.
While the comparison with zero is cheap, going backward over memory will mess with the hardware prefetcher.

[Filip Pizlo]

(In reply to comment #10)
> (In reply to comment #8)
> > I will add one.  As I said in an earlier comment, I was using r? to get feedback on an incomplete patch.  The final patch will have to include changes to Deque and a test.  If you prefer, I can wait with requesting feedback until the patch is complete.  However, you just found a bug, so I think it's a good thing.
> 
> My bad. I thought you needed a quick review to unblock your FTL patches.
> 
> > > > Source/WTF/wtf/Vector.h:535
> > > > +        for (unsigned i = swapBound; i--;)
> > > > +            std::swap(left[i], right[i]);
> > > 
> > > Why do you go from swapBound to zero instead of zero to swapBound-1?
> > 
> > This goes from swapBound - 1 to 0.  I prefer downward loops because they tend to be slightly cheaper in hardware (loop condition compares against zero, a constant, rather than the length, a non-constant that needs to be kept in a register or somewhere else).  This style of downward loop is particularly robust; it works with both unsigned and signed indices.
> 
> I gotta love your way of thinking there :)
> 
> You can use a forward loop with clang. It optimizes it to either indexed forward loop or a downward loop depending on what is best for the memory access on the particular platform.

All compilers do this, if they can prove no loop-carried dependencies; this may be hard if the constructor/destructor of T does anything funny.  Even partial funny business like:

if (soooper rare case)
    call out-of-line function from a different module

will break any change-loop-direction kinds of optimizations.

> While the comparison with zero is cheap, going backward over memory will mess with the hardware prefetcher.

Huh.  Never heard of that one.  I'll take your word for it though. ;-)

[Filip Pizlo]

Created attachment 224302 [details]
the patch

[WebKit Commit Bot]

Attachment 224302 [details] did not pass style-queue:


ERROR: Source/WTF/wtf/Deque.h:41:  Code inside a namespace should not be indented.  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/Deque.h:165:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
ERROR: Source/WTF/wtf/Deque.h:196:  Should be indented on a separate line, with the colon or comma first on that line.  [whitespace/indent] [4]
Total errors found: 3 in 9 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Michael Saboff]

Comment on attachment 224302 [details]
the patch

r=me

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/164185