Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve and extend our custom collection types #8

Open
jix opened this issue Sep 16, 2024 · 3 comments
Open

Improve and extend our custom collection types #8

jix opened this issue Sep 16, 2024 · 3 comments

Comments

@jix
Copy link
Member

jix commented Sep 16, 2024

We're using quite a few custom collection types, mostly TableSeq, IdVec or collections built on top of them (like IndexedIdVec) or otherwise related to TableSeq or Id types. I want to improve these in the following ways:

  • Implement more methods
    • Often there are standard library collection types that offer good guidance on which methods are useful for certain kind of collections
  • Offer more specialized wrappers for common use cases, e.g.:
    • TableSeq<T> corresponds (usage wise) to a Vec<HashTable<T>> but many uses of it could be a Vec<HashSet<T>> or Vec<HashMap<K, V>> so adding a SetSeq<T> and MapSeq<K, V> makes sense.
    • Often the subtable index for a TableSeq<T> (or future SetSeq<T> and MapSeq<K, V>) is the id_index() of an Id type, so Id{Table,Set,Map}Seq types would be useful
    • Polarity aware types that are indexed by a Var but allow insertion and querying using a Lit, automatically applying Boolean negation to the stored values as appropriate. This requires some currently missing traits to classify which types support Boolean negation (see also Traits for Boolean negation #7)
    • Have custom order preserving set and map types.
      • Essentially what the 3rd party indexmap crate offers, but more memory efficient
        • indexmap always uses a hashtable of 64-bit indices and caches the 64-bit hash value for all entries, that ends up using almost 3x as much memory as needed in most of our use cases
      • IndexedIdSet<u32, T> is essentially what this should be, but that doesn't have a great API for this use case because it also wants to be a map type with u32 keys
      • The index type used should be appropriately sized for the contained type or known size bound, e.g. when adding optional support for 64-bit Var/Lit, it should be IndexedIdSet<u64, T> instead of IndexedIdSet<u32, T>
@jix
Copy link
Member Author

jix commented Sep 16, 2024

I've started implementing some of this, as I needed it for something else I was working on, but I still need to extract it into a separate branch to turn it into at least a WIP PR.

@jix jix changed the title Improve and extend our custom collection types. Improve and extend our custom collection types Sep 16, 2024
@jix
Copy link
Member Author

jix commented Sep 30, 2024

The PR #13 adds SetSeq and IdSetSeq.

@jix
Copy link
Member Author

jix commented Oct 30, 2024

PR #17 provides the order preserving types mentioned in the issue

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant