hpack - packing JSON horizontally

As part of writing dmangame’s game viewer, I would generate a giant JSON object representing what happened on each turn of the game. It looked something like this:

TURNS = [
  { turn: 1, actions: [ ... ], scores: [ ... ],
  { turn: 2, actions: [ ... ], scores: [ ... ],
  { turn: 3, actions: [ ... ], scores: [ ... ],
  { turn: 4, actions: [ ... ], scores: [ ... ],
  // ...
  { turn: 3000, actions: [ ... ], scores: [ ... ],
];

The viewer would then iterate through the turn object and draw the game onto a canvas, turn by turn. It turns (pun intended) out that storing the data this way became very expensive, since there was lots of repeated keys. I had run across the idea of horizontal packing and realized it would be useful here.

Generally, horizontal packing is used to turn homogoneous objects into a table, but in my case, my objects were not necessarily homogoneous - what happens in turns 1 may not be the same as what happened in turn2. Therefore, I wrote my own implementation of horizontal packing that allowed for packing a heterogenous collection of objects, as long as the objects were mostly the same.

The advantage of horizontal packing is that it 1) reduces total file size and 2) reduces the time it takes to unpack large JSON objects, since parsing JSON is relatively slow.

The implementation provided works in two steps for encoding an array of objects:

Iterate through the array recursively, building a lookup of keys
Iterate through the array again, turning each object into an array

The reason we have two phases is because the objects are not homogoneous, there might be new keys in a later object, so we have to go through all the objects to figure out the proper labeling of object key -> column ID.

To decode a packed object is simpler, though - we only need one pass, since the key lookup is already built.

I’m pretty satisfied with how hpack turned out and have pulled it out of the original codebase: there’s now a python and javascript implementation for packing and unpacking objects. I still haven’t written tests, but I’m sure they’ll appear sooner or later.

okay