Shards: Crash on HEAP exhaustion [SAT solver]

[bararchy]

Fetching https://github.com/stumpycr/stumpy_png.git
Fetching https://github.com/stumpycr/stumpy_core.git
Fetching https://github.com/stumpycr/stumpy_utils.git
Fetching https://github.com/l3kn/pcf-parser.git
Failed to match versions for #<Shards::Dependency {stumpy_png => {"github" => "stumpycr/stumpy_png", "version" => "HEAD"}}>
Failed to match versions for #<Shards::Dependency {stumpy_core => {"github" => "stumpycr/stumpy_core", "version" => "~> 1.6.2"}}>
GC Warning: Repeated allocation of very large block (appr. size 12884905984):
        May lead to memory leak and poor performance
Unhandled exception: Negative size (ArgumentError)
Failed to raise an exception: END_OF_STACK
[0x55adfd147196] ???
[0x55adfd0d8c8b] __crystal_raise +43
[0x55adfd0d9aec] ???
[0x55adfd0e1d10] ???
[0x55adfd0dd25c] ???
[0x55adfd0dc25d] ???
[0x55adfd0e53ab] ???
[0x55adfd0ef75f] ???
[0x55adfd0db557] main +55
[0x7f0e62e4ece3] __libc_start_main +243
[0x55adfd0d46be] _start +46
[0x0] ???

[ysbaddaden]

A reproducible shard.yml ?

[bararchy]

It seems downgrading to last stable version solved this.
The shard.yml

name: project
version: 1.1.1
targets:
  project:
    main: src/project.cr

crystal: 0.29.0

license: MIT

dependencies:
  shainet:
    github: NeuraLegion/shainet
  myhtml:
    github: kostya/myhtml
  cadmium:
    github: watzon/cadmium
    branch: master
  fix:
    github: NeuraLegion/fix
  har:
    github: NeuraLegion/har
    branch: HEAD
  msgpack:
    github: benoist/msgpack-crystal
  kemal:
    github: kemalcr/kemal
    branch: HEAD
  kemal-basic-auth:
    github: kemalcr/kemal-basic-auth
  selenium:
    github: ysbaddaden/selenium-webdriver-crystal
    branch: HEAD
  stumpy_png:
    github: stumpycr/stumpy_png
    version: "~> 4.4.1"
  stumpy_utils:
    github: stumpycr/stumpy_utils

development_dependencies:
  ameba:
    github: veelenga/ameba
  mysql:
    github: crystal-lang/crystal-mysql

[j8r]

I can reproduce this on Alpine (shards 0.9.0) with https://github.com/DFabric/dppm/blob/master/shard.yml.
It seems that having more dependencies impact performance, to the point of being stuck after 8~9 shards.
Downgrading solves indeed the issue.

[j8r]

Gotcha (dppm is a project that has a big enough shards.yml)

git bisect start
git bisect good v0.8.1
git bisect bad v0.9.0
git bisect run sh -c 'shards build; cd ../dppm; timetout 12 ../shards/bin/shards install'

The commit found is 6698da36c78268ff8dc1798c9c9048641d7814ac:

6698da36c78268ff8dc1798c9c9048641d7814ac is the first bad commit
commit 6698da36c78268ff8dc1798c9c9048641d7814ac
Author: Julien Portalier <[email protected]>
Date:   Wed Jan 23 11:01:07 2019 +0100

    Add basic SAT solver

:040000 040000 5f0897f6ae6e09a9cd9bd5cc6831010fc9971448 dd18231bfbf6e09af1dd73e09fc301dcc5665cb4 M     src
:040000 040000 ed55cbb4fef9f2dca6a0a379af79f5039f9c8ab8 c63fd19c5f7076234ab0bf7c03258c77e9a2afea M     test

[ysbaddaden]

@j8r that commit is isolated: it's just a new class (SAT) and some tests for it. It's not used to resolve anything.

[j8r]

I've increased the timeout to 20 seconds, know I have this:

f22317367ec83c93cf9b12c6ae1a9cb8f699b4e0 is the first bad commit
commit f22317367ec83c93cf9b12c6ae1a9cb8f699b4e0
Author: Julien Portalier <[email protected]>
Date:   Sat Feb 2 13:32:20 2019 +0100

    Use SAT solver in all commands

:040000 040000 8ac9dd7f1ec8a33fcb1cf6c8ab0199162540750c 84653254a762b6ec92c0499ac1215a1f89dfb431 M      src
:040000 040000 67be5c9f12001a3d9c4adb99191f223455741e4b cb4a57a29f8ca888d4fde9e8d7180d59e03d0d79 M      test

[ysbaddaden]

Please open another issue for the performance issue, instead of adding unrelated information here, thanks.

[bararchy]

@ysbaddaden I believe @j8r refers to the original issue, which might originate from the performance hit that goes worse and worse until it hits Stack Overflow .

• I think

[ysbaddaden]

Note that limiting versions will constrain the graph (133 dependencies) and the number of clauses to solve (1081 clauses), speeding things up dramatically.

Obviously it's a workaround (still a good change) and doesn't fix the root issue.

