FTA#1: “Hashmaps do not (efficiently) support range queries. Since the keys are stored in pseudorandom order”
FTA#2: “Object keys (think JSON) are hashed to a 4-byte digest and stored inside B-tree nodes”
It still will likely be faster because of better cache locality, but doesn’t that means this also does not (efficiently) support range queries?
That page also says
“tree traversal inside the critical path can be satisfied entirely using fixed 4-byte word comparisons, never actually requiring string comparisons except for detection of hash collisions. This design choice alone contributes to much of the runtime performance of Lite³.”
How can that be true, given that this beats libraries that use hash maps, that also rarely require string comparisons, by a large margin?
“Inserting a colliding key will not corrupt your data or have side effects. It will simply fail to insert.”
I also notice this uses the DJB2 hash function, which has hash collisions between short strings (http://dmytry.blogspot.com/2009/11/horrible-hashes.html), and those are more likely to be present in json documents. You get about 8 + 3 × 5 = 23 bits of hash for four-character strings, for example, increasing the risk of collisions to, ballpark, about one in three thousand.
=> I think that needs fixing before this can be widely used.
Looking at the actual code (https://github.com/fastserial/lite3/blob/main/src/lite3.c#L2...), it seems like it performs up to 128 probes to find a target before failing, rather than bailing immediately if a collision is detected. It seems like maybe the documentation needs to be updated?
It's a bit unfortunate that the wire format is tied to a specific hash function. It also means that the spec will ossify around a specific hash function, which may not end up being the optimal choice. Neither JSON nor Protobuf have this limitation. One way around this would be to ditch the hashing and use the keys for the b-tree directly. It might be worth benchmarking - I don't think it's necessarily any slower, and an inline cache of key prefixes (basically a cheapo hash using the first N chars) should help preserve performance for common cases.
> It seems like maybe the documentation needs to be updated
Looks like it, yes:
/**
Enable hash probing to tolerate 32-bit hash collisions.
Hash probing configuration (quadratic open addressing for 32-bit hashes:
h_i = h_0 + i^2)
Limit attempts with `LITE3_HASH_PROBE_MAX` (defaults to 128).
Probing cannot be disabled.
*/
#ifndef LITE3_HASH_PROBE_MAX
#define LITE3_HASH_PROBE_MAX 128U
#endif
#if LITE3_HASH_PROBE_MAX < 2
#error "LITE3_HASH_PROBE_MAX must be >= 2"
#endif
> It also means that the spec will ossify around a specific hash function
It is a bit ugly, and will break backwards compatibility, but supporting a second hash function isn’t too hard.
You can, on load, hash a few keys, compare them to the hashes, and, from that, if the input has many keys with high probability, infer which hash function was used.
There also might be spare bit somewhere to indicate ‘use the alternative hash function’.
> The JSON standard requires that the root-level type always be an ‘object'
> or 'array'. This also applies to Lite³.
I don’t think that is true, and https://www.json.org/json-en.html agrees with that. Single values (numbers, strings, booleans, null) also are valid json.
FTA#2: “Object keys (think JSON) are hashed to a 4-byte digest and stored inside B-tree nodes”
It still will likely be faster because of better cache locality, but doesn’t that means this also does not (efficiently) support range queries?
That page also says
“tree traversal inside the critical path can be satisfied entirely using fixed 4-byte word comparisons, never actually requiring string comparisons except for detection of hash collisions. This design choice alone contributes to much of the runtime performance of Lite³.”
How can that be true, given that this beats libraries that use hash maps, that also rarely require string comparisons, by a large margin?
Finally, https://lite3.io/design_and_limitations.html#autotoc_md37 says:
“Inserting a colliding key will not corrupt your data or have side effects. It will simply fail to insert.”
I also notice this uses the DJB2 hash function, which has hash collisions between short strings (http://dmytry.blogspot.com/2009/11/horrible-hashes.html), and those are more likely to be present in json documents. You get about 8 + 3 × 5 = 23 bits of hash for four-character strings, for example, increasing the risk of collisions to, ballpark, about one in three thousand.
=> I think that needs fixing before this can be widely used.