sort_test.go

package qsort

import (
	"bytes"
	"math/rand"
	"reflect"
	"sort"
	"strconv"
	"testing"
)

var prng = rand.New(rand.NewSource(0))

// Note, "8", "16", "32" etc are all byte measurements, not bits. So a 32 byte
// integer, for example, which you might see in e.g. a SHA256 hash.

func TestSort8(t *testing.T) {
	testSort(t, 8)
}

func TestSort16(t *testing.T) {
	testSort(t, 16)
}

func TestSort24(t *testing.T) {
	testSort(t, 24)
}

func TestSort32(t *testing.T) {
	testSort(t, 32)
}

func testSort(t *testing.T, size int) {
	const (
		iterations = 1000
		minCount   = 0
		maxCount   = 1000
	)

	buf := make([]byte, maxCount*size)
	// A first test to validate that the swap function is called properly:
	prng.Read(buf)

	values := make([]byte, len(buf))
	copy(values, buf)

	tmp := make([]byte, size)
	Sort(buf, size, func(i, j int) {
		vi := values[i*size : (i+1)*size]
		vj := values[j*size : (j+1)*size]
		copy(tmp, vi)
		copy(vi, vj)
		copy(vj, tmp)
	})

	if !bytes.Equal(buf, values) {
		t.Fatal("values were not sorted correctly by the swap function")
	}

	for i := 0; i < iterations; i++ {
		count := randint(minCount, maxCount)
		slice := buf[:count*size]
		prng.Read(slice)

		// Test with/without duplicates.
		repeat := randint(0, count)
		for j := repeat; repeat > 0 && j < len(slice) && j+repeat < len(slice); j += repeat {
			copy(slice[j:j+repeat], slice[:repeat])
		}

		expect := values[:len(slice)]
		copy(expect, slice)
		sort.Sort(newGeneric(expect, size, nil))

		if !sort.IsSorted(newGeneric(expect, size, nil)) {
			t.Fatal("reference implementation did not produce a sorted output")
		}

		Sort(slice, size, nil)

		if !reflect.DeepEqual(expect, slice) {
			t.Fatal("buffer was not sorted correctly")
		}
	}
}

func TestPivot8(t *testing.T) {
	lo := uint64(1)
	mid := uint64(2)
	hi := uint64(3)

	for i := 0; i < 1000; i++ {
		input := []uint64{lo, mid, hi}
		rand.Shuffle(3, func(i, j int) {
			input[i], input[j] = input[j], input[i]
		})
		medianOfThree64(input, 3, nil)
		if input[0] != mid {
			t.Fatal("medianOfThree128 did not put pivot in first position")
		}
	}
}

func TestPivot16(t *testing.T) {
	lo := uint128{lo: 1}
	mid := uint128{lo: 2}
	hi := uint128{lo: 3}

	for i := 0; i < 1000; i++ {
		input := []uint128{lo, mid, hi}
		rand.Shuffle(3, func(i, j int) {
			input[i], input[j] = input[j], input[i]
		})
		medianOfThree128(input, 3, nil)
		if input[0] != mid {
			t.Fatal("medianOfThree128 did not put pivot in first position")
		}
	}
}

func TestPivot24(t *testing.T) {
	lo := uint192{lo: 1}
	mid := uint192{lo: 2}
	hi := uint192{lo: 3}

	for i := 0; i < 1000; i++ {
		input := []uint192{lo, mid, hi}
		rand.Shuffle(3, func(i, j int) {
			input[i], input[j] = input[j], input[i]
		})
		medianOfThree192(input, 3, nil)
		if input[0] != mid {
			t.Fatal("medianOfThree192 did not put pivot in first position")
		}
	}
}

func TestPivot32(t *testing.T) {
	lo := uint256{d: 1}
	mid := uint256{d: 2}
	hi := uint256{d: 3}

	for i := 0; i < 1000; i++ {
		input := []uint256{lo, mid, hi}
		rand.Shuffle(3, func(i, j int) {
			input[i], input[j] = input[j], input[i]
		})
		medianOfThree256(input, 3, nil)
		if input[0] != mid {
			t.Fatal("medianOfThree256 did not put pivot in first position")
		}
	}
}

func randint(lo, hi int) int {
	if hi == lo {
		return lo
	}
	return prng.Intn(hi-lo) + lo
}

func BenchmarkSort8(b *testing.B) {
	for _, count := range []int{1e3, 1e4, 1e5, 1e6} {
		b.Run("random-"+strconv.Itoa(count), benchSort(count, 8, 0, random, nil))
		if count > 1e4 {
			b.Run("partially-ordered(10)-"+strconv.Itoa(count), benchSort(count, 8, 10, random, nil))
			b.Run("partially-ordered(100)-"+strconv.Itoa(count), benchSort(count, 8, 100, random, nil))
			b.Run("partially-ordered(1000)-"+strconv.Itoa(count), benchSort(count, 8, 1000, random, nil))
		}
	}
}

func stdlibSort8(b *testing.B, size int) {
	// 8 bytes per int64
	b.SetBytes(8 * int64(size))
	data := make([]int64, size)
	unsorted := make([]int64, size)
	for j := 0; j < len(unsorted); j++ {
		unsorted[j] = int64(rand.Intn(size / 10))
	}
	b.StopTimer()
	for i := 0; i < b.N; i++ {
		copy(data, unsorted)
		b.StartTimer()
		sort.Slice(data, func(i, j int) bool { return data[i] < data[j] })
		b.StopTimer()
	}
}

func stdlibSort8PartiallySorted(b *testing.B, size int, partitions int) {
	// 8 bytes per int64
	b.SetBytes(8 * int64(size))
	data := make([]int64, size)
	// panic if not a whole number
	partitionSize := int(size / partitions)
	partitionOrder := rand.Perm(partitions)
	groupedPartitions := make([][]int64, partitions)

	for i := 0; i < len(groupedPartitions); i++ {
		partition := make([]int64, partitionSize)
		for j := 0; j < len(partition); j++ {
			partition[j] = int64(rand.Intn(size / 10))
		}
		sort.Slice(partition, func(i, j int) bool { return partition[i] < partition[j] })
		groupedPartitions[partitionOrder[i]] = partition
	}

	partiallyOrdered := make([]int64, size)
	for _, partition := range groupedPartitions {
		partiallyOrdered = append(partiallyOrdered, partition...)
	}

	b.StopTimer()
	for i := 0; i < b.N; i++ {
		copy(data, partiallyOrdered)
		b.StartTimer()
		sort.Slice(data, func(i, j int) bool { return data[i] < data[j] })
		b.StopTimer()
	}
}

func BenchmarkStdlibSort8(b *testing.B) {
	for _, size := range []int{1e5, 1e6} {
		b.Run("random-"+strconv.Itoa(size), func(b *testing.B) {
			stdlibSort8(b, size)
		})
		b.Run("partially-sorted(10)-"+strconv.Itoa(size), func(b *testing.B) {
			stdlibSort8PartiallySorted(b, size, 10)
		})
		b.Run("partially-sorted(100)-"+strconv.Itoa(size), func(b *testing.B) {
			stdlibSort8PartiallySorted(b, size, 100)
		})
		b.Run("partially-sorted(1000)-"+strconv.Itoa(size), func(b *testing.B) {
			stdlibSort8PartiallySorted(b, size, 1000)
		})
	}
}

func BenchmarkSort8Indirect(b *testing.B) {
	swap := func(int, int) {}
	const count = 100000
	b.Run("random", benchSort(count, 8, 0, random, swap))
	b.Run("asc", benchSort(count, 8, 0, asc, swap))
	b.Run("desc", benchSort(count, 8, 0, desc, swap))
}

func BenchmarkSort16(b *testing.B) {
	for _, count := range []int{1e3, 1e4, 1e5, 1e6} {
		b.Run(strconv.Itoa(count), benchSort(count, 16, 0, random, nil))
	}
}

func BenchmarkSort16Indirect(b *testing.B) {
	swap := func(int, int) {}
	const count = 100000
	b.Run("random", benchSort(count, 16, 0, random, swap))
	b.Run("asc", benchSort(count, 16, 0, asc, swap))
	b.Run("desc", benchSort(count, 16, 0, desc, swap))
}

func BenchmarkSort24(b *testing.B) {
	for _, count := range []int{1e3, 1e4, 1e5, 1e6} {
		b.Run(strconv.Itoa(count), benchSort(count, 24, 0, random, nil))
	}
}

func BenchmarkSort24Indirect(b *testing.B) {
	swap := func(int, int) {}
	const count = 100000
	b.Run("random", benchSort(count, 24, 0, random, swap))
	b.Run("asc", benchSort(count, 24, 0, asc, swap))
	b.Run("desc", benchSort(count, 24, 0, desc, swap))
}

func BenchmarkSort32(b *testing.B) {
	for _, count := range []int{1e3, 1e4, 1e5, 1e6} {
		b.Run(strconv.Itoa(count), benchSort(count, 0, 32, random, nil))
	}
}

func BenchmarkSort32Indirect(b *testing.B) {
	swap := func(int, int) {}
	const count = 100000
	b.Run("random", benchSort(count, 32, 0, random, swap))
	b.Run("asc", benchSort(count, 32, 0, asc, swap))
	b.Run("desc", benchSort(count, 32, 0, desc, swap))
}

type order int

const (
	random order = iota
	asc
	desc
	partiallyOrdered
)

func benchSort(count, size, partitions int, order order, indirect func(int, int)) func(*testing.B) {
	return func(b *testing.B) {
		b.StopTimer()
		buf := make([]byte, count*size)
		unsorted := make([]byte, count*size)
		prng.Read(unsorted)

		if order == asc || order == desc {
			sort.Sort(newGeneric(unsorted, size, nil))
		}
		if order == desc {
			g := newGeneric(unsorted, size, nil)
			items := g.Len()
			for i := 0; i < items/2; i++ {
				g.Swap(i, items-1-i)
			}
		}

		if order == partiallyOrdered {
			// panic if not a whole number
			partitionSize := int((count * size) / partitions)
			partitionOrder := rand.Perm(partitions)
			groupedPartitions := make([][]byte, partitions)

			for i := 0; i < len(groupedPartitions); i++ {
				partition := make([]byte, partitionSize)
				sort.Sort(newGeneric(partition, partitionSize, nil))
				groupedPartitions[partitionOrder[i]] = partition
			}

			for _, partition := range groupedPartitions {
				unsorted = append(unsorted, partition...)
			}
		}

		b.SetBytes(int64(len(buf)))

		for i := 0; i < b.N; i++ {
			copy(buf, unsorted)
			b.StartTimer()
			Sort(buf, size, indirect)
			b.StopTimer()
		}
	}
}