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

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=174715

            Bug ID: 174715
           Summary: Add a data structure for fixed sets of data that can
                    switch its implementation strategy based on the input
           Product: WebKit
           Version: WebKit Nightly Build
          Hardware: Unspecified
                OS: Unspecified
            Status: NEW
          Severity: Normal
          Priority: P2
         Component: Web Template Framework
          Assignee: webkit-unassigned at lists.webkit.org
          Reporter: sam at webkit.org

It's become increasingly common for there to be a need for a fixed (at compile time) set or map of objects. We have increasingly turned to NeverDestroyed<HashSet<>>s for these, but in many cases this is non-optimal. We should add a data structure that chooses the right underlying model (Single item, linear search array, binary search array, hash set, perfect hashing) based on the input (or direct choice by the author in special cases). (as a side note, when sets are needed, we could look into optimizations like having the hash table and the values array in contiguous readonly memory, we could avoid the need for deleted values and perhaps other aspects that are only needed in dynamic hash tables).

References to comments leading to this bug:

I noted in bug 174348:

"My biggest takeaway is that we have a lot of static maps / sets / vectors that never change and that perhaps we should have specialized data structures for them. And, it reaffirmed my curiosity on determining the right size of a list deserves what data structure (e.g. does a list of 4 items really need to be in a HashSet, or would lookups in Vector be just as fast)."


Darin noted in bug 174533:

"I am annoyed by the overuse of HashSet for fixed sets where more efficient algorithms may work better. I think I need to build a FixedSet family of class templates. Then it can be a HashSet only when the set is huge, an array with binary search when it’s smaller, an array with linear search when it’s even smaller, and a single function call when it has exactly one element. Either FixedSet can automatically do the right thing, we can have multiple FixedSet classes with identical interfaces but different implementations (FixedSingleItemSet, FixedLinearSearchSet, FixedBinarySearchSet, FixedHashSet), or FixedSet can take a template parameter to tell it which type of implementation to generate."

-- 
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/498ad6ef/attachment-0001.html>