Bug 155552 – Implement SmallPtrSet and integrate it into the Parser

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Saam Barati]

This data structure will use an inline array when the set is small.
It won't have a remove operation.
This should help speed up some of the HashSets we use inside the parser.
It'll also be helpful in other places.

See http://llvm.org/docs/doxygen/html/SmallPtrSet_8h_source.html

[Saam Barati]

Created attachment 274272 [details]
WIP

might be ready.

[Saam Barati]

I've been getting about a 1.5-2.5% octane/code-load speed up from this.

[Saam Barati]

Created attachment 274328 [details]
perf numbers

looks like a code-load progression.
Will post patch soon.

[Saam Barati]

Created attachment 274344 [details]
patch

[Saam Barati]

Comment on attachment 274344 [details]
patch

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

> Source/JavaScriptCore/parser/Parser.h:195
> +    Scope(Scope&& rhs)

Actually, with vector.constructAndAppend(...) we don't need this.
I'm removing it locally.

I'm also adding a comment at the top of the fields inside Scope saying
that they must be movable through memcpy.

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/SmallPtrSet.h:113:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/WTF/wtf/SmallPtrSet.h:243:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 2 in 8 files


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

[Saam Barati]

Created attachment 274345 [details]
patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/SmallPtrSet.h:113:  Multi line control clauses should use braces.  [whitespace/braces] [4]
ERROR: Source/WTF/wtf/SmallPtrSet.h:243:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 2 in 8 files


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

[Saam Barati]

Created attachment 274346 [details]
patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/SmallPtrSet.h:113:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 1 in 8 files


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

[Saam Barati]

Created attachment 274347 [details]
patch

[WebKit Commit Bot]

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


ERROR: Source/WTF/wtf/SmallPtrSet.h:113:  Multi line control clauses should use braces.  [whitespace/braces] [4]
Total errors found: 1 in 8 files


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

[Saam Barati]

landed in:
http://trac.webkit.org/changeset/198375

[Sam Weinig]

Would there be value in trying to add this optimization (perhaps optionally using traits) to our HashMap/HashSet code? Presumably this optimization could be useful in other places, where they weren't necessarily storing pointers.

Also, is the reason you don't support remove to avoid having a branch for a deleteValue sentinel?

[Oliver Hunt]

Comment on attachment 274347 [details]
patch

I would rather have had the inline size be a template parameter (as we do for other data structures) - we could give a default capacity so the general behaviour wouldn't be impacted.

[Geoffrey Garen]

Comment on attachment 274347 [details]
patch

Longer-term, it would be nice to have inline capacity as an option in WTF::HashSet and WTF::HashMap. Perhaps the optimizations you've added for never removing, linear scanning, and memcpy are fundamentally incompatible with those more flexible data structures. But maybe not.

[Saam Barati]

(In reply to comment #14)
> Would there be value in trying to add this optimization (perhaps optionally
> using traits) to our HashMap/HashSet code? Presumably this optimization
> could be useful in other places, where they weren't necessarily storing
> pointers.
> 
> Also, is the reason you don't support remove to avoid having a branch for a
> deleteValue sentinel?

I think it's worth experimenting with some inline capacity inside HashMap/HashSet.
I'm sure there are places where this would really help out.

Not supporting remove() does remove a branch, but it also simplifies some
of the assumptions made in the code. It wouldn't be that difficult to add support
for remove, but I'm hesitant to do it. I really want this data structure to
be as simple as possible.

I think one place where it might be worth adding some complexity is in supporting
smart pointers. I don't think it'd be that difficult to do.

[Saam Barati]

(In reply to comment #15)
> Comment on attachment 274347 [details]
> patch
> 
> I would rather have had the inline size be a template parameter (as we do
> for other data structures) - we could give a default capacity so the general
> behaviour wouldn't be impacted.

I think this is worth doing at some point. It seems like a good patch
to do when we find code that needs it. LLVM's implementation does support
inline capacity as a template parameter.

[Saam Barati]

(In reply to comment #16)
> Comment on attachment 274347 [details]
> patch
> 
> Longer-term, it would be nice to have inline capacity as an option in
> WTF::HashSet and WTF::HashMap. Perhaps the optimizations you've added for
> never removing, linear scanning, and memcpy are fundamentally incompatible
> with those more flexible data structures. But maybe not.

I'm not sure. I would have to familiarize myself more with the details
of how HashMap/HashSet are implemented. I'm sure it would be possible
to add inline capacity to HashMap/HashSet in some form, but maybe it
wouldn't be exactly as it is implemented here. For example, HashMap/HashSet
support remove, so when we're in small mode and we perform contains(.) we will 
have to traverse the entire inline array instead of just up to m_size.