Skip to content

Consider using proper hashing for Dict #3

@PgBiel

Description

@PgBiel

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)

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or requestgood first issueGood for newcomersnix incompatibilitySome function works differently or doesn't work in the Nix target

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions