perf: speed up LinkedHashMap Remove() function from O(n) to O(1) #264

ErenDursun · 2024-08-18T14:45:39Z

This pull request speeds up the LinkedHashMap Remove() function from O(n) to O(1) and closes #178
This is a reimplementation of #211 (with generics)

benchmarks before changes

goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/maps/linkedhashmap
cpu: AMD Ryzen 7 5800H with Radeon Graphics         
BenchmarkTreeMapGet100-16                2074827               596.3 ns/op             0 B/op          0 allocs/op
BenchmarkTreeMapGet1000-16                195075              5819 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapGet10000-16                 7900            146032 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapGet100000-16                 558           2122081 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut100-16                 828850              1398 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut1000-16                 86884             14209 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut10000-16                 4630            255836 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut100000-16                 349           3419082 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapRemove100-16             3643064               326.9 ns/op             0 B/op          0 allocs/op
BenchmarkTreeMapRemove1000-16             346851              3210 ns/op              12 B/op          0 allocs/op
BenchmarkTreeMapRemove10000-16             29650             37156 ns/op           14452 B/op          0 allocs/op
BenchmarkTreeMapRemove100000-16                1        14399768819 ns/op       40397499288 B/op          101433 allocs/op
PASS
ok      github.com/emirpasic/gods/v2/maps/linkedhashmap 30.794s

benchmarks after changes

goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/maps/linkedhashmap
cpu: AMD Ryzen 7 5800H with Radeon Graphics         
BenchmarkTreeMapGet100-16                2051914               580.3 ns/op             0 B/op          0 allocs/op
BenchmarkTreeMapGet1000-16                204310              5628 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapGet10000-16                 8079            147311 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapGet100000-16                 546           2222615 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut100-16                1711609               687.0 ns/op             0 B/op          0 allocs/op
BenchmarkTreeMapPut1000-16                155341              7439 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut10000-16                 6922            171496 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapPut100000-16                 480           2421338 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapRemove100-16             5723505               208.4 ns/op             0 B/op          0 allocs/op
BenchmarkTreeMapRemove1000-16             591494              2026 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapRemove10000-16             59067             20384 ns/op               0 B/op          0 allocs/op
BenchmarkTreeMapRemove100000-16             5954            204094 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/emirpasic/gods/v2/maps/linkedhashmap 17.761s