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

std: make ArrayHashMap eql function accept an additional param #10742

Merged
merged 2 commits into from Feb 1, 2022

Conversation

andrewrk
Copy link
Member

which is the index of the key that already exists in the hash map.

This enables the use case of using AutoArrayHashMap(void, void) which
may seem surprising at first, but is actually pretty handy!
This commit includes a proof-of-concept of how I want to use it, with a
new InternArena abstraction for stage2 that provides a compact way to
store values (and types) in an "internment arena", thus making types
stored exactly once (per arena), representable with a single u32 as a
reference to a type within an InternArena, and comparable with a
simple u32 integer comparison. If both types are in the same
InternArena, you can check if they are equal by seeing if their index is
the same.

What's neat about AutoArrayHashMap(void, void) is that it allows us to
look up the indexes by key, without actually storing the keys.
Instead, keys are treated as ephemeral values that are constructed as
needed.

As a result, we have an extremely efficient encoding of types and
values, represented only by three arrays, which has no pointers, and can
therefore be serialized and deserialized by a single writev/readv call.
The map field is denormalized data and can be computed from the other
two fields.

This is in contrast to our current Type/Value system which makes
extensive use of pointers.

The test at the bottom of InternArena.zig passes in this commit.

which is the index of the key that already exists in the hash map.

This enables the use case of using `AutoArrayHashMap(void, void)` which
may seem surprising at first, but is actually pretty handy!
This commit includes a proof-of-concept of how I want to use it, with a
new InternArena abstraction for stage2 that provides a compact way to
store values (and types) in an "internment arena", thus making types
stored exactly once (per arena), representable with a single u32 as a
reference to a type within an InternArena, and comparable with a
simple u32 integer comparison. If both types are in the same
InternArena, you can check if they are equal by seeing if their index is
the same.

What's neat about `AutoArrayHashMap(void, void)` is that it allows us to
look up the indexes by key, *without actually storing the keys*.
Instead, keys are treated as ephemeral values that are constructed as
needed.

As a result, we have an extremely efficient encoding of types and
values, represented only by three arrays, which has no pointers, and can
therefore be serialized and deserialized by a single writev/readv call.
The `map` field is denormalized data and can be computed from the other
two fields.

This is in contrast to our current Type/Value system which makes
extensive use of pointers.

The test at the bottom of InternArena.zig passes in this commit.
@andrewrk andrewrk added proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. frontend Tokenization, parsing, AstGen, Sema, and Liveness. standard library This issue involves writing Zig code for the standard library. breaking Implementing this issue could cause existing code to no longer compile or have different behavior. labels Jan 31, 2022
@andrewrk
Copy link
Member Author

I added the "breaking" label but note that it's only breaking for the "adapted" variants of the ArrayHashMap API. Regular usage with AutoArrayHashMap is unaffected.

@andrewrk andrewrk merged commit 3e99495 into master Feb 1, 2022
@andrewrk andrewrk deleted the ArrayHashMapEql branch February 1, 2022 18:20
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
breaking Implementing this issue could cause existing code to no longer compile or have different behavior. frontend Tokenization, parsing, AstGen, Sema, and Liveness. proposal This issue suggests modifications. If it also has the "accepted" label then it is planned. standard library This issue involves writing Zig code for the standard library.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant