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
Created attachment 274272 [details] WIP might be ready.
I've been getting about a 1.5-2.5% octane/code-load speed up from this.
Created attachment 274328 [details] perf numbers looks like a code-load progression. Will post patch soon.
Created attachment 274344 [details] patch
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.
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.
Created attachment 274345 [details] patch
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.
Created attachment 274346 [details] patch
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.
Created attachment 274347 [details] patch
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.
landed in: http://trac.webkit.org/changeset/198375
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?
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.
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.
(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.
(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.
(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.