Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

runtime: TestStructHash, TestArrayHash etc failing on plan9-arm #45090

Closed
millerresearch opened this issue Mar 17, 2021 · 11 comments
Closed

runtime: TestStructHash, TestArrayHash etc failing on plan9-arm #45090

millerresearch opened this issue Mar 17, 2021 · 11 comments

Comments

@millerresearch
Copy link

@millerresearch millerresearch commented Mar 17, 2021

After CL280372, hash tests are failing on plan9-arm:

--- FAIL: TestSmhasherAppendedZeros (0.00s)
    hash_test.go:161: unexpected number of collisions: got=92 mean=0.000008 stddev=0.002821 threshold=50.423229
--- FAIL: TestSmhasherSmallKeys (0.03s)
    hash_test.go:161: unexpected number of collisions: got=256 mean=0.503906 stddev=0.709864 threshold=156.983435
--- FAIL: TestSmhasherZeros (0.00s)
    hash_test.go:161: unexpected number of collisions: got=127 mean=0.000122 stddev=0.011054 threshold=51.658213
--- FAIL: TestArrayHash (0.00s)
    hash_test.go:703: too many allocs 8.000000 - hash not balanced
--- FAIL: TestStructHash (0.00s)
    hash_test.go:759: too many allocs 8.000000 - hash not balanced
FAIL
FAIL	runtime	76.325s

Also failing in hash/maphash:

--- FAIL: TestSmhasherAppendedZeros (0.00s)
    smhasher_test.go:99: unexpected number of collisions: got=70 mean=0.000000 stddev=0.000000
--- FAIL: TestSmhasherZeros (0.00s)
    smhasher_test.go:99: unexpected number of collisions: got=864 mean=0.000000 stddev=0.000000
FAIL
FAIL	hash/maphash	0.187s
@randall77
Copy link
Contributor

@randall77 randall77 commented Mar 17, 2021

Weird that this is happening on this 32-bit platform and not others.

@mengzhuo

@mengzhuo
Copy link
Contributor

@mengzhuo mengzhuo commented Mar 18, 2021

This will affect on plan9/386 too.
Plan9 ONLY use extendRandom for initial hashkey generate while other platforms read OS random into hashkey first.

go/src/runtime/os_plan9.go

Lines 326 to 329 in f5e6d3e

//go:nosplit
func getRandomData(r []byte) {
extendRandom(r, 0)
}

This will always had 0 in the first byte. We have three options for this issue:

  1. Get random data from OS on plan9 ( I prefer this one but I don't have any plan9 to check. @millerresearch Can you help us?
  2. Xor constant primes in the mix32 (slower and it will got failed if data is identical to hashkey: 2^32 -1 )
  3. Drop wyhash and revert to cityhash

p.s. plan9 has /dev/random file which we can read from. https://9fans.github.io/plan9port/man/man3/rand.html

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 18, 2021

Change https://golang.org/cl/302909 mentions this issue: runtime: init hashkey data by /dev/random on plan9

@tmthrgd
Copy link
Contributor

@tmthrgd tmthrgd commented Mar 18, 2021

CL 6386 is relevant. Plan9 used to read from /dev/random before that CL, but that was intentionally removed because it was "slow and [...] may block". Perhaps things have changed since 2015 though.

@mengzhuo
Copy link
Contributor

@mengzhuo mengzhuo commented Mar 18, 2021

@tmthrgd

CL 6386 is right.
It much more slower and I think maybe we can put const primes into hashkey first for plan9.

read /dev/random
ok  	archive/tar	3.241s
ok  	archive/zip	4.145s
ok  	bufio	3.142s
ok  	bytes	16.037s
ok  	compress/bzip2	2.547s
ok  	compress/flate	3.316s
without /dev/random
ok  	archive/tar	0.257s
ok  	archive/zip	1.246s
ok  	bufio	0.286s
ok  	bytes	12.756s
@mengzhuo
Copy link
Contributor

@mengzhuo mengzhuo commented Mar 19, 2021

@wangyi-fudan Any idea how can we initial hashkey without any entropy input?

@millerresearch
Copy link
Author

@millerresearch millerresearch commented Mar 19, 2021

@0intro, is the GCE-specific slowness described in #10028 still the case? Maybe it's time to investigate that.
What virtualisation technology does GCE use? Can I replicate it at home for debugging or do I need to set up a GCE account and try to do it remotely?

@0intro
Copy link
Member

@0intro 0intro commented Mar 19, 2021

I don't think that's specific to GCE. /dev/random has always been slow and Plan 9 and can block (like /dev/random on Linux).

At some point, I wrote randfs, which replaces /dev/random by a, much faster, pseudo-random generator (similar to /dev/urandom on Linux). It solved the issue, but we finally changed getRandomData, because we didn't really need true random numbers just to improve the distribution of hash values.

If we're going to use the Plan 9's /dev/random, we will have to reintroduce randfs as a dependency to run Go on Plan 9, which wouldn't be very desirable.

I'd prefer options 2. or 3.

@millerresearch
Copy link
Author

@millerresearch millerresearch commented Mar 19, 2021

What exactly is the requirement for the output produced by getRandomData? Is there a specification somewhere?

@mengzhuo
Copy link
Contributor

@mengzhuo mengzhuo commented Mar 24, 2021

What exactly is the requirement for the output produced by getRandomData? Is there a specification somewhere?

For wyhash it only needs a non-zero integer to "mix" (xor + multiply)

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 24, 2021

Change https://golang.org/cl/303969 mentions this issue: runtime: init plan9 hashkey by time

@gopherbot gopherbot closed this in a95454b Mar 30, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
7 participants