Bug 236852 – Clean up / optimize even more call sites constructing vectors

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Chris Dumez]

Clean up / optimize even more call sites constructing vectors.

[Chris Dumez]

Created attachment 452559 [details]
Patch

[Chris Dumez]

Created attachment 452565 [details]
Patch

[Chris Dumez]

Created attachment 452572 [details]
Patch

[Chris Dumez]

Created attachment 452587 [details]
Patch

[Chris Dumez]

Created attachment 452612 [details]
Patch

[Chris Dumez]

Created attachment 452613 [details]
Patch

[Chris Dumez]

Created attachment 452649 [details]
Patch

[Darin Adler]

Comment on attachment 452649 [details]
Patch

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

Some of these places where we create one-element vectors are cases where the receiving function should take a span so we don’t have to allocate/deallocate vector storage on the heap just to pass one thing in.

I haven’t been able to spot whatever mistake is making tests fail.

Seems like even more of these could use WTF::map.

> Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> +        // so we need to put them all in a set to get a unique list.
> +        HashSet<String> objectStoreSet;
> +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> +        objectStores = copyToVector(objectStoreSet);

Not new: It is unpleasant this puts the strings in hash table order, basically random. I would be tempted to use ListHashSet or sort afterward so things work more consistently. Unless somehow the order of this vector definitely does not matter.

In fact, removing duplicates from a list is probably not best done by putting it into a hash table and then taking it back out. Could use std::sort, std::unique, then remove past the end.

> Source/WebCore/Modules/indexeddb/IDBKeyData.h:171
> +    add(hasher, keyData.isDeletedValue());

There is no good reason to include a boolean "isDeletedValue" in the hash. If the deleted value is being used for hash tables, then those keys will never be hashed. Also, leaving something out of the hash only causes hash collisions, no other correctness problem.

> Source/WebCore/Modules/indexeddb/IDBTransaction.cpp:124
> +    Vector<String> names = isVersionChange() ? m_database->info().objectStoreNames() : m_info.objectStores();

Doesn’t auto work?

> Source/WebCore/Modules/mediasource/SourceBufferList.h:52
>      unsigned long length() const { return m_list.size(); }
> +
>      SourceBuffer* item(unsigned long index) const { return (index < m_list.size()) ? m_list[index].get() : nullptr; }

The "unsigned long" type here is not good.

> Source/WebCore/dom/DOMStringList.h:51
>      void append(const String& string) { m_strings.append(string); }
> +    void append(String&& string) { m_strings.append(WTFMove(string)); }

Not sure we need both of these; I think you can remove the const String& without changing behavior?

> Source/WebCore/dom/FullscreenManager.cpp:269
> +    topDocument.fullscreenManager().m_fullscreenElementStack = Vector { WTFMove(fullscrenElement) };

Is Vector needed here?

> Source/WebCore/dom/LoadableScript.cpp:54
> +    Ref protectedThis { *this };

Really should move this to callers. But maybe too risky at this time.

> Source/WebCore/html/canvas/WebGLRenderingContextBase.cpp:3027
>      Vector<RefPtr<WebGLShader>> shaderObjects;
>      for (auto shaderType : shaderTypes) {
> -        RefPtr<WebGLShader> shader = program.getAttachedShader(shaderType);
> -        if (shader)
> -            shaderObjects.append(shader);
> +        if (RefPtr shader = program.getAttachedShader(shaderType))
> +            shaderObjects.append(WTFMove(shader));
>      }
>      return shaderObjects;

Can we use compactMap?

> Source/WebCore/html/parser/HTMLMetaCharsetParser.cpp:90
>          String attributeName = StringImpl::create8BitIfPossible(attribute.name);
>          String attributeValue = StringImpl::create8BitIfPossible(attribute.value);

Besides narrowing to 8-bit, maybe we should put these in the AtomString table?

> Source/WebCore/page/TextIndicator.cpp:373
> +    data.textBoundingRectInRootViewCoordinates = WTFMove(textBoundingRectInRootViewCoordinates);
> +    data.textRectsInBoundingRectCoordinates = WTFMove(textRectsInBoundingRectCoordinates);

We don’t need move rectangles. They are all scalars.

> Source/WebCore/platform/audio/AudioDSPKernelProcessor.cpp:59
> +        m_kernels.reserveCapacity(m_kernels.capacity() + numberOfChannels());

If this happens repeatedly, then maybe we *don’t* want to reserve the exactly right amount of capacity, causing us to do a realloc each time. We could do a single shrinkToFit at the very end if we are going to keep the vector around.

> Source/WebCore/platform/audio/DynamicsCompressorKernel.cpp:66
> -    m_preDelayBuffers.clear();
> +    m_preDelayBuffers.shrink(0);
>      for (unsigned i = 0; i < numberOfChannels; ++i)
>          m_preDelayBuffers.append(makeUnique<AudioFloatArray>(MaxPreDelayFrames));
> +    m_preDelayBuffers.shrinkToFit();

Maybe we could use an idiom where we set capacity exactly here, and use uncheckedAppend? Not sure how practical that is.

> Source/WebCore/platform/gamepad/mac/LogitechGamepad.cpp:65
> +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> +            );

I don’t understand why this is Vector::from rather than just Vector with an initializer list.

> Source/WebCore/platform/gamepad/mac/StadiaHIDGamepad.cpp:76
> +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> +            );

Ditto.

> Source/WebCore/platform/graphics/PathUtilities.cpp:312
> +    Vector<Path> paths;

reserveInitialCapacity(polys.size())?

> Source/WebCore/platform/graphics/cocoa/FontPlatformDataCocoa.mm:71
> +    auto map = defaultVariationValues(platformFont, shouldLocalizeAxisNames);

It sure does seem unnecessarily confusing to choose the name "map" for this local. I think we can just do without the local variable. The next line of code wouldn't be too long.

