Closed mpizenberg closed 1 year ago
I think there is something like this that can work. ("filter out items faster than a HashSet.contains
" in https://github.com/pubgrub-rs/pubgrub/pull/88#issuecomment-833780223) but I think the big thing is your 3. The big savings if from incompats like a depends on b
, where we only have to check it for a
, as when we get to b
we already know it is contradicted. Definitely worth continued exploration. Thanks for sharing!
I had some time to experiment. I found some variations that broke even, but nothing that was an overall improvement. As other parts get faster, the opportunity's here may become clearer. Or we may think of other structures with even less overhead. Definitely worth continued exploration.
Indeed, let's leave this type of change for later, if it still makes sense at that time.
Another idea that turned out to be not as performant as expected. The code base has changed quite a bit since then. So let's just discard this and as you say, we'll likely identify clearer opportunities later.
Inspired by the
contradicted_incompatibilities
change that was recently introduced in #88 I wanted to see if instead of checking for each incompat if it is incontradicted_incompatibilities
, we could simply remove those contradicted incompats and only add them again when backtracking.It works, but it's slower. I think because of few downsides:
self.incompatibilities
from aMap<P, Vec<Id>>
to aMap<P, Set<Id>>
to be able to remove contradicted incompatsself.contradicted...
toself.incompat...
when backtracking.self.contradicted...
type fromSet<id>
toMap<P, Set<Id>>
and so we don't know in Id was already contradicted when evaluating the other packages of the same incompat.Regardless of the fact that it's slower, I thought it was cool enough to share (but not to merge)