I've started to learn Go so I was interested in comparing Go performance

against some other languages.

I have a simple microbenchmark that I use to get a quick idea of relative

performance.

I was disappointed to see that the performance of Go was not as as good as

I expected.

My benchmark factors a couple of big integers using Pollard's Rho method:

N5 = 766150476015982127183457373

N6 = 62823675885202669644104829577

Both are the products of just two primes.

-------------------------------------------

Go 1.1rc2 :

C:\Projects\GoCode\src\rho>go test -v

=== RUN: ExampleN5

--- PASS: ExampleN5 (10.053s)

=== RUN: ExampleN6

--- PASS: ExampleN6 (15.348s)

PASS

ok rho 25.452s

C:\Projects\GoCode\src\rho>go test -cpuprofile=rho.prof -bench="Both"

-benchmem=true

testing: warning: no tests to run

PASS

BenchmarkBoth 1 25958000000 ns/op 1105711392 B/op

25343461 allocs/op

ok rho 26.018s

-------------------------------------------

Python 3.3 :

rho(N5) = 1178524040059

9.34 s per run

rho(N6) = 663410067979

15.11 s per run

------------------------------------------

Scala 2.10.1 :

scala> TimeRho(N5)

rho(766150476015982127183457373) = 1178524040059

Time = 2112 ms

scala> TimeRho(N6)

rho(62823675885202669644104829577) = 663410067979

Time = 3104 ms

-------------------------------------------

As you can see above, Go and Python have about the same speed, while Scala

(and Java) are much faster.

This surprised me because I had thought that because Go is statically typed

it would have been faster than Python,

and I expected its performance to be closer to Scala or Java.

I've attached the Go files if anyone is interested.

After some editing to make pprof work on Windows, I managed to collect a

profile.

It seems that there is a lot of time spent on memory allocation, but that's

about all I can determine at this point,

given my unfamiliarity with Go.

The output from pprof is below.

Any ideas on how to make big.Int faster in Go?

-- Peter

-------------------------------------------------------------

C:\Projects\GoCode\src\rho>go tool pprof rho.test.exe rho.prof

The system cannot find the path specified.

Welcome to pprof! For help, type 'help'.

(pprof) top50 --cum

Total: 2593 samples

0 0.0% 0.0% 2370 91.4% gosched0

0 0.0% 0.0% 2370 91.4% rho.BenchmarkBoth

3 0.1% 0.1% 2370 91.4% rho.Rho

0 0.0% 0.1% 2370 91.4% testing.(*B).launch

0 0.0% 0.1% 2370 91.4% testing.(*B).runN

0 0.0% 0.1% 1906 73.5% math/big.(*Int).GCD

144 5.6% 5.7% 1902 73.4% math/big.(*Int).binaryGCD

276 10.6% 16.3% 606 23.4% math/big.(*Int).Sub

156 6.0% 22.3% 596 23.0% math/big.(*Int).Rsh

104 4.0% 26.3% 431 16.6% math/big.(*Int).Set

240 9.3% 35.6% 384 14.8% math/big.nat.sub

79 3.0% 38.6% 364 14.0% math/big.nat.set

7 0.3% 38.9% 346 13.3% math/big.(*Int).Mod

110 4.2% 43.2% 326 12.6% math/big.nat.make

13 0.5% 43.7% 309 11.9% math/big.(*Int).QuoRem

8 0.3% 44.0% 297 11.5% math/big.nat.div

65 2.5% 46.5% 289 11.1% math/big.nat.divLarge

59 2.3% 48.7% 267 10.3% runtime.makeslice

54 2.1% 50.8% 238 9.2% runtime.mallocgc

8 0.3% 51.1% 207 8.0% makeslice1

61 2.4% 53.5% 205 7.9% runtime.copy

106 4.1% 57.6% 198 7.6% math/big.nat.shr

22 0.8% 58.4% 196 7.6% math/big.(*Int).Neg

84 3.2% 61.7% 163 6.3% math/big.nat.add

152 5.9% 67.5% 152 5.9% math/big.nat.norm

143 5.5% 73.0% 143 5.5% runtime.memmove

125 4.8% 77.9% 125 4.8% math/big.nat.cmp

64 2.5% 80.3% 120 4.6% math/big.nat.trailingZeroBits

10 0.4% 80.7% 80 3.1% math/big.(*Int).Mul

0 0.0% 80.7% 78 3.0% gc

24 0.9% 81.6% 78 3.0% runtime.MCache_Alloc

0 0.0% 81.6% 78 3.0% runtime.gc

7 0.3% 81.9% 70 2.7% math/big.nat.mul

66 2.5% 84.5% 66 2.5% math/big.trailingZeroBits

64 2.5% 86.9% 64 2.5% math/big.subVV