> Source/WebKit/GPUProcess/media/RemoteSourceBufferProxy.cpp:81
> +    segmentInfo.audioTracks.reserveInitialCapacity(segment.audioTracks.size());
>      for (auto& audioTrackInfo : segment.audioTracks) {
>          auto identifier = m_remoteMediaPlayerProxy->addRemoteAudioTrackProxy(*audioTrackInfo.track);
> -        segmentInfo.audioTracks.append({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> +        segmentInfo.audioTracks.uncheckedAppend({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });

Could consider using WTF::map with a lambda with side effects here. After all, map is defined to be called sequentially, it’s not a super-magical parallel thing.

Same for the other two below.

> Source/WebKit/NetworkProcess/WebStorage/StorageManager.cpp:298
> +    for (const auto& localStorageNamespace : m_localStorageNamespaces.values())

I don’t think these const do much good.

> Source/WebKit/UIProcess/WebBackForwardList.cpp:371
> -        for (size_t i = 0; i < size; ++i) {
> -            didRemoveItem(m_entries[i]);
> -            removedItems.append(WTFMove(m_entries[i]));
> -        }
> +        for (auto& entry : m_entries)
> +            didRemoveItem(entry);
>  
> -        m_entries.clear();
>          m_currentIndex = std::nullopt;
> -        m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
> +        m_page->didChangeBackForwardList(nullptr, std::exchange(m_entries, { }));

Is this safe? Does didRemoveItem have any side effects that might be sensitive to the change in algorithm here?

> Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:676
> +        origins.reserveCapacity(origins.size() + dataRecord.origins.size());

Is this a good algorithm? Maybe shrinkToFit at the end is better.

> Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:717
> +                cookieHostNames.reserveCapacity(cookieHostNames.size() + dataRecord.cookieHostNames.size());

Same question. I always worry if we are manually expanding capacity, because it can lead to too many resizes in theory.

> Source/WebKit/UIProcess/ios/TextCheckerIOS.mm:265
> +                    detail.guesses = makeVector<String>(guesses);

Maybe even get rid of the local variable and do this as a one-liner?

> Source/WebKit/WebProcess/WebPage/WebPage.cpp:7862
>      Vector<RefPtr<SandboxExtension>> dragSandboxExtensions;

compactMap?

[Chris Dumez]

(In reply to Darin Adler from comment #8)
> Comment on attachment 452649 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=452649&action=review
> 
> Some of these places where we create one-element vectors are cases where the
> receiving function should take a span so we don’t have to
> allocate/deallocate vector storage on the heap just to pass one thing in.
> 
> I haven’t been able to spot whatever mistake is making tests fail.

I'll check. I was assuming the failures were unrelated until now.

> 
> Seems like even more of these could use WTF::map.
> 
> > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > +        // so we need to put them all in a set to get a unique list.
> > +        HashSet<String> objectStoreSet;
> > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > +        objectStores = copyToVector(objectStoreSet);
> 
> Not new: It is unpleasant this puts the strings in hash table order,
> basically random. I would be tempted to use ListHashSet or sort afterward so
> things work more consistently. Unless somehow the order of this vector
> definitely does not matter.
> 
> In fact, removing duplicates from a list is probably not best done by
> putting it into a hash table and then taking it back out. Could use
> std::sort, std::unique, then remove past the end.
> 
> > Source/WebCore/Modules/indexeddb/IDBKeyData.h:171
> > +    add(hasher, keyData.isDeletedValue());
> 
> There is no good reason to include a boolean "isDeletedValue" in the hash.
> If the deleted value is being used for hash tables, then those keys will
> never be hashed. Also, leaving something out of the hash only causes hash
> collisions, no other correctness problem.
> 
> > Source/WebCore/Modules/indexeddb/IDBTransaction.cpp:124
> > +    Vector<String> names = isVersionChange() ? m_database->info().objectStoreNames() : m_info.objectStores();
> 
> Doesn’t auto work?
> 
> > Source/WebCore/Modules/mediasource/SourceBufferList.h:52
> >      unsigned long length() const { return m_list.size(); }
> > +
> >      SourceBuffer* item(unsigned long index) const { return (index < m_list.size()) ? m_list[index].get() : nullptr; }
> 
> The "unsigned long" type here is not good.

Yes, will switch to unsigned.

> > Source/WebCore/dom/DOMStringList.h:51
> >      void append(const String& string) { m_strings.append(string); }
> > +    void append(String&& string) { m_strings.append(WTFMove(string)); }
> 
> Not sure we need both of these; I think you can remove the const String&
> without changing behavior?

Yes, I can indeed drop it without making any additional code patches.

> 
> > Source/WebCore/dom/FullscreenManager.cpp:269
> > +    topDocument.fullscreenManager().m_fullscreenElementStack = Vector { WTFMove(fullscrenElement) };
> 
> Is Vector needed here?

Apparently not, not sure why I added it.

> > Source/WebCore/dom/LoadableScript.cpp:54
> > +    Ref protectedThis { *this };
> 
> Really should move this to callers. But maybe too risky at this time.

Right, I'd rather not to this in this large patch.

> 
> > Source/WebCore/html/canvas/WebGLRenderingContextBase.cpp:3027
> >      Vector<RefPtr<WebGLShader>> shaderObjects;
> >      for (auto shaderType : shaderTypes) {
> > -        RefPtr<WebGLShader> shader = program.getAttachedShader(shaderType);
> > -        if (shader)
> > -            shaderObjects.append(shader);
> > +        if (RefPtr shader = program.getAttachedShader(shaderType))
> > +            shaderObjects.append(WTFMove(shader));
> >      }
> >      return shaderObjects;
> 
> Can we use compactMap?

shaderTypes is defined as an array (with only 2 items).

> 
> > Source/WebCore/html/parser/HTMLMetaCharsetParser.cpp:90
> >          String attributeName = StringImpl::create8BitIfPossible(attribute.name);
> >          String attributeValue = StringImpl::create8BitIfPossible(attribute.value);
> 
> Besides narrowing to 8-bit, maybe we should put these in the AtomString
> table?

Seems a little risky as part of this large patch.

> > Source/WebCore/page/TextIndicator.cpp:373
> > +    data.textBoundingRectInRootViewCoordinates = WTFMove(textBoundingRectInRootViewCoordinates);
> > +    data.textRectsInBoundingRectCoordinates = WTFMove(textRectsInBoundingRectCoordinates);
> 
> We don’t need move rectangles. They are all scalars.

OK. One is a Vector of rectangles though so that one is probably still valuable.

> 
> > Source/WebCore/platform/audio/AudioDSPKernelProcessor.cpp:59
> > +        m_kernels.reserveCapacity(m_kernels.capacity() + numberOfChannels());
> 
> If this happens repeatedly, then maybe we *don’t* want to reserve the
> exactly right amount of capacity, causing us to do a realloc each time. We
> could do a single shrinkToFit at the very end if we are going to keep the
> vector around.

I don't not believe this happens repeatedly. This is delayed initialization to avoid doing too much work in the constructor iirc.

> 
> > Source/WebCore/platform/audio/DynamicsCompressorKernel.cpp:66
> > -    m_preDelayBuffers.clear();
> > +    m_preDelayBuffers.shrink(0);
> >      for (unsigned i = 0; i < numberOfChannels; ++i)
> >          m_preDelayBuffers.append(makeUnique<AudioFloatArray>(MaxPreDelayFrames));
> > +    m_preDelayBuffers.shrinkToFit();
> 
> Maybe we could use an idiom where we set capacity exactly here, and use
> uncheckedAppend? Not sure how practical that is.
> 
> > Source/WebCore/platform/gamepad/mac/LogitechGamepad.cpp:65
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> I don’t understand why this is Vector::from rather than just Vector with an
> initializer list.

Good question, initializer list works fine here so I'll switch.

> 
> > Source/WebCore/platform/gamepad/mac/StadiaHIDGamepad.cpp:76
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> Ditto.
> 
> > Source/WebCore/platform/graphics/PathUtilities.cpp:312
> > +    Vector<Path> paths;
> 
> reserveInitialCapacity(polys.size())?

Sure.

> 
> > Source/WebCore/platform/graphics/cocoa/FontPlatformDataCocoa.mm:71
> > +    auto map = defaultVariationValues(platformFont, shouldLocalizeAxisNames);
> 
> It sure does seem unnecessarily confusing to choose the name "map" for this
> local. I think we can just do without the local variable. The next line of
> code wouldn't be too long.

OK.

> > Source/WebKit/GPUProcess/media/RemoteSourceBufferProxy.cpp:81
> > +    segmentInfo.audioTracks.reserveInitialCapacity(segment.audioTracks.size());
> >      for (auto& audioTrackInfo : segment.audioTracks) {
> >          auto identifier = m_remoteMediaPlayerProxy->addRemoteAudioTrackProxy(*audioTrackInfo.track);
> > -        segmentInfo.audioTracks.append({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> > +        segmentInfo.audioTracks.uncheckedAppend({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> 
> Could consider using WTF::map with a lambda with side effects here. After
> all, map is defined to be called sequentially, it’s not a super-magical
> parallel thing.
> 
> Same for the other two below.

OK.

> 
> > Source/WebKit/NetworkProcess/WebStorage/StorageManager.cpp:298
> > +    for (const auto& localStorageNamespace : m_localStorageNamespaces.values())
> 
> I don’t think these const do much good.

OK.

> 
> > Source/WebKit/UIProcess/WebBackForwardList.cpp:371
> > -        for (size_t i = 0; i < size; ++i) {
> > -            didRemoveItem(m_entries[i]);
> > -            removedItems.append(WTFMove(m_entries[i]));
> > -        }
> > +        for (auto& entry : m_entries)
> > +            didRemoveItem(entry);
> >  
> > -        m_entries.clear();
> >          m_currentIndex = std::nullopt;
> > -        m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
> > +        m_page->didChangeBackForwardList(nullptr, std::exchange(m_entries, { }));
> 
> Is this safe? Does didRemoveItem have any side effects that might be
> sensitive to the change in algorithm here?

I will double check.

> 
> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:676
> > +        origins.reserveCapacity(origins.size() + dataRecord.origins.size());
> 
> Is this a good algorithm? Maybe shrinkToFit at the end is better.

I don't understand the problem and I don't see how shrinkToFit() applies since I am not reserving too much capacity.
My change avoids unnecessary memory allocations for this loop:
```
for (auto& origin : dataRecord.origins)
    origins.uncheckedAppend(origin);
```

Note that we just allocated the Vector before the outer loop, therefore, the Vector doesn't have "extra" capacity. As far as I can tell, we're doing less memory allocations with my patch, not more.

> 
> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:717
> > +                cookieHostNames.reserveCapacity(cookieHostNames.size() + dataRecord.cookieHostNames.size());
> 
> Same question. I always worry if we are manually expanding capacity, because
> it can lead to too many resizes in theory.

Same comments as above. I do not understand how my change leads to more resizes. As far as I can tell, I can tell, I allocate just enough capacity right before each loop.
The only reason my code would cause an unnecessary capacity change is if the vector already had extra capacity. Looking at the code, I just don't see how that's possible.
We just allocated the Vector, and then we call append() in a nested loop.

> 
> > Source/WebKit/UIProcess/ios/TextCheckerIOS.mm:265
> > +                    detail.guesses = makeVector<String>(guesses);
> 
> Maybe even get rid of the local variable and do this as a one-liner?

Ok.

> 
> > Source/WebKit/WebProcess/WebPage/WebPage.cpp:7862
> >      Vector<RefPtr<SandboxExtension>> dragSandboxExtensions;
> 
> compactMap?

Done. I also changed the Vector to contain a Ref<> instead of a RefPtr<>.

[Chris Dumez]

Created attachment 452664 [details]
Patch

[Chris Dumez]

Retrying EWS. I haven't seen any evidence of an issue with the patch yet. I think the bots may be in a bad state.

[Chris Dumez]

(In reply to Darin Adler from comment #8)
> Comment on attachment 452649 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=452649&action=review
> 
> Some of these places where we create one-element vectors are cases where the
> receiving function should take a span so we don’t have to
> allocate/deallocate vector storage on the heap just to pass one thing in.
> 
> I haven’t been able to spot whatever mistake is making tests fail.
> 
> Seems like even more of these could use WTF::map.
> 
> > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > +        // so we need to put them all in a set to get a unique list.
> > +        HashSet<String> objectStoreSet;
> > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > +        objectStores = copyToVector(objectStoreSet);
> 
> Not new: It is unpleasant this puts the strings in hash table order,
> basically random. I would be tempted to use ListHashSet or sort afterward so
> things work more consistently. Unless somehow the order of this vector
> definitely does not matter.
> 
> In fact, removing duplicates from a list is probably not best done by
> putting it into a hash table and then taking it back out. Could use
> std::sort, std::unique, then remove past the end.
> 
> > Source/WebCore/Modules/indexeddb/IDBKeyData.h:171
> > +    add(hasher, keyData.isDeletedValue());
> 
> There is no good reason to include a boolean "isDeletedValue" in the hash.
> If the deleted value is being used for hash tables, then those keys will
> never be hashed. Also, leaving something out of the hash only causes hash
> collisions, no other correctness problem.
> 
> > Source/WebCore/Modules/indexeddb/IDBTransaction.cpp:124
> > +    Vector<String> names = isVersionChange() ? m_database->info().objectStoreNames() : m_info.objectStores();
> 
> Doesn’t auto work?
> 
> > Source/WebCore/Modules/mediasource/SourceBufferList.h:52
> >      unsigned long length() const { return m_list.size(); }
> > +
> >      SourceBuffer* item(unsigned long index) const { return (index < m_list.size()) ? m_list[index].get() : nullptr; }
> 
> The "unsigned long" type here is not good.
> 
> > Source/WebCore/dom/DOMStringList.h:51
> >      void append(const String& string) { m_strings.append(string); }
> > +    void append(String&& string) { m_strings.append(WTFMove(string)); }
> 
> Not sure we need both of these; I think you can remove the const String&
> without changing behavior?
> 
> > Source/WebCore/dom/FullscreenManager.cpp:269
> > +    topDocument.fullscreenManager().m_fullscreenElementStack = Vector { WTFMove(fullscrenElement) };
> 
> Is Vector needed here?
> 
> > Source/WebCore/dom/LoadableScript.cpp:54
> > +    Ref protectedThis { *this };
> 
> Really should move this to callers. But maybe too risky at this time.
> 
> > Source/WebCore/html/canvas/WebGLRenderingContextBase.cpp:3027
> >      Vector<RefPtr<WebGLShader>> shaderObjects;
> >      for (auto shaderType : shaderTypes) {
> > -        RefPtr<WebGLShader> shader = program.getAttachedShader(shaderType);
> > -        if (shader)
> > -            shaderObjects.append(shader);
> > +        if (RefPtr shader = program.getAttachedShader(shaderType))
> > +            shaderObjects.append(WTFMove(shader));
> >      }
> >      return shaderObjects;
> 
> Can we use compactMap?
> 
> > Source/WebCore/html/parser/HTMLMetaCharsetParser.cpp:90
> >          String attributeName = StringImpl::create8BitIfPossible(attribute.name);
> >          String attributeValue = StringImpl::create8BitIfPossible(attribute.value);
> 
> Besides narrowing to 8-bit, maybe we should put these in the AtomString
> table?
> 
> > Source/WebCore/page/TextIndicator.cpp:373
> > +    data.textBoundingRectInRootViewCoordinates = WTFMove(textBoundingRectInRootViewCoordinates);
> > +    data.textRectsInBoundingRectCoordinates = WTFMove(textRectsInBoundingRectCoordinates);
> 
> We don’t need move rectangles. They are all scalars.
> 
> > Source/WebCore/platform/audio/AudioDSPKernelProcessor.cpp:59
> > +        m_kernels.reserveCapacity(m_kernels.capacity() + numberOfChannels());
> 
> If this happens repeatedly, then maybe we *don’t* want to reserve the
> exactly right amount of capacity, causing us to do a realloc each time. We
> could do a single shrinkToFit at the very end if we are going to keep the
> vector around.
> 
> > Source/WebCore/platform/audio/DynamicsCompressorKernel.cpp:66
> > -    m_preDelayBuffers.clear();
> > +    m_preDelayBuffers.shrink(0);
> >      for (unsigned i = 0; i < numberOfChannels; ++i)
> >          m_preDelayBuffers.append(makeUnique<AudioFloatArray>(MaxPreDelayFrames));
> > +    m_preDelayBuffers.shrinkToFit();
> 
> Maybe we could use an idiom where we set capacity exactly here, and use
> uncheckedAppend? Not sure how practical that is.
> 
> > Source/WebCore/platform/gamepad/mac/LogitechGamepad.cpp:65
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> I don’t understand why this is Vector::from rather than just Vector with an
> initializer list.
> 
> > Source/WebCore/platform/gamepad/mac/StadiaHIDGamepad.cpp:76
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> Ditto.
> 
> > Source/WebCore/platform/graphics/PathUtilities.cpp:312
> > +    Vector<Path> paths;
> 
> reserveInitialCapacity(polys.size())?
> 
> > Source/WebCore/platform/graphics/cocoa/FontPlatformDataCocoa.mm:71
> > +    auto map = defaultVariationValues(platformFont, shouldLocalizeAxisNames);
> 
> It sure does seem unnecessarily confusing to choose the name "map" for this
> local. I think we can just do without the local variable. The next line of
> code wouldn't be too long.
> 
> > Source/WebKit/GPUProcess/media/RemoteSourceBufferProxy.cpp:81
> > +    segmentInfo.audioTracks.reserveInitialCapacity(segment.audioTracks.size());
> >      for (auto& audioTrackInfo : segment.audioTracks) {
> >          auto identifier = m_remoteMediaPlayerProxy->addRemoteAudioTrackProxy(*audioTrackInfo.track);
> > -        segmentInfo.audioTracks.append({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> > +        segmentInfo.audioTracks.uncheckedAppend({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> 
> Could consider using WTF::map with a lambda with side effects here. After
> all, map is defined to be called sequentially, it’s not a super-magical
> parallel thing.
> 
> Same for the other two below.
> 
> > Source/WebKit/NetworkProcess/WebStorage/StorageManager.cpp:298
> > +    for (const auto& localStorageNamespace : m_localStorageNamespaces.values())
> 
> I don’t think these const do much good.
> 
> > Source/WebKit/UIProcess/WebBackForwardList.cpp:371
> > -        for (size_t i = 0; i < size; ++i) {
> > -            didRemoveItem(m_entries[i]);
> > -            removedItems.append(WTFMove(m_entries[i]));
> > -        }
> > +        for (auto& entry : m_entries)
> > +            didRemoveItem(entry);
> >  
> > -        m_entries.clear();
> >          m_currentIndex = std::nullopt;
> > -        m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
> > +        m_page->didChangeBackForwardList(nullptr, std::exchange(m_entries, { }));
> 
> Is this safe? Does didRemoveItem have any side effects that might be
> sensitive to the change in algorithm here?

I looked at the implementation and didn’t find anything obviously risky. I think this is safe.

> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:676
> > +        origins.reserveCapacity(origins.size() + dataRecord.origins.size());
> 
> Is this a good algorithm? Maybe shrinkToFit at the end is better.
> 
> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:717
> > +                cookieHostNames.reserveCapacity(cookieHostNames.size() + dataRecord.cookieHostNames.size());
> 
> Same question. I always worry if we are manually expanding capacity, because
> it can lead to too many resizes in theory.
> 
> > Source/WebKit/UIProcess/ios/TextCheckerIOS.mm:265
> > +                    detail.guesses = makeVector<String>(guesses);
> 
> Maybe even get rid of the local variable and do this as a one-liner?
> 
> > Source/WebKit/WebProcess/WebPage/WebPage.cpp:7862
> >      Vector<RefPtr<SandboxExtension>> dragSandboxExtensions;
> 
> compactMap?

[Chris Dumez]

(In reply to Darin Adler from comment #8)
> Comment on attachment 452649 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=452649&action=review
> 
> Some of these places where we create one-element vectors are cases where the
> receiving function should take a span so we don’t have to
> allocate/deallocate vector storage on the heap just to pass one thing in.
> 
> I haven’t been able to spot whatever mistake is making tests fail.
> 
> Seems like even more of these could use WTF::map.
> 
> > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > +        // so we need to put them all in a set to get a unique list.
> > +        HashSet<String> objectStoreSet;
> > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > +        objectStores = copyToVector(objectStoreSet);
> 
> Not new: It is unpleasant this puts the strings in hash table order,
> basically random. I would be tempted to use ListHashSet or sort afterward so
> things work more consistently. Unless somehow the order of this vector
> definitely does not matter.
> 
> In fact, removing duplicates from a list is probably not best done by
> putting it into a hash table and then taking it back out. Could use
> std::sort, std::unique, then remove past the end.
> 
> > Source/WebCore/Modules/indexeddb/IDBKeyData.h:171
> > +    add(hasher, keyData.isDeletedValue());
> 
> There is no good reason to include a boolean "isDeletedValue" in the hash.
> If the deleted value is being used for hash tables, then those keys will
> never be hashed. Also, leaving something out of the hash only causes hash
> collisions, no other correctness problem.
> 
> > Source/WebCore/Modules/indexeddb/IDBTransaction.cpp:124
> > +    Vector<String> names = isVersionChange() ? m_database->info().objectStoreNames() : m_info.objectStores();
> 
> Doesn’t auto work?
> 
> > Source/WebCore/Modules/mediasource/SourceBufferList.h:52
> >      unsigned long length() const { return m_list.size(); }
> > +
> >      SourceBuffer* item(unsigned long index) const { return (index < m_list.size()) ? m_list[index].get() : nullptr; }
> 
> The "unsigned long" type here is not good.
> 
> > Source/WebCore/dom/DOMStringList.h:51
> >      void append(const String& string) { m_strings.append(string); }
> > +    void append(String&& string) { m_strings.append(WTFMove(string)); }
> 
> Not sure we need both of these; I think you can remove the const String&
> without changing behavior?
> 
> > Source/WebCore/dom/FullscreenManager.cpp:269
> > +    topDocument.fullscreenManager().m_fullscreenElementStack = Vector { WTFMove(fullscrenElement) };
> 
> Is Vector needed here?
> 
> > Source/WebCore/dom/LoadableScript.cpp:54
> > +    Ref protectedThis { *this };
> 
> Really should move this to callers. But maybe too risky at this time.
> 
> > Source/WebCore/html/canvas/WebGLRenderingContextBase.cpp:3027
> >      Vector<RefPtr<WebGLShader>> shaderObjects;
> >      for (auto shaderType : shaderTypes) {
> > -        RefPtr<WebGLShader> shader = program.getAttachedShader(shaderType);
> > -        if (shader)
> > -            shaderObjects.append(shader);
> > +        if (RefPtr shader = program.getAttachedShader(shaderType))
> > +            shaderObjects.append(WTFMove(shader));
> >      }
> >      return shaderObjects;
> 
> Can we use compactMap?
> 
> > Source/WebCore/html/parser/HTMLMetaCharsetParser.cpp:90
> >          String attributeName = StringImpl::create8BitIfPossible(attribute.name);
> >          String attributeValue = StringImpl::create8BitIfPossible(attribute.value);
> 
> Besides narrowing to 8-bit, maybe we should put these in the AtomString
> table?
> 
> > Source/WebCore/page/TextIndicator.cpp:373
> > +    data.textBoundingRectInRootViewCoordinates = WTFMove(textBoundingRectInRootViewCoordinates);
> > +    data.textRectsInBoundingRectCoordinates = WTFMove(textRectsInBoundingRectCoordinates);
> 
> We don’t need move rectangles. They are all scalars.
> 
> > Source/WebCore/platform/audio/AudioDSPKernelProcessor.cpp:59
> > +        m_kernels.reserveCapacity(m_kernels.capacity() + numberOfChannels());
> 
> If this happens repeatedly, then maybe we *don’t* want to reserve the
> exactly right amount of capacity, causing us to do a realloc each time. We
> could do a single shrinkToFit at the very end if we are going to keep the
> vector around.
> 
> > Source/WebCore/platform/audio/DynamicsCompressorKernel.cpp:66
> > -    m_preDelayBuffers.clear();
> > +    m_preDelayBuffers.shrink(0);
> >      for (unsigned i = 0; i < numberOfChannels; ++i)
> >          m_preDelayBuffers.append(makeUnique<AudioFloatArray>(MaxPreDelayFrames));
> > +    m_preDelayBuffers.shrinkToFit();
> 
> Maybe we could use an idiom where we set capacity exactly here, and use
> uncheckedAppend? Not sure how practical that is.
> 
> > Source/WebCore/platform/gamepad/mac/LogitechGamepad.cpp:65
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> I don’t understand why this is Vector::from rather than just Vector with an
> initializer list.
> 
> > Source/WebCore/platform/gamepad/mac/StadiaHIDGamepad.cpp:76
> > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > +            );
> 
> Ditto.
> 
> > Source/WebCore/platform/graphics/PathUtilities.cpp:312
> > +    Vector<Path> paths;
> 
> reserveInitialCapacity(polys.size())?
> 
> > Source/WebCore/platform/graphics/cocoa/FontPlatformDataCocoa.mm:71
> > +    auto map = defaultVariationValues(platformFont, shouldLocalizeAxisNames);
> 
> It sure does seem unnecessarily confusing to choose the name "map" for this
> local. I think we can just do without the local variable. The next line of
> code wouldn't be too long.
> 
> > Source/WebKit/GPUProcess/media/RemoteSourceBufferProxy.cpp:81
> > +    segmentInfo.audioTracks.reserveInitialCapacity(segment.audioTracks.size());
> >      for (auto& audioTrackInfo : segment.audioTracks) {
> >          auto identifier = m_remoteMediaPlayerProxy->addRemoteAudioTrackProxy(*audioTrackInfo.track);
> > -        segmentInfo.audioTracks.append({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> > +        segmentInfo.audioTracks.uncheckedAppend({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> 
> Could consider using WTF::map with a lambda with side effects here. After
> all, map is defined to be called sequentially, it’s not a super-magical
> parallel thing.
> 
> Same for the other two below.
> 
> > Source/WebKit/NetworkProcess/WebStorage/StorageManager.cpp:298
> > +    for (const auto& localStorageNamespace : m_localStorageNamespaces.values())
> 
> I don’t think these const do much good.
> 
> > Source/WebKit/UIProcess/WebBackForwardList.cpp:371
> > -        for (size_t i = 0; i < size; ++i) {
> > -            didRemoveItem(m_entries[i]);
> > -            removedItems.append(WTFMove(m_entries[i]));
> > -        }
> > +        for (auto& entry : m_entries)
> > +            didRemoveItem(entry);
> >  
> > -        m_entries.clear();
> >          m_currentIndex = std::nullopt;
> > -        m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
> > +        m_page->didChangeBackForwardList(nullptr, std::exchange(m_entries, { }));
> 
> Is this safe? Does didRemoveItem have any side effects that might be
> sensitive to the change in algorithm here?
> 
> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:676
> > +        origins.reserveCapacity(origins.size() + dataRecord.origins.size());
> 
> Is this a good algorithm? Maybe shrinkToFit at the end is better.

Oh, maybe because the vector already has some initial capacity (16?). I’ll check and update as needed.

> > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:717
> > +                cookieHostNames.reserveCapacity(cookieHostNames.size() + dataRecord.cookieHostNames.size());
> 
> Same question. I always worry if we are manually expanding capacity, because
> it can lead to too many resizes in theory.
> 
> > Source/WebKit/UIProcess/ios/TextCheckerIOS.mm:265
> > +                    detail.guesses = makeVector<String>(guesses);
> 
> Maybe even get rid of the local variable and do this as a one-liner?
> 
> > Source/WebKit/WebProcess/WebPage/WebPage.cpp:7862
> >      Vector<RefPtr<SandboxExtension>> dragSandboxExtensions;
> 
> compactMap?

[Chris Dumez]

Created attachment 452695 [details]
Patch

[Chris Dumez]

(In reply to Chris Dumez from comment #13)
> (In reply to Darin Adler from comment #8)
> > Comment on attachment 452649 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=452649&action=review
> > 
> > Some of these places where we create one-element vectors are cases where the
> > receiving function should take a span so we don’t have to
> > allocate/deallocate vector storage on the heap just to pass one thing in.
> > 
> > I haven’t been able to spot whatever mistake is making tests fail.
> > 
> > Seems like even more of these could use WTF::map.
> > 
> > > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > > +        // so we need to put them all in a set to get a unique list.
> > > +        HashSet<String> objectStoreSet;
> > > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > > +        objectStores = copyToVector(objectStoreSet);
> > 
> > Not new: It is unpleasant this puts the strings in hash table order,
> > basically random. I would be tempted to use ListHashSet or sort afterward so
> > things work more consistently. Unless somehow the order of this vector
> > definitely does not matter.
> > 
> > In fact, removing duplicates from a list is probably not best done by
> > putting it into a hash table and then taking it back out. Could use
> > std::sort, std::unique, then remove past the end.
> > 
> > > Source/WebCore/Modules/indexeddb/IDBKeyData.h:171
> > > +    add(hasher, keyData.isDeletedValue());
> > 
> > There is no good reason to include a boolean "isDeletedValue" in the hash.
> > If the deleted value is being used for hash tables, then those keys will
> > never be hashed. Also, leaving something out of the hash only causes hash
> > collisions, no other correctness problem.
> > 
> > > Source/WebCore/Modules/indexeddb/IDBTransaction.cpp:124
> > > +    Vector<String> names = isVersionChange() ? m_database->info().objectStoreNames() : m_info.objectStores();
> > 
> > Doesn’t auto work?
> > 
> > > Source/WebCore/Modules/mediasource/SourceBufferList.h:52
> > >      unsigned long length() const { return m_list.size(); }
> > > +
> > >      SourceBuffer* item(unsigned long index) const { return (index < m_list.size()) ? m_list[index].get() : nullptr; }
> > 
> > The "unsigned long" type here is not good.
> > 
> > > Source/WebCore/dom/DOMStringList.h:51
> > >      void append(const String& string) { m_strings.append(string); }
> > > +    void append(String&& string) { m_strings.append(WTFMove(string)); }
> > 
> > Not sure we need both of these; I think you can remove the const String&
> > without changing behavior?
> > 
> > > Source/WebCore/dom/FullscreenManager.cpp:269
> > > +    topDocument.fullscreenManager().m_fullscreenElementStack = Vector { WTFMove(fullscrenElement) };
> > 
> > Is Vector needed here?
> > 
> > > Source/WebCore/dom/LoadableScript.cpp:54
> > > +    Ref protectedThis { *this };
> > 
> > Really should move this to callers. But maybe too risky at this time.
> > 
> > > Source/WebCore/html/canvas/WebGLRenderingContextBase.cpp:3027
> > >      Vector<RefPtr<WebGLShader>> shaderObjects;
> > >      for (auto shaderType : shaderTypes) {
> > > -        RefPtr<WebGLShader> shader = program.getAttachedShader(shaderType);
> > > -        if (shader)
> > > -            shaderObjects.append(shader);
> > > +        if (RefPtr shader = program.getAttachedShader(shaderType))
> > > +            shaderObjects.append(WTFMove(shader));
> > >      }
> > >      return shaderObjects;
> > 
> > Can we use compactMap?
> > 
> > > Source/WebCore/html/parser/HTMLMetaCharsetParser.cpp:90
> > >          String attributeName = StringImpl::create8BitIfPossible(attribute.name);
> > >          String attributeValue = StringImpl::create8BitIfPossible(attribute.value);
> > 
> > Besides narrowing to 8-bit, maybe we should put these in the AtomString
> > table?
> > 
> > > Source/WebCore/page/TextIndicator.cpp:373
> > > +    data.textBoundingRectInRootViewCoordinates = WTFMove(textBoundingRectInRootViewCoordinates);
> > > +    data.textRectsInBoundingRectCoordinates = WTFMove(textRectsInBoundingRectCoordinates);
> > 
> > We don’t need move rectangles. They are all scalars.
> > 
> > > Source/WebCore/platform/audio/AudioDSPKernelProcessor.cpp:59
> > > +        m_kernels.reserveCapacity(m_kernels.capacity() + numberOfChannels());
> > 
> > If this happens repeatedly, then maybe we *don’t* want to reserve the
> > exactly right amount of capacity, causing us to do a realloc each time. We
> > could do a single shrinkToFit at the very end if we are going to keep the
> > vector around.
> > 
> > > Source/WebCore/platform/audio/DynamicsCompressorKernel.cpp:66
> > > -    m_preDelayBuffers.clear();
> > > +    m_preDelayBuffers.shrink(0);
> > >      for (unsigned i = 0; i < numberOfChannels; ++i)
> > >          m_preDelayBuffers.append(makeUnique<AudioFloatArray>(MaxPreDelayFrames));
> > > +    m_preDelayBuffers.shrinkToFit();
> > 
> > Maybe we could use an idiom where we set capacity exactly here, and use
> > uncheckedAppend? Not sure how practical that is.
> > 
> > > Source/WebCore/platform/gamepad/mac/LogitechGamepad.cpp:65
> > > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > > +            );
> > 
> > I don’t understand why this is Vector::from rather than just Vector with an
> > initializer list.
> > 
> > > Source/WebCore/platform/gamepad/mac/StadiaHIDGamepad.cpp:76
> > > +            auto hatswitchValues = Vector<SharedGamepadValue>::from(
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterTop],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterRight],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterBottom],
> > > +                m_buttonValues[(size_t)GamepadButtonRole::LeftClusterLeft]
> > > +            );
> > 
> > Ditto.
> > 
> > > Source/WebCore/platform/graphics/PathUtilities.cpp:312
> > > +    Vector<Path> paths;
> > 
> > reserveInitialCapacity(polys.size())?
> > 
> > > Source/WebCore/platform/graphics/cocoa/FontPlatformDataCocoa.mm:71
> > > +    auto map = defaultVariationValues(platformFont, shouldLocalizeAxisNames);
> > 
> > It sure does seem unnecessarily confusing to choose the name "map" for this
> > local. I think we can just do without the local variable. The next line of
> > code wouldn't be too long.
> > 
> > > Source/WebKit/GPUProcess/media/RemoteSourceBufferProxy.cpp:81
> > > +    segmentInfo.audioTracks.reserveInitialCapacity(segment.audioTracks.size());
> > >      for (auto& audioTrackInfo : segment.audioTracks) {
> > >          auto identifier = m_remoteMediaPlayerProxy->addRemoteAudioTrackProxy(*audioTrackInfo.track);
> > > -        segmentInfo.audioTracks.append({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> > > +        segmentInfo.audioTracks.uncheckedAppend({ MediaDescriptionInfo(*audioTrackInfo.description), identifier });
> > 
> > Could consider using WTF::map with a lambda with side effects here. After
> > all, map is defined to be called sequentially, it’s not a super-magical
> > parallel thing.
> > 
> > Same for the other two below.
> > 
> > > Source/WebKit/NetworkProcess/WebStorage/StorageManager.cpp:298
> > > +    for (const auto& localStorageNamespace : m_localStorageNamespaces.values())
> > 
> > I don’t think these const do much good.
> > 
> > > Source/WebKit/UIProcess/WebBackForwardList.cpp:371
> > > -        for (size_t i = 0; i < size; ++i) {
> > > -            didRemoveItem(m_entries[i]);
> > > -            removedItems.append(WTFMove(m_entries[i]));
> > > -        }
> > > +        for (auto& entry : m_entries)
> > > +            didRemoveItem(entry);
> > >  
> > > -        m_entries.clear();
> > >          m_currentIndex = std::nullopt;
> > > -        m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
> > > +        m_page->didChangeBackForwardList(nullptr, std::exchange(m_entries, { }));
> > 
> > Is this safe? Does didRemoveItem have any side effects that might be
> > sensitive to the change in algorithm here?
> > 
> > > Source/WebKit/UIProcess/WebsiteData/WebsiteDataStore.cpp:676
> > > +        origins.reserveCapacity(origins.size() + dataRecord.origins.size());
> > 
> > Is this a good algorithm? Maybe shrinkToFit at the end is better.
> 
> Oh, maybe because the vector already has some initial capacity (16?). I’ll
> check and update as needed.

Ok, I double checked. Vectors do start with an initial (minimum capacity) which is 16 by default and configurable via template parameters. As a result, my calls to reserveCapacity() would indeed result in possibility unnecessary allocations IF reserveCapacity() were to reduce the pre-existing capacity.

However, reserveCapacity() bails early if the new capacity is smaller or equal to the existing one. As a result, I think my code was correct and would only increase the capacity to something that we know for sure we'll need in the following loop.

I have however removed those changes from my patch to facilitate landing and in case there is still an issue with my approach that I didn't understand.

[Chris Dumez]

Created attachment 452697 [details]
Patch

[Chris Dumez]

Created attachment 452711 [details]
Patch

[Chris Dumez]

The iOS failure doesn't look related:
Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   org.webkit.WebKitTestRunnerApp	0x000000010f19b9a3 WTFCrashWithInfo(int, char const*, char const*, int) + 19
1   org.webkit.WebKitTestRunnerApp	0x000000010f1ceaf0 WTR::TestInvocation::runUISideScriptImmediately(OpaqueWKError const*, void*) + 98
2   com.apple.WebKit              	0x0000000116237854 WebKit::GenericCallback<>::performCallbackWithReturnValue() + 40
3   com.apple.WebKit              	0x0000000116233930 WebKit::RemoteLayerTreeDrawingAreaProxy::commitLayerTree(WebKit::RemoteLayerTreeTransaction const&, WebKit::RemoteScrollingCoordinatorTransaction const&) + 594
4   com.apple.WebKit              	0x0000000115f44d3b WebKit::RemoteLayerTreeDrawingAreaProxy::didReceiveMessage(IPC::Connection&, IPC::Decoder&) + 273
5   com.apple.WebKit              	0x00000001161d2eae IPC::MessageReceiverMap::dispatchMessage(IPC::Connection&, IPC::Decoder&) + 224

Based on https://results.webkit.org/?suite=layout-tests&test=editing%2Fspelling%2Fediting-word-with-marker-2.html, it appears it is a flaky crash on the bots already.

[Darin Adler]

Here’s the capacity story:

1) Adding to a vector has an algorithm to balance memory use with excessive reallocation, designed so that it’s not pathologically slow in any case.

2) If we were to reserve capacity every time we added an element (straw person example because no one would do that), then it would be pathologically slow.

3) When we know the exact size we can reserve capacity exactly once, which is *always* a win over the more than one times we’d reallocate, and also has the same or better memory benefits as shrinkToFit.

4) When we are *growing* by an exact size, reserving the capacity might be a win, but might screw up the algorithm. For example, if we happened to be growing by a single element each time, but doing that many times repeatedly, then this would give us the same problem as (2) above.

5) If our main concern is the total memory use at the end, and it’s like (4) above, then it’s possible we should just append and not do any capacity reserving and then shrinkToFit at the end.

6) It’s possible we could design the perfect idiom for growing a bunch at a time. Maybe reserveCapacity already has the smarts to avoid pathological edge cases and I just don’t realize it?

So while I *always* know that reserving capacity for the entire size of a vector is good without thinking deeply, reserving as we grow might actually not be as good and it’s trickier to be sure we are right. That’s my concern. Maybe I am wrong.

[Chris Dumez]

(In reply to Darin Adler from comment #19)
> Here’s the capacity story:
> 
> 1) Adding to a vector has an algorithm to balance memory use with excessive
> reallocation, designed so that it’s not pathologically slow in any case.

Indeed, appendSlow() calls expandCapacity(size + 1), which calls expandCapacity(size + 1), which calls:
`return reserveCapacity<action>(std::max(newMinCapacity, std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)));`

The `std::max(static_cast<size_t>(minCapacity), capacity() + capacity() / 4 + 1)` logic is likely the optimization you are referring to.
However, as I pointed out earlier, reserveCapacity() will just bail out early if the new capacity is smaller than (or the same as) the new one.

As a result, my extra calls to reserveCapacity() would not invalidate this optimization in expandCapacity(). Worse case scenario, we already have the capacity due to the optimization you mentioned and my new reserveCapacity() calls will be a no-op.
Best case scenario, we don't already have the capacity and my new reserveCapacity() calls will allocate enough capacity for the next loop.

Again, I took those out of my latest patch iteration as it seems a bit controversial.

[Darin Adler]

Yes, was just trying to convey this concern so we can figure it out for the future. I understand it’s no longer about this patch.

The risk I see is that reserveCapacity may result in a larger number of smaller-sized reallocations than if we hadn’t done reserveCapacity. If this happens it could hurt performance. I agree that there is no risk that reserveCapacity will allocate too much memory and no risk that it will shrink capacity. Because reserveCapacity allocates precise amounts of additional capacity, whereas expandCapacity intentionally allocates more to avoid pathologically large number of reallocations.

I am not saying that this is a problem.

[Chris Dumez]

(In reply to Darin Adler from comment #21)
> Yes, was just trying to convey this concern so we can figure it out for the
> future. I understand it’s no longer about this patch.
> 
> The risk I see is that reserveCapacity may result in a larger number of
> smaller-sized reallocations than if we hadn’t done reserveCapacity. If this
> happens it could hurt performance. I agree that there is no risk that
> reserveCapacity will allocate too much memory and no risk that it will
> shrink capacity. Because reserveCapacity allocates precise amounts of
> additional capacity, whereas expandCapacity intentionally allocates more to
> avoid pathologically large number of reallocations.
> 
> I am not saying that this is a problem.

Oh I see. Yes, I believe you're right that my potentially smaller reserveCapacity() calls could in theory hurt performance if append() would have reserved more. I think it is better not to make the change I suggested then.

[Chris Dumez]

Created attachment 452870 [details]
Patch

[Darin Adler]

Comment on attachment 452870 [details]
Patch

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

Hope I’m just not just writing the same comments again. I can’t remember what is new here.

> Source/WTF/wtf/cf/LanguageCF.cpp:109
>      Vector<String> languages;
> +    languages.reserveInitialCapacity(platformLanguagesCount);
>      for (CFIndex i = 0; i < platformLanguagesCount; i++) {
>          auto platformLanguage = static_cast<CFStringRef>(CFArrayGetValueAtIndex(platformLanguages.get(), i));
> -        languages.append(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
> +        languages.uncheckedAppend(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
>      }

Makes me think we should have a makeVector for CF in a VectorCF.h that is like VectorCocoa.h, because this would be nicer:

    auto languages = makeVector(platformLanguages.get(), [shouldMinimizeLanguages](CFTypeRef language) {
        return httpStyleLanguageCode(checked_cf_cast<CFStringRef>(language), shouldMinimizeLanguages);
    });

> Source/WebCore/Modules/applepay/cocoa/PaymentMethodCocoa.mm:105
> +        result.addressLines = Vector { String { street } };

I don’t think we need Vector here.

> Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> +        // so we need to put them all in a set to get a unique list.
> +        HashSet<String> objectStoreSet;
> +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> +        objectStores = copyToVector(objectStoreSet);

I made some of these comments already, but four comments on this moved code:

1) To actually get the optimization pretty sure we need to call WTFMove on storeNames rather than on the result of std::get.
2) JavaScript rather than javascript.
3) Why doesn’t HashSet have a constructor that takes a pair of iterators?
4) Building a set is not a great way to remove duplicates. A ListHashSet would be better because it preserves ordering rather than accidentally scrambling ordering using hashing resulting in a pseudo-random ordering. An algorithm using std::sort and std::unique would be even better, significantly more efficient, and yields a sorted results rather than a pseudo-random one.
5) Even if we don’t change the algorithm as suggested in (4), the operation of "remove duplicates from a Vector<String>" seems like it should be broken out into a separate function; maybe one that takes an rvalue reference to a vector and return a vector.

    objectStores = removeDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
    objectStores = sortAndRemoveDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
    objectStores = sortUnique(std::get<Vector<String>>(WTFMove(storeNames)));

Note that it seems obvious once you have to name the function that "remove duplicates and scramble the order" is not a good semantic.

> Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:184
>          objectStores.append(WTFMove(std::get<String>(storeNames)));

Calling append is not a great way to create a single-element vector. Maybe this:

    objectStores = { std::get<String>(WTFMove(storeNames)) };

> Source/WebCore/Modules/indexeddb/IDBKeyData.h:168
> +    add(hasher, keyData.isNull());

Is the other data to hash when the data is null? Maybe we need an if statement or early return?

> Source/WebCore/Modules/mediasource/SourceBufferList.h:63
>      Vector<RefPtr<SourceBuffer>>::iterator begin() { return m_list.begin(); }
>      Vector<RefPtr<SourceBuffer>>::iterator end() { return m_list.end(); }
> +    Vector<RefPtr<SourceBuffer>>::const_iterator begin() const { return m_list.begin(); }
> +    Vector<RefPtr<SourceBuffer>>::const_iterator end() const { return m_list.end(); }

I think we can use "auto" for these return types. And many other return types, but these seem to particularly benefit from it.

> Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTask.mm:132
> +    SpeechRecognitionResultData data { WTFMove(alternatives), !!isFinal };
> +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));

Might read better as a one liner since we would need one less WTFMove.

> Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTaskMock.mm:68
> +    SpeechRecognitionAlternativeData alternative { "Test", 1.0 };
> +    SpeechRecognitionResultData data { { WTFMove(alternative) }, true };
> +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));

Similar thought.

> Source/WebCore/dom/DOMStringList.h:64
> +    { }

I usually format these braces vertically, when the part above is formatted vertically. I suppose we should choose one style or the other for the future here.

> Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:214
> +        records.reserveCapacity(records.size() + value.size());
>          for (auto& record : value)
> -            records.append(record);
> +            records.uncheckedAppend(record);

I thought we discussed not making this change.

> Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:688
> +        keys.reserveCapacity(keys.size() + records.size());
>          for (auto& record : records)
> -            keys.append(record.key);
> +            keys.uncheckedAppend(record.key);

Ditto.

> Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:74
> +    m_cachedStatements.reserveInitialCapacity(static_cast<size_t>(StatementType::Invalid));
>      for (size_t i = 0; i < static_cast<size_t>(StatementType::Invalid); ++i)
> -        m_cachedStatements.append(nullptr);
> +        m_cachedStatements.uncheckedAppend(nullptr);

Should be:

    m_cachedStatements = Vector<std::unique_ptr<WebCore::SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid), nullptr);

Or something roughly like that. No loop.

> Source/WebKit/Shared/ApplePay/WebPaymentCoordinatorProxy.cpp:97
> +        return URL(URL(), linkIconURLString);

We really have to fix the URL class so this super-common operation can be written in a less bizarre way!

[Chris Dumez]

(In reply to Darin Adler from comment #24)
> Comment on attachment 452870 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=452870&action=review
> 
> Hope I’m just not just writing the same comments again. I can’t remember
> what is new here.
> 
> > Source/WTF/wtf/cf/LanguageCF.cpp:109
> >      Vector<String> languages;
> > +    languages.reserveInitialCapacity(platformLanguagesCount);
> >      for (CFIndex i = 0; i < platformLanguagesCount; i++) {
> >          auto platformLanguage = static_cast<CFStringRef>(CFArrayGetValueAtIndex(platformLanguages.get(), i));
> > -        languages.append(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
> > +        languages.uncheckedAppend(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
> >      }
> 
> Makes me think we should have a makeVector for CF in a VectorCF.h that is
> like VectorCocoa.h, because this would be nicer:
> 
>     auto languages = makeVector(platformLanguages.get(),
> [shouldMinimizeLanguages](CFTypeRef language) {
>         return httpStyleLanguageCode(checked_cf_cast<CFStringRef>(language),
> shouldMinimizeLanguages);
>     });

Yes, I think this would be nice. However, I'd rather not make such a change this is already large patch.

> 
> > Source/WebCore/Modules/applepay/cocoa/PaymentMethodCocoa.mm:105
> > +        result.addressLines = Vector { String { street } };
> 
> I don’t think we need Vector here.

I thought I tried that and it didn't build but I may be misremembering. I'll try again.

> > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > +        // so we need to put them all in a set to get a unique list.
> > +        HashSet<String> objectStoreSet;
> > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > +        objectStores = copyToVector(objectStoreSet);
> 
> I made some of these comments already, but four comments on this moved code:
> 
> 1) To actually get the optimization pretty sure we need to call WTFMove on
> storeNames rather than on the result of std::get.
> 2) JavaScript rather than javascript.
> 3) Why doesn’t HashSet have a constructor that takes a pair of iterators?
> 4) Building a set is not a great way to remove duplicates. A ListHashSet
> would be better because it preserves ordering rather than accidentally
> scrambling ordering using hashing resulting in a pseudo-random ordering. An
> algorithm using std::sort and std::unique would be even better,
> significantly more efficient, and yields a sorted results rather than a
> pseudo-random one.
> 5) Even if we don’t change the algorithm as suggested in (4), the operation
> of "remove duplicates from a Vector<String>" seems like it should be broken
> out into a separate function; maybe one that takes an rvalue reference to a
> vector and return a vector.
> 
>     objectStores =
> removeDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
>     objectStores =
> sortAndRemoveDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
>     objectStores = sortUnique(std::get<Vector<String>>(WTFMove(storeNames)));
> 
> Note that it seems obvious once you have to name the function that "remove
> duplicates and scramble the order" is not a good semantic.

This is pre-existing code and my patch didn't make things worse AFAICT. However, I will adopt sort + unique in this patch.

> > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:184
> >          objectStores.append(WTFMove(std::get<String>(storeNames)));
> 
> Calling append is not a great way to create a single-element vector. Maybe
> this:
> 
>     objectStores = { std::get<String>(WTFMove(storeNames)) };

Ok.

> 
> > Source/WebCore/Modules/indexeddb/IDBKeyData.h:168
> > +    add(hasher, keyData.isNull());
> 
> Is the other data to hash when the data is null? Maybe we need an if
> statement or early return?

This is pre-existing logic but I suspect you are right. I'll double check and fix if needed.

> 
> > Source/WebCore/Modules/mediasource/SourceBufferList.h:63
> >      Vector<RefPtr<SourceBuffer>>::iterator begin() { return m_list.begin(); }
> >      Vector<RefPtr<SourceBuffer>>::iterator end() { return m_list.end(); }
> > +    Vector<RefPtr<SourceBuffer>>::const_iterator begin() const { return m_list.begin(); }
> > +    Vector<RefPtr<SourceBuffer>>::const_iterator end() const { return m_list.end(); }
> 
> I think we can use "auto" for these return types. And many other return
> types, but these seem to particularly benefit from it.

OK.

> > Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTask.mm:132
> > +    SpeechRecognitionResultData data { WTFMove(alternatives), !!isFinal };
> > +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));
> 
> Might read better as a one liner since we would need one less WTFMove.

OK.

> 
> > Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTaskMock.mm:68
> > +    SpeechRecognitionAlternativeData alternative { "Test", 1.0 };
> > +    SpeechRecognitionResultData data { { WTFMove(alternative) }, true };
> > +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));
> 
> Similar thought.

OK.

> > Source/WebCore/dom/DOMStringList.h:64
> > +    { }
> 
> I usually format these braces vertically, when the part above is formatted
> vertically. I suppose we should choose one style or the other for the future
> here.
> 
> > Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:214
> > +        records.reserveCapacity(records.size() + value.size());
> >          for (auto& record : value)
> > -            records.append(record);
> > +            records.uncheckedAppend(record);
> 
> I thought we discussed not making this change.

We did and I did drop it at some point, not sure what happened. I may have messed up with GIT and re-uploaded an older iteration. I'll drop again, sorry about that.

> > Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:688
> > +        keys.reserveCapacity(keys.size() + records.size());
> >          for (auto& record : records)
> > -            keys.append(record.key);
> > +            keys.uncheckedAppend(record.key);
> 
> Ditto.

Will drop.

> 
> > Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:74
> > +    m_cachedStatements.reserveInitialCapacity(static_cast<size_t>(StatementType::Invalid));
> >      for (size_t i = 0; i < static_cast<size_t>(StatementType::Invalid); ++i)
> > -        m_cachedStatements.append(nullptr);
> > +        m_cachedStatements.uncheckedAppend(nullptr);
> 
> Should be:
> 
>     m_cachedStatements =
> Vector<std::unique_ptr<WebCore::
> SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid), nullptr);
> 
> Or something roughly like that. No loop.