[ysbaddaden]

The GC warning is caused by the high number of contradicted clauses that are remembered (for explaining resolve conflicts). Not remembering them avoids the warnings —but disables conflict explanations.

I think we should move to a Conflict Driven SAT solver, that would learn from these conflicts, thus limiting the number of repeated conflicts, and speeding the overall solver... but that's not trivial work.

[ysbaddaden]

I renamed the issue: it's not a stack overflow. When not remembering conflicting clauses, the SAT solver eventually finds a solution, without filling the stack, and memory usage is stable.

[straight-shoota]

Maybe we could disable the remembering as a quick fix?

[ysbaddaden]

No: it still takes 44 minutes on a Haswell laptop to solve (in release mode). The SAT solver is slow when the number of variables/clauses climbs up. But I didn't expect it to become that slow (only dozens of seconds, maybe half a minute).

The only workaround, for now, is to _limit the number of reachable versions_ in your dependencies. I tested and optimized the SAT solver against Lucky apps, that do define such version constraints (e.g. ~> 0.12), with a total of a dozen shards to install, it only takes half a second to solve (not even in release mode).

The solution is to optimize the SAT solver, for example by:

• moving to a _conflict-driven clause learning_ algorithm;
• optimizing/rewriting the SAT solver;
• simplifying the generated CNF clauses;
• using an external library (most are in C++, but PicoSAT and Lingeling are in C and Cadical has a C interface). no luck, cadical isn't faster.

[ysbaddaden]

I tried CaDiCaL (state of the art CDCL solver), but it didn't fare any better than the slow solver we have: the real issue isn't the solver, but the absurdly high number of CNF clauses created to make sure that two versions of the same library can't be installed at the same time.

