[Webkit-unassigned] [Bug 174715] Add a data structure for fixed sets of data that can switch its implementation strategy based on the input

bugzilla-daemon at webkit.org bugzilla-daemon at webkit.org
Fri Jul 21 13:33:06 PDT 2017


--- Comment #5 from Darin Adler <darin at apple.com> ---
We already use perfect hashing implemented with gperf for cases where we decided performance was absolutely critical. The goal here is not necessarily to replace that, but to replace the cases where we needlessly use HashSet and create something that is unnecessarily large in code size and inefficient. With something trivially easy to use correctly and with good performance.

We may want to do this for just sets, or both sets and maps, for just strings or for all types of keys.

I do not think we should use perfect hashing for very small sets. I think we can outperform it with linear search and maybe even with binary search for some larger sets. Even for larger sets, I am not entirely sure perfect hashing is what we should be after. These are the considerations from most important to least, I think:

1) clarity of source code
2) memory use
3) code size
4) speed

Maybe I’m wrong about 2-4, but I am pretty sure that 1 is the top one.

You are receiving this mail because:
You are the assignee for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-unassigned/attachments/20170721/c5b5cbd4/attachment.html>

More information about the webkit-unassigned mailing list