Denser packing of data

[jnyrup]

I have some ideas for increased packing of the data, but before implementing and experimenting, I'd like to sketch the idea first to hear if this has any interest.

Currently the data is stored as text, with:

• 5 characters for the hash,
• 3 characters for the line number in TZL and
• 1 newline character.

With ASCII encoding of the characters, that 72 bits per line and 11,336 KB in total.

My first thought was, why storing all those newlines, when both the hash and the line number are fixed sized?
Removing that brings us down to 64 bits per line, which is an 11% reduction, or -1256 KB uncompressed and ~89 KB compressed in absolute numbers.

Next-up, we're storing the data in text, which seems to favor human readability when debugging, but the data is ~100% of the time machine-read.
E.g. we use three ASCII digits (24 bits) to refer to one of the 420 different zones.
If we instead stored the data in some binary format, we wouldn't need more than $\lceil log_2(420)\rceil = 9$ bits, which still leaves room for 92 new zones.

The hash alphabet 0123456789bcdefghjkmnpqrstuvwxyz is 32 characters, so in theory we only need 5 bits to cover them all.
For hashes of length five, this would reduce from 5*8=40 to 5*5=25 bits,

In total we could get down to 34 bits per line which is a 52% reduction.

Some unknowns that require implementation and experimentation:

• Effects on gzip compressibility
• Effects on performance
• Does it work with both little and big Endian systems?

[mattjohnsonpint]

Makes sense. I'd love to see a prototype on the data builder at least.

We can work on the lookup separately. It will likely use some bitmasking techniques.

[jnyrup]

I finally got around experimenting with this in https://github.com/jnyrup/GeoTimeZone/tree/dense_packing using the simple tricks.
This bring down the number of ASCII chars per line in TZ.dat from 9 to 7.
The uncompressed size is reduced by ~22%.
The compressed size is reduced by ~4%.
My runtime benchmarks are not completely stable, but nothing seems to have regressed.

baseline
(5+3+1) ASCII chars per hash

Method	Runtime	data	Mean	Error	StdDev	Gen0	Allocated
GetTimeZone	.NET 6.0	0 timezones	220.7 ns	2.16 ns	1.80 ns	0.0138	88 B
GetTimeZone	.NET Framework 4.8	0 timezones	588.6 ns	2.83 ns	2.65 ns	0.1516	955 B
GetTimeZone	.NET 6.0	1 timezone	267.6 ns	1.07 ns	1.00 ns	0.0291	184 B
GetTimeZone	.NET Framework 4.8	1 timezone	673.8 ns	2.77 ns	2.46 ns	0.1783	1123 B
GetTimeZone	.NET 6.0	3 timezones	290.0 ns	0.41 ns	0.38 ns	0.0391	248 B
GetTimeZone	.NET Framework 4.8	3 timezones	712.4 ns	2.83 ns	2.65 ns	0.1879	1187 B

Remove line endings
(5+3) ASCII chars per hash
packed: 3,402,918b -> 3,316,150b (0.97)
unpacked: 11,607,921 -> 10,318,152b (0.89)

Method	Runtime	data	Mean	Error	StdDev	Gen0	Allocated
GetTimeZone	.NET 6.0	0 timezones	212.8 ns	1.76 ns	1.65 ns	0.0138	88 B
GetTimeZone	.NET Framework 4.8	0 timezones	606.4 ns	0.50 ns	0.47 ns	0.1516	955 B
GetTimeZone	.NET 6.0	1 timezone	268.0 ns	0.18 ns	0.17 ns	0.0291	184 B
GetTimeZone	.NET Framework 4.8	1 timezone	689.2 ns	4.19 ns	3.92 ns	0.1783	1123 B
GetTimeZone	.NET 6.0	3 timezones	296.1 ns	0.79 ns	0.74 ns	0.0391	248 B
GetTimeZone	.NET Framework 4.8	3 timezones	723.8 ns	4.94 ns	4.38 ns	0.1879	1187 B

Compress line numbers
(5+2) ASCII chars per hash
packed: 3,316,150b -> 3,268,523b (0.99)
unpacked: 10,318,152b -> 9,028,383b (0.88)

Method	Runtime	data	Mean	Error	StdDev	Gen0	Allocated
GetTimeZone	.NET 6.0	0 timezones	210.1 ns	0.21 ns	0.20 ns	0.0138	88 B
GetTimeZone	.NET Framework 4.8	0 timezones	602.3 ns	5.74 ns	5.37 ns	0.1516	955 B
GetTimeZone	.NET 6.0	1 timezone	264.2 ns	1.54 ns	1.44 ns	0.0291	184 B
GetTimeZone	.NET Framework 4.8	1 timezone	691.3 ns	5.46 ns	5.10 ns	0.1783	1123 B
GetTimeZone	.NET 6.0	3 timezones	292.9 ns	2.73 ns	2.55 ns	0.0391	248 B
GetTimeZone	.NET Framework 4.8	3 timezones	722.6 ns	4.45 ns	3.94 ns	0.1879	1187 B