Hi, I am using the following version of go : PS C:\Temp> go version go version go1.13.5 windows/amd64
I am trying to compare the performance of QuickUnion (just the basic one
with no weighting/ranking/path compression) and QuickFind algorithms.
My benchmarking test cases basically create a (N-1) element array of pairs
starting with (0,1), (1,2).....all the way upto (N-2,N-1). N is the number
of data points. The benchmarking is run for N=10,100,1000.
The benchmark functions then test the union-find functions by creating all
the connections from the above array of pairs.
>From the Benchmarking results, it appears that the QuickUnion function is
taking longer than the QuickFind function for the same data size and same
set of input pairs.
QuickFind benchmarking results.
Running tool: C:\Go\bin\go.exe test -benchmem -run=^$ github.com\en-vee\ds
-bench ^(BenchmarkQuickFind)$
goos: windows
goarch: amd64
pkg: github.com/en-vee/ds
BenchmarkQuickFind/BenchmarkQuickFind10-8 36392860
33.2 ns/op 0 B/op 0 allocs/op
BenchmarkQuickFind/BenchmarkQuickFind100-8 3199598 388
ns/op 0 B/op 0 allocs/op
BenchmarkQuickFind/BenchmarkQuickFind1000-8 300667 3852
ns/op 0 B/op 0 allocs/op
PASS
ok github.com/en-vee/ds 5.064s
Success: Benchmarks passed.
QuickUnion benchmarking results (See how much poorly they perform as
compared to the QuickFind. The times per op are almost double the times for
QuickFind).
Running tool: C:\Go\bin\go.exe test -benchmem -run=^$ github.com\en-vee\ds
-bench ^(BenchmarkQuickUnion)$
goos: windows
goarch: amd64
pkg: github.com/en-vee/ds
BenchmarkQuickUnion/BenchmarkQuickUnion10-8 17946232
65.4 ns/op 0 B/op 0 allocs/op
BenchmarkQuickUnion/BenchmarkQuickUnion100-8 88495
13516 ns/op 0 B/op 0 allocs/op
BenchmarkQuickUnion/BenchmarkQuickUnion1000-8 907
1328386 ns/op 0 B/op 0 allocs/op
PASS
ok github.com/en-vee/ds 4.691s
Success: Benchmarks passed.
Upon CPU profiling the BenchmarkQuickUnion test case, the two for loops
related to the Find operation take the maximum time, but I am surprised
that this function is taking longer because the loop does not iterate
through the entire Array for any pair. Infact, I guess the loops must be
performing only 2 iterations per pair. (Also see the pprof CPU profile
attachment which shows the QuickUnion CPU profile for my function
QuickUnion).
Is the array lookup being performed by the Find operations in QuickUnion
function, causing this performance bottleneck ?
I guess the most surprising bit is : Why is QuickUnion slower than
QuickFind for the same input data ? Or am I missing something ?
(BTW, the implementations are based on Robert Sedgwick's equivalent
implementations in C as given in his excellent book)
The QuickUnion and Quick Find functions are as below :
QuickUnion
func quickUnion(a []int, p, q int) {
var i, j int
for i = p; i != a[i]; i = a[i] {
}
for j = q; j != a[j]; j = a[j] {
}
if i != j {
a[i] = j
}
}
QuickFind
func qf(a []int, p, q int) {
// Are p and q already connected ?
if a[p] == a[q] {
return
}
n := len(a)
for i := 0; i < n; i++ {
if a[i] == a[p] {
a[i] = a[q]
}
}
}
My benchmarking test cases :
BenchmarkQuickUnion
func BenchmarkQuickUnion(b *testing.B) {
type pair struct {
X int
Y int
}
bmTestSizes := []int{10, 100, 1000}
for _, bmTestSize := range bmTestSizes {
a := createSlice(bmTestSize)
pairs := make([]pair, bmTestSize-1, bmTestSize-1)
// Create a slice of pairs
for j := 0; j < bmTestSize-1; j++ {
pairs[j] = pair{j, j + 1}
}
pLen := bmTestSize - 1
//b.ResetTimer()
bmName := fmt.Sprintf("BenchmarkQuickUnion%d", bmTestSize)
b.Run(bmName, func(b *testing.B) {
for i := 0; i < b.N; i++ {
for j := 0; j < pLen; j++ {
quickUnion(a, pairs[j].X, pairs[j].Y)
}
//qf(a, (len(a)-1)/2, len(a)-1)
}
})
}
}
BenchmarkQuickFind
func BenchmarkQuickFind(b *testing.B) {
type pair struct {
X int
Y int
}
bmTestSizes := []int{10, 100, 1000, 10000, 100000}
for _, bmTestSize := range bmTestSizes {
a := createSlice(bmTestSize)
pairs := make([]pair, bmTestSize-1, bmTestSize-1)
// Create a slice of pairs
for j := 0; j < bmTestSize-1; j++ {
pairs[j] = pair{j, j + 1}
}
pLen := bmTestSize - 1
bmName := fmt.Sprintf("BenchmarkQuickFind%d", bmTestSize)
b.Run(bmName, func(b *testing.B) {
for i := 0; i < b.N; i++ {
for j := 0; j < pLen; j++ {
qf(a, pairs[j].X, pairs[j].Y)
}
}
})
}
}
Enter code here...
--
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+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/golang-nuts/65420a77-29be-45ac-b57b-64bf05b5f480%40googlegroups.com.
Title: Pprof listing
File: ds.test.qu100
Type: cpu
Time: Feb 15, 2020 at 6:31pm (AEDT)
Duration: 1.42s, Total samples = 1.30s (91.44%)
Total: 1.30s
Type: cpu
Time: Feb 15, 2020 at 6:31pm (AEDT)
Duration: 1.42s, Total samples = 1.30s (91.44%)
Total: 1.30s
github.com/en-vee/ds.quickUnion
C:\Users\neeraj.vaidya\go\src\github.com\en-vee\ds\ds.go
Total: 1.27s 1.27s (flat, cum) 97.69% 55 . . } 56 . . //fmt.Printf("%d-%d\n", p, q) 57 . . //fmt.Println(a) 58 . . } 59 . . 60 . . func quickUnion(a []int, p, q int) { . . 509b10: SUBQ $0x18, SP ds.go:60 . . 509b14: MOVQ BP, 0x10(SP) ds.go:60 . . 509b19: LEAQ 0x10(SP), BP ds.go:60 61 . . 62 . . //aLen := len(a) 63 . . 64 . . var i, j int 65 . . 66 . . // Follow from a[p] 67 . . 68 610ms 610ms for i = p; i != a[i]; i = a[i] { . . 509b1e: MOVQ 0x20(SP), DX ds.go:68 . . 509b23: MOVQ 0x28(SP), BX ds.go:68 . . 509b28: MOVQ 0x38(SP), SI ds.go:68 . . 509b2d: JMP 0x509b32 ds.go:68 160ms 160ms 509b2f: MOVQ DI, SI ds.go:68 . . 509b32: CMPQ BX, SI ds.go:68 . . 509b35: JAE 0x509b76 ds.go:68 60ms 60ms 509b37: MOVQ 0(DX)(SI*8), DI ds.go:68 390ms 390ms 509b3b: CMPQ DI, SI ds.go:68 . . 509b3e: JNE 0x509b2f ds.go:68 ⋮ . . 509b76: MOVQ SI, AX ds.go:68 . . 509b79: MOVQ BX, CX ds.go:68 . . 509b7c: CALL runtime.panicIndex(SB) ds.go:68 . . 509b81: NOPL ds.go:68 . . 509b82: INT $0x3 . . 509b83: INT $0x3 . . 509b84: INT $0x3 . . 509b85: INT $0x3 . . 509b86: INT $0x3 . . 509b87: INT $0x3 . . 509b88: INT $0x3 . . 509b89: INT $0x3 . . 509b8a: INT $0x3 . . 509b8b: INT $0x3 . . 509b8c: INT $0x3 . . 509b8d: INT $0x3 . . 509b8e: INT $0x3 69 . . } 70 . . 71 610ms 610ms for j = q; j != a[j]; j = a[j] { 10ms 10ms 509b40: MOVQ 0x40(SP), DI ds.go:71 . . 509b45: JMP 0x509b4a ds.go:71 170ms 170ms 509b47: MOVQ R8, DI ds.go:71 . . 509b4a: CMPQ BX, DI ds.go:71 . . 509b4d: JAE 0x509b6b ds.go:71 50ms 50ms 509b4f: MOVQ 0(DX)(DI*8), R8 ds.go:71 380ms 380ms 509b53: CMPQ R8, DI ds.go:71 . . 509b56: JNE 0x509b47 ds.go:71 ⋮ . . 509b6b: MOVQ DI, AX ds.go:71 . . 509b6e: MOVQ BX, CX ds.go:71 . . 509b71: CALL runtime.panicIndex(SB) ds.go:71 72 . . } 73 . . 74 10ms 10ms if i != j { 10ms 10ms 509b58: CMPQ SI, DI ds.go:74 . . 509b5b: JE 0x509b61 ds.go:74 75 40ms 40ms a[i] = j . . 509b5d: MOVQ DI, 0(DX)(SI*8) ds.go:75 30ms 30ms 509b61: MOVQ 0x10(SP), BP ds.go:75 10ms 10ms 509b66: ADDQ $0x18, SP ds.go:75 . . 509b6a: RET ds.go:75 76 . . } 77 . . } 78 . . 79 . . func quickUnionMT(a []int, p, q int) { 80 . . //aLen := len(a)
