FAQ
Hi,

due to the change to 64 bit ints in tip, I noticed that 64 bit integer
division is almost three times slower than 32 bit integer division, on an
amd64 system[1].

I created a small collection of benchmarks and disassemblies[2] that
demonstrate the behaviour.

To be honest I lack the deeper understanding to say if this difference
in performance is to be expected or something that can be fixed, which
is why I am asking you to take a look at it.

In the case that this is actually expected, how should we deal with it
in future versions of Go, where int implies int64 on 64 bit systems?
Using int32 explicitly will definitely lead to less nice code because of
a lot of required conversions.


Thanks,
Dominik


[1]: Linux dominikh-pc 3.2.1-gentoo-r2 #7 SMP Mon May 7 16:40:12 CEST
2012 x86_64 Intel(R) Core(TM) i7-2600K CPU @ 3.40GHz GenuineIntel
GNU/Linux

[2]: http://play.golang.org/p/4CbUZSj2lr

--

Search Discussions

  • Minux at Jan 19, 2013 at 9:21 pm

    On Sun, Jan 20, 2013 at 5:13 AM, Dominik Honnef wrote:
    due to the change to 64 bit ints in tip, I noticed that 64 bit integer
    division is almost three times slower than 32 bit integer division, on an
    amd64 system[1].
    This is to be expected.
    doing 64-bit division will (must) be slower than 32-bit division,
    because AFAIK, all division circuits use some sort of iteration
    algorithm (that is, don't expect a single cycle division circuit
    to be built with adequate clock frequency as the other single
    cycle arithmetic circuits).

    --
  • Jan Mercl at Jan 19, 2013 at 9:23 pm
    On Sat, Jan 19, 2013 at 10:13 PM, Dominik Honnef wrote:

    Cannot reproduce here (Xeon on dont-know-how-much GHz)

    jnml@fsc-r630:~/src/tmp/20130119$ cat a_test.go
    package main

    import (
    "testing"
    )

    func BenchmarkBase(b *testing.B) {
    var x int32
    for i := 1; i < b.N; i++ {
    }
    _ = x
    }

    func BenchmarkInt(b *testing.B) {
    var x int
    for i := 1; i < b.N; i++ {
    x /= 42
    }
    _ = x
    }

    func BenchmarkInt32(b *testing.B) {
    var x int32
    for i := 1; i < b.N; i++ {
    x /= 42
    }
    _ = x
    }

    func BenchmarkInt64(b *testing.B) {
    var x int64
    for i := 1; i < b.N; i++ {
    x /= 42
    }
    _ = x
    }
    jnml@fsc-r630:~/src/tmp/20130119$ go test -bench .
    testing: warning: no tests to run
    PASS
    BenchmarkBase 2000000000 0.88 ns/op
    BenchmarkInt 100000000 10.3 ns/op
    BenchmarkInt32 500000000 4.85 ns/op
    BenchmarkInt64 100000000 10.2 ns/op
    ok tmp/20130119 6.870s
    jnml@fsc-r630:~/src/tmp/20130119$ go version
    go version devel +422c00e8e022 Sun Nov 11 07:51:20 2012 +1100
    jnml@fsc-r630:~/src/tmp/20130119$

    -j

    --
  • Minux at Jan 19, 2013 at 9:25 pm

    On Sun, Jan 20, 2013 at 5:22 AM, Jan Mercl wrote:

    On Sat, Jan 19, 2013 at 10:13 PM, Dominik Honnef wrote:

    Cannot reproduce here (Xeon on dont-know-how-much GHz)

    jnml@fsc-r630:~/src/tmp/20130119$ cat a_test.go
    package main

    import (
    "testing"
    )

    func BenchmarkBase(b *testing.B) {
    var x int32
    for i := 1; i < b.N; i++ {
    }
    _ = x
    }

    func BenchmarkInt(b *testing.B) {
    var x int
    for i := 1; i < b.N; i++ {
    x /= 42
    }
    _ = x
    }
    division by a constant should be turned into multiplication by magic
    constants
    by the Go compiler just to avoid the costly divide instruction.

    you can verify that by 'go tool 6g -S'.

    --
  • Michael Jones at Jan 19, 2013 at 11:11 pm
    Integer division is slow.

    It is the unloved arithmetic operation in CPU design because of its low
    frequency of occurrence in the instruction stream. It is the one--if you
    remember childhood schooling--that was "not like the others" in its
    mechanism: there was lots of guessing using leading digits, trial divisors,
    and so on. This awkwardness exists even in base 2 (though much less) and
    means that any division circuit my have to do at least one "fixup" step. (A
    good design does either zero or one fixup, but that one means more work and
    plausibly an extra cycle on what is already a long cycle-count activity.)

    As one specific example, when adding and subtracting were 1 cycle and
    multiply was 4, a 32-bit integer division required 19 cycles.

    On Sat, Jan 19, 2013 at 1:25 PM, minux wrote:


    On Sun, Jan 20, 2013 at 5:22 AM, Jan Mercl wrote:

    On Sat, Jan 19, 2013 at 10:13 PM, Dominik Honnef <dominikh@fork-bomb.org>
    wrote:

    Cannot reproduce here (Xeon on dont-know-how-much GHz)

    jnml@fsc-r630:~/src/tmp/20130119$ cat a_test.go
    package main

    import (
    "testing"
    )

    func BenchmarkBase(b *testing.B) {
    var x int32
    for i := 1; i < b.N; i++ {
    }
    _ = x
    }

    func BenchmarkInt(b *testing.B) {
    var x int
    for i := 1; i < b.N; i++ {
    x /= 42
    }
    _ = x
    }
    division by a constant should be turned into multiplication by magic
    constants
    by the Go compiler just to avoid the costly divide instruction.

    you can verify that by 'go tool 6g -S'.

    --



    --
    Michael T. Jones | Chief Technology Advocate | mtj@google.com | +1
    650-335-5765

    --

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJan 19, '13 at 9:14p
activeJan 19, '13 at 11:11p
posts5
users4
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase