Official git repository for libdivide: optimized integer division
C++ C Makefile
Latest commit c6ed070 Feb 23, 2017 @jwilk jwilk committed with Document "gener" column in benchmark output (#31)
Fixes #30


Build Status Build Status

libdivide is a "library" for optimizing integer division. See for more information on libdivide.

This is a summary of how to use libdivide's testing tools to develop on libdivide itself.

libdivide consists of a single header file libdivide.h which compiles as both C and C++.

libdivide has two test tools: a verification utility "tester", and a benchmarking utility "benchmark". The verification utility is used to help ensure that the division algorithm is correct, and the benchmarking utility is used to measure the speed increase. On Mac OS X, Linux, and other Unix-like systems, you can build both with the Makefile. On Windows, there is a Visual C++ 2010 project that can build both, in windows/libdivide_Win32.

To build the tester via the Makefile, build one of the following targets:

  • debug: builds the tester without optimization
  • release: builds the tester with optimization

Both build an executable "tester". You can pass it one or more of the following arguments: u32, s32, u64, s64, to test the four cases (signed, unsigned, 32 bit, or 64 bit), or run it with no arguments to test all four. The tester is multithreaded so it can test multiple cases simultaneously. The tester will verify the correctness of libdivide via a set of randomly chosen denominators, by comparing the result of libdivide's division to hardware division. It may take a long time to run, but it will output as soon as it finds a discrepancy.

The benchmarking utility is built with target "benchmark." You may pass it one of the same arguments (u32, s32, u64, s64) to compare libdivide's speed against hardware division.

"benchmark" tests a simple function that inputs an array of random numerators and a single divisor, and returns the sum of their quotients. It tests this using both hardware division, and the various division approaches supported by libdivide, including vector division.

It will output data like this:

 #  system  scalar  scl_us  vector  vec_us   gener  algo
 1   5.733   0.849   0.580   0.431   0.431   1.663     0
 2   6.716   0.847   0.580   0.431   0.431   1.663     0
 3   6.687   1.425   1.427   1.862   1.444  22.156     1
 4   6.668   0.851   0.580   0.431   0.431   1.663     0
 5   6.697   1.425   1.425   1.837   1.425  22.156     1

It will keep going as long as you let it, so it's best to stop it when you are happy with the denominators tested. These columns have the following significance. All times are in nanoseconds, and lower is better.

     #:  The divisor that is tested
system:  Hardware divide time
scalar:  libdivide time, using scalar functions
scl_us:  libdivide time, using scalar unswitching functions
vector:  libdivide time, using vector functions
vec_us:  libdivide time, using vector unswitching
 gener:  Time taken to generate the divider struct
  algo:  The algorithm used.  See libdivide_*_get_algorithm

The benchmarking utility will also verify that each function returns the same value, so "benchmark" is valuable for its verification as well.

Before sending in patches to libdivide, please run the tester to completion with all four types, and the benchmark utility for a reasonable period, to ensure that you have not introduced a regression. Happy hacking!