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

Consider using proper hashing for Dict #3

Open
PgBiel opened this issue Apr 27, 2024 · 0 comments
Open

Consider using proper hashing for Dict #3

PgBiel opened this issue Apr 27, 2024 · 0 comments
Labels
enhancement New feature or request good first issue Good for newcomers nix incompatibility Some function works differently or doesn't work in the Nix target

Comments

@PgBiel
Copy link
Member

PgBiel commented Apr 27, 2024

Dictionaries currently work in the following way:

  • Some primitives, such as string, integers, booleans and paths, as well as field-less records, are stringified and turned into attributes of an internal attribute set. Thus, the "hashing" process of dict keys is, really, conversion to a string. This, at least, allows more efficient dictionary access by leveraging attribute sets.
  • Other types, including floats, cannot be reliably stringified in an unambiguous way. Thus, they are stored in a Nix list with key/value pairs. Access to those keys is thus O(n).

We could try to implement some proper hashing system instead of stringifying things. However, I'm not sure how possible that is for arbitrary attribute sets or lists (especially considering that they could have infinite depth). Also, we'd like have to keep using attribute sets with strings for fast access in some way if we want to have some amount of performance.

Still, it'd be interesting to take an attempt at this.
(See the reference implementation for JavaScript at src/dict.mjs)

@PgBiel PgBiel added enhancement New feature or request good first issue Good for newcomers nix incompatibility Some function works differently or doesn't work in the Nix target labels Apr 27, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers nix incompatibility Some function works differently or doesn't work in the Nix target
Projects
None yet
Development

No branches or pull requests

1 participant