I had thought of that and had tried it. We could even move it to the initializer list if it worked. Sadly, the compiler doesn't seem to like it.
```
In file included from /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/unified-sources/UnifiedSource31.cpp:1:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/MemoryStorageArea.cpp:27:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/MemoryStorageArea.h:28:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/StorageAreaBase.h:28:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/Platform/IPC/Connection.h:31:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/Platform/IPC/Decoder.h:32:
/Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/Vector.h:200:32: error: call to implicitly-deleted copy constructor of 'std::unique_ptr<WebCore::SQLiteStatement>'
            new (NotNull, dst) T(val);
/Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/Vector.h:275:62: note: in instantiation of member function 'WTF::VectorFiller<false, std::unique_ptr<WebCore::SQLiteStatement>>::uninitializedFill' requested here
        VectorFiller<VectorTraits<T>::canFillWithMemset, T>::uninitializedFill(dst, dstEnd, val);
/Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/Vector.h:645:29: note: in instantiation of member function 'WTF::VectorTypeOperations<std::unique_ptr<WebCore::SQLiteStatement>>::uninitializedFill' requested here
            TypeOperations::uninitializedFill(begin(), end(), val);
In file included from /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/unified-sources/UnifiedSource31.cpp:5:
/Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:75:26: note: in instantiation of member function 'WTF::Vector<std::unique_ptr<WebCore::SQLiteStatement>, 0, WTF::CrashOnOverflow, 16>::Vector' requested here
    m_cachedStatements = Vector<std::unique_ptr<WebCore::SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid), nullptr);
In file included from /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/unified-sources/UnifiedSource31.cpp:1:
In file included from /Volumes/Data/WebKit/OpenSource/Source/WebKit/WebKit2Prefix.h:72:
In file included from /usr/include/c++/v1/algorithm:653:
/usr/include/c++/v1/memory:1584:3: note: copy constructor is implicitly deleted because 'unique_ptr<WebCore::SQLiteStatement>' has a user-declared move constructor
  unique_ptr(unique_ptr&& __u) _NOEXCEPT
  ^
1 error generated.
```

