Users skipping r != s check in a lesswap causes data races and incorrect results with multiple goroutines.
See the detailed explanation in this thread.

Hello, thanks for the sorty library.
Would sorty provide a SortInterface(interface{}) funciton, which use reflect to determine the concrete type of parameter?
I think it's very convenient for the callers to call this SortInterface function without care about the concrete type to be sorted.

Thanks.

Hi and thanks for a really fast and nice library!!

However, I've stubbled into a problem. When I do debug my unit test, it spits out a (compilation??) error and a stack (see parts of it below).

I'm using a Mac M1 and go 1.20.3.

Steps to reproduce:

1. git clone https://github.com/mariotoffia/goannoy.git
2. cd go annoy & open vs code
3. Click on debug test in tests/precision_test.go -> TestPrecision.
4. The console outputs the error stack

However, when doing run test or do go test in the shell it seems to work. It is just that I cannot debug. Can you give me some pointers where to event start to debug this problem?

Cheers,
Mario :)

Parts of the error stack:
Starting: /Users/solo/go/bin/dlv dap --listen=127.0.0.1:55316 --log-dest=3 from /Users/solo/progs/github/goannoy/tests
DAP server listening at: 127.0.0.1:55316
Build Error: go test -c -o /Users/solo/progs/github/goannoy/tests/__debug_bin -gcflags all=-N -l .

github.com/mariotoffia/goannoy/tests.test

github.com/jfcg/sorty/v2.SortSlice: nosplit stack over 792 byte limit
github.com/jfcg/sorty/v2.SortSlice<1>
grows 336 bytes, calls github.com/jfcg/sorty/v2.sortI4<1>
grows 176 bytes, calls runtime.gcWriteBarrier<1>
grows 224 bytes, calls runtime.wbBufFlush<0>
grows 32 bytes, calls runtime.wbBufFlush<1>
grows 32 bytes, calls runtime.cgoCheckWriteBarrier<1>
grows 48 bytes, calls runtime.cgoIsGoPointer<1>
grows 80 bytes, calls runtime.inHeapOrStack<1>
grows 32 bytes, calls runtime.spanOf<1>
grows 48 bytes, calls runtime.arenaIndex<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l2<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l1<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l2<1>
216 bytes over limit
grows 48 bytes, calls runtime.panicIndexU<1>
grows 0 bytes, calls runtime.goPanicIndexU<1>
grows 0 bytes, calls runtime.morestack<0>
216 bytes over limit
grows 48 bytes, calls runtime.panicIndexU<1>
grows 0 bytes, calls runtime.goPanicIndexU<1>
grows 0 bytes, calls runtime.morestack<0>
216 bytes over limit
grows 32 bytes, calls runtime.(*mspan).base<1>
grows 0 bytes, calls runtime.morestack<0>
168 bytes over limit
grows 32 bytes, calls runtime.(*mSpanStateBox).get<1>
grows 32 bytes, calls runtime/internal/atomic.(*Uint8).Load<1>
200 bytes over limit
grows 80 bytes, calls runtime.activeModules<1>
136 bytes over limit
grows 80 bytes, calls runtime.cgoInRange<1>
136 bytes over limit
grows 80 bytes, calls runtime.cgoInRange<1>
136 bytes over limit
grows 48 bytes, calls runtime.cgoIsGoPointer<1>
grows 80 bytes, calls runtime.inHeapOrStack<1>
grows 32 bytes, calls runtime.spanOf<1>
grows 48 bytes, calls runtime.arenaIndex<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l2<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l1<1>
216 bytes over limit
grows 48 bytes, calls runtime.arenaIdx.l2<1>
216 bytes over limit
grows 48 bytes, calls runtime.panicIndexU<1>
grows 0 bytes, calls runtime.goPanicIndexU<1>
grows 0 bytes, calls runtime.morestack<0>
216 bytes over limit
grows 48 bytes, calls runtime.panicIndexU<1>
grows 0 bytes, calls runtime.goPanicIndexU<1>
grows 0 bytes, calls runtime.morestack<0>
216 bytes over limit
grows 32 bytes, calls runtime.(*mspan).base<1>
grows 0 bytes, calls runtime.morestack<0>
168 bytes over limit
grows 32 bytes, calls runtime.(*mSpanStateBox).get<1>
grows 32 bytes, calls runtime/internal/atomic.(*Uint8).Load<1>
200 bytes over limit
grows 80 bytes, calls runtime.activeModules<1>
136 bytes over limit
grows 80 bytes, calls runtime.cgoInRange<1>
136 bytes over limit
grows 80 bytes, calls runtime.cgoInRange<1>
136 bytes over limit
grows 48 bytes, calls runtime.inPersistentAlloc<1>
56 bytes over limit
grows 48 bytes, calls runtime.systemstack<0>
grows 16 bytes, calls indirect
grows 0 bytes, calls runtime.morestack<0>
72 bytes over limit
grows 16 bytes, calls runtime.abort<0>
72 bytes over limit
grows 16 bytes, calls gosave_systemstack_switch<20>
grows 0 bytes, calls runtime.abort<0>
72 bytes over limit
grows 16 bytes, calls runtime.save_g<0>
72 bytes over limit
.... cont...

