3 ms·
Thumbs up. Maps are important. Red black trees are probably the standard. I'd want to sit down and think about how the wire format sharing the in-memory struct
by justin66 14y ago
Thumbs up. Maps are important.
Red black trees are probably the standard. I'd want to sit down and think about how the wire format sharing the in-memory structure effects things. :) Do we need to be able to determine the amount of memory used by the map ahead of time?
- kentonv 14y ago> 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).