High performance data structures design & optimizing for the GC

In my last post on the topic, I talked about ImmutableDictionary and why it was too costly for us to use. At the same time, it is basically the data structure that we need for the task at hand. That task is keeping track of the current set of modified pages, with multiple concurrent versions running at the same time.ImmutableDictionary is perfect for the task, because it gives us the right immutable behavior, but its performance makes it unacceptable. So the solution is to design a data structure that would fit our needs and requirements.The people who wrote ImmutableDictionary are not stupid. They didn’t set out to make something that would be slow. The issue is that they set out to solve a generic problem. We can benefit from specializing the data structure for our needs (removing a lot of complexity along the way).Concretely, we need something that:Provides O(1) lookup.Plays nicely with the GC and allocates rarely.Has a simple structure for the GC to work with (not a lot of…

Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town