proposal: add a trie type for efficient route lookups using netaddr.IP{,Prefix}

[mdlayher]

I'd like to introduce netaddr in an application at work that uses a big trie full of routes using net.IP and net.IPNet. I suspect there could be some serious performance/memory improvements by using netaddr instead and I think it could be a fun educational project for me too.

Would there be interest in having this as part of the upstream library? I can always start out with my own repo too.

/cc @bradfitz @danderson @josharian

[mdlayher]

Also with generics on the horizon it's possible that building such a thing might be a lot more ergonomic in a year or two. I personally wouldn't mind yolo changing the API to swap out empty interfaces when possible, but I guess it'd also depend on what the compatibility plans are for netaddr.

[josharian]

Brad started a SMART implementation. I've been meaning for ages to finish it up. I'd love it if you did. :) I'm pretty sure wireguard-go would use one too. I think it should probably go in a separate package, but I'm +1 on inet.af/smart. I agree that generics would help with IPv4 vs IPv6, but initially I'd say just make two copies and we can reduce to one with generics as appropriate. We could even do it without API changes, just swap in a generic backend. The SMART implementation might also be a reason to extract out uint128 support into a separate package, since you won't need zones in your routing table. (Or give up on space efficiency and write just one that uses full IPs at every node!)

[mdlayher]

Brad started a SMART implementation. I've been meaning for ages to finish it up. I'd love it if you did. :)

Have a link? I don't think I've seen it.

[josharian]

Weird, I can't find it. But I'm certain it existed. @bradfitz?

[danderson]

You had the name slightly off: https://github.com/bradfitz/art

That's the data type used by *BSD's network stack iirc, and is very efficient at a bunch of things, much moreso than a basic trie.

[mdlayher]

Nice, thanks for the link. I will investigate that and see if I can help out.

[mdlayher]

I no longer have a need for this and we've been integrated into stdlib, so I'm going to close this out.

[bradfitz]

Fwiw, I still want this... Somewhere.

[mdlayher]

@bradfitz ack, will reopen for tracking!