If generics, when they are released, turn out to perform well, I'm going to rewrite this library to use them and get the line count way down.

This issue tracks the research into performance and, if it looks good, actual implementation.

Don't expect anything here until generics are actually released.

The changes are 'trivial' in that they don't change any algorithms or structure of the code.

name               old time/op  new time/op  delta
ZSortUint64T-4     2.71µs ± 7%  2.70µs ±15%     ~     (p=0.684 n=10+10)
ZSorterUint64T-4   2.77µs ± 9%  2.69µs ± 5%     ~     (p=0.243 n=10+9)
ZSortUint64S-4     15.2µs ± 8%  13.2µs ± 5%  -12.98%  (p=0.000 n=10+10)
ZSorterUint64S-4   11.6µs ± 1%   8.8µs ± 0%  -24.39%  (p=0.000 n=10+8)
ZSortUint64M-4     48.9µs ± 7%  45.1µs ± 6%   -7.75%  (p=0.000 n=10+8)
ZSorterUint64M-4   31.6µs ± 0%  28.8µs ± 0%   -8.96%  (p=0.000 n=9+8)
ZSortUint64L-4     68.2ms ± 0%  62.1ms ± 1%   -8.96%  (p=0.000 n=9+10)
ZSorterUint64L-4   68.4ms ± 0%  61.9ms ± 0%   -9.45%  (p=0.000 n=10+9)
ZSortSortedL-4     2.47ms ± 1%  2.41ms ± 1%   -2.51%  (p=0.000 n=10+10)
ZSorterSortedL-4   1.72ms ± 1%  1.66ms ± 1%   -3.32%  (p=0.000 n=10+9)

I've done some benchmark on both. It seems that sort.Slice has 20% performance improvement comparing to sort.Interface.

However it means stop supporting go 1.7 and earlier versions.

One of the defining characteristics of zermelo is that it supports constraints.Float types, likely a rarity for radix sort libraries given the bit-flipping and type-casting shenanigans you have to do to make it happen. Which means we need to deal with NaN values.

NaNs are lots of fun. By their own admission, they are not numbers. You can't sort them because you can't even compare them, much less consider their digits by radix. You can only have a policy on what to do with them when present.

zermelo currently does a whole linear scan through the slice before any other action, looking for NaNs and setting them up front, ahead of all other elements. This only happens in the constraints.Float code. It then does its flip-sort-flip magic on the remainder of the slice. This behavior was chosen as it is also how sort.Float64s() handles NaNs.

But comes now slices.Sort(), the new generic comparison sort in golang.org/x/exp. I fully expect constraints and slices and map to show up in the stdlib, probably in go1.19 if nothing goes wrong. We shall see, but that is my assumption. I do know it is much faster than the sort package, likely due to less function pointer dereferencing and more inlining, and probably also just a better comparison sort implementation.

I'm not quite sure if there is a defined behavior at all for NaNs in slices.Sort, but it seems unlikely given is a generic comparison sort on constraints.Ordered. What I am sure of is that it isn't the same as sort.

Which is all a long way of saying we need an official policy, documented and tested, about what is done with NaNs.

• coverage is only ~91%: not great, not terrible
• Most of the new generic functions and interfaces are missing documentation
• Benchmarks are technically there, but are different than 1.0 and need re-documentation
• File layout should be reorganized so that generic API and old API are in separate files so that v2 is easy to move to, and after it will be easy to keep 1.x synced indefinitely.
• Anything else I missed in my haste to make generics happen...

I may also attempt to get timing in tests to work better on win64. Apparently time.Now() is coarse in win64 and you have to do some kind of goofy system-specific call to get nanos. It's a pita so I may not bother...

Now that generics are here, I should eventually make a v2 of this package that cleans up the API and removes the subpackages.

I plan to not use the "folder" method, which is to say I'm just going to update the go.mod to v2 and change import strings. If you are using an obsolete go this will break you; you have been warned.

The sorted variable will never become true:

https://github.com/shawnsmithdev/zermelo/blob/71f3d2cee9e588c954bdd6c1ad73de45444ed1a3/zuint32/zuint32.go#L48-L68

Readme says

The subpackages zuint and zint must still use reflection as the bit width (32/64) is only available at runtime.

However this is not correct. Bit width is available at build time and can be defined as constant: https://play.golang.org/p/IfKUhv0agJ

This commit drops all the non-generic, reflection-based code, including all previous subpackages.

It also renames several functions, and moves the float code into a new subpackage.

This represents a large change to the API and thus is a new major version.

This closes #9 .

The below is a prototype implementation of radix sort for []uint64. It's about 3x slower than the existing implementation. I need to do some profiling on this. If it is even possible to reduce this performance hit to a tolerable amount, it might be worth refactoring the whole library in this style.

package internal

type radixee struct {
	len int
	mask func(int) func(int) byte
}

type radixer struct {
	x radixee // to sort
	y radixee // buffer

	digits int
	copier func(int, int, bool)
}

func SortRadixer(r radixer) {
	if r.x.len > r.y.len {
		panic("buffer too small")
	}
	if r.x.len < 2 {
		return
	}

	flip := false
	var key byte
	var offset [256]int
	for digit := 0; digit < r.digits; digit++ {
		var counts [256]int
		mask := r.x.mask(digit)
		for i := 0; i < r.x.len; i++ {
			key = mask(i)
			counts[key]++
		}
		offset[0] = 0
		for i := 1; i < len(offset); i++ {
			offset[i] = offset[i-1] + counts[i-1]
		}
		for i := 0; i < r.x.len; i++ {
			key = mask(i)
			r.copier(offset[key], i, flip)
			offset[key]++
		}
		r.x, r.y = r.y, r.x
		flip = !flip
	}
}


func uint64Copier(x, y []uint64) func(int, int, bool) {
	return func(dst, src int, flip bool) {
		if flip {
			x[dst] = y[src]
		} else {
			y[dst] = x[src]
		}
	}
}

func uint64Masker(x []uint64) func(int) func(int) byte {
	return func(offset int) func(int) byte {
		bitOffset := uint(offset * 8)
		keyMask := uint64(0xFF << bitOffset)
		return func(i int) byte {
			return byte((x[i] & keyMask) >> bitOffset)
		}
	}
}

func SortUint64V2(x, buffer []uint64) {
	y := buffer[:len(x)]
	SortRadixer(radixer{
		x:      radixee{len: len(x), mask: uint64Masker(x)},
		y:      radixee{len: len(y), mask: uint64Masker(y)},
		digits: 8,
		copier: uint64Copier(x, y),
	})
}

This commit represents the biggest change to zermelo in years as it add support for go 1.18 generics. This means most of the old subpackages are now obsolete, along with the old Sorter and Sort.

The tests have been thrown out and rewritten, and for now there's no longer any benchmarks. This will likely be cleaned up over time.

The intention here is to keep backwards compatability with the old non-generic interface, but there may have been mistakes made here and there. This branch (likely to be called 1.5.x) will strive to keep that API, but there will be a v2 eventually that will drop all that and thereby greatly simplify the public API.

For now this should be considered relatively rough code, compared to the stability of zermelo up to now, but I've done what I can to test it extensively. Any bug reports are greatly appreciated.

The goal here is to attempt to add SortStrings[S ~string]([]S) and StringSorter[~string]

• Should be faster than sort.Strings and slices.Sort for large slices
• Should result in lexicographic sorting (MSD radix sort), such that sort.StringsAreSorted is always true after sorting
• Possibly allows for v2 Sort function that handles the entire constraints.Ordered type space, assuming I can get reflection and generics to play nice together.

I tried this once when I first wrote zermelo and it was too slow, but may as well give it another shot.

Now that histogram and watermark(s) are one (#4), I see the opportunity to further evolve this into (state of the art) in-place sorting.

Would you entertain a PR or do you want to keep the current algorithm?