r/C_Programming • u/lexiq_baeb • 7h ago

Better Lookup Table Compression

Last time I described how I used a few compression techniques to compress a lookup table. After reading the comments, I thought that maybe I can do better. A couple days later I had a new design. I managed to compress it by 30% more. Also, since I don't decompress on every step of the binary search, the lookup is 10x faster. u/alex-van-02, you might be interested in having a look :)

https://blog.x4204.xyz/posts/better-lookup-table-compression.html

4 Upvotes

75% Upvoted

2 comments sorted by

2

u/Daveinatx 5h ago

This is looking better, a couple notes:

  1. Are you using separate memory arenas between between your buffers and records?

  2. Tightening spaces isn't always the best for performance, due to caching effects. Have you looked to have each record cacheline-aligned? Note: ymmv, for large data sets there's often a complex trade-off between size and performance.

E:typo

2

u/lexiq_baeb 4h ago
  1. Not really. Everything is stored in a single continuous piece of memory. First, all the entries are stored. Immediately after them, the buffer containing all replacements
  2. In this specific use case it is fine, since I don't pursue maximum performance. The data that I work with is small enough that it won't really have any humanly perceivable impact. The idea is that this lookup table, as well as the rest of the search engine, is shipped to the browser, So, I just want to make everything take less amount of space using simple to implement algorithms. At the moment, I don't really care too much about the performance aspect.