GNU make job server-alike for GHC --make

added Tfeature request needs triage labels

changed title from Parallel --make with cabal-install/stack to GNU make job server-alike for GHC --make

changed the description

added compiler perf label and removed needs triage label

A problem when building large amounts of dependencies with stack or cabal is that we don't get to exploit any package level parallelism due to cabal using --make mode without any -j flags.

Presumably you rather meant "module level parallelism" instead of "package-level parallelism"?

I did! Much clearer, thanks.

changed the description

This is a reasonable suggestion although it's a bit unclear how exactly this would work. Afterall, make has the advantage of being the root of the process tree and can therefore pass the jobserver location to the children. However, we don't have this luxury; relaying this information would require support from the build system (e.g. Cabal). It's of course possible, but it requires a bit more effort.

I think GHC would have to become a good jobserver child so Cabal/Stack/Shake can be the jobserver server.

I've been thinking about this too. Now that parallel gc has been improved, I expect the payoff here to be high. There is a related Cabal issue here: https://github.com/haskell/cabal/issues/976

Jobserver support is not the only solution here. I had been contemplating an interface like:

ghc ... -j10 --jsem /tmp/ghc.sem

Here ghc would open or create a named semaphore /tmp/ghc.sem. If it creates, it would initialise it to 10, if it doesn't create it would limit it's parallelism to 10 threads. It would then use this named semaphore instead of the QSem in par_upsweep.

This approach could be used without cabal support with cabal build --ghc-options='-j -jsem /temp/ghc.sem'. I'm not necessarily advocating for the semaphore approach, just showing it.

A subtlety here is that we would like a ghc's garbage collections to use the number of threads that that ghc has claimed from the jobserver or semaphore. One way to achieve this would be to alter how ghc calls setNumCapabilities. Currently this is called at the start of the upsweep. Instead we could could increment capabilities when we claim a thread and decrement capabilities when we return a thread.

The GNU make jobserver seems to work pretty much like this. The top level make invocation has a semaphore and sub-makes will claim capabilities from it.

