juliank, 6 hours ago to random

It's not quite clear to me how to implement the behaviour of apt upgrade entirely backwards compatible.

That is, apt upgrade removes no packages. Anything needing a removal would cause a package to be kept back instead. But um solver3 will happily install a new dependency instead of keeping the upgrade back to avoid a removal.

For apt-get upgrade, new installs are not allowed either. I'm not sure if solver3 does funky stuff there, after all it can only change versions.

juliank, 14 hours ago (edited 13 hours ago) to random

The Debian dependency problem (DebSAT)

1. It's main clauses have the form

V -> D1 v D2 v ... v Dn
V -> not C1
V ~> R1 v R2 v ... v Rn

2. The root clauses have the form

ROOT -> V1 v ... v Vn
ROOT ~> V1 v ... v Vn

A basic solver algorithm is

solve(choice)
unit propagation
l = choose_literal()
return solve(l) or solve(not l)

solve(ROOT)

where:

choose_literal() finds the clause with the smallest number of allowed choices, -> before ~>, returning the first allowed Di

juliank, 5 days ago to random

Fresh off the presses: New blog post: The new APT 3.0 solver

https://blog.jak-linux.org/2024/05/14/solver3/

Comments here.

juliank, 7 days ago to random

In Madrid watching Acapulcu on Apple TV+ on a Chromecast with Google TV attached to a hotel TV.

Does it get weirder than that?

juliank, 7 days ago to random

Thought experiment: Two routes, same travel time, one is 6 min bus and 23 min metro, other is 23 min bus and 6 minute metro what would you take?

juliank, 8 days ago to random

Enjoy your churros and porras. Chocolate came later 😋

juliank, 8 days ago to random

I'll now start blocking the KeePassXC hate mob. We're all trying to do our best here and I don't need to constantly engage with new haters while trying to navigate a foreign cities metro system.

juliank, 9 days ago to random

The whole "illegals vote I'm US elections" discussion is funny as a German because here

• everyone needs to register their home address with the city within a week or two of moving there, you are automatically "registered to vote" by this and assigned the closest place to vote when an election happens.
• to vote, you need to present ID and it's checked against the people allowed to vote in that place.

juliank, 9 days ago to random

Today I'm wearing new Armed Angels Dylaan jeans and Veja Condor 2 shoes with a custom orthotics.

And a Bionic Beaver t-shirt.

juliank, 9 days ago to random

How's Firefox on iPadOS?

juliank, 9 days ago to random

I'm in Germany so of course I am taking trains that are scheduled to arrive 2 hours before my flight boarding, despite having fast lane security check and basically needing maybe 30 minutes to the gate.

But the key word is scheduled. It's easy to get an hour or two of delays if somebody jumps on the track , an ICE breaks down in front of you, or something

juliank, 10 days ago to random

Yo no hablo Español

juliank, 10 days ago to random

Hasta luego

juliank, 10 days ago to random

Install the best version of apt below 2.9?

apt --no-strict-pinning --solver 3.0 satisfy 'apt (<< 2.9)'

Quite fancy.

juliank, 11 days ago to random

Lots of changes for solver3. I made it very slow over the past day, but I solved the fundamental issue in my approach now and we're back to competitive with the classic apt solver.

There's still more performance potential incoming. One problem is that we queue dependencies that have a single solution rather than recursively install them.

If we mark them recursively we can do it in one big transaction and avoid the need for some rescoring if we see some Conflicts.

So much fun.

juliank, 11 days ago to random

I was missing negative unit propagation in my dependency solver hence it was just running forever trying to install apt-utils=2.7.14build2 in all places it could backtrack to.

Like it doesn't do logical backtracking, it just backtracks to the previous decision level.

Now I propagate correctly

apt=2.7.14build2
-> not apt=<other version>
-> not any of its reverse dependencies

And it works correctly.

juliank, 12 days ago to random

Anyway so solver3 currently stores a partial implication graph; recording only the first thing it sees implying something.

To implement conflict-driven clause learning like the state of the ART sat solvers we're going to need to make that a list.

But then we can start doing the dance of finding the cut-off point in the graph and non-chronologically backjumping that CDCL does.

But even now it works quite nice, there's not much need to do backtracking really in most cases.

juliank, 12 days ago to random

DPLL has a "Pure literal elimination" phase that makes it a good sat solver. If a literal exists only in a single polarity in your formular, you can just assign it that value.

This does not work for dependency solvers however. To translate this to a dependency solver:

It would install every package that has no conflicts

Anyway thinking about literals and CNF formular is much harder than thinking about the whole thing in terms of dependencies.

juliank, 14 days ago to random

The problem with the solver design without optimization is that each fallback doubles the runtime, in the worst case:

Let's say you have a 100 packages you want to upgrade. But all of them fail to be upgraded.

You need 2**100 attempts to figure that out.

If instead you upgrade the first package first, then try to upgrade the 2nd package, and so on, you need 2*100 attempts, but the solver will be less optimal.

juliank, 14 days ago to random

Can I make the dependency solver calculate strongly connected components of the dependency graph to speed it up?

juliank, 14 days ago to random

Regarding unsatisfiable dependencies:

I believe they are a bug in the archive. Falling back from A to B in A|B because A is uninstallable is a bad thing.

You temporarily break A's dependencies and then people installing during that time get B while everyone before and after gets A, leading to unintentional deviation.

1/2

juliank, 14 days ago to random

Sigh

juliank, 15 days ago to random

It was the dawn of the third age of mankind – ten years after the Earth-Minbari War.

juliank, 15 days ago to random

I don't suppose anyone has a Spanish fantasy or sci-fi series I can stream to prepare for the travel to Madrid?

It's less about the language itself, but my brain is stuck mostly on Italian and French for the intonation.

Didn't help watching a drama that is half French spoken the past days.

juliank, 15 days ago to random

I really don't like this Mr Adams from Massachusetts. In