5 ms·

Current implementation has the following limitations: Maximum object size: 65534 keys The order of object keys is not preserved ... These

by qixxiq 11mo ago

Current implementation has the following limitations: Maximum object size: 65534 keys The order of object keys is not preserved ... These limitations may be lifted by using more bytes to store offset pointers and counts on binary level. Though it's hard to imagine a real application which would need that. I've worked on _many_ applications which have needed those features. Object keys is a per implementation detail, but failing at 65k keys seems like a problem people would likely hit if this were to be used at larger scales.

pshirshov 11mo ago
In our usecase, for which we created the library, we made this tradeoff to save several bytes per pointer and keep binary form more compact. The application splits large objects into smaller chunks. 99% of the structures there are relatively small but there are tons of them. Most likely you can do the same - just split large structures into smaller ones. If you need support for larger structures, you may create your own implementation or extend ours (and I would really like to hear about your usecase). SICK as a concept is simple. SICK as the library was created to cover some particular usecases and may be not suitable for everyone. We would welcome any contributions.
- duped 11mo ago
  If you use varints for pointers you can have the best of both worlds, and achieve even better compaction for the smallest objects.
  - pshirshov 11mo ago
    Yep, can be done but they aren't free because of variable size. With constant pointers I can access const-sized elements directly, with varints I would have to do some rituals. I have another binary encoding for different purposes (https://github.com/7mind/baboon https://github.com/7mind/baboon) which relies on varints, in case of SICK I decided to go with pointers of constant size to save some pennies on access efficiency.
halayli 11mo ago
I don't know what kind of data you are dealing with but its illogical and against all best practices to have this many keys in a single object. it's equivalent to saying having tables with 65k columns is very common. on the other hand most database decisions are about finding the sweet spot compromise tailored toward the common use case they are aiming for, but your comment sound like you are expecting a magic trick.
- xienze 11mo ago
  > I don't know what kind of data you are dealing with but its illogical and against all best practices to have this many keys in a single object. The whole point of this project is to handle efficiently parsing "huge" JSON documents. If 65K keys is considered outrageously large, surely you can make do with a regular JSON parser.
  - pshirshov 11mo ago
    > If 65K keys is considered outrageously large You can split it yourself. If you can't, replace Shorts with Ints in the implementation and it would just work, but I would be very happy to know your usecase. Just bumping the pointer size to cover relatively rare usecases is wasteful. It can be partially mitigated with more tags and tricks, but it still would be wasteful. A tiny chunking layer is easy to implement and I don't see any downsides in that.
    - cogman10 11mo ago
      How wasteful? Presumably 4 bytes dedicated to the keys would be dwarfed by any strings thrown into the dataset. Regardless, other than complexity, would there be any reason to not support a dynamic key size? You could dedicate the first 2 bits on the key to the length of the key. 1 byte would work if there's only 64 keys, 2 bytes would give you 16k keys and 3 4M. And if you wanted to you could use a frequency table to order the pointers such that more frequently used keys are smaller values in the dictionary.
      - 11mo ago
nine_k 11mo ago
I'd say that it's generally unwise to use fixed-width integers in a data structure where this width can vary widely, and has no logical upper limit. Arbitrary-size integers are well known, used in practice, and not hard to implement.
- pshirshov 11mo ago
  Even if it's "generally unwise" it was a well-thought decision in this particular case. See my other comments. An array of elements with constant size is indexed for free. An array of elements of varying size needs a separate index. SICK's binary representation (EBA) was created with several particular usecases in mind. I needed most compact representation and fastest access (for very underpowered devices), large objects were not a big concern-they can be chunked externally.
  - nine_k 11mo ago
    For indexes, I completely agree! If I were to add support for larger amount of keys, I probably would introduce two versions of the data structure, with 16-bit and 32-bit indexing. And, maybe, 8-bit indexing for tiny amounts of keys. But that would definitely complicate the design, and should be done only when there's a real need. Every such decision is a trade-off; I think yours is fine.
    - pshirshov 11mo ago
      I guess that can even be done without breaking the format. I may introduce Obj32 table and maintain backward compatibility. But I'm not sure that's necessary, external chunking works just fine.
eknkc 11mo ago
.net has a polymorphic serializer where the output json contains a $type field for deserializer to choose the concrete type. It needs to be the very first key in the object. I’ve been bitten by this because postgresql’s jsonb also does not preserve the key ordering. I believe the latest .net release addresses this but key ordering does matter sometimes.
- pshirshov 11mo ago
  When order is important it can be maintained by an external layer with, e.g. a an encoding into a list of pairs.
ericmcer 11mo ago
Isn't the order of JSON keys not guaranteed by the official spec? I don't remember when I learned that but I have always behaved as if that cannot be relied upon.
- pshirshov 11mo ago
  No, according to the spec the order is not preserved but most parsers preserve the order (or maintain some order based on side effects) and engineers rely on that (and sometimes that backfires). Essentially, SICK also maintains some strange order based on values of some homegrown trivial hash function but the only right approach to JSON objects is to treat their keys as an unordered set.
- btschaegg 11mo ago
  Since RFC 4627 (the original): > An object is an unordered collection of zero or more name/value pairs, [...] Further, since RFC 7159: > JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences. Both are in the current version (RFC 8259). OTOH, I find the "but the order is not supposed to be guaranteed!" debate REALLY stupid when it comes to software where it's clear that at some point, a human will have to look at the content and correlate it with another system. There's nothing more evil than re-shuffling JSON just for the fun of it and making everyone who has to look at the result miserable. Yes, I'm talking about you, ELK devs. Edit: (And/or whoever wrote the underlying Java/Go libs they use for JSON that don't allow developers to patch ordering in. I remember reading GitHub issues about this.)
  - harrall 11mo ago
    Less than 1% of the hash maps I use have ever needed order. The underlying data structures between both are different. Ordered hash maps use more memory, are slower, and are more complicated. Knowing CS fundamentals, using an ordered hash map should be a deliberate choice like renting a box truck when you need to move a lot of stuff. Don’t just drive a box truck everywhere because you might pick up a couch from a thrift store one day.

by qixxiq 11mo ago

pshirshov 11mo ago

In our usecase, for which we created the library, we made this tradeoff to save several bytes per pointer and keep binary form more compact. The application splits large objects into smaller chunks. 99% of the structures there are relatively small but there are tons of them. Most likely you can do the same - just split large structures into smaller ones. If you need support for larger structures, you may create your own implementation or extend ours (and I would really like to hear about your usecase). SICK as a concept is simple. SICK as the library was created to cover some particular usecases and may be not suitable for everyone. We would welcome any contributions.

duped 11mo ago
If you use varints for pointers you can have the best of both worlds, and achieve even better compaction for the smallest objects.
- pshirshov 11mo ago
  Yep, can be done but they aren't free because of variable size. With constant pointers I can access const-sized elements directly, with varints I would have to do some rituals. I have another binary encoding for different purposes (https://github.com/7mind/baboon https://github.com/7mind/baboon) which relies on varints, in case of SICK I decided to go with pointers of constant size to save some pennies on access efficiency.

halayli 11mo ago

I don't know what kind of data you are dealing with but its illogical and against all best practices to have this many keys in a single object. it's equivalent to saying having tables with 65k columns is very common. on the other hand most database decisions are about finding the sweet spot compromise tailored toward the common use case they are aiming for, but your comment sound like you are expecting a magic trick.

