juliank

juliank, 47 minutes ago to random

I do have fancy profiling graph for the solver. I ran the solver 20 times from Python on a cache, it took:

Resolve: 90.10825674049556 +/- 7.953068206569682 ms

Same range as current solver.

Thanks to -fno-omit-frame-pointer on Ubuntu 24.04 this call graph actually works reasonably well!

juliank, 1 hour ago to random

So you told solver3 to

apt install foo=1 --no-strict-pinning

But you have foo=2 and foo=3 too. What will it do?

(1) It marks foo=1 for install
(2) It marks foo=2, foo=3 and (3) their transitive reverse deps as not for install

Now it reaches a bar with depends foo. It will only be able to pick foo=1 due to (1) above.

You reach a baz=1/2/3 Depends foo=1/2/3. Now baz=2/3 have been rejected already in (2) so it will just try 1 directly.

Without (3) we'd try all baz in order and backtrack.

juliank, 8 hours 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, 20 hours 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, 1 day 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, 1 day 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, 1 day ago to random

APT solver update:

I didn't actually hack on it but I remembered I had dumps from the noble time_t upgrades with problems, and I ran solver3 on those and it performed decently, so I am quite happy.

Shows the backtracking is working correctly.

Still need to actually go and record the unsatisfiability cores (i.e. A->B->C->D and X->Y->Z but D conflicts Z) before backtracking so I can show them to the user at the end. And to avoid making the same bad decisions again in different branches...

juliank, 1 day ago to random

APT solver as a snap:

I anticipate the new apt solver to be available in the snap store this or next week, as the "solver3" snap. You will then be able to use it using

apt --solver /snap/bin/solver3

This is quite a slow experience as it uses the external dependency solver protocol but you can test with it on all releases.

For performance evaluation you'll have to wait for the 2.9.x release and use --solver 3.0.

zacchiro, 2 days ago to random

So-called "technology transfer" at universities is a disease for [open] science. Episode #1451.

A student of mine asked the authors of a security paper, involving LLMs and cyberattacks, details about their experimental setting, which were crucial for reproducibility (and reviewability…).

Answer (from tech. transfer staff): « To receive the code and the prompts, [university] would need to enter into a license agreement (with strong confidentiality clauses and a $30,000 onetime fee) »

juliank, 2 days ago to random

Took a bit to figure out but
std::sort()

reads from outside the given range if your operator< is inconsistent, aka returning true for A==B.

Causing stuff to crash of course.

juliank, 2 days ago to random

So I am missing error reporting somewhere on the backtracking path; but if backtracking is successful, you are good to go. e.g. install libapt-pkg6.0t64=2.7.14build2 and change versions accordingly to satisfy dependencies. Works.

juliank, 3 days ago to random

Solver3 status:

Backtracking is hilariously broken but we are getting somewhere. It's only enabled for Recommends right now but there's some weird memory issues everywhere due to the item moving between two std::vector. No Conflicts learning

The barebones why sort of works:
I can print you dependency chains outlining the reason for each package being installed. Notably they're not the most readable, as they do cross provides.

So a Depends B, x Provides B, x depends c

Shows up as a -> x -> b.

juliank, 3 days ago to random

Well so far the archive is pretty fallback free, so solver3 can now install ubuntu-desktop and kubuntu-desktop and the end result is comparable to apt.

Minor differences if you install both ubuntu and kubuntu desktops, you lose 3 packages:

• qtspeech5-speechd-plugin because qtspeech5-flite-plugin is already installed.

• sddm-theme-maya because sddm-theme-breeze is already installed

• xserver-xorg-input-all xserver-xorg-input-libinput because xserver-xorg-input-wacom is installed (UGH)

juliank, 3 days ago to random

Technically each dependency can be required by multiple packages but I only track the first one I see.

juliank, 3 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, 3 days ago to random

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

juliank, 3 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