Still trying to get my head around this weird construct (added in moby/libnetwork@3feb3aa) even more with the "timeCompensate" below.

Do we know why does the lock/unlock have to happen inside the loop here (but the others lock outside)?

The comment above the for loop is attempting to explain it but I'm not sure I understand it. Could it be that releasing the lock in every iteration allows other goroutines to continue work instead of lagging too much? Either way, this PR is not modifying that logic.

Actually the commit message of the commit you posted confirms it.

Yeah, was looking at that description and wondered if that changed now that there's an RWMutex, but yeah, this code is complicated, so perhaps that didn't work

Perhaps a micro-optimisation, but if these loops run many times, perhaps worth it while we're changing;

how about using bytes.Split or even bytes.SplitN (if we expect these to have 4 components)? Quick (naive) benchmark;

package main

import (
	"bytes"
	"strings"
	"testing"
)

func BenchmarkSplitString(b *testing.B) {
	path := []byte("/one/two/three/four")
	sep := "/"
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		params := strings.Split(string(path[1:]), sep)
		nid := params[0]
		tname := params[1]
		key := params[2]
		_, _, _ = nid, tname, key
	}
}

func BenchmarkSplitBytes(b *testing.B) {
	path := []byte("/one/two/three/four")
	sep := []byte("/")
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		params := bytes.Split(path[1:], sep)
		nid := string(params[0])
		tname := string(params[1])
		key := string(params[2])
		_, _, _ = nid, tname, key
	}
}

func BenchmarkSplitNString(b *testing.B) {
	path := []byte("/one/two/three/four")
	sep := "/"
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		params := strings.SplitN(string(path[1:]), sep, 4)
		nid := params[0]
		tname := params[1]
		key := params[2]
		_, _, _ = nid, tname, key
	}
}

func BenchmarkSplitNBytes(b *testing.B) {
	path := []byte("/one/two/three/four")
	sep := []byte("/")
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		params := bytes.SplitN(path[1:], sep, 4)
		nid := string(params[0])
		tname := string(params[1])
		key := string(params[2])
		_, _, _ = nid, tname, key
	}
}

BenchmarkSplitString
BenchmarkSplitString-10     	14783635	        79.58 ns/op	      88 B/op	       2 allocs/op
BenchmarkSplitBytes
BenchmarkSplitBytes-10      	16331946	        72.41 ns/op	      96 B/op	       1 allocs/op
BenchmarkSplitNString
BenchmarkSplitNString-10    	16576970	        71.87 ns/op	      88 B/op	       2 allocs/op
BenchmarkSplitNBytes
BenchmarkSplitNBytes-10     	19375464	        63.30 ns/op	      96 B/op	       1 allocs/op

I initially had that that but whatever you gain by that is offset by the fact that you need to redo the conversion in deleteEntry.

Looks like this is redundant, as we already know the prefix (which is what we're passing to iterate), which means we can also (instead of only stripping the / prefix), strip /+nid+/, and take params[0], params[1] (instead of 1 and 2);

// Format is "/<networkID>/<tableName>/<endpointID>/<value>",
// trim "/+nid+/" before splitting.
params := bytes.Split(path[len(nid)+2:], []byte("/"))
tname := string(params[0])
key := string(params[1])

deleteEntry needs both /<tname>/<nid>/<key> and /<nid>/<tname>/<key> so there's no way around it. I mean we could pass the whole string for /<nid>/<tname>/<key> but then we'd have to pass tname nid and key anyway for the first path.

Silly question (I can't comment on the line below); as the problem was that we were deleting inside the loop, and as we're already taking a lock, would it make sense to collect the list of entries to delete in WalkPrefix, and then delete them outside of it? Would that make it more performant?

Also wondering; it seems we're using the WalkPrefix to collect all entries with the given prefix so that we can delete all of them; if (IIUC), the format is /<networkID>/<tableName>/<endpointID>/<value>, but we only collect /<networkID>/<tableName>/<endpointID>, that means we're manually performing a delete multiple times (once for each <value>). Perhaps we could make use of DeletePrefix() 🤔

Yeah I thought about this too. The current logic is very hairy because it's not simply a deleting a bunch of radixes, it also checks for each entry if it was successfully deleted and only then it updates the state of the number of entries in that network: https://github.com/moby/moby/pull/44501/files#diff-7b5363044492af3bcc6d8117470bfc51476d389c7a90670cfd5c62a83c32445aR777

And there's that whole timecompensation logic too. So yeah, again, I tried to change the least amount of logic in an area I'm not very comfortable in. If somebody wants to decipher the timecompensation logic and use DeletePrefix that's just an optimization which is not the purpose of this PR.

We should probably also consider using concatenation for these simple cases (instead of Sprintf())

I don't think it's worth to sacrifice readability in this case.

See my other comment; perhaps if we drop the key for these, we can use DeletePrefix;

We may want to do the actual delete outside of the WalkPrefix function in that case though to remove duplicates first (although it looks like DeletePrefix will just ignore if it was already deleted).

What happens when for some unknown reason (something something timeCompensation that I don't understand) not all entries in a prefix are to be deleted? Then you cannot use DeletePrefix, you have to redo a walk for each entry.