commit	13d63439bf15e2b55593a4173c341ae389d9a6f4	[log] [tgz]
author	Haibo Huang <hhb@google.com>	Wed Dec 09 15:51:27 2020 -0800
committer	Haibo Huang <hhb@google.com>	Wed Dec 09 15:51:27 2020 -0800
tree	3d92e5b435611f66779c77cdf8e1dd3b50769081
parent	7a8156ad2be52905760f5c5e0eb6bf4ccf3e248d [diff]
parent	63058eff77e11aa15bf531df5dd34395ec3017c8 [diff]

tree: 3d92e5b435611f66779c77cdf8e1dd3b50769081

README.md

FXdiv

Header-only library for division via fixed-point multiplication by inverse

On modern CPUs and GPUs integer division is several times slower than multiplication. FXdiv implements an algorithm to replace an integer division with a multiplication and two shifts. This algorithm improves performance when an application performs repeated divisions by the same divisor.

Features

Integer division for uint32_t, uint64_t, and size_t
Header-only library, no installation or build required
Compatible with C99, C++, OpenCL, and CUDA
Uses platform-specific compiler intrinsics for optimal performance
Covered with unit tests and microbenchmarks

Example

#include <fxdiv.h>

/* Division of array by a constant: reference implementation */
void divide_array_c(size_t length, uint32_t array[], uint32_t divisor) {
  for (size_t i = 0; i < length; i++) {
    array[i] /= divisor;
  }
}

/* Division of array by a constant: implementation with FXdiv */
void divide_array_fxdiv(size_t length, uint32_t array[], uint32_t divisor) {
  const struct fxdiv_divisor_uint32_t precomputed_divisor =
    fxdiv_init_uint32_t(divisor);
  for (size_t i = 0; i < length; i++) {
    array[i] = fxdiv_quotient_uint32_t(array[i], precomputed_divisor);
  }
}

Status

Currently working features:

Platform	uint32_t	uint64_t	size_t
x86-64 gcc	Works	Works	Works
x86-64 clang	Works	Works	Works
x86-64 MSVC	Works	Works	Works
x86 gcc	Works	Works	Works
x86 clang	Works	Works	Works
x86 MSVC	Works	Works	Works
ARMv7 gcc	Works	Works	Works
ARMv7 clang	Works	Works	Works
ARMv7 MSVC*	Compiles	Compiles	Compiles
ARM64 gcc	Works	Works	Works
ARM64 clang	Works	Works	Works
ARM64 MSVC*	Compiles	Compiles	Compiles
PPC64 gcc	Works	Works	Works
WAsm clang	Works	Works	Works
Asm.js clang	Works	Works	Works
PNaCl clang	Works	Works	Works
CUDA	Untested	Untested	Untested
OpenCL	Untested	Untested	Untested

*ARMv7 and ARM64 builds with MSVC are presumed to work, but were only verified to compile successfully

References

Granlund, Torbjörn, and Peter L. Montgomery. “Division by invariant integers using multiplication.” In ACM SIGPLAN Notices, vol. 29, no. 6, pp. 61-72. ACM, 1994. Available: gmplib.org/~tege/divcnst-pldi94.pdf