Morally yes. (though technically it doesn't use a semaphore on linux). The only downside I see of using jobserver is incurring the runtime dependency.

What is the runtime dependency?

The make jobserver?

It seems to me that make doesn't actually have an actual server component. I was imagining something much like you're describing for GHC --make where cabal-install/stack manages the semaphore.

Ah I see!

With your idea @duog it seems that you still would leave some potential parallelism on the table because the build tool would still have to wait to trigger the build for a certain package until it was sure the dependencies were built? Thinking about it, this is already the case with all existing build tools so it might not be too much of a problem.

I suppose for the best results you want a system which requires the .hi file has been produced for all dependent modules but doesn't wait until the .conf file has been finished. Perhaps a good place to experiment with this would be hadrian..

I do like @duog's suggestion of using POSIX semaphores. It's a bit of a trade-off:

Pro: It's easy to implement, requiring very little support on the part of the build tool
Pro: It is a language agnostic interface and could in principle be used to mediate CPU resource access with other tools (although admittedly I don't know of any other build tools that do this, perplexingly)
Con: This is platform dependent; on Windows you would need to instead use a semaphore object.

I suppose for the best results you want a system which requires the .hi file has been produced for all dependent modules but doesn't wait until the .conf file has been finished. Perhaps a good place to experiment with this would be hadrian..

This is similar to the idea explored in #17843 and #13152.

Another idea would be to consolidate all building to a build server, eliminating the need to repeatedly re-read and typecheck interface files. That being said, at the moment this likely won't be terribly helpful given that most build systems use Cabal, which uses GHC's --make mode. One could potentially see a benefit across packages, although this will require changes in GHC to support builds across multiple packages within a single session.

(although admittedly I don't know of any other build tools that do this, perplexingly) The GNU Make jobserver does this. (see issue description)

I've opened https://github.com/haskell/unix/issues/179 in relation to this. I don't see any haskell bindings for the CreateSemaphore Win32 function.

Parallelism across packages is a much harder problem than this. There seem to be two approaches:

invoke GHC many times, with the build tool ensuring that a modules dependencies are built before it's started
invoke ghc once and have it do all packages in one go

I have a strong bias against the former. Remember the common (and IMO most important) case for GHC is compiling a single package, during development. I don't believe multiple invocations of ghc -c can compete with ghc --make in this case. So my preference is to focus on improving --make

The latter is very complicated. Before Cabal knows how to invoke ghc to build a package it must configure it, so it would have to be able to configure it before it's dependencies are built. Seems impractical if it's not a built-type: Simple project. Modifying ghc to build multiple packages is in progress I think(can't find issue).

One can imagine a ghc, when being invoked in --make mode, to delegate it's work to a server process. Then Cabal would "just" need to be taught to call ghc --make as soon as it knows the arguments.

One can imagine a ghc, when being invoked in --make mode, to delegate it's work to a server process. Then Cabal would "just" need to be taught to call ghc --make as soon as it knows the arguments.

Yes, this is what I was hinting at in my previous comment. I think this would be relatively easy to implement and open a number of interesting doors for improving parallelism.

I don't believe multiple invocations of ghc -c can compete with ghc --make in this case.

Compete on what metric? Speed?

As number of modules increases GHC retains a lot more memory in --make mode which causes longer major collections. My personal impression is that -c definitely uses less memory and was potentially faster than --make mode. (Without any evidence)

On Total cpu time. Let me clarify what I mean. There are still relatively low hanging fruit for --make mode. In particular, #12896, #14095 are ones I know about. I am biased towards improving --make because I believe (without clear evidence) that once this fruit is picked that --make will be faster.

I’ve been wondering how close ghcide is to being the more granular dependencies approach described in #14095.

It is quite close. If you could know the options which each component needed to be compiled with before compiling anything, then it would already work. The issue I think is that in order to work out the options for package P which depends on Q, you first need to build and install P before cabal can give you the right options.

mentioned in merge request !5176 (closed)

I was tipped off that Cargo in fact implements the exact GNU Make protocol, not something merely inspired by it: https://github.com/rust-lang/cargo/pull/4110

Perhaps there is an emerging standard after all, and GHC (and cabal-install) should do the same.

Per what @expipiplus1 wrote in !5176 (comment 391413), Nixpkgs is also pursuing this.

mentioned in issue #20685

mentioned in commit expipiplus1/ghc@007e94f9

mentioned in merge request !7000

mentioned in commit expipiplus1/ghc@f388bed9

mentioned in commit expipiplus1/ghc@9065c49a

mentioned in commit expipiplus1/ghc@6b1a04d3

mentioned in commit expipiplus1/ghc@3deff3c5

After looking at the details of the make jobserver protocol a bit, I'll admit that I'm a bit perplexed by it. While it is apparently ubiquitous, it seems to be a remarkably complex and fragile solution to a problem that is very easily solved by standard POSIX semaphores. Specifically, there are a number of tricky corner cases that an implementor must handle correctly:

the server needs to ensure that it keeps track of how many slots each client takes and must watch the write fd of each to have any hope of catching a client which crashes without releasing its allocation
clients must be careful to keep track of which character corresponds to each slot they hold; this also introduces the potential limitation of any given client being able to hold at most 2^8 slots.
spawn a subprocess with access to a jobserver is surprisingly tricky to do robustly. Specifically, the server must pipe() to create the pipe, fork() the client, set CLOSEXEC on the fds for the server's side of the pipe, and finally exec() the client. As far as I can tell, it's not even possible to implement this using posix_spawn, which complicates matters on, e.g., Darwin where fork'ing is frowned upon
various quirks in make's implementation further complicate usage
there are a number of conventions for passing the jobserver fds now in user (MAKEFLAGS=--jobserver-fds=..., MAKEFLAGS=--jobserver-auth=..., CARGO_MAKEFLAGS=...)

The Nixpkgs implementation of the jobserver protocol uses FUSE to avoid some of these issues. However, I'm not convinced that this is a viable option for something like GHC and cabal-install.

Frankly, I do wonder whether the make jobserver protocol is really the right direction here. For all of their flaws, POSIX semaphores do seem like a much simpler solution here.

I agree the jobserver protocol is complex and fragile. The semaphore solution also seems fragile, as pennae says below.

I had thought jobserver used pipes for portability reasons, but I'm not so convinced now. Indeed it uses a windows semaphore primitive on windows.

Perhaps the right approach is to use semaphores in GHC and another binary, in or out of tree, to translate between GHC and jobserver?

translation isn't really feasible. the translating process would have to continuously poll the semaphore for missing/unused tokens and acquire/return tokens as necessary, which would come at a performance cost and introduce dead times in high churn situations. that's one of the reasons we went for fuse; shuffling tokens between disconnected pools based on their fill state is a dirty workaround for protocols that don't have interop in mind (and make is definitely in that category!).

I had thought jobserver used pipes for portability reasons, but I'm not so convinced now. Indeed it uses a windows semaphore primitive on windows.

Make has been around for quite a while so I suspect that it was indeed for portability reasons. Afterall, prior to POSIX semaphores being standardized there were System V semaphores, which brought their own bucket of issues (although I don't recall specifically what those were)

Perhaps the right approach is to use semaphores in GHC and another binary, in or out of tree, to translate between GHC and jobserver?

Indeed I was going to suggest the exact same thing but, yes, I suppose you are right @pennae. Sad.

hi, pennae here (who wrote the jobserver implementation @Ericson2314 mentioned).

the make jobservers protocol is simple on the surface mostly because it forgoes consistency checking (if a client doesn't return a token, that token is lost) and uses a single kernel object for all its functions (effectively turning the pipe into a semaphore without automatic release on process exit). it indeed isn't the best solution by a long shot, the fact that we had to go for FUSE to make it work at all is a good proof of that.

we don't actually care much which protocol anything uses, as long as there's a good way to support it in the jobserver we proposed for nixos. posix semaphores could work, but their accounting is entirely done in userspace. we're very reluctant about using those as a backend, seeing how a misbehaving client could wreck the token pool by exiting without returning its tokens (or even returning more than it got in the first place), just like in the make pipe case.

we could implement a more complicated request/response protocol on unix sockets for acquiring/releasing tokens, but at that point there's not much to be gained over what make already does :(

we could implement a more complicated request/response protocol on unix sockets for acquiring/releasing tokens, but at that point there's not much to be gained over what make already does :(

I'm actually not sure that is true. Specifically the interface could simply be to set an environment variable with the name of a UNIX socket. There would need to be only one socket, not one for client. Subprocesses would automatically be able to use the jobserver of their parent by virtue of the environment variable being propagated. Automatic release is possible (albeit slightly racily) by the server using SO_PEERCRED to determine the pid of the client (although admittedly I'm not sure how portable this is).

on second thought it could be even simpler: one successful connect() equals one token, one close() equals one token returned. no further accounting needed at all, and it still has the handshake property we had to resort to fuse for in the case of the make protocol. the only problem with both schemes is that the token has to be acquired before the child it is intended for is started, but the socket holding the token can be passed by posix_spawn. (pretty sure the make protocol is compatible with posix_spawn too, but haven't looked into it too deeply. should be, since every child always gets both ends of the pipe)

changed the description

Having discussed this with @bgamari @mpickering we've decided to proceed in implementing our own protocol, based on that in !5176 (closed), using posix semaphores.

We expect cabal-install (and stack if there is interest) to be the the only clients of the protocol in the near term. If and when nix or other build systems grow jobserver support we can revisit this.

Having discussed this with @bgamari @mpickering we've decided to proceed in implementing our own protocol, based on that in !5176 (closed), using posix semaphores.

Will there be a windows implementation as well?

Surely we must make every effort to provide a windows implementation. I don't think this will present a problem: https://docs.microsoft.com/en-us/windows/win32/api/winbase/nf-winbase-createsemaphoreexa

Seems very close to a posix semaphore.

I might need help with it though.

mentioned in commit 58b3500d

mentioned in commit 00289a68

mentioned in commit 67ac2af6

mentioned in commit aa906d22

mentioned in commit 2236d230

mentioned in commit 9d8f44a9

mentioned in commit a3d8ccd7

mentioned in commit 316f5328

https://github.com/ghc-proposals/ghc-proposals/pull/540

"This proposes a mechanism for dynamically scheduling parallelism across multiple GHC invocations through use of a system semaphore."

Pending shepherd recommendation

Can this ticket be closed now that !8970 (closed) has landed?

closed

added ghc proposal label

GNU make job server-alike for GHC --make

Motivation

Proposal

Notes

Child items ...

Activity