bubble-sort 150x faster than golang default sort

[Michael Nelson]

I wanted to try out the benchmark functionality, so wrote a bubble-sort to see how slow it was in comparison to the golang sort package - but was surprised to find the bubblesort was over 150 times faster than the default sort. I was unsure if this was a result of the sort.Interface implementation (ie. extra function calls rather than slice indexing), so I also added a benchmark of the simple bubblesort using sort.Interface, which is still over 15 times faster than Go's built in sort.

Is there an obvious reason for this?

$ git clone https://github.com/absoludity/gosort.git && cd gosort && go test -bench=".*1000"

PASS

BenchmarkDefaultSort1000            2000           1159938 ns/op

BenchmarkSort1000         200000              8917 ns/op

BenchmarkSort1000WithInterface     50000             69624 ns/op

[David Symonds]

On Sun, Dec 23, 2012 at 11:29 AM, Michael Nelson <absol...@gmail.com> wrote:

> https://github.com/absoludity/gosort.git

Not so useful as they've just gone down for maintenance. Can you drop
it in play.golang.org and share a link that way?

[Stephen Day]

Try your benchmarks with different input sizes (10000, 1000000, etc.). I suspect the bubble sort will lose out when the input becomes sufficiently large, assuming there isn't a bug in your bubble sort (which does happen ;) ).

[Rémy Oudompheng]

Your benchmark is sorting the global input slice in place, so you are benchmarking the sorting of already sorted arrays. Bubble-sort is very effective on already sorted arrays, but I'd say the algorithm with empty code would be even more efficient.

You should check what you actually want to benchmark.

Rémy.

[Nathan Fiedler]

Look at my sortingo package [1] which has implementations of various sorting algorithms. While it doesn't include bubble sort (because it really is a terrible sort), it does provide a test bed for comparing the sorts. In addition to the usual sorts there is burstsort, which didn't perform nearly as we'll as my Java implementation. I think that has a lot to do with the garbage collector.

n

[1] http://code.google.com/p/sortingo/

[Michael Nelson]

Thanks Rémy - that solves my problem (and sorry for the noise). I'd forgotten arrays are passed by value, slices are not. The numbers make more sense now (naive bubblesort only being faster only for very small slices due to no overhead of function calls to swap etc.). 

$ go test -bench=".*"                                                                                                                            

PASS

BenchmarkDefaultSort10    500000              4742 ns/op

BenchmarkSort10  1000000              1238 ns/op

BenchmarkSort10WithInterface      200000              7638 ns/op

BenchmarkDefaultSort100    20000             88951 ns/op

BenchmarkSort100           10000            127898 ns/op

BenchmarkSort100WithInterface       2000            783821 ns/op

BenchmarkDefaultSort1000            1000           1513072 ns/op

BenchmarkSort1000            100          13073000 ns/op

BenchmarkSort1000WithInterface        20          83477900 ns/op

--
-
Michael Nelson
http://micknelson.wordpress.com/

[Michael Nelson]

On Sun, Dec 23, 2012 at 6:36 AM, Nathan Fiedler <nathan...@gmail.com> wrote:

Look at my sortingo package [1] which has implementations of various sorting algorithms. While it doesn't include bubble sort (because it really is a terrible sort),

Yeah - I was expecting bubblesort only to be useful as a slow benchmark to improve upon.

 

it does provide a test bed for comparing the sorts. In addition to the usual sorts there is burstsort, which didn't perform nearly as we'll as my Java implementation. I think that has a lot to do with the garbage collector.

Thanks Nathan - that does indeed look useful.

n

[1] http://code.google.com/p/sortingo/