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

HashMap and moving GC #62

Open
CeleritasCelery opened this issue Mar 3, 2024 · 0 comments
Open

HashMap and moving GC #62

CeleritasCelery opened this issue Mar 3, 2024 · 0 comments
Labels
design needed Items where more design help is needed

Comments

@CeleritasCelery
Copy link
Owner

With the moving GC, we have an issue where the hash values of keys can change during garbage collection. The hash of an object is taken from its value, which is just a tagged pointer. So when the pointer moves, so does the hash. There are a couple possible solutions to this.

1. store the hash value in the object header

This is what other dynamic languages like C# and Java do. This is easy because we only need to calculate the hash once and it will never change. However this also takes more memory, at least 4 bytes if we want a good hash. This is especially problematic for Cons, which are very common and should only be 2 words wide. This would require them to have a header, which they currently don't need.

2. rehash the keys during GC

This is the path we are going to take for now until we can think of a better solution. Every GC the hashmap keys will have to be recalculated and inserted. This is costly. The way we do this now is via RefCell that let's us mutate a HashMap during collection. But this means we could also have runtime panics if there exists a root to one of the hashmap values. Not ideal. Here is paper about how to handle this issue and make it lest costly.

Ideally we should define a custom HashMap that let's us rehash all the keys without moving the values. I think this might be possible, but it might also require us forking either HashMap or IndexMap.

3. Is there a possible third option?

@CeleritasCelery CeleritasCelery added the design needed Items where more design help is needed label Mar 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
design needed Items where more design help is needed
Projects
None yet
Development

No branches or pull requests

1 participant