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

DedupAddrs should not allocate #2323

Closed
MarcoPolo opened this issue Jun 2, 2023 · 4 comments · Fixed by #2395
Closed

DedupAddrs should not allocate #2323

MarcoPolo opened this issue Jun 2, 2023 · 4 comments · Fixed by #2395

Comments

@MarcoPolo
Copy link
Collaborator

Sort.Slice will allocate unfortunately :(
golang/go#17332

func BenchmarkDedupAddrs(b *testing.B) {
	b.ReportAllocs()
	tcpAddr := ma.StringCast("/ip4/127.0.0.1/tcp/1234")
	quicAddr := ma.StringCast("/ip4/127.0.0.1/udp/1234/quic-v1")
	wsAddr := ma.StringCast("/ip4/127.0.0.1/tcp/1234/ws")
	addrs := []ma.Multiaddr{tcpAddr, quicAddr, tcpAddr, quicAddr, wsAddr}
	for i := 0; i < b.N; i++ {
		addrs = DedupAddrs(addrs)
	}
}

Originally posted by @sukunrt in #2322 (comment)

@sukunrt
Copy link
Member

sukunrt commented Jun 12, 2023

I just wanted to fix the comment.
fix here: #2350
The allocations are low(3/op) so it's fine to leave it as is. Converting it to an O(n^2) in place algorithm might lead to performance issues. It is an overkill implementing a custom no allocation O(nlgn) algorithm for this.

@marten-seemann
Copy link
Contributor

Are you sure there’s a performance penalty for a O(N^2) for small N? I’d expect it to be negligible for typical values of N.

@sukunrt
Copy link
Member

sukunrt commented Jun 12, 2023

I think you're right.

These are the benchmarks for an O(N^2) implementation:

BenchmarkDedupAddrs10-8          4220767               276.8 ns/op             0 B/op          0 allocs/op
BenchmarkDedupAddrs20-8          1315252               915.9 ns/op             0 B/op          0 allocs/op
BenchmarkDedupAddrs50-8           182114              6581 ns/op               0 B/op          0 allocs/op
BenchmarkDedupAddrs100-8           46258             25906 ns/op               0 B/op          0 allocs/op

Even if a node has 100 addrs(my kubo node has 15 before deduping), this isn't prohibitively expensive.

These are the numbers for the current implementation:

BenchmarkDedupAddrs10-8          6057549               192.2 ns/op            88 B/op          3 allocs/op
BenchmarkDedupAddrs20-8          3525658               338.6 ns/op            88 B/op          3 allocs/op
BenchmarkDedupAddrs50-8          1787802               670.7 ns/op            88 B/op          3 allocs/op
BenchmarkDedupAddrs100-8          974338              1204 ns/op              88 B/op          3 allocs/op

@marten-seemann
Copy link
Contributor

There's https://pkg.go.dev/golang.org/x/exp/slices, which provides allocation-free sorting. I created #2395 to make use of that package.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
3 participants