0 0.0% 86.9% 62 2.4% runtime.parfordo

6 0.2% 87.2% 51 2.0% runtime.MCentral_AllocList

4 0.2% 87.3% 50 1.9% runtime.new

34 1.3% 88.6% 44 1.7% sweepspan

5 0.2% 88.8% 42 1.6% MCentral_Grow

34 1.3% 90.1% 34 1.3% runtime.markallocated

33 1.3% 91.4% 33 1.3% math/big.shrVU

27 1.0% 92.4% 30 1.2% scanblock

14 0.5% 93.0% 28 1.1% math/big.basicMul

22 0.8% 93.8% 22 0.8% math/big.divWW

7 0.3% 94.1% 19 0.7% math/big.(*Int).Add

0 0.0% 94.1% 18 0.7% markroot

17 0.7% 94.8% 17 0.7% runtime.markspan

0 0.0% 94.8% 16 0.6% runtime.MHeap_Alloc

12 0.5% 95.2% 12 0.5% math/big.addVV

(pprof) top50

Total: 2593 samples

276 10.6% 10.6% 606 23.4% math/big.(*Int).Sub

240 9.3% 19.9% 384 14.8% math/big.nat.sub

156 6.0% 25.9% 596 23.0% math/big.(*Int).Rsh

152 5.9% 31.8% 152 5.9% math/big.nat.norm

144 5.6% 37.3% 1902 73.4% math/big.(*Int).binaryGCD

143 5.5% 42.8% 143 5.5% runtime.memmove

125 4.8% 47.7% 125 4.8% math/big.nat.cmp

110 4.2% 51.9% 326 12.6% math/big.nat.make

106 4.1% 56.0% 198 7.6% math/big.nat.shr

104 4.0% 60.0% 431 16.6% math/big.(*Int).Set

84 3.2% 63.2% 163 6.3% math/big.nat.add

79 3.0% 66.3% 364 14.0% math/big.nat.set

66 2.5% 68.8% 66 2.5% math/big.trailingZeroBits

65 2.5% 71.3% 289 11.1% math/big.nat.divLarge

64 2.5% 73.8% 120 4.6% math/big.nat.trailingZeroBits

64 2.5% 76.3% 64 2.5% math/big.subVV

61 2.4% 78.6% 205 7.9% runtime.copy

59 2.3% 80.9% 267 10.3% runtime.makeslice

54 2.1% 83.0% 238 9.2% runtime.mallocgc

34 1.3% 84.3% 34 1.3% runtime.markallocated

34 1.3% 85.6% 44 1.7% sweepspan

33 1.3% 86.9% 33 1.3% math/big.shrVU

27 1.0% 87.9% 30 1.2% scanblock

24 0.9% 88.9% 78 3.0% runtime.MCache_Alloc

22 0.8% 89.7% 196 7.6% math/big.(*Int).Neg

22 0.8% 90.6% 22 0.8% math/big.divWW

17 0.7% 91.2% 17 0.7% runtime.markspan

14 0.5% 91.7% 28 1.1% math/big.basicMul

13 0.5% 92.2% 309 11.9% math/big.(*Int).QuoRem

12 0.5% 92.7% 12 0.5% math/big.addVV

12 0.5% 93.2% 12 0.5% math/big.nat.clear

11 0.4% 93.6% 11 0.4% runtime.memclr

11 0.4% 94.0% 11 0.4% runtime.settype_flush

10 0.4% 94.4% 80 3.1% math/big.(*Int).Mul

9 0.3% 94.8% 9 0.3% math/big.addVW

8 0.3% 95.1% 207 8.0% makeslice1

8 0.3% 95.4% 8 0.3% math/big.addMulVVW

8 0.3% 95.7% 297 11.5% math/big.nat.div

8 0.3% 96.0% 8 0.3% runtime.SizeToClass

8 0.3% 96.3% 8 0.3% runtime.casp

7 0.3% 96.6% 19 0.7% math/big.(*Int).Add

7 0.3% 96.8% 346 13.3% math/big.(*Int).Mod

7 0.3% 97.1% 70 2.7% math/big.nat.mul

6 0.2% 97.3% 6 0.2% math/big.subVW

6 0.2% 97.6% 51 2.0% runtime.MCentral_AllocList

5 0.2% 97.8% 42 1.6% MCentral_Grow

5 0.2% 98.0% 11 0.4% math/big.(*Int).Lsh

4 0.2% 98.1% 4 0.2% math/big.mulWW

4 0.2% 98.3% 50 1.9% runtime.new

3 0.1% 98.4% 3 0.1% math/big.(*Int).Cmp

--

You received this message because you are subscribed to the Google Groups "golang-nuts" group.

To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.