Slow performance populating tree about cidranger HOT 11 OPEN

@ldkingvivi Seems like you integrated those changes already and added even more functionality. The Contains() bool function is very useful!

from cidranger.

Yes, you may do what you want with it.

Also as a side note, I'd encourage discussion on the gist itself, as it's linked to from places other than here.

I also updated it to address the issue regarding find(). Solution was basically the same as what @ldkingvivi proposed.
I also included another fix when matching against v4 /32 or v6 /128 addresses.

from cidranger.

Since there seems to be moderate interest in my implementation, I've published it as a full package here: https://github.com/phemmer/go-iptrie/

from cidranger.

@phemmer What are the other alternatives you found?

from cidranger.

They're listed in the benchmark code on the issue description.

from cidranger.

@phemmer Find func may not seem do what you want, it doesn't return most specific result. Try two entry in trie like 8.8.8.0/24 and 8.8.8.0/25 each with some value, and Find "8.8.8.8", it will show up /24 value instead of /25 value.

I think the original fn just Contain, which return bool and doesn't matter if that's more specific or not, and your Find fn try to return most specific entry(smallest prefix), which require follow the children path

maybe change the find fn to

func (p *Trie) find(number netip.Addr) any {
	if !netContains(p.network, number) {
		return nil
	}

	if p.network.Bits() == 128 {
		return nil
	}
	bit := p.discriminatorBitFromIP(number)
	child := p.children[bit]
	if child != nil {
           if r := child.find(number); r != nil{
		return r
           }
        }
    
        if p.value != nil {
		return p.value
	}

	return nil
}

from cidranger.

@phemmer I'm guessing your gist is under MIT License, since it's based on cidranger. I can develop/publish a go module with this code, tests, benchmarks, docs and give you credit in the README. Let me know if that is fine with you.

from cidranger.

@phemmer Awesome, from my local benchmarks it seems the changes made by @ldkingvivi make it even faster.

See here: https://github.com/ldkingvivi/cidranger/blob/master/iptire/trie.go

from cidranger.

@phemmer my change was mainly adding Entry with generic, so containing and cover networking will all return something instead of pure prefix, and of course some tests and benchmark using existing way how cidrange tested/benchmakred. Do you want me create a PR to your repo? I will likely have time during weekend.

ldkingvivi@d5fcd23

from cidranger.

@phemmer my change was mainly adding Entry with generic

I had considered using generics, but stuck with any types as the usage is simpler (in some scenarios). I think using generics is a valid design that some might prefer, but I think it should likely be a new package entirely. It's possible one might be able to implement a design using any types on top of a generics implementation. But I didn't feel the effort was justified. If you do have a solid design that still allows both to be used, then it might be worth considering.

containing and cover networking will all return something instead of pure prefix

The Contains method stops searching on the first (largest) network it finds. Thus it's not going to be have access to the data from the most specific network (largest prefix) entry. If you do want the data from the largest network that matches, you can use the FindLargest method instead. I don't want to change Contains to be anything other than a boolean.

Having CoveredNetworks return the data, or something which allows obtaining both the data and the network might be valid. However I feel like a good design that allows retrieving the data along with the network itself would be rather complicated. Though I could be wrong, as I may not have considered all possibilities. I'm instead considering ripping out CoveredNetworks entirely. It's there because it was in cidranger. However I don't know of any valid use cases for it (if you have one, I'd love to hear it). So rather than expand its capability, I'm more inclined to remove it until someone actually needs it. I would rather provide minimal functionality, and expand it in the future, than have to maintain useless functionality in perpetuity.

and of course some tests and benchmark using existing way how cidrange tested/benchmakred

I omitted tests from my gist because gists are meant to be concise, not because they didn't exist. They exist, and were published in the package.

As far as benchmarks, the package also contains a benchmarking suite. If you don't feel the benchmarks are meaningful, I'd be willing to consider additional scenarios. I do know that the random networks aren't likely representative of real-world scenarios, as it creates too many networks which are too large. I've considered solving that using a curve to make smaller prefixes more rare. But I don't think it'd change the overall results significantly, so I haven't bothered.

Do you want me create a PR to your repo? I will likely have time during weekend.

If you like, though I'd recommend proposing specific changes for discussion first. The proposals should be in that repo as well, as this one should be for discussions about cidranger only, and I feel we've hijacked it enough.

from cidranger.

I didn't referring to Contains, but ContainingNetworks. Also for the comments about tests and benchmark, I just simply mentioned the fact what I added, nothing criticize your gist. At this point, I will just continue use my branch directly, since I do have use case to fetch data other than just prefix, as well as generic for my use case.

One thing I agree, we probably hijacked this place enough, I will stop doing that now.

from cidranger.