sorty

README

sorty

Type-specific, fast, efficient, concurrent/parallel sorting library.

sorty is a concurrent QuickSort implementation (with an improved InsertionSort as subroutine). It is in-place and does not require extra memory. You can call corresponding Sort*() to rapidly sort your slices (in ascending order) or collections of objects. For example:

sorty.SortS(string_slice) // native slice
sorty.Sort(n, lesswap)    // lesswap() function based

If you have a pair of Less() and Swap(), then you can trivially write your lesswap() and sort your generic collections using multiple cpu cores quickly.

sorty is stable, well tested and pretty careful with resources & performance:

• lesswap() operates faster than sort.Interface on generic collections.
• For each Sort*() call, sorty uses up to Mxg (3 by default, including caller) concurrent goroutines and up to one channel.
• Goroutines and channel are created/used only when necessary.
• Mxg=1 (or a short input) yields single-goroutine sorting, no goroutines or channel will be created.
• Mxg can be changed live, even during an ongoing Sort*() call.
• Mli,Hmli,Mlr parameters are tuned to get the best performance, see below.
• sorty API adheres to semantic versioning.

Benchmarks

Comparing against sort.Slice, sortutil, zermelo and radix with Go version 1.16.3 on:

Machine	CPU	OS	Kernel
R	Ryzen 1600	Manjaro	5.4.108
X	Xeon Haswell	Ubuntu 20.04	5.4.0-1040-gcp
i5	Core i5 4210M	Manjaro	5.4.108

Sorting random uint32 array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	15.82	18.44	16.02
sortutil	2.32	3.08	3.87
zermelo	2.00	1.80	1.09
sorty-1	6.35	7.76	6.13
sorty-2	3.32	3.91	3.19
sorty-3	2.15	2.73	2.65
sorty-4	1.89	2.04	2.27
sortyLsw-1	14.10	16.87	14.37
sortyLsw-2	7.33	8.56	7.49
sortyLsw-3	5.03	5.78	5.97
sortyLsw-4	3.74	4.44	5.32

Sorting random float32 array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	17.44	19.53	17.15
sortutil	2.91	3.11	4.46
zermelo	4.50	4.17	3.18
sorty-1	7.59	8.59	6.99
sorty-2	4.00	4.38	3.66
sorty-3	2.71	2.86	2.83
sorty-4	2.36	2.43	2.53
sortyLsw-1	15.31	17.60	15.15
sortyLsw-2	7.91	8.96	7.94
sortyLsw-3	5.63	6.00	6.42
sortyLsw-4	4.52	4.71	5.55

Sorting random string array (in seconds):

Library(-Mxg)	R	X	i5
sort.Slice	8.56	10.36	8.42
sortutil	1.64	2.39	2.30
radix	4.29	6.23	3.38
sorty-1	5.76	7.91	6.23
sorty-2	2.89	3.96	3.41
sorty-3	1.97	2.77	3.10
sorty-4	1.76	2.12	2.86
sortyLsw-1	7.52	9.74	8.08
sortyLsw-2	3.76	5.10	4.37
sortyLsw-3	2.68	3.25	3.96
sortyLsw-4	2.17	2.67	3.77

Testing & Parameter Tuning

First, make sure everything is fine:

go test -timeout 1h

You can tune Mli,Hmli,Mlr for your platform/cpu with (optimization flags):

go test -timeout 4h -gcflags '-dwarf=0 -B -wb=0' -ldflags '-s -w' -tags tuneparam

Now update Mli,Hmli,Mlr in sorty.go and compare your tuned sorty with others:

go test -timeout 1h -gcflags '-dwarf=0 -B -wb=0' -ldflags '-s -w'

Remember to build sorty (and your functions like SortObjAsc()) with the same optimization flags you used for tuning. -B flag is especially helpful.

Support

If you use sorty and like it, please support via ETH:0x464B840ee70bBe7962b90bD727Aac172Fa8B9C15

Documentation

Overview

Package sorty is a type-specific, fast, efficient, concurrent/parallel sorting library. It is a QuickSort implementation, is in-place and does not require extra memory. Call corresponding Sort*() to concurrently sort your slices (in ascending order) or collections of objects. For example:

sorty.SortS(string_slice) // native slice
sorty.Sort(n, lesswap)    // lesswap() function based

Index

• Variables
• func IsSorted(n int, lsw Lesswap) int
• func IsSortedF4(ar []float32) int
• func IsSortedF8(ar []float64) int
• func IsSortedI(ar []int) int
• func IsSortedI4(ar []int32) int
• func IsSortedI8(ar []int64) int
• func IsSortedP(ar []uintptr) int
• func IsSortedS(ar []string) int
• func IsSortedU(ar []uint) int
• func IsSortedU4(ar []uint32) int
• func IsSortedU8(ar []uint64) int
• func Search(n int, fn func(int) bool) int
• func Sort(n int, lsw Lesswap)
• func SortF4(ar []float32)
• func SortF8(ar []float64)
• func SortI(ar []int)
• func SortI4(ar []int32)
• func SortI8(ar []int64)
• func SortP(ar []uintptr)
• func SortS(ar []string)
• func SortU(ar []uint)
• func SortU4(ar []uint32)
• func SortU8(ar []uint64)
• type Lesswap

Variables

var (
	// Mxg is the maximum concurrent goroutines used for sorting per Sort*() call.
	Mxg uint32 = 3

	// Mli is the maximum array length for insertion sort in
	// Sort*() except SortS() and Sort().
	Mli = 100
	// Hmli is the maximum array length for insertion sort in SortS() and Sort().
	Hmli = 40

	// Mlr is the maximum array length for recursion when there is available goroutines.
	// So Mlr+1 is the minimum array length for new sorting goroutines.
	Mlr = 496
)

Functions

func IsSorted

func IsSorted(n int, lsw Lesswap) int

IsSorted returns 0 if underlying collection of length n is sorted, otherwise it returns i > 0 with less(i,i-1) = true.

func IsSortedF4

func IsSortedF4(ar []float32) int

IsSortedF4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedF8

func IsSortedF8(ar []float64) int

IsSortedF8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI

func IsSortedI(ar []int) int

IsSortedI returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI4

func IsSortedI4(ar []int32) int

IsSortedI4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedI8

func IsSortedI8(ar []int64) int

IsSortedI8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedP

func IsSortedP(ar []uintptr) int

IsSortedP returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedS

func IsSortedS(ar []string) int

IsSortedS returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU

func IsSortedU(ar []uint) int

IsSortedU returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU4

func IsSortedU4(ar []uint32) int

IsSortedU4 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func IsSortedU8

func IsSortedU8(ar []uint64) int

IsSortedU8 returns 0 if ar is sorted in ascending order, otherwise it returns i > 0 with ar[i] < ar[i-1]

func Search

func Search(n int, fn func(int) bool) int

Search returns lowest integer k in [0,n) where fn(k) is true, assuming:

fn(k) => fn(k+1)

If there is no such k, it returns n. It can be used to locate an element in a sorted array or collection.

func Sort

func Sort(n int, lsw Lesswap)

Sort concurrently sorts underlying collection of length n via lsw(). Once for each non-trivial type you want to sort in a certain way, you can implement a custom sorting routine (for a slice for example) as:

func SortObjAsc(c []Obj) {
	lsw := func(i, k, r, s int) bool {
		if c[i].Key < c[k].Key { // your custom strict comparator (like < or >)
			if r != s {
				c[r], c[s] = c[s], c[r]
			}
			return true
		}
		return false
	}
	sorty.Sort(len(c), lsw)
}

func SortF4

func SortF4(ar []float32)

SortF4 concurrently sorts ar in ascending order.

func SortF8

func SortF8(ar []float64)

SortF8 concurrently sorts ar in ascending order.

func SortI

func SortI(ar []int)

SortI concurrently sorts ar in ascending order.

func SortI4

func SortI4(ar []int32)

SortI4 concurrently sorts ar in ascending order.

func SortI8

func SortI8(ar []int64)

SortI8 concurrently sorts ar in ascending order.

func SortP

func SortP(ar []uintptr)

SortP concurrently sorts ar in ascending order.

func SortS

func SortS(ar []string)

SortS concurrently sorts ar in ascending order.

func SortU

func SortU(ar []uint)

SortU concurrently sorts ar in ascending order.

func SortU4

func SortU4(ar []uint32)

SortU4 concurrently sorts ar in ascending order.

func SortU8

func SortU8(ar []uint64)

SortU8 concurrently sorts ar in ascending order.

Types

type Lesswap

type Lesswap func(i, k, r, s int) bool

Lesswap function operates on an underlying collection to be sorted as:

if less(i, k) { // strict ordering like < or >
	if r != s {
		swap(r, s)
	}
	return true
}
return false