zermelo

README

zermelo

A radix sorting library for Go. Trade memory for speed!

import "github.com/shawnsmithdev/zermelo"

func foo(large []uint64)
    zermelo.Sort(large)
}

About

Zermelo is a sorting library featuring implementations of radix sort. I am especially influenced here by these two articles that describe various optimizations and how to work around the typical limitations of radix sort.

You will generally only want to use zermelo if you won't mind the extra memory used for buffers and your application frequently sorts slices of supported types with at least 256 elements (128 for 32-bit types, somewhat more for floats on ARM). The larger the slices you are sorting, the more benefit you will gain by using zermelo instead of the standard library's in-place comparison sort.

Etymology

Zermelo is named after Ernst Zermelo, who developed the proof for the well-ordering theorem.

Supported Types

• []float32
• []float64
• []int
• []int32
• []int64
• []uint
• []uint32
• []uint64

Subpackages

Zermelo provides individual subpackages for each of the supported types. Subpackages have a SortBYOB() method where you can Bring Your Own Buffer (BYOB), for minimizing allocations. Providing a buffer that is smaller than the slice you are sorting will cause a runtime panic.

import "github.com/shawnsmithdev/zermelo/zuint64"

func foo(bar SomeRemoteData)
    data := make([]uint64, REALLY_BIG)
    buffer := make([]uint64, REALLY_BIG)

    while bar.hasMore() {
        bar.Read(data)
        zuint64.SortBYOB(data, buffer)
        doSomething(data)
    }
}

Sorter

A Sorter will reuse buffers created during Sort() calls. This is not thread safe. Buffers are grown as needed at a 25% exponential growth rate. This means if you sort a slice of size n, subsequent calls with slices up to n * 1.25 in length will not cause another buffer allocation. This does not apply to the first allocation, which will make a buffer of the same size as the requested slice. This way, if the slices being sorted do not grow in size, there is no unused buffer space.

import "github.com/shawnsmithdev/zermelo"

func foo(bar [][]uint64) {
    sorter := zermelo.New()
    for _, x := range(bar) {
        sorter.Sort(x)
    }
}

Benchmarks

You can run the benchmark on your own hardware.

go test -v -bench . -benchmem

The benchmark tests two types of slices:

• []uint64
• []float64

For each of the tested types, it runs the benchmark on a slice of that type with four sizes:

• T (tiny) 64
• S (small) 256
• M (medium) 1024
• L (large) 1048576

For each slice type and size, three sorters are benchmarked:

• GoSort - The standard library sort: sort.Slice() or sort.Float64s
• ZSort - zermelo.Sort(), does not reuse buffers
• ZSorter - zermelo.New().Sort(), does reuse buffers

One pass for each sorter is also made against a large, presorted []uint64.

Documentation

Overview

Package zermelo is a library for sorting slices in Go.

Index

• func Sort(x interface{}) error
• type Sorter
  • func New() Sorter

Functions

func Sort

func Sort(x interface{}) error

Sort attempts to sort x.

If x is a supported slice type, this library will be used to sort it. Otherwise, if x implements sort.Interface it will passthrough to the sort.Sort() algorithm. Returns an error on unsupported types.

Types

type Sorter

type Sorter interface {
	// Sort attempts to sort x, returning an error if unable to sort.
	Sort(x interface{}) error
	// CopySort returns a sorted copy of x, or an error if unable to copy or sort.
	CopySort(x interface{}) (interface{}, error)
}

A Sorter can sort things like slices.

func New

func New() Sorter

New creates a Sorter that reuses buffers on repeated Sort() or CopySort() calls on the same type. This is not thread safe. CopySort() does not support passthrough of sort.Interface values.