I will try a bit more but I may not be able to do it.

> 
> > Source/WebKit/Shared/ApplePay/WebPaymentCoordinatorProxy.cpp:97
> > +        return URL(URL(), linkIconURLString);
> 
> We really have to fix the URL class so this super-common operation can be
> written in a less bizarre way!

Yes, I agree. I'll look into it. Maybe in a follow-up. Or maybe I can just add a new constructor, adopt it only here in this patch and follow-up for wider adoption.

[Darin Adler]

Not trying to get you to do all of this in one patch.

[Chris Dumez]

(In reply to Chris Dumez from comment #25)
> (In reply to Darin Adler from comment #24)
> > Comment on attachment 452870 [details]
> > Patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=452870&action=review
> > 
> > Hope I’m just not just writing the same comments again. I can’t remember
> > what is new here.
> > 
> > > Source/WTF/wtf/cf/LanguageCF.cpp:109
> > >      Vector<String> languages;
> > > +    languages.reserveInitialCapacity(platformLanguagesCount);
> > >      for (CFIndex i = 0; i < platformLanguagesCount; i++) {
> > >          auto platformLanguage = static_cast<CFStringRef>(CFArrayGetValueAtIndex(platformLanguages.get(), i));
> > > -        languages.append(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
> > > +        languages.uncheckedAppend(httpStyleLanguageCode(platformLanguage, shouldMinimizeLanguages));
> > >      }
> > 
> > Makes me think we should have a makeVector for CF in a VectorCF.h that is
> > like VectorCocoa.h, because this would be nicer:
> > 
> >     auto languages = makeVector(platformLanguages.get(),
> > [shouldMinimizeLanguages](CFTypeRef language) {
> >         return httpStyleLanguageCode(checked_cf_cast<CFStringRef>(language),
> > shouldMinimizeLanguages);
> >     });
> 
> Yes, I think this would be nice. However, I'd rather not make such a change
> this is already large patch.
> 
> > 
> > > Source/WebCore/Modules/applepay/cocoa/PaymentMethodCocoa.mm:105
> > > +        result.addressLines = Vector { String { street } };
> > 
> > I don’t think we need Vector here.
> 
> I thought I tried that and it didn't build but I may be misremembering. I'll
> try again.
> 
> > > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:182
> > > +        // It is valid for javascript to pass in a list of object store names with the same name listed twice,
> > > +        // so we need to put them all in a set to get a unique list.
> > > +        HashSet<String> objectStoreSet;
> > > +        objectStoreSet.add(objectStores.begin(), objectStores.end());
> > > +        objectStores = copyToVector(objectStoreSet);
> > 
> > I made some of these comments already, but four comments on this moved code:
> > 
> > 1) To actually get the optimization pretty sure we need to call WTFMove on
> > storeNames rather than on the result of std::get.
> > 2) JavaScript rather than javascript.
> > 3) Why doesn’t HashSet have a constructor that takes a pair of iterators?
> > 4) Building a set is not a great way to remove duplicates. A ListHashSet
> > would be better because it preserves ordering rather than accidentally
> > scrambling ordering using hashing resulting in a pseudo-random ordering. An
> > algorithm using std::sort and std::unique would be even better,
> > significantly more efficient, and yields a sorted results rather than a
> > pseudo-random one.
> > 5) Even if we don’t change the algorithm as suggested in (4), the operation
> > of "remove duplicates from a Vector<String>" seems like it should be broken
> > out into a separate function; maybe one that takes an rvalue reference to a
> > vector and return a vector.
> > 
> >     objectStores =
> > removeDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
> >     objectStores =
> > sortAndRemoveDuplicates(std::get<Vector<String>>(WTFMove(storeNames)));
> >     objectStores = sortUnique(std::get<Vector<String>>(WTFMove(storeNames)));
> > 
> > Note that it seems obvious once you have to name the function that "remove
> > duplicates and scramble the order" is not a good semantic.
> 
> This is pre-existing code and my patch didn't make things worse AFAICT.
> However, I will adopt sort + unique in this patch.
> 
> > > Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:184
> > >          objectStores.append(WTFMove(std::get<String>(storeNames)));
> > 
> > Calling append is not a great way to create a single-element vector. Maybe
> > this:
> > 
> >     objectStores = { std::get<String>(WTFMove(storeNames)) };
> 
> Ok.
> 
> > 
> > > Source/WebCore/Modules/indexeddb/IDBKeyData.h:168
> > > +    add(hasher, keyData.isNull());
> > 
> > Is the other data to hash when the data is null? Maybe we need an if
> > statement or early return?
> 
> This is pre-existing logic but I suspect you are right. I'll double check
> and fix if needed.
> 
> > 
> > > Source/WebCore/Modules/mediasource/SourceBufferList.h:63
> > >      Vector<RefPtr<SourceBuffer>>::iterator begin() { return m_list.begin(); }
> > >      Vector<RefPtr<SourceBuffer>>::iterator end() { return m_list.end(); }
> > > +    Vector<RefPtr<SourceBuffer>>::const_iterator begin() const { return m_list.begin(); }
> > > +    Vector<RefPtr<SourceBuffer>>::const_iterator end() const { return m_list.end(); }
> > 
> > I think we can use "auto" for these return types. And many other return
> > types, but these seem to particularly benefit from it.
> 
> OK.
> 
> > > Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTask.mm:132
> > > +    SpeechRecognitionResultData data { WTFMove(alternatives), !!isFinal };
> > > +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));
> > 
> > Might read better as a one liner since we would need one less WTFMove.
> 
> OK.
> 
> > 
> > > Source/WebCore/Modules/speech/cocoa/WebSpeechRecognizerTaskMock.mm:68
> > > +    SpeechRecognitionAlternativeData alternative { "Test", 1.0 };
> > > +    SpeechRecognitionResultData data { { WTFMove(alternative) }, true };
> > > +    _delegateCallback(SpeechRecognitionUpdate::createResult(_identifier, { WTFMove(data) }));
> > 
> > Similar thought.
> 
> OK.
> 
> > > Source/WebCore/dom/DOMStringList.h:64
> > > +    { }
> > 
> > I usually format these braces vertically, when the part above is formatted
> > vertically. I suppose we should choose one style or the other for the future
> > here.
> > 
> > > Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:214
> > > +        records.reserveCapacity(records.size() + value.size());
> > >          for (auto& record : value)
> > > -            records.append(record);
> > > +            records.uncheckedAppend(record);
> > 
> > I thought we discussed not making this change.
> 
> We did and I did drop it at some point, not sure what happened. I may have
> messed up with GIT and re-uploaded an older iteration. I'll drop again,
> sorry about that.
> 
> > > Source/WebKit/NetworkProcess/cache/CacheStorageEngineCache.cpp:688
> > > +        keys.reserveCapacity(keys.size() + records.size());
> > >          for (auto& record : records)
> > > -            keys.append(record.key);
> > > +            keys.uncheckedAppend(record.key);
> > 
> > Ditto.
> 
> Will drop.
> 
> > 
> > > Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:74
> > > +    m_cachedStatements.reserveInitialCapacity(static_cast<size_t>(StatementType::Invalid));
> > >      for (size_t i = 0; i < static_cast<size_t>(StatementType::Invalid); ++i)
> > > -        m_cachedStatements.append(nullptr);
> > > +        m_cachedStatements.uncheckedAppend(nullptr);
> > 
> > Should be:
> > 
> >     m_cachedStatements =
> > Vector<std::unique_ptr<WebCore::
> > SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid), nullptr);
> > 
> > Or something roughly like that. No loop.
> 
> I had thought of that and had tried it. We could even move it to the
> initializer list if it worked. Sadly, the compiler doesn't seem to like it.
> ```
> In file included from
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/
> unified-sources/UnifiedSource31.cpp:1:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/
> MemoryStorageArea.cpp:27:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/
> MemoryStorageArea.h:28:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/
> StorageAreaBase.h:28:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/Platform/IPC/Connection.h:31:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/Platform/IPC/Decoder.h:32:
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/
> Vector.h:200:32: error: call to implicitly-deleted copy constructor of
> 'std::unique_ptr<WebCore::SQLiteStatement>'
>             new (NotNull, dst) T(val);
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/
> Vector.h:275:62: note: in instantiation of member function
> 'WTF::VectorFiller<false,
> std::unique_ptr<WebCore::SQLiteStatement>>::uninitializedFill' requested here
>         VectorFiller<VectorTraits<T>::canFillWithMemset,
> T>::uninitializedFill(dst, dstEnd, val);
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/usr/local/include/wtf/
> Vector.h:645:29: note: in instantiation of member function
> 'WTF::VectorTypeOperations<std::unique_ptr<WebCore::SQLiteStatement>>::
> uninitializedFill' requested here
>             TypeOperations::uninitializedFill(begin(), end(), val);
> In file included from
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/
> unified-sources/UnifiedSource31.cpp:5:
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/NetworkProcess/storage/
> SQLiteStorageArea.cpp:75:26: note: in instantiation of member function
> 'WTF::Vector<std::unique_ptr<WebCore::SQLiteStatement>, 0,
> WTF::CrashOnOverflow, 16>::Vector' requested here
>     m_cachedStatements =
> Vector<std::unique_ptr<WebCore::
> SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid), nullptr);
> In file included from
> /Volumes/Data/WebKit/OpenSource/WebKitBuild/Release/DerivedSources/WebKit/
> unified-sources/UnifiedSource31.cpp:1:
> In file included from
> /Volumes/Data/WebKit/OpenSource/Source/WebKit/WebKit2Prefix.h:72:
> In file included from /usr/include/c++/v1/algorithm:653:
> /usr/include/c++/v1/memory:1584:3: note: copy constructor is implicitly
> deleted because 'unique_ptr<WebCore::SQLiteStatement>' has a user-declared
> move constructor
>   unique_ptr(unique_ptr&& __u) _NOEXCEPT
>   ^
> 1 error generated.
> ```
> 
> I will try a bit more but I may not be able to do it.

Oh, I think I got it to build. This in the initializer list:
```
m_cachedStatements(Vector<std::unique_ptr<WebCore::SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid)))
```

> > 
> > > Source/WebKit/Shared/ApplePay/WebPaymentCoordinatorProxy.cpp:97
> > > +        return URL(URL(), linkIconURLString);
> > 
> > We really have to fix the URL class so this super-common operation can be
> > written in a less bizarre way!
> 
> Yes, I agree. I'll look into it. Maybe in a follow-up. Or maybe I can just
> add a new constructor, adopt it only here in this patch and follow-up for
> wider adoption.

[Chris Dumez]

Created attachment 452878 [details]
Patch

[Darin Adler]

Comment on attachment 452878 [details]
Patch

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

> Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:69
> +    , m_cachedStatements(Vector<std::unique_ptr<WebCore::SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid)))

Two other thoughts. First, does this work?

    , m_cachedStatements(static_cast<size_t>(StatementType::Invalid))

Or if we can’t do that and the super-long length of this line bothers you, we could name the Vector type. Something like this:

    using StatementVector = Vector<std::unique_ptr<WebCore::SQLiteStatement>>;

Could be in the header file inside the class. Or above in this .cpp file. With as short or long a name as you think is needed.

[Chris Dumez]

(In reply to Darin Adler from comment #29)
> Comment on attachment 452878 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=452878&action=review
> 
> > Source/WebKit/NetworkProcess/storage/SQLiteStorageArea.cpp:69
> > +    , m_cachedStatements(Vector<std::unique_ptr<WebCore::SQLiteStatement>>(static_cast<size_t>(StatementType::Invalid)))
> 
> Two other thoughts. First, does this work?
> 
>     , m_cachedStatements(static_cast<size_t>(StatementType::Invalid))

Oh duh, yes :) This would be much nicer indeed and I bet it will build. Trying now...

