search

chainguard-dev / apko

Build OCI images from APK packages directly without Dockerfile
https://apko.dev
Apache License 2.0
1.21k stars 125 forks source link

Consider already selected packages during solve #1406

Open jonjohnsonjr opened 1 week ago

jonjohnsonjr commented 1 week ago 
We ran into a very very slow solve. I can't tell if it was actually slow
or infinite, but it didn't seem to be convering very quickly. I realized
that we essentially recurse the entire graph for every constraint, even
for things we've already solved. This was surprising, because I thought
we handled that already, but it seems like we didn't.

I've added an example "abseil-regression.yaml" that took over a second
to solve (as of this writing) before this change and takes about 1ms
after this change. There's an open PR in wolfi that timed out because
the abseil dep graph got even more gnarly and took several hours, so
there was something (at least) quadratic going on here, oops.

I've deleted a test that was exercising a scenario where packages were
disallowed from providing themselves because there is no code path where
that was actually possible (all invocations had "true" hard-coded).

I also ran this against a several thousand image configs and they all
produced the same results before and after this change, so I am fairly
confident in it.
jonjohnsonjr commented 1 week ago

e2e tests are failing because a lot of our examples use alpine repos, and currently musl on x86_64 is at 1.2.5-r6 whereas musl on aarch64 is at 1.2.5-r5

dannf commented 4 days ago

I've tested this branch and it fixes the issue for me. Thanks! Do you mind referencing https://github.com/chainguard-dev/melange/issues/1651 in the commit log?