Bug 40089 – Add a takeFirst() method to Deque and use it where appropriate

• Component: New Bugs
• Status: RESOLVED FIXED

[Tony Gentilcore]

Add a takeFirst() method to Deque and use it where appropriate

[Tony Gentilcore]

Created attachment 57716 [details]
Patch

[Tony Gentilcore]

abarth, you suggested adding a takeFirst() method in https://bugs.webkit.org/show_bug.cgi?id=20710.

Is this what you had in mind?

[Darin Adler]

Comment on attachment 57716 [details]
Patch

> +    template<typename T>
> +    inline T& Deque<T>::takeFirst()
> +    {
> +        T& temp = first();
> +        removeFirst();
> +        return temp;
> +    }

This won't work. This returns a reference to the place in memory where the first item was stored, but once removeFirst is called that location in memory no longer contains an object. The return type of takeFirst needs to be T, not T&, and the local variable, which should not be named "temp" since we don't use abbreviations like that in WebKit, should also be of type T. I would write it like this:

    template<typename T>
    inline T Deque<T>::takeFirst()
    {
        T oldFirst = first();
        removeFirst();
        return oldFirst;
    }

The only reason this seemed to be working is that we got lucky. The storage the object had been in was hanging around just long enough to not immediately crash.

[Adam Barth]

You can also use an out-param (WebKit style would be by reference) if you want to avoid doing two copies.  It might be worth looking at the ASM that gets generated to see if it's a win.

[Tony Gentilcore]

Created attachment 57789 [details]
Patch

[Tony Gentilcore]

(In reply to comment #3)
> (From update of attachment 57716 [details])
> > +    template<typename T>
> > +    inline T& Deque<T>::takeFirst()
> > +    {
> > +        T& temp = first();
> > +        removeFirst();
> > +        return temp;
> > +    }
> 
> This won't work.

Completely brain-dead mistake. I apologize it got uploaded. Fixed.

> This returns a reference to the place in memory where the first item was stored, but once removeFirst is called that location in memory no longer contains an object. The return type of takeFirst needs to be T, not T&, and the local variable, which should not be named "temp"

Point about "temp" fixed and noted for future reference. Thank you.

> since we don't use abbreviations like that in WebKit, should also be of type T. I would write it like this:
> 
>     template<typename T>
>     inline T Deque<T>::takeFirst()
>     {
>         T oldFirst = first();
>         removeFirst();
>         return oldFirst;
>     }
> 
> The only reason this seemed to be working is that we got lucky. The storage the object had been in was hanging around just long enough to not immediately crash.

[Tony Gentilcore]

(In reply to comment #4)
> You can also use an out-param (WebKit style would be by reference) if you want to avoid doing two copies.  It might be worth looking at the ASM that gets generated to see if it's a win.

Since this is an inline template method the ASM varies by call point. However, I went through a couple of them and it looks like the compiler is able to be smart about avoiding copies. For instance, in the case of the call in SegmentedString::advanceSubstring(), the extra copies are avoided (just the single copy at the call site remains). Listing below. Also most of the users are storing things that are cheap to copy in the Deque anyway.

If you like, I could modify this to use an out-param instead, but it might largely defeat the point as some of the call sites become considerably uglier. Please let me know what you think.

--- d:\chromiumgit\src\third_party\webkit\javascriptcore\wtf\deque.h -----------

    template<typename T>
    inline T Deque<T>::takeFirst()
    {
601162F0  push        esi  
601162F1  mov         esi,ecx 
        T oldFirst = first();
601162F3  mov         eax,dword ptr [esi] 
601162F5  mov         ecx,dword ptr [esi+8] 
601162F8  shl         eax,4 
601162FB  add         eax,ecx 
601162FD  mov         ecx,dword ptr [eax] 
601162FF  push        edi  
60116300  mov         edi,dword ptr [esp+0Ch] 
60116304  mov         dword ptr [edi],ecx 
60116306  mov         edx,dword ptr [eax+4] 
60116309  mov         dword ptr [edi+4],edx 
6011630C  mov         ecx,dword ptr [eax+8] 
6011630F  mov         dword ptr [edi+8],ecx 
60116312  test        ecx,ecx 
60116314  je          WTF::Deque<WebCore::SegmentedSubstring>::takeFirst+29h (60116319h) 
60116316  sub         dword ptr [ecx],0FFFFFF80h 
60116319  mov         al,byte ptr [eax+0Ch] 
6011631C  mov         byte ptr [edi+0Ch],al 
        removeFirst();
6011631F  mov         eax,dword ptr [esi] 
60116321  mov         ecx,dword ptr [esi+8] 
60116324  shl         eax,4 
60116327  lea         edx,[eax+ecx+10h] 
6011632B  add         eax,ecx 
6011632D  push        edx  
6011632E  push        eax  
6011632F  call        WTF::VectorDestructor<1,WebCore::SegmentedSubstring>::destruct (5FEB3610h) 
60116334  mov         ecx,dword ptr [esi+0Ch] 
60116337  mov         eax,dword ptr [esi] 
60116339  dec         ecx  
6011633A  add         esp,8 
6011633D  cmp         eax,ecx 
6011633F  jne         WTF::Deque<WebCore::SegmentedSubstring>::takeFirst+5Eh (6011634Eh) 
            TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
        else {
            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
            size_t newStart = newCapacity - (oldCapacity - m_start);
            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
            m_start = newStart;
        }
        m_buffer.deallocateBuffer(oldBuffer);
        checkValidity();
    }

    template<typename T>
    inline T Deque<T>::takeFirst()
    {
        T oldFirst = first();
        removeFirst();
        return oldFirst;
60116341  mov         eax,edi 
60116343  pop         edi  
60116344  mov         dword ptr [esi],0 
6011634A  pop         esi  
        else {
            TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
            size_t newStart = newCapacity - (oldCapacity - m_start);
            TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
            m_start = newStart;
        }
        m_buffer.deallocateBuffer(oldBuffer);
        checkValidity();
    }

    template<typename T>
    inline T Deque<T>::takeFirst()
    {
        T oldFirst = first();
        removeFirst();
        return oldFirst;
    }
6011634B  ret         4    
        removeFirst();
6011634E  inc         eax  
6011634F  mov         dword ptr [esi],eax 
        return oldFirst;
60116351  mov         eax,edi 
60116353  pop         edi  
60116354  pop         esi  
    }
60116355  ret         4

[Adam Barth]

Comment on attachment 57789 [details]
Patch

LGTM.  Thanks for looking into the details.

WebCore/html/HTMLTokenizer.cpp:217
 +          CachedScript* cs = m_pendingScripts.takeFirst().get();
I know this does the same thing as before, but it looks sketch.  Who else is hold a reference to this object for us?

[Tony Gentilcore]

(In reply to comment #8)
> (From update of attachment 57789 [details])
> LGTM.  Thanks for looking into the details.
> 
> WebCore/html/HTMLTokenizer.cpp:217
>  +          CachedScript* cs = m_pendingScripts.takeFirst().get();
> I know this does the same thing as before, but it looks sketch.  Who else is hold a reference to this object for us?

m_pendingScripts is a Deque<CachedResourceHandle> and CachedResourceHandle acts as a refcounting smart pointer for CachedResources. So, as written, if the CachedResource didn't have any other CachedResourceHandles at the same time, then that could cause the CachedResource to be freed. It has always been this way since CachedResourceHandle was introduced in r36109. This has probably never turned up because something else is holding another CachedResourceHandle. However, it is obviously a bad idea to rely on that fact. Thus, I believe the right fix is:
CachedResourceHandle<CachedScript> cs = m_pendingScripts.takeFirst();

Would you like me to make that change in this patch or would it be better in a separate patch?

[Darin Adler]

(In reply to comment #9)
> Would you like me to make that change in this patch or would it be better in a separate patch?

Separate patch.

[WebKit Commit Bot]

Comment on attachment 57789 [details]
Patch

Clearing flags on attachment: 57789

Committed r60683: <http://trac.webkit.org/changeset/60683>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.