folly::uint_divisor

Declared in <folly/math/Division.h>

Accelerated division by a fixed divisor. Calculates quotient, remainder, and divisibility.

Given a fixed divisor known ahead of time, this precomputes a magic multiplier once at construction so that each subsequent division and remainder is a handful of multiplies and shifts (inexpensive) rather than a hardware division (expensive).

The technique works for any unsigned integer Word that has an unsigned integer type of twice the width available to hold the intermediate product. For folly::uint128_t (which has no double‐width type) and for uint64_t on platforms where there is no int128 support, uint_divisor is still defined but falls back to native / and %.

A uint_divisor may be constructed speculatively and never used, so merely constructing one with a zero divisor must not fail. Deferring failure until an operation is invoked would require a failure path in every hot path operation. For example, branch and throw or branch and SIGFPE. But the design intention is to have fully‐optimized hot paths. The alternatives are either to support zero divisor or to declare it undefined behavior. But if we declare it undefined behavior, we impose upon the caller to check, which may affect hot paths as well.

Instead, zero divisor is supported everywhere exactly as if it were one. It is defined behavior so that a caller which can tolerate this behavior can avoid its own checks in the hot path.

In addition, there are special named operations which assume the divisor is neither zero nor one. There are debug‐build‐only checks but in non‐debug builds these become compiler hints that allow the compiler to skip emission of the zero/one special‐case handling and generate faster code. Calling these members in the zero divisor or one divisor case is forbidden and undefined behavior.

Example:

folly::uint_divisor<uint32_t> divisor(7); auto qr = divisor(100); // qr.quotient == 14, qr.remainder == 2 divisor.div(100); // 14 divisor.rem(100); // 2 divisor.is_divisor_of(100); // false 100u / divisor; // 14 100u % divisor; // 2

From: https://lemire.me/blog/2019/02/08/faster‐remainders‐when‐the‐divisor‐is‐a‐constant‐beating‐compilers‐and‐libdivide/

CAUTION: Divisor Zero:

These properties hold whenever divisor != 0. But since the operations are not mathematically defined operations when divisor == 0, these properties are also undefined (neither hold nor do not hold) when divisor == 0. quotient = dividend / divisor remainder = dividend % divisor

In addition to these properties which are not defined when divisor == 0, we have mathematical invariants where the mathematical operations are always defined.

There is a fundamental inequality: remainder < divisor In its signed form it would be the more‐familiar inequality: |remainder| < |divisor|

This holds whenever divisor != 0, but fails when divisor == 0.

There is a fundamental equation: dividend = divisor × quotient + remainder

This holds whenever divisor != 0. It also holds when both divisor == 0 and dividend == 0. This can hold when divisor == 0 and dividend != 0, but it depends on how we choose to define it. We could hypothetically define it so that quotient = 0 and remainder = dividend. This would cause the fundamental equation to hold in the divisor == 0 case. But this would require extra checks in the hot paths. So we define the divisor == 0 case so that it behaves like the divisor == 1 case: quotient = dividend and remainder = 0. This causes the fundamental equation to fail in the case that divisor == 0 and dividend != 0. But it optimizes the implementation hot path.

Since the fundamental equation is violated in the case that divisor == 0 and dividend != 0, caution is warranted.

Created with MrDocs