Fast division, modulus and divisibility checks in Go for divisors known only at runtime.

Related tags

fastdiv
Overview

fastdiv

GoDoc

Fast division, modulus and divisibility checks for divisors known only at runtime via the method of:

"Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries" Daniel Lemire, Owen Kaser, Nathan Kurz arXiv:1902.01961

Usage:

var divisor uint32 = 3

// intialize a divisor at runtime
d := fastdiv.NewUint32(divisor)

// use it repeatedly
var total uint32
for i := uint32(1); i < 10; i++ {
	total += d.Div(i)
	if d.Divisible(i) {
		fmt.Printf("%d is divisible by %d\n", i, divisor)
	}
}
fmt.Printf("Sum of quotients = %d", total)

// Output:
// 3 is divisible by 3
// 6 is divisible by 3
// 9 is divisible by 3
// Sum of quotients = 12

The method works by pre-computing an approximate inverse of the divisor such that the quotient is given by the high part of the multiplication and the remainder can be calculated by multiplying the fraction contained in the low part by the original divisor. In general, the required accuracy for the approximate inverse is twice the width of the original divisor. For divisors that are half the width of a register or less, this means that the quotient can be calculated with one high-multiplication (top word of a full-width multiplication), the remainder can be calculated with one low-multiplication followed by a high-multiplication and both can be calculated with one full-width multiplication and one high-multiplication.

On amd64 architecture for divisors that are 32-bits or less, this method can be faster than the traditional Granlund-Montgomery-Warren approach used to optimize constant divisions in the compiler. The requirement that the approximate inverse be twice the divisor width means that extended arithmetic is required for 64-bit divisors. The extended arithmetic makes this method is somewhat slower than the Granlund-Montgomery-Warren approach for these larger divisors, but still faster than 64-bit division instructions.

The per operation speed up over a division instruction is ~2-3x and the overhead of pre-computing the inverse can be amortized after 1-6 repeated divisions with the same divisor.

op size var const fastdiv var / fastdiv # to breakeven
div uint16 15.5 ns 5.46 ns 5.32 ns 2.9x 1
mod uint16 16.2 ns 7.68 ns 7.68 ns 2.1x 1
div int16 16.7 ns 5.91 ns 6.55 ns 2.5x 1
mod int16 17.5 ns 8.86 ns 8.86 ns 2.0x 1
div uint32 15.5 ns 7.28 ns 5.53 ns 2.8x 2
mod uint32 15.7 ns 9.63 ns 7.09 ns 2.2x 2
div int32 16.0 ns 5.91 ns 5.91 ns 2.7x 2
mod int32 16.1 ns 8.86 ns 8.27 ns 1.9x 2
div uint64 21.4 ns 5.91 ns 6.89 ns 3.1x 5
mod uint64 20.3 ns 8.30 ns 8.87 ns 2.3x 6
div int64 26.2 ns 7.26 ns 8.51 ns 3.0x 5
mod int64 25.8 ns 9.57 ns 16.8 ns 1.5x 6
Issues
  • n (16 bits) too small for shift of 31

    n (16 bits) too small for shift of 31

    Found vet:

    $ vet ./...
    /Users/dgryski/go/src/github.com/bmkessler/fastdiv/int16.go:51:41: n (16 bits) too small for shift of 31
    
    opened by dgryski 0
  • [question] big.Int divisor

    [question] big.Int divisor

    Really nice project! I didn't go far to fastdiv, can the operations(DIV/MOD) be used in big.Int(math/big)? If so, some elliptic curves(such as secp256k1) in go code would be more faster. Thanks.

    opened by BohuTANG 0
Shotizam analyzes the size of Go binaries

Shotizam Shotizam analyzes the size of Go binaries and outputs SQL with size info for analysis in SQLite3. $ shotizam --sqlite /some/go.binary SQLite

Brad Fitzpatrick 547 Jul 27, 2021
🐶 Automated code review tool integrated with any code analysis tools regardless of programming language

reviewdog - A code review dog who keeps your codebase healthy. reviewdog provides a way to post review comments to code hosting service, such as GitHu

reviewdog 4.2k Sep 10, 2021
🔒🌍 Security scanner for your Terraform code

????tfsec uses static analysis of your terraform templates to spot potential security issues.

tfsec 3.3k Sep 8, 2021
Type check the empty interface{}

Static type checker for interface{} with a type list This is an experiment. This is a tool that performs a static type check on values of type interfa

Sina Siadat 16 Aug 25, 2021
The most opinionated Go source code linter for code audit.

go-critic Highly extensible Go source code linter providing checks currently missing from other linters. There is never too much static code analysis.

null 985 Sep 12, 2021
Sloc, Cloc and Code: scc is a very fast accurate code counter with complexity calculations and COCOMO estimates written in pure Go

Sloc Cloc and Code (scc) A tool similar to cloc, sloccount and tokei. For counting physical the lines of code, blank lines, comment lines, and physica

Ben Boyter 2.7k Sep 10, 2021
A reference for the Go community that covers the fundamentals of writing clean code and discusses concrete refactoring examples specific to Go.

A reference for the Go community that covers the fundamentals of writing clean code and discusses concrete refactoring examples specific to Go.

Lasse Martin Jakobsen 1.8k Sep 6, 2021
Know when GC runs from inside your golang code

gcnotifier gcnotifier provides a way to receive notifications after every run of the garbage collector (GC). Knowing when GC runs is useful to instruc

Carlo Alberto Ferraris 160 Jul 5, 2021
apicompat checks recent changes to a Go project for backwards incompatible changes

Introduction apicompat is a tool to check for the introduction of backwards incompatible changes. apicompat: Guarantees that all consumers of a librar

Bradley Falzon 174 Aug 9, 2021
structslop is a static analyzer for Go that recommends struct field rearrangements to provide for maximum space/allocation efficiency.

structslop Package structslop defines an Analyzer that checks struct can be re-arranged fields to get optimal struct size.

orijtech 335 Sep 1, 2021
🔥 ~6x faster, stricter, configurable, extensible, and beautiful drop-in replacement for golint

revive Fast, configurable, extensible, flexible, and beautiful linter for Go. Drop-in replacement of golint. Revive provides a framework for developme

Minko Gechev 2.9k Sep 14, 2021
MOVED TO GITLAB

blanket blanket is a tool that helps you catch functions which don't have direct unit tests in your Go packages. Installation go get -u gitlab.com/ver

Jeffrey D. 14 Mar 23, 2020
depth is tool to retrieve and visualize Go source code dependency trees.

depth is tool to retrieve and visualize Go source code dependency trees. Install Download the appropriate binary for your platform from the Rele

Kyle Banks 641 Sep 8, 2021
Run linters from Go code -

Lint - run linters from Go Lint makes it easy to run linters from Go code. This allows lint checks to be part of a regular go build + go test workflow

Surul Software Labs GmbH 66 Oct 5, 2020
This is a style verifier intended to be used with the Gerrit checks plugin.

GERRITFMT This is a style verifier intended to be used with the Gerrit checks plugin. HOW TO USE Install formatters: go install github.com/bazelbuild/

Google 22 Apr 20, 2021
A toy deadlock detector written in Go.

Toy Deadlock Detector This package aims to provide a DSL to represent processes as finite state machines and their concurrent composition. A detector

Yuto Takahashi 27 Apr 27, 2021
Fast linters Runner for Go

golangci-lint Fast linters runner for Go golangci-lint is a fast Go linters runner. It runs linters in parallel, uses caching, supports yaml config, h

null 8.5k Sep 9, 2021
A static code analyzer for annotated TODO comments

todocheck todocheck is a static code analyzer for annotated TODO comments. It let's you create actionable TODOs by annotating them with issues from an

Preslav Mihaylov 353 Sep 8, 2021
errcheck checks that you checked errors.

errcheck errcheck is a program for checking for unchecked errors in go programs. Install go get -u github.com/kisielk/errcheck errcheck requires Go 1

Kamil Kisiel 1.7k Sep 14, 2021