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: interface hash table not Quadratic Probing #41553

Closed
dreamerjackson opened this issue Sep 22, 2020 · 2 comments
Closed

runtime: interface hash table not Quadratic Probing #41553

dreamerjackson opened this issue Sep 22, 2020 · 2 comments

Comments

@dreamerjackson
Copy link
Contributor

@dreamerjackson dreamerjackson commented Sep 22, 2020

i read soource code about interface hash table. the code say hash use Quadratic Probing. but absolutely not.
this is just h +=i not h +=i *i, this is a special design or a bug?


func (t *itabTableType) find(inter *interfacetype, typ *_type) *itab {
	// Implemented using quadratic probing.
	// Probe sequence is h(i) = h0 + i*(i+1)/2 mod 2^k.
	// We're guaranteed to hit all table entries using this probe sequence.
	mask := t.size - 1
	h := itabHashFunc(inter, typ) & mask
	for i := uintptr(1); ; i++ {
		p := (**itab)(add(unsafe.Pointer(&t.entries), h*sys.PtrSize))
		// Use atomic read here so if we see m != nil, we also see
		// the initializations of the fields of m.
		// m := *p
		m := (*itab)(atomic.Loadp(unsafe.Pointer(p)))
		if m == nil {
			return nil
		}
		if m.inter == inter && m._type == typ {
			return m
		}
		h += i
		h &= mask
	}
}
@martisch
Copy link
Contributor

@martisch martisch commented Sep 22, 2020

h is increased on every iteration by an i that is increasing on every iteration. If it would be linear if the addition would be by a costant e.g. h += 10.

See:
https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF#:~:text=%2C%20%E2%88%92112.-,Ramanujan%20summation,%E2%8B%AF%20is%20also%20%E2%88%92112.

Which gives the sum of integers 1+2+...+n = n*(n+1)/2

Loading

@martisch martisch closed this Sep 22, 2020
@dreamerjackson
Copy link
Contributor Author

@dreamerjackson dreamerjackson commented Oct 15, 2020

thanks!

Loading

@golang golang locked and limited conversation to collaborators Oct 15, 2021
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants