WideIntProofOfConcept

WideIntProofOfConcept copied to clipboard

Wide Integer Math (Proof of Concept)

This header provides a class template Wider<T>, such that Wider<uint64_t> acts like an unsigned 128-bit type, Wider<Wider<uint64_t>> acts like an unsigned 256-bit type, and so on. Wider<T> overloads all the arithmetic operators, and also provides a free function countleadingzeros(w).

A sufficiently smart compiler should produce the same codegen for Wider<uint64_t> as it does for the built-in primitive type __uint128_t. Any significant differences in codegen (in either direction) should probably be filed as "missed optimization" bugs against the relevant compiler.

As of April 2020, Clang supports a built-in type unsigned _ExtInt(n) that implements n-bit arithmetic for any n at all, even non-powers of two. A sufficiently smart compiler should produce the same codegen for Wider<Wider<...>> as it does for unsigned _ExtInt(n).

The following tables show naïve instruction counts (not counting labels, but counting the ret) for each member function of wider_tests::Tests<W>. The letter "P" indicates codegen that appears perfect as far as I know. The word "call" indicates failure to completely inline the code (usually because it's so big).

"__udivti3" and "__umodti3" indicate that certain arithmetic operations on __uint128_t are delegated to a library function. The library function is macro-optimized with many special cases (division by small integers, division by integers with many trailing zeros, et cetera). In contrast, Wider's operator/ omits these special cases, resulting in smaller code but almost certainly slower code in common situations.

All numbers are produced by Godbolt Compiler Explorer, using -O3 -std=c++14, on GCC trunk and Clang trunk.

128-bit math using __uint128_t, unsigned _BitInt(128), and Wider<uint64_t>:

256-bit math using unsigned _ExtInt(256) and Wider<Wider<uint64_t>>:

512-bit math using unsigned _ExtInt(512) and Wider<Wider<Wider<uint64_t>>>: