starlark: set internal iteration use hashtable linked lists

google / starlark-go

Starlark in Go: the Starlark configuration language, implemented in Go

BSD 3-Clause "New" or "Revised" License

2.32k stars 212 forks source link

starlark: set internal iteration use hashtable linked lists #404

Closed emcfarlane closed 1 year ago

emcfarlane commented 2 years ago

Removes allocations on Set operations. Added a single benchmark testing equality, should improve other set operations too.

Old: Benchmark/bench_set_equal-8 35050 34043 ns/op 16384 B/op 1 allocs/op

New: Benchmark/bench_set_equal-8 41312 28884 ns/op 0 B/op 0 allocs/op

emcfarlane commented 1 year ago

Thanks for reviewing, sorry for the long delay in my changes to feedback too. Have removed the allocation changes but introduced some doc changes for go1.19. Please let me know if this should be separated out.