GitHub actions job logs have expired, hence benchmark results cannot be viewed.

The data race detector is picking up an issue in long() of sortyLsw.go.

WARNING: DATA RACE
Write at 0x00c0004f4290 by goroutine 49:
  sync/atomic.AddInt32()
      C:/Program Files/Go/src/runtime/race_amd64.s:305 +0xb
  sync/atomic.AddUint32()
      <autogenerated>:1 +0x1a
  github.com/jfcg/sorty.Sort·dwrap·24()
      C:/Users/chkohner/go/pkg/mod/github.com/jfcg/[email protected]/sortyLsw.go:397 +0x64

Previous read at 0x00c0004f4290 by goroutine 47:
  github.com/jfcg/sorty.Sort()
      C:/Users/chkohner/go/pkg/mod/github.com/jfcg/[email protected]/sortyLsw.go:406 +0x33c

This makes it impossible to write and run unit tests with race detection enabled, because it fails any test that sorty is used in.

benchstat:

old time/op  new time/op  delta
8.02s ± 0%  17.20s ± 3%  +114.54%  (p=0.000 n=9+9)

benchmarks_test.go:

package main

import (
	"bytes"
	"math/rand"
	"reflect"
	"sort"
	"testing"
	"unsafe"

	sorty "github.com/jfcg/sorty/v2"
	"golang.org/x/exp/slices"
)

const (
	recordSize = 256
	keySize    = 8
	numRecords = 60_000_000
)

func makeArr() []byte {
	rand.Seed(1)
	arr := make([]byte, numRecords*recordSize)
	for i := 0; i < keySize; i++ {
		arr[i] = byte(rand.Intn(256))
	}
	return arr
}

type sortable []byte

func (a sortable) Len() int { return len(a) / recordSize }
func (a sortable) Less(i, j int) bool {
	i *= recordSize
	j *= recordSize
	return bytes.Compare(
		a[i:i+keySize],
		a[j:j+keySize],
	) < 0
}
func (a sortable) Swap(i, j int) {
	i *= recordSize
	j *= recordSize
	x := a[i : i+recordSize]
	y := a[j : j+recordSize]
	buf := make([]byte, recordSize)
	copy(buf, x)
	copy(x, y)
	copy(y, buf)
}

func BenchmarkStdSort(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		arr := makeArr()
		b.StartTimer()
		sort.Sort(sortable(arr))
	}
}

func BenchmarkSorty(b *testing.B) {
	// sorty.MaxGor = 1
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		arr := makeArr()
		b.StartTimer()
		sorty.Sort(numRecords, func(i, k, r, s int) bool {
			i *= recordSize
			k *= recordSize
			if bytes.Compare(arr[i:i+keySize], arr[k:k+keySize]) < 0 {
				if r != s {
					r *= recordSize
					s *= recordSize
					x, y := arr[r:r+recordSize], arr[s:s+recordSize]
					buf := make([]byte, recordSize)
					copy(buf, x)
					copy(x, y)
					copy(y, buf)
				}
				return true
			}
			return false
		})
	}
}

func BenchmarkExpSlicesSort(b *testing.B) {
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		arr := makeArr()
		b.StartTimer()

		var arr2 [][recordSize]byte
		hdr := (*reflect.SliceHeader)(unsafe.Pointer(&arr2))
		hdr.Len = numRecords
		hdr.Cap = numRecords
		hdr.Data = uintptr(unsafe.Pointer(&arr[0]))
		slices.SortFunc(arr2, func(a, b [recordSize]byte) bool {
			return bytes.Compare(a[:keySize], b[:keySize]) < 0
		})
	}
}