Thanks Jake.
The logic about the slice being reused across iterations makes sense.
I will run these tests on my machine.
On Monday, 17 February 2020 08:48:12 UTC+11, Jake Montgomery wrote:
>
> Without speaking to the correctness of your algorithm, I can tell you why
> your results are not as you expect. It is a classic benchmark mistake. You
> are creating your slice, filled with ordered integers, then running your
> code on the same slice again and again. So after the first iteration the
> slice is "sorted" already. For whatever reason, QuickFind likes this
> scenario a lot, and QuickUnion does not. What you really want is to use the
> same initial data for each iteration. That means resetting the 'a' slice
> inside the "for i := 0; i < b.N; i++" loop. When the code is modified like
> this:
>
> package quickfind
>
> import (
> "fmt"
> "testing"
> )
>
> type pair struct {
> X int
> Y int
> }
>
> 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
> }
> }
>
> 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]
> }
> }
> }
>
> func createSlice(n int) []int {
> a := make([]int, n, n)
> return a
> }
>
> func fillSlice(a []int) {
> // initialize each element of the array to it's index value
> for i := range a {
> a[i] = i
> }
> }
>
> func createPairs(bmTestSize int) []pair {
> 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}
> }
> return pairs
>
> }
>
> func BenchmarkQuickUnion(b *testing.B) {
> bmTestSizes := []int{10, 100, 1000, 10000}
> for _, bmTestSize := range bmTestSizes {
> bmName := fmt.Sprintf("BenchmarkQuickUnion%d", bmTestSize)
> b.Run(bmName, func(b *testing.B) {
> b.StopTimer()
> pairs := createPairs(bmTestSize)
> a := createSlice(bmTestSize)
> pLen := bmTestSize - 1
> b.StartTimer()
> for i := 0; i < b.N; i++ {
> b.StopTimer()
> fillSlice(a)
> b.StartTimer()
> for j := 0; j < pLen; j++ {
> quickUnion(a, pairs[j].X, pairs[j].Y)
> }
> }
> })
> }
> }
>
> func BenchmarkQuickFind(b *testing.B) {
>
> bmTestSizes := []int{10, 100, 1000, 10000}
> for _, bmTestSize := range bmTestSizes {
> bmName := fmt.Sprintf("BenchmarkQuickFind%d", bmTestSize)
> b.Run(bmName, func(b *testing.B) {
> b.StopTimer()
> pairs := createPairs(bmTestSize)
> pLen := bmTestSize - 1
> a := createSlice(bmTestSize)
> b.StartTimer()
> for i := 0; i < b.N; i++ {
> b.StopTimer()
> fillSlice(a)
> b.StartTimer()
> for j := 0; j < pLen; j++ {
> qf(a, pairs[j].X, pairs[j].Y)
> }
> }
> })
> }
> }
>
>
> I get:
>
> BenchmarkQuickUnion/BenchmarkQuickUnion10-4 6483990
> 158 ns/op
> BenchmarkQuickUnion/BenchmarkQuickUnion100-4 2472957
> 531 ns/op
> BenchmarkQuickUnion/BenchmarkQuickUnion1000-4 142843
> 7048 ns/op
> BenchmarkQuickUnion/BenchmarkQuickUnion10000-4 17023
> 68428 ns/op
> BenchmarkQuickFind/BenchmarkQuickFind10-4 3646029
> 328 ns/op
> BenchmarkQuickFind/BenchmarkQuickFind100-4 88860
> 13043 ns/op
> BenchmarkQuickFind/BenchmarkQuickFind1000-4 774
> 1488236 ns/op
> BenchmarkQuickFind/BenchmarkQuickFind10000-4 7
> 150857786 ns/op
> PASS
> ok command-line-arguments 443.341s
>
> QuickUnion outperforms QuickFind in every case, and massively outperforms
> on large sets. Again, I have no idea if your code is actually correct.
> Because the slice needs to be reconfigured for each run, it makes the high
> iteration benchmarks (the ones with small sets) take a long time to run. On
> my machine these took about 8 minutes, so be patient.
>
>
> On Saturday, February 15, 2020 at 2:55:18 PM UTC-5, envee wrote:
>>
>> My apologies about syntax coloring.
>> Here is the createSlice function :
>>
>> func createSlice(n int) []int {
>> a := make([]int, n, n)
>> // initialize each element of the array to it's index value
>> for i := range a {
>> a[i] = i
>> }
>> return a
>> }
>>
>>
>>
>> On Sunday, 16 February 2020 06:31:49 UTC+11, Jake Montgomery wrote:
>>>
>>> On Saturday, February 15, 2020 at 6:24:02 AM UTC-5, envee wrote:
>>>>
>>>> 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...
>>>>
>>>>
>>>>
>>> As Roberts said, please post code without color please. Use plain text,
>>> or a simple code block, or the playground.
>>> I would love to try to replicate your results, but the createSlice()
>>> function is missing. Can you provide it?
>>>
>>
--
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/597965e4-20f5-4af7-8abe-fa83f3d180df%40googlegroups.com.