[Chris Dumez]

Created attachment 452881 [details]
Patch

[Darin Adler]

Comment on attachment 452881 [details]
Patch

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

> Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:185
> +        // so we need to put them all in a set to get a unique list.

Comment should not mention "put them all in a set".

> Source/WebCore/Modules/indexeddb/IDBDatabase.cpp:188
> +        objectStores = sortAndRemoveDuplicates(WTFMove(std::get<Vector<String>>(storeNames)));
> +    } else
> +        objectStores = { WTFMove(std::get<String>(storeNames)) };

I think these WTFMove are wrong. it should be std::get<Vector<String>>(WTFMove(storeNames)).

[Chris Dumez]

Created attachment 452884 [details]
Patch

[Chris Dumez]

Comment on attachment 452881 [details]
Patch

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

> Source/WebCore/Modules/indexeddb/IDBKeyData.h:168
> +    add(hasher, keyData.isNull());

Note that I looked into it I am not convinced we need to do anything special (e.g. an early return is keyData is null).
If keyData is null, then keyData.type() will be IndexedDB::KeyType::Invalid and the next switch() will already do nothing.

[Darin Adler]

Comment on attachment 452881 [details]
Patch

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

>> Source/WebCore/Modules/indexeddb/IDBKeyData.h:168
>> +    add(hasher, keyData.isNull());
> 
> Note that I looked into it I am not convinced we need to do anything special (e.g. an early return is keyData is null).
> If keyData is null, then keyData.type() will be IndexedDB::KeyType::Invalid and the next switch() will already do nothing.

Not sure why null wasn’t implemented as a type instead of a separate flag. Later we could change this to use a Variant so we don’t have to write so much code.

[EWS]

Committed r290329 (247650@main): <https://commits.webkit.org/247650@main>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 452884 [details].

[Radar WebKit Bug Importer]

<rdar://problem/89311261>