Performance degrades severely under prefix load

[bplotnick]

When a prefix is "loaded" - meaning that we have acquired a large number of ips from it - performance degrades as O(number of acquired IPs)

The benchmark code misses this because it immediately releases IPs after acquiring them. But with a slight change, you can see this:

--- a/prefix_benchmark_test.go
+++ b/prefix_benchmark_test.go
@@ -33,6 +33,7 @@ func BenchmarkAcquireIP(b *testing.B) {
                if err != nil {
                        panic(err)
                }
+               ips := make([]*IP, b.N)
                for n := 0; n < b.N; n++ {
                        ip, err := ipam.AcquireIP(ctx, p.Cidr)
                        if err != nil {
@@ -41,7 +42,10 @@ func BenchmarkAcquireIP(b *testing.B) {
                        if ip == nil {
                                panic("IP nil")
                        }
-                       p, err = ipam.ReleaseIP(ctx, ip)
+                       ips[n] = ip
+               }
+               for _, i := range ips {
+                       _, err := ipam.ReleaseIP(ctx, i)
                        if err != nil {
                                panic(err)
                        }

You should see performance degrade significantly.

On my machine, if i measure the time it takes to acquire the last IP, with in-memory storage the 2nd acquired is ~1us, the 101st is 13us, and the 10001 is 1ms.

I believe this is due to this loop: https://github.com/metal-stack/go-ipam/blob/master/prefix.go#L378, which will scan the entire range.

[majst01]

Interesting observation, your guess where the time is spent might be correct, but i have actually no better solution in mind howto find the next available ip in the prefix, other than iterating through the prefix.

First action would be to write a benchmark for this specific func acquireSpecificIPInternal and see if your guess is correct.
If you have time to write a PR for that, i am happy to review

[majst01]

@bplotnick added a benchmark which shows the root cause in this #147 also made the memory case at least twice as fast