1. 39

  2. 6

    gg’s tail recursion lets us write job descriptions that dynamically schedule computation as they discover the work to be done, in a very flexible manner that is completely agnostic to the specific data patterns or languages encoded in the IR.

    Bazel’s compute IR, by contrast lacks this feature or anything comparable This a deliberate decision on their part in order to make bazel builds more analyzable

    Wow very interesting! This is definitely an issue I’ve experienced with Bazel, or really 2 issues. First, it makes you rewrite your whole build system in its BUILD description language, i.e. you throw out the Makefile/autoconf/cmake. Second, that language is extremely static, i.e. it’s a big monolithic static build graph. (And I worked on Bazel itself very briefly in ~2006)

    Discovering work dynamically brings to mind the Shake build system, although I’ve never used it:


    I would be interested to hear how it compares.

    Also brings to mind “redo”. I think a couple years ago I told apenwarr I didn’t like the fact that redo does not have a static dependency graph because it makes things hard to parallelize. The point of specifying dependencies is to make things incremental, parallel and correct. If I don’t get all those benefits, I’d just write a shell script without dependencies.


    However maybe gg is providing a way to have the best of both worlds… I will definitely take a look.

    Peeking at the source code, it looks like it uses syscall tracing:

       460 src/thunk/thunk.cc
       476 src/models/gcc-args.cc
       515 src/util/path.cc
       939 src/models/gcc.cc
      3587 src/trace/linux/x86_64/syscalltbl.cc
     17762 total

    Recent paper on this: https://arxiv.org/abs/2007.12737

    I remember the fabricate build tool (citation) from ~10 years ago but I don’t think it was ever parallel: https://github.com/brushtechnology/fabricate

    Also, I’ve been thinking about using shell as the “coordination language” for distributed systems (e.g. allowing you to specify graphs via declarative configuration, with metaprogramming much like Bazel does it). The use of tail recursion here is interesting and I’m not sure if shell will fit that model …

    1. 1

      Why would a dynamic dependency graph make it harder to parallelize? Just because your don’t see all dependencies at the start does not limit you.

      An argument against static: It requires you to specify potentially too many dependencies. In a dynamic system you could dynamically leave out the ones you don’t need in this run. This means a static system might have to work more than necessary.

      1. 2

        Well how do you distribute the tasks if you don’t know dependencies? You have to run code on the client machine to figure out dependencies before distributing them, which limits parallelism. The preprocessor section in the blog post talks about that.

        The static graph definitely has the downside you mention. On the other hand, you have “perfect” information up front and can make optimal scheduling decisions. The way Bazel works is that it knows / computes the entire static build graph before starting the first build task (or at least it worked that way for 10+ years; I think it still does.)

        And this is good for C++, because compiling C++ translation units is expensive, and you can schedule it well for performance wins. But it’s bad for say Go because the Go compiler itself can sometimes compile faster than you can compute static dependencies.

    2. 4

      Hm I just noticed that the gg paper shares 2 authors with this 2020 paper POSH: A Data-Aware Shell

      POSH optimizes shell scripts by bringing code to data, sort of in the style MapReduce. It is for what I’d call big data / small computation (that is, I/O intensive workloads). So it is actually complementary to gg, which is small data / big computation (CPU intensive).

      Although POSH doesn’t share a runtime with gg, which I was sort of surprised by. The gg IR looks very shell-like, so I thought it would be natural to extend that to pipelines somehow.

      Coincidentally I learned about POSH from another shell optimization project which I just learned about, Pash! (also 2020)

      PaSh: Light-touch Data-Parallel Shell Processing

      Notes on these projects here: https://github.com/oilshell/oil/issues/867

      And I read the gg paper more carefully and put some notes here: https://github.com/oilshell/oil/wiki/Distributed-Shell

      There is a great video about it on YouTube, a Hacker News thread with some interesting experiences with lambda for astronomy, and more etc.

      I really like the framing of this work: low latency, cold vs. warm clusters, etc. They don’t mention the shell connection that much, but I think there is an obvious relation, and the tool itself is very shell oriented (the gg infer wrapper, etc.). It also makes me a lot more interested in Lambda, which has apparently supported arbitrary containers since late 2018.

      1. 2

        Sounds related to Joyent Manta (or whatever it’s called these days).

        1. 3

          Oh yeah thanks for mentioning that! I remember going to talk at Joyent in SF about Manta when it launched (2011 or 2013?) It’s a good idea: Unix-style polyglot MapReduce. (Hadoop has something similar but not widely used.)

          In fact I’m pretty sure I remember Bryan Cantrill saying in another talk that part of the reason Samsung acquired Joyent is because they had a huge Manta bill? Like it was cheaper to acquire the whole company LOL… (I think Samsung was allergic to Google Cloud for competitive reasons, and apparently AWS too ?)

          I don’t have a reference, but all the press releases mention Manta:


          FWIW they used Solaris Zones, and this was before there were any standard container formats. So I don’t think they had anything like what AWS Lambda or Kubernetes has with Docker containers.

          1. 1

            FWIW they used Solaris Zones, and this was before there were any standard container formats. So I don’t think they had anything like what AWS Lambda or Kubernetes has with Docker containers.

            No, but for some use cases what they had was even better imo, and something I haven’t seen replicated elsewhere. They used some fancy ZFS overlay stuff to give every zone built-in access to thousands of pkgsrc packages from a given pkgsrc quarterly revision, as if they had been installed in the zone. They didn’t count as part of your zone size and didn’t slow down zone startup, so were basically a “free” 10gb or so of dependencies you didn’t have to drag around yourself as part of a container.

            Especially for data analysis work and one-off jobs this was nice. You could write a script assuming that basically anything reasonable was already installed in the zone: compilers and interpreters for almost any language, the whole Python data-science stack, R, CLI utilities like jq and xmlstarlet, etc., etc. You could also then specify additional pkgsrc packages to install at startup, or .tar.gz’s to copy into the zone, but you only had to do that for more unusual or non-open-source stuff.

            1. 1

              Yeah I don’t doubt that it was better in many ways, especially if you compare it to Docker at that time [1]. Although when I went to that particular talk, close to launch time, they didn’t have a good solution yet. I think they just had a fixed Zone that resembled the host Zone. It was a canned set of packages.

              Actually I just tried NearlyFreeSpeech, which uses FreeBSD jails, and it’s kind of similar. They have something called “realms” which is a big blob of software they update once in awhile.


              I think this probably works for a lot of use cases, but it’s less flexible than what’s becoming the standard with Linux, e.g. with Lambda and Kubernetes (the latter of which feels just as clunky as Docker).

              Having fast startup is definitely a problem with these types of systems, and I think their solution addresses that. However I think there is still the “local dev environment problem”.

              If they have Python 3.4, and you want Python 3.8,. you might be out of luck, or you might be in for a lot of work.

              This is problem extends up the stack, especially with the scientific software stack, e.g. NumPy/SciPy/Pandas and R. They move faster than distros move. Packaging them is a huge pain. The upstream devs really only work on Linux or Windows.

              The HN thread on gg has a good example of that with respect to astronomy, and I’ve experienced similar problems for a long time: https://news.ycombinator.com/item?id=20433315

              So Lambda is still a pain, but I’m virtually certain the pain would be just as bad or worse on Manta, even now..

              BTW I took another look at Manta: https://apidocs.joyent.com/manta/job-patterns.html

              e.g. for https://github.com/oilshell/oil/issues/867

              My reaction is that I think they need structured data over pipes. I love the shell, but I’ve also done a lot of MapReduce stuff, and having records is sort of a “must have”. Still working on it in Oil: https://github.com/oilshell/oil/wiki/Structured-Data-in-Oil

              [1] I’m glad Docker is getting refactored into something more stable / refactored away

      2. 3

        “Researchware”: not the word we deserve, but the word we need.