Description
Go version
go1.23.2
Output of go env in your module/workspace:
GO111MODULE=''
GOARCH='amd64'
GOBIN=''
GOCACHE='/home/magicaltux/.cache/go-build'
GOENV='/home/magicaltux/.config/go/env'
GOEXE=''
GOEXPERIMENT=''
GOFLAGS=''
GOHOSTARCH='amd64'
GOHOSTOS='linux'
GOINSECURE=''
GOMODCACHE='/home/magicaltux/go/pkg/mod'
GONOPROXY='****'
GONOSUMDB='****'
GOOS='linux'
GOPATH='/home/magicaltux/go'
GOPRIVATE='****'
GOPROXY='https://proxy.golang.org,direct'
GOROOT='/pkg/main/dev-lang.go.dev.1.23.2.linux.amd64'
GOSUMDB='sum.golang.org'
GOTMPDIR=''
GOTOOLCHAIN='auto'
GOTOOLDIR='/pkg/main/dev-lang.go.dev.1.23.2.linux.amd64/pkg/tool/linux_amd64'
GOVCS=''
GOVERSION='go1.23.2'
GODEBUG=''
GOTELEMETRY='local'
GOTELEMETRYDIR='/home/magicaltux/.config/go/telemetry'
GCCGO='gccgo'
GOAMD64='v1'
AR='ar'
CC='gcc'
CXX='g++'
CGO_ENABLED='1'
GOMOD='/dev/null'
GOWORK=''
CGO_CFLAGS='-O2 -g'
CGO_CPPFLAGS=''
CGO_CXXFLAGS='-O2 -g'
CGO_FFLAGS='-O2 -g'
CGO_LDFLAGS='-O2 -g'
PKG_CONFIG='pkg-config'
GOGCCFLAGS='-fPIC -m64 -pthread -Wl,--no-gc-sections -fmessage-length=0 -ffile-prefix-map=/tmp/go-build2062254558=/tmp/go-build -gno-record-gcc-switches'What did you do?
In slices, implementation of xorshift is wrong.
Source: https://cs.opensource.google/go/go/+/refs/tags/go1.23.2:src/slices/sort.go;l=178
// xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
type xorshift uint64
func (r *xorshift) Next() uint64 {
*r ^= *r << 13
*r ^= *r >> 17
*r ^= *r << 5
return uint64(*r)
}Looking at the paper however, the values used in slices are aimed at a 32bits integer, and while this will likely be mostly pseudo-random (when it is used, it is seeded with a slice's length, so not too random), it might be a good idea to use the correct value, especially if linking to the paper right above.
What did you see happen?
Pseudo-random numbers that might not produce the full 2^64-1 sequence it is expected to produce.
What did you expect to see?
The code can be very easily fixed by using the values the paper provides for 64 bits:
// xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf
type xorshift uint64
func (r *xorshift) Next() uint64 {
*r ^= *r << 13
*r ^= *r >> 7
*r ^= *r << 17
return uint64(*r)
}While probably not critical, this is a very small change that will result in proper usage of the method described in the cited paper.
Metadata
Metadata
Assignees
Type
Projects
Relationships
Participants
Activity
ianlancetaylor commentedon Oct 31, 2024
CC @eliben
eliben commentedon Oct 31, 2024
@zhangyunhao116 PTAL
this comes from https://go-review.googlesource.com/c/exp/+/399315
MagicalTux commentedon Oct 31, 2024
Confirming the same issue is in the reference implementation: https://github.com/zhangyunhao116/pdqsort/blob/master/pdqsort.go#L135
Looking at the history, the type was changed from
uinttouint64so it might have been fine on 32bits archs whereuintis indeed 32 bits; I'm guessing the type was changed touint64without updating the shift values.mengzhuo commentedon Nov 1, 2024
According to the Xorshift RNGs, the order should be
[13, 7 ,17]instead of[13, 17 ,7](or[13,17,43]I think this is a typo from paper
But you can't find it in the matrix above, the closest one is
[13,17,15]gopherbot commentedon Nov 1, 2024
Change https://go.dev/cl/624295 mentions this issue:
slice: correct triple of xorshift RNGzhangyunhao116 commentedon Nov 1, 2024
Yes, the implementation used an incorrect triple (
[13, 17, 5], from uint32 case in the paper). This is because the initial version used uint (we have uint32 and uint64 versions in the paper), but we needed to keep consistent random numbers across all architectures (32-bit, 64-bit, 128-bit), so we eventually switched to the uint64 version, but without using the corresponding triple during this process. The algorithm actually doesn't require high-quality random numbers, which is why it wasn't detected in testing.We can change the triple to
[13, 17, 43](one of the 275 triples from the paper) or switch to the author's preferred[13, 7, 17], both options are valid. (the latter seems to have more testing?)The only impact of modifying the triple is that different triples may rearrange equal elements differently. However, we don't actually guarantee the order here (previous algorithm changes would also cause this effect), so the change is fine.
gabyhelp commentedon Nov 1, 2024
Related Issues and Documentation
(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)
slice, sort: correct triple of xorshift RNG
jdemeyer commentedon Apr 7, 2025
Maybe too late now, but this might have been good to mention in the Go 1.24 release notes. This change broke some tests in my code because "equal" elements sorted differently (my fault of course, but I did check if anything changed regarding sorting in the release notes).