Glistix / Glistix/stdlib

Consider using proper hashing for `Dict`

Open
#3 0 comments 0 reactions 0 assignees View on GitHub
enhancement good first issue nix incompatibility
Dominant language
Gleam
Stars
5
Forks
2
PR merge metrics
No merged PRs in 30d

Description

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`)

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.