5 ms·

Protobufs are awesomely useful, and this seems like a great enhancement. However, I'm disappointed that there's no map representation. That's a been major issue

by necubi 14y ago

Protobufs are awesomely useful, and this seems like a great enhancement. However, I'm disappointed that there's no map representation. That's a been major issue for us with protobufs compared with thrift or json. While you can represent maps as lists of pairs, it's awkward and lacks the key uniqueness constraint.

kentonv 14y ago
I agree! I actually intend to add maps at some point, just haven't worked out the details yet. It's a little weird in Cap'n Proto since the in-memory structure is also the wire format, and the right in-memory representation of a map is not perfectly obvious (Hash table? B-tree? Red/black?).
- jmillikin 14y ago
  I wrote an implementation of the D-Bus protocol, which has maps, and after doing so I wish it didn't. Maps are a pain for implementors. For example, the semantics of duplicate keys are not obvious. Do you throw an error, or keep the first value, or keep the last value, or do something else? Whatever the decision, somebody will be unhappy with it. Better to just give the user a list of (key, value) pairs and let them figure out what to do with it (e.g. pass it to a map construction function that behaves as they like).
- 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).

by necubi 14y ago

kentonv 14y ago

I agree! I actually intend to add maps at some point, just haven't worked out the details yet. It's a little weird in Cap'n Proto since the in-memory structure is also the wire format, and the right in-memory representation of a map is not perfectly obvious (Hash table? B-tree? Red/black?).

jmillikin 14y ago
I wrote an implementation of the D-Bus protocol, which has maps, and after doing so I wish it didn't. Maps are a pain for implementors. For example, the semantics of duplicate keys are not obvious. Do you throw an error, or keep the first value, or keep the last value, or do something else? Whatever the decision, somebody will be unhappy with it. Better to just give the user a list of (key, value) pairs and let them figure out what to do with it (e.g. pass it to a map construction function that behaves as they like).
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).