Hacker News new | comments | show | ask | jobs | submit login
Show HN: New variable-length integer algorithm (github.com)
2 points by kloeq 183 days ago | hide | past | web | favorite | 4 comments



It seems the algorithm is not very new as it looks pretty much like the one named varint-PU in the following paper: http://stepanovpapers.com/CIKM_2011.pdf


Yes the aim is to improve varint and I'm not the only one. This algorithm is the fastest I've seen yet. Also FLIT64 works well with common CPU operations.


The usual varint is called varint-SU in the Stepanov's paper. The varint-PU is just like what you call FLIT64, at least I don't see any difference.


As a nonacadecic person I find the algorithm description in the paper very hard to read. It says the PU variant packs the "descriptor bits". Thus a 4 byte example would make suffix 0Bxxxx0111 whereas FLIT does 0Bxxxx1000. This minor difference means that one can unmarshall based on tailing zero count and bit shifts rather than the loops described in the paper. In other words, it trades the most expensive CPU operations (jumps) for the cheapest ones. Also FLIT64 has a worst case of 9 bytes rather than varints 10 bytes.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: