What About the Integer Numbers? Fast Arithmetic with Tagged Integers – A Plea for Hardware Support - Leijen, Daan (Microsoft, 2022)
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.
Presented at ML language workshop 2022 (co-located with ICFP'22).