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 $\mathbb{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.

I am a member of the Research In Software Engineering (RISE) group and chair of the Programming Languages working group (PLX). Currently, I am interested in the design and application of strong type systems and declarative programming languages, like Haskell. In particular, I am interested in programming with Effect inference in the Koka project. Furthermore, I work on domain specific embedded languages, language design, and compiler technology.