search

inetaf / netaddr

Network address types
BSD 3-Clause "New" or "Revised" License
715 stars 39 forks source link

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

Open mdlayher opened 3 years ago

mdlayher commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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 commented 3 years ago

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

danderson commented 3 years ago

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 commented 3 years ago

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

mdlayher commented 2 years ago

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

bradfitz commented 2 years ago

Fwiw, I still want this... Somewhere.

mdlayher commented 2 years ago

@bradfitz ack, will reopen for tracking!