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?

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.

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’.

Reading the code (nice-looking, BTW, for C code, but since it is C code, also full of warnings that other languages can protect you from) I spotted this (https://github.com/fastserial/lite3/blob/acbb97984eca1183ddc...):

> 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.

Yes, the latest json rfc made it insecure. Prone to trivial man in the middle attacks.

Wise people ignore that.

This needs more attention than it's getting. Perhaps if you made some changes to the landing pages could help?

"outperforms the fastest JSON libraries (that make use of SIMD) by up to 120x depending on the benchmark. It also outperforms schema-only formats, such as Google Flatbuffers (242x). Lite³ is possibly the fastest schemaless data format in the world."

^ This should be a bar graph at the top of the page that shows both serializing sizes and speeds.

It would also be nice to see a json representation on the left and a color coded string of bytes on the right that shows how the data is packed.

Then the explanation follows.

As already mentioned in other comments, it doesn't really make sense to compare to json parsers since lite3 parses, well, lite3 and not json. It serves a different use case and I think focusing on performance vs json (especially json parsers) is not the best thing about this project

I've added that second link to the toptext.

I'm sorry we missed that Show HN (https://news.ycombinator.com/item?id=45992832)! It belonged in the SCP (https://news.ycombinator.com/item?id=26998308).