Concurrency benchmark for Go goroutines

Chip Camden		April, 2011

In my experience, the only good benchmark is a real application.
When benchmark tests are too contrived, then the factor under
measurement usually ends up being a trivial component of real
application performance, while far more important elements are

Therefore, this test of the performance benefits of goroutines
addresses the decades old problem of sort optimization.  The
test routine generates an array whose size is specified by the
user, containing random integers.  It then times the execution
of up to four different sort algorithms, and finally verifies
that each sort algorithm worked.  These four algorithms are:

1. The standard sort provided by the "sort" package.  This is
an in-place quicksort.  It provides a good bar against which to
compare the other algorithms.

2. A naive mergesort.  I have often found that a mergesort can
be faster than a quicksort when a large number of elements are
being sorted.  This algorithm is provided as a baseline, because
its optimization will be the basis for our parallelism test.

3. A parallel mergesort.  This algorithm sorts the two halves
of each split in parallel goroutines, if the size of each slice
is at or above a user-designated threshold.  If you make the
threshold too small, then the overhead of starting a goroutine and
receiving its result over a channel outweighs the time saved through

4. A combination of parallel mergesort and quicksort.  This is
identical to (3), except that below the parallelism threshold, it
reverts to sorting each half with the "sort" package's quicksort.
Thus, it seeks to gain the benefit of parallelism for larger
slices, while taking advantage of quicksort's alleged better
performance for smaller slices.


Compile mergesort.go and testsort.go, then link testsort.  On
amd64 platforms, the command is:

6g mergesort.go && 6g testsort.go && 6l -o testsort testsort.6

Change the 6s to 8s for i386, etc.


testsort [-n ARRAYSIZE] [-p THRESHOLD] [-t TESTS]


ARRAYSIZE	is the size of the array to sort (default = 1000000)

THRESHOLD	is the parallelism threshold (default = 50000)

TESTS		are letters specifying the tests to run, in the order
		specified (default = qmpc):
		q = quicksort (sort.SortInts)
		m = mergesort (naive)
		p = parallel mergesort
		c = combo parallel mergesort/quicksort

The only data currently gathered from the tests is the elapsed time
for each, in nanoseconds.  Results are sent to stdout.