I currently create a variable for each dependency/version pairs, which creates lots of variables. The SAT solver then tries to set all variables, even when a version has already been selected for a dependency. The solver is generic and only knows about it after testing clauses: one will fail creating a conflict, but possibly run after many others have been tested. Then the solver will try the next variable... possibly another version (exponential to how many versions are reachable for each dependencies). This leads to using lots of memory to remember the conflict, and lots of wasted CPU time, testing the same things over and over (and a CDCL doesn't help).

We could specialize the SAT solver to know about this constraint. Maybe add a range/set constraint that would group some variables together, allowing only one variable in the range/set to be selected at a time. That would greatly reduce the number of CNF clauses, and dramatically reduce the number of useless an repeated conflict checks, which should bring back the solver to an acceptable number of clauses (and runtime).

NOTE: I already limit the variables/clauses to reachable dependencies and versions. Adding stricter version constraints will reduce the number of versions to consider for each dependency, achieving the same optimization. Whenever possible, please add such constraints to your apps and libraries today! It's useless for your app to consider foo v0.4 and below if you're currently running v0.5 for example. Add a foo >= 0.5.0 constraint. Same for libraries that require a minimal version, ...

[dscottboggs]

I believe I am experiencing a similar issue. I hope that my experience can help this issue be tracked down in time.

• When running shards [install] on this project's directory, the command seems to freeze up for quite some time.
• Eventually the command exits with an obscured error code.
• The issue does not occur under 0.8.1
• The issue does not occur on my other (less powerful) machine. Specifically, the machine I am having this issue with has 24GB of RAM, and 2X Xeon Quad-core CPUs, and both the project and cache dirs are on (separate) SSDs

Additionally, I built shards from source on master and received the following output:

GC Warning: Failed to expand heap by 6459232256 bytes
GC Warning: Failed to expand heap by 6442455040 bytes
GC Warning: Out of Memory! Heap size: 6294 MiB. Returning NULL!
Invalid memory access (signal 11) at address 0xc0000000
[0x55e09bb72736] *CallStack::print_backtrace:Int32 +118
[0x55e09bb60270] __crystal_sigfault_handler +192
[0x7fa6704fed00] ???
[0x55e09bc1ec0e] *Pointer(Array(Int32)) +14
[0x55e09bc1e9fe] *Array(Array(Int32)) +46
[0x55e09bc1e9c6] *Array(Array(Int32)) +6
[0x55e09bc1e2be] *Shards::Solver::SAT#update_watchlist<Array(Deque(Array(Int32))), Int32, Array(Shards::Solver::SAT::Assignment), Bool>:Bool +686
[0x55e09bc1bcd3] *Shards::Solver#solve:(Array(Shards::Package) | Nil) +2307
[0x55e09bc180c4] *Shards::Commands::Install#run:Nil +500
[0x55e09bc17db9] *Shards::Commands::Install +25
[0x55e09bb62180] ~procProc(Array(String), Array(String), Nil) +448
[0x55e09bc34ceb] *OptionParser::ParseTask#parse:Nil +619
[0x55e09bc00f6d] *OptionParser#parse<Array(String)>:Nil +93
[0x55e09bbfe9b5] *Shards::run:OptionParser +677
[0x55e09bb5220b] __crystal_main +2619
[0x55e09bc36b36] *Crystal::main_user_code<Int32, Pointer(Pointer(UInt8))>:Nil +6
[0x55e09bc36a99] *Crystal::main<Int32, Pointer(Pointer(UInt8))>:Int32 +41
[0x55e09bb5cda6] main +6
[0x7fa6702caee3] __libc_start_main +243
[0x55e09bb516fe] _start +46
[0x0] ???

Again, I hope this can be helpful.

[ysbaddaden]

Please don't add anymore me too messages. The issue is identified and easily reproducible!

All that's missing is someone willing to tackle it; I don't have that time.

[dscottboggs]

I see... I should have read more of the issue. I just thought it was very strange that I was getting the issue only on my _more_ powerful computer, but there must be some unrelated reason why that is happening. Sorry to bother.

[ysbaddaden]

Oh yeah, I missed that, that's weird... does the old machine really has 0.9.0 installed?

[j8r]

A solution could be to change the solver to a more efficient one.
Is there any issue of having the package names with their all available versions stored in a Hash(String, Set(SemanticVersion)), and filtering this versions when reaching a restriction for a package?

[ysbaddaden]

A solution could be to change the solver to a more efficient one.

No. As explained above, a more efficient SAT solver (state of the art) is just as slow (if not slower, in addition to being _incapable_ to track conflicts):

The real issue isn't the solver, but the absurdly high number of CNF clauses created to make sure that two versions of the same library can't be installed at the same time.

The solver must be specialized:

We could specialize the SAT solver to know about this constraint. Maybe add a range/set constraint that would group some variables together, allowing only one variable in the range/set to be selected at a time. That would greatly reduce the number of CNF clauses, and dramatically reduce the number of useless an repeated conflict checks, which should bring back the solver to an acceptable number of clauses (and runtime).

[ysbaddaden]

I started rewriting Solver::SAT to specialize it for version resolution with the 1 dependency == 1 constraint hardcoded. I'll see where it goes.

[straight-shoota]

In the mean time: should 9.0.0 be yanked? It's essentially not usable.

[ysbaddaden]

Why? I never got the issue, despite testing many different shards and lucky apps with a _bunch_ of dependencies. Nobody complained during the very long beta. The issue also has a workaround: add version restrictions to limit how many versions of dependencies are reachable, and it will resolve.

[wontruefree]

9.0.0 does not work for amber projects either. It I have not upgraded to 9.0.0 because it seems to break a lot of projects.

[bararchy]

@ysbaddaden we also downgrade the shards package on all dev machines as it breaks builds and CI.

[straight-shoota]

@ysbaddaden Even if there is a workaround, it's still broken. shards should just work without having to specify versions explicitly. And the workaround is not really effective either because you don't have control over the dependency specification of third party shards.

I don't use 0.9.0 either because of this issue.
The official crystal distribution still ships 0.8.1 as well.

[ysbaddaden]

Shards 0.8 is also completely broken. It's insiduous, because it feels like it's working, but it's not. Reproducible installs are not working, it can't detect/fix the simplest conflicts, thinks there is a conflict when there is none, happily resolves unsolvable solutions, and more (can't upgrade selected dependencies, ...) that 0.9 does.

I wish this had been catched during the very long beta period, but now that 0.9 is released there is no reason to yank it, especially so long after a release. It wouldnt make sense.

[ysbaddaden]

Anyway, too much work. I'll work on this very casually, dont expect a fix until some weeks. If someone feels like digging in, please do.

[straight-shoota]

The solver prior to 0.9.0 has huge problems as well, but it seems in practical application this is not much relevant. But the new parser fails to with many shard configurations, that used to work previously, so this is a more prevalent issue.

I wish this had been catched during the very long beta period, but now that 0.9 is released there is no reason to yank it, especially so long after a release. It wouldnt make sense.

That's true, sadly.

[ysbaddaden]

Crash closed by #302. Bug superseded by #303 (Shards takes hours to resolve dependencies).

[AlexWayfer]

I guess it's related:

name: foo
version: 0.1.0

authors:
  - Alexander Popov

targets:
  foo:
    main: src/foo.cr

crystal: 0.31.1

dependencies:
  twitcr:
    github: greenbigfrog/twitcr

development_dependencies:
  spectator:
    gitlab: arctic-fox/spectator
  ameba:
    github: crystal-ameba/ameba
    version: ~> 0.10.1

> shards outdated
Resolving dependencies
Fetching https://github.com/greenbigfrog/twitcr.git
Fetching https://gitlab.com/arctic-fox/spectator.git
Fetching https://github.com/crystal-ameba/ameba.git
Unhandled exception: Index out of bounds (IndexError)
Failed to raise an exception: END_OF_STACK
[0x55559f986d56] ???
[0x55559f918efb] __crystal_raise +43
[0x55559f919d1b] ???
[0x55559f921e2e] ???
[0x55559f91d389] ???
[0x55559f91c43d] ???
[0x55559f9254e1] ???
[0x55559f92f745] ???
[0x55559f91b6e7] main +55
[0x7fb3d2726153] __libc_start_main +243
[0x55559f9146ee] _start +46
[0x0] ???