Giter Site home page Giter Site logo

lemire / fastmod Goto Github PK

View Code? Open in Web Editor NEW
290.0 14.0 27.0 169 KB

A C/C++ header file for fast 32-bit division remainders (and divisibility tests) on 64-bit hardware.

License: Apache License 2.0

Makefile 3.48% C 26.63% C++ 60.79% CMake 9.11%
performance

fastmod's Introduction

fastmod

Ubuntu 22.04 CI (GCC 11) VS17-CI

A header file for fast 32-bit division remainders on 64-bit hardware.

How fast? Faster than your compiler can do it!

Compilers cleverly replace divisions by multiplications and shifts, if the divisor is known at compile time. In a hashing benchmark, our simple C code can beat state-of-the-art compilers (e.g., LLVM clang, GNU GCC) on a recent Intel processor (Skylake).

Further reading:

Usage

We support all major compilers (LLVM's clang, GNU GCC, Visual Studio). This library only makes sense when compiling 64-bit binaries.

It is a header-only library but we have unit tests. Assuming a Linux/macOS setting:

make
./unit

The tests are exhaustive and take some time.

You can also build the tests using cmake which will work nearly everywhere (including under Windows).

cmake -B build 

To enable the exhaustive tests, do...

cmake -B build -D FASTMOD_EXHAUSTIVE_TESTS=ON

Under Windows, you can run tests as follows:

cmake --build build --config Release
cd build
ctest . --config Release

Users of Visual Studio need to compile to a 64-bit binary, typically by selecting x64 or ARM64 in the build settings. Visual Studio should default on 64-bit builds on 64-bit systems.

Code samples

In C, you can use the header as follows.

#include "fastmod.h"

// unsigned...

uint32_t d = ... ; // divisor, should be non-zero
uint64_t M = computeM_u32(d); // do once

fastmod_u32(a,M,d);// is a % d for all 32-bit unsigned values a.

fastdiv_u32(a,M);// is a / d for all 32-bit unsigned values a, d>1.


is_divisible(a,M);// tells you if a is divisible by d

// signed...

int32_t d = ... ; // should be non-zero and between [-2147483647,2147483647]
int32_t positive_d = d < 0 ? -d : d; // absolute value
uint64_t M = computeM_s32(d); // do once

fastmod_s32(a,M,positive_d);// is a % d for all 32-bit a

fastdiv_s32(a,M,d);// is a / d for all 32-bit a,  d must not be one of -1, 1, or -2147483648

In C++, it is much the same except that every function is in the fastmod namespace so you need to prefix the calls with fastmod:: (e.g., fastmod::is_divisible).

Go version

(Speculative work) 64-bit benchmark

It is an open problem to derive 64-bit divisions that are faster than what the compiler can produce for constant divisors. For comparisons to native % and / operations, as well as bitmasks, we have provided a benchmark with 64-bit div/mod. You can compile these benchmarks with make benchmark. These require C++11. It is not currently supported under Visual Studio.

fastmod's People

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

fastmod's Issues

Allow signed 32 bit division on MSVC

If I am not wrong, __mulh is available on MSVC, would it be possible to use this for MSVC to allow 32 bit signed division?

I am not in the possession of MSVC so I cannot test this, but the change would be trivial

Typo in fastmod.h

In #3 I introduced a typo at line 9 in fastmod.h, <cstding> should be <cstdint>, I'm not sure how that escaped me. (I didn't open a pull request for this as I felt it was rather overkill for this thing.)

Why use 128-bit integers for 32 bit operations?

The code seems to be using 128 bit operations for the 32 bit code:

FASTMOD_API uint64_t mul128_u32(uint64_t lowbits, uint32_t d) {
return ((__uint128_t)lowbits * d) >> 64;
}

// fastdiv computes (a / d) given precomputed M for d>1
FASTMOD_API uint32_t fastdiv_u32(uint32_t a, uint64_t M) {
return (uint32_t)(mul128_u32(M, a));
}

However, unless I am mistaken, this can all be done with only 64 bit integer operations:

  1. Break M into 32 bit chunks h and l
  2. The high-64 bit chunk of the 128 bit multiplication u128(M) * a should be exactly the same as (u64(h) * u64(a)) >> 32
Label 128-97 96-64 64-33 32-1
M     h l
a      0 a
out1     [la la]
out2   [ha ha]  
out3 [0 0]  
out4 [0 0]    
result 0 high32(h*a) high32(la) + low32(ha) low32(l*a)
^ What we want

Edited as I originally had the 0s from the multiplication in the wrong columns.

Division by 1 returns 0

When d is 1, the computation in computeM_u32 overflows to 0:

return UINT64_C(0xFFFFFFFFFFFFFFFF) / d + 1;

Then M is 0, and fastdiv_u32(a,M) returns 0 for any a (fastmod_u32(a,M) works correctly, as a % 1 == 0).

Unnamed namespace causes ODR violations in C++

Putting everything in an unnamed namespace means that your header can't safely be used by templates or other code in headers. If a function template or inline function that uses fastmod is used in two different translation units the two copies of the function will call different versions of fastmod in different unnamed namespaces, which breaks the One-Definition Rule and so has undefined behaviour. With C++20 Modules this is likely to be diagnosed and fail to compile.

not portable to MSVC

__uint128_t is not available on msvc.

Perhaps replace the __uint128_t stuff with custom implementation?

Looks like all it needs to implement is mul(128,32)

Can skip the right shift, just grab upper 64 bits

comment fix

at line 86 of fastmod.h

// fastmod computes (a / d) given precomputed M for d>1

should read

// fastdiv computes (a / d) given precomputed M for d>1

Best,
Jeffrey Sarnoff

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.