What About the Integer Numbers? Fast Arithmetic with Tagged Integers — A Plea for Hardware Support

In this article we consider how to efficiently support proper
integers Z on modern hardware. The key issue we address is
how to do fast tagged arithmetic where we use efficient small fixed-bit
integers for most arithmetic, and use a slow path when an operation
overflows or if one of the arguments happens to be a big (heap allocated) integer.
We present three novel techniques (to the best of our knowledge) to
do perform operations as fast as possible. In particular, the _sofa_
technique can perform an addition on small integers with a single branch to check for both
overflow and/or if one of the arguments was a big integer.
Even though we improve upon common techniques, it is quite apparent that
common instruction set architectures (x64, arm64, and riscV) do not support
fast tagged integer arithmetic well and we also propose potential ISA
extensions to support tagged arithmetic better in hardware.
The techniques we discuss are widely applicable, not only for languages
that natively support proper integers, like Python, Lisp, or Haskell, but also
for example JavaScript that would use double’s as a fallback.