xienze 11mo ago
> I don't know what kind of data you are dealing with but its illogical and against all best practices to have this many keys in a single object. The whole point of this project is to handle efficiently parsing "huge" JSON documents. If 65K keys is considered outrageously large, surely you can make do with a regular JSON parser.
- pshirshov 11mo ago
  > If 65K keys is considered outrageously large You can split it yourself. If you can't, replace Shorts with Ints in the implementation and it would just work, but I would be very happy to know your usecase. Just bumping the pointer size to cover relatively rare usecases is wasteful. It can be partially mitigated with more tags and tricks, but it still would be wasteful. A tiny chunking layer is easy to implement and I don't see any downsides in that.
  - cogman10 11mo ago
    How wasteful? Presumably 4 bytes dedicated to the keys would be dwarfed by any strings thrown into the dataset. Regardless, other than complexity, would there be any reason to not support a dynamic key size? You could dedicate the first 2 bits on the key to the length of the key. 1 byte would work if there's only 64 keys, 2 bytes would give you 16k keys and 3 4M. And if you wanted to you could use a frequency table to order the pointers such that more frequently used keys are smaller values in the dictionary.
    - 11mo ago

nine_k 11mo ago

I'd say that it's generally unwise to use fixed-width integers in a data structure where this width can vary widely, and has no logical upper limit. Arbitrary-size integers are well known, used in practice, and not hard to implement.

pshirshov 11mo ago
Even if it's "generally unwise" it was a well-thought decision in this particular case. See my other comments. An array of elements with constant size is indexed for free. An array of elements of varying size needs a separate index. SICK's binary representation (EBA) was created with several particular usecases in mind. I needed most compact representation and fastest access (for very underpowered devices), large objects were not a big concern-they can be chunked externally.
- nine_k 11mo ago
  For indexes, I completely agree! If I were to add support for larger amount of keys, I probably would introduce two versions of the data structure, with 16-bit and 32-bit indexing. And, maybe, 8-bit indexing for tiny amounts of keys. But that would definitely complicate the design, and should be done only when there's a real need. Every such decision is a trade-off; I think yours is fine.
  - pshirshov 11mo ago
    I guess that can even be done without breaking the format. I may introduce Obj32 table and maintain backward compatibility. But I'm not sure that's necessary, external chunking works just fine.

eknkc 11mo ago

.net has a polymorphic serializer where the output json contains a $type field for deserializer to choose the concrete type. It needs to be the very first key in the object. I’ve been bitten by this because postgresql’s jsonb also does not preserve the key ordering. I believe the latest .net release addresses this but key ordering does matter sometimes.

pshirshov 11mo ago
When order is important it can be maintained by an external layer with, e.g. a an encoding into a list of pairs.

ericmcer 11mo ago

Isn't the order of JSON keys not guaranteed by the official spec? I don't remember when I learned that but I have always behaved as if that cannot be relied upon.

pshirshov 11mo ago
No, according to the spec the order is not preserved but most parsers preserve the order (or maintain some order based on side effects) and engineers rely on that (and sometimes that backfires). Essentially, SICK also maintains some strange order based on values of some homegrown trivial hash function but the only right approach to JSON objects is to treat their keys as an unordered set.
btschaegg 11mo ago
Since RFC 4627 (the original): > An object is an unordered collection of zero or more name/value pairs, [...] Further, since RFC 7159: > JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences. Both are in the current version (RFC 8259). OTOH, I find the "but the order is not supposed to be guaranteed!" debate REALLY stupid when it comes to software where it's clear that at some point, a human will have to look at the content and correlate it with another system. There's nothing more evil than re-shuffling JSON just for the fun of it and making everyone who has to look at the result miserable. Yes, I'm talking about you, ELK devs. Edit: (And/or whoever wrote the underlying Java/Go libs they use for JSON that don't allow developers to patch ordering in. I remember reading GitHub issues about this.)
- harrall 11mo ago
  Less than 1% of the hash maps I use have ever needed order. The underlying data structures between both are different. Ordered hash maps use more memory, are slower, and are more complicated. Knowing CS fundamentals, using an ordered hash map should be a deliberate choice like renting a box truck when you need to move a lot of stuff. Don’t just drive a box truck everywhere because you might pick up a couch from a thrift store one day.