Lookup IDs become more random over time, worsening compression

[Ostrzyciel]

When serializing a long file, Jelly-JVM will evict the least-recently used (LRU) entry in the lookup table to make room for a new one. If the queue of LRU entries looks like this:

1, 2, 3, 4, 5

then they can be replaced with entry IDs like this:

1, 0, 0, 0, 0

thanks to delta compression (0 means "last + 1"). This saves space on the wire, as representing 0 takes zero bytes. Unfortunately, over time these IDs becomes very chaotic, as we evict entries semi-randomly.

I tried this with OpenStreetMap data, 4096 name table size, 256 rows per frame.

• 100th frame: 54 name entries, 7 non-sequential evictions
• 1,000th frame: 55 name entries, 46 non-sequential evictions
• 10,000th frame: 51 name entries, 51 non-sequential evictions

So, this simply stops working over time.

We have a few options to fix this:

1. We can reset the dictionary periodically, but it would require re-emitting some entries that were already communicated before.
2. We can prefer evicting elements in sequence, even if they are not least-recently used – but were not used in a while. I think I already tried something similar before, but with the motivation being faster serialization, not better compression.
3. Move frequently used entries to a "special" frequent block at the start of the table. Then, the rest of the table would be always filled in sequentially. Moving entries could be done either using the current facilities (basically, restate the entry with a different ID), or we could add a dedicated way of doing this (e.g., extra field).

Note that whatever we implement here, it will help to get the most out of packed lookup entries: Jelly-RDF/jelly-protobuf#41

[Ostrzyciel]

We could also make a hybrid of 1. and 3., where every N triples we "compact" the lookups by moving frequently-used entries to the front.

[Ostrzyciel]

The size of the frequently-used section could be by default 127 for tables sized 1024 and up, to fit the ID in one byte.

[Ostrzyciel]

We could also make a hybrid of 1. and 3., where every N triples we "compact" the lookups by moving frequently-used entries to the front.

Or we can devise an algorithm that moves these frequently used items as we go, to reduce jitter.