> Do we need to be able to determine the amount of memory used by the map ahead of time?
That's a very good question and I debate it a lot. Since Cap'n Proto messages tend to be arena-allocated, dynamically growing space can be problematic. Currently, for lists, you must specify the list size before filling in the data. That could be improved in a few ways, but maps will likely be harder.
If you do know sizes in advance, I think hashtables make the most sense. If we want something that allows dynamic additions and maybe even removals (and can figure out how to reconcile that with arena allocation), B-trees might be a really nice approach. Maybe you could even use a huge mmap'd Cap'n Proto file as a database (warning: very speculative, lots of obstacles to resolve).
That's a very good question and I debate it a lot. Since Cap'n Proto messages tend to be arena-allocated, dynamically growing space can be problematic. Currently, for lists, you must specify the list size before filling in the data. That could be improved in a few ways, but maps will likely be harder.
If you do know sizes in advance, I think hashtables make the most sense. If we want something that allows dynamic additions and maybe even removals (and can figure out how to reconcile that with arena allocation), B-trees might be a really nice approach. Maybe you could even use a huge mmap'd Cap'n Proto file as a database (warning: very speculative, lots of obstacles to resolve).