unofficial mirror of guix-devel@gnu.org 
 help / color / mirror / code / Atom feed
From: ilmu <ilmu@rishi.is>
To: Julien Lepiller <julien@lepiller.eu>
Cc: "guix-devel@gnu.org" <guix-devel@gnu.org>
Subject: Re: Deep vs Shallow trace: Removing the tradeoff?
Date: Sun, 28 Mar 2021 23:16:23 +0000	[thread overview]
Message-ID: <XuR-Ovr-FmTCISJzQZIxOdkzop1DWhD4bHddDL0DlelKnzKWuavLL-Rxl0_-Iq0Q0deg3nXiAkbovMchjneo6YSMH5pUzKQVcFYpkcV-emI=@rishi.is> (raw)
In-Reply-To: <01A29E7C-0E60-4518-A775-92B6F6A8B816@lepiller.eu>


[-- Attachment #1.1: Type: text/plain, Size: 3800 bytes --]

First of all, thanks for engaging with me, sorry for not putting more work into the initial email. Note that I have attached inline images from the paper, the paper is also attached to this email.

> What I understand from the above is that there is not so much of a difference between Bazel and Nix/Guix. The "shallow" tracing is a deep tracing. It just records something different.

[classification.png]

The framework they present is that a build system can be classified based on how it decides whether a rebuild is necessary and how it schedules the necessary rebuilds (i.e. how it sorts the work to be done). They consider these orthogonal strategies a complete description of "what a build system is".

[constructive_traces.png]

The constructive trace allows you to keep intermediate artifacts but creates the extra overhead of managing these.

[deep_constructive_traces.png]

Since a deep constructive trace only looks at the terminal dependencies you have something of a merkle-dag. What I was suggesting is to be able to do "shallow builds" while still supporting "early cutoff". For reference:

[early_cutoff.png]

Early cutoff is a very desirable property that nix does not have (and I assume therefore that neither does guix).

[shallow_builds.png]

Basically, if we have a proof that the immediate dependencies are complete then we don't need to fetch anything deeper in the dependency tree.

> In Nix/Guix, we recursively compute the hash of packages from their inputs, receipe and other stuff. This hash is unrelated to the checksum of the result and changes as soon as one element changes. It essentially records the whole source dependency graph.
> From what you write, Bazel records the checksum of inputs and receipe, so it essentially encodes the whole binary dependency graph. It's not "shallow", as a real change down the graph can have repercussions higher up.
> Actually Eelco described something similar for Nix in his thesis, the intensionnal model. As you noticed, different receipes or inputs can lead to the same output (bitwise). The idea is to declare the expected checksum of the result, and use this to compute the store item name. As long as you apply changes that do not affect the output, different receipes (updates) can be used to generate the same item. So if you update a package, it might affect its output checksum, so you need to change it. Dependents might not be affected, in which case you can block update propagation there.
> The question being how to monitor that packages need to be rebuilt or have the same hash?

I think the pictures above should clarify, I should have looked at the paper again before sending my previous email, I read it quite a long time ago.. The property I was trying to recover in the nix-style build systems is this idea of an early cutoff. The strategy for achieving that is to use constructive traces with depth 1 (what I was calling "shallow traces") and then recursive succinct arguments of knowledge for retaining the shallow build property that you get from the "infinitely deep traces".

> I don't really understand why it must be zero-knowledge. My understanding is that to have a zero-knowledge proof, you first need a proof of the claim, then find a clever way to proove you have the proof, without disclosing it. Not sure it's helpful here. If you have a proof that you don't need to rebuild, why not share that proof to everyone in the first place?

Sure, you only need the succinctness property. I should have been more precise, what I am mainly after is resolving the tradeoff between shallow and deep traces.

I hope that this discussion can at least be helpful for people that are not familiar with these ideas, even if - as it seems from your response - the idea does not have merit.

Kind regards,
- ilmu

[-- Attachment #1.2.1: Type: text/html, Size: 4676 bytes --]

[-- Attachment #1.2.2: classification.png --]
[-- Type: image/png, Size: 22228 bytes --]

[-- Attachment #1.2.3: constructive_traces.png --]
[-- Type: image/png, Size: 72834 bytes --]

[-- Attachment #1.2.4: deep_constructive_traces.png --]
[-- Type: image/png, Size: 82885 bytes --]

[-- Attachment #1.2.5: early_cutoff.png --]
[-- Type: image/png, Size: 22288 bytes --]

[-- Attachment #1.2.6: shallow_builds.png --]
[-- Type: image/png, Size: 70537 bytes --]

[-- Attachment #2: build-systems.pdf --]
[-- Type: application/pdf, Size: 728559 bytes --]

  reply	other threads:[~2021-03-29  5:43 UTC|newest]

Thread overview: 8+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-03-27 16:56 Deep vs Shallow trace: Removing the tradeoff? ilmu
2021-03-28  0:50 ` Julien Lepiller
2021-03-28 23:16   ` ilmu [this message]
2021-03-30 10:46     ` Ludovic Courtès
2021-03-30 20:20     ` Bengt Richter
2021-04-02 15:45       ` ilmu
2021-04-17 15:05         ` Ludovic Courtès
2021-04-18  5:51           ` ilmu

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

  List information: https://guix.gnu.org/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='XuR-Ovr-FmTCISJzQZIxOdkzop1DWhD4bHddDL0DlelKnzKWuavLL-Rxl0_-Iq0Q0deg3nXiAkbovMchjneo6YSMH5pUzKQVcFYpkcV-emI=@rishi.is' \
    --to=ilmu@rishi.is \
    --cc=guix-devel@gnu.org \
    --cc=julien@lepiller.eu \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/guix.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).