Add a takeFirst() method to Deque and use it where appropriate
Created attachment 57716 [details] Patch
abarth, you suggested adding a takeFirst() method in https://bugs.webkit.org/show_bug.cgi?id=20710. Is this what you had in mind?
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.
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.
Created attachment 57789 [details] Patch
(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.
(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
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?
(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?
(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.
Comment on attachment 57789 [details] Patch Clearing flags on attachment: 57789 Committed r60683: <http://trac.webkit.org/changeset/60683>
All reviewed patches have been landed. Closing bug.