public inbox for goredo-devel@lists.stargrave.org
Atom feed
From: goredo <spacefrogg-goredo@spacefrogg•net>
To: goredo-devel@lists.cypherpunks.su
Subject: Re: Memory exhaustion issues
Date: Thu, 5 Sep 2024 21:49:27 +0200 (GMT+02:00)	[thread overview]
Message-ID: <1e69002a-0717-4a1b-a38f-b38d43de9a63@spacefrogg.net> (raw)
In-Reply-To: <Ztn9X4IQL4Mds-GL@stargrave.org>

Hi,

My apologies, this has gotten a long message.

I see that I was not precise enough in my suggestion. I will try to sketch the issue and maybe we find a better resolve than the current implementation. Given, we run redo with a single job, just for the argument.

We start building a target that depends directly on 10 targets, each of them also depends on 10 more targets, none of the targets repeat. This leaves us with a dependency tree of depth 3 and 111 targets total. Let us name the target on the first level target 1, on the next level targets 10-19 and the third level 100-199. Now, because we are building with one job, we enter target 1, hit redo-ifchange 10 11 12 ... 19, and block until the call returns. Right now we have three open processes, redo, target 1 and redo-ifchange.

Right now redo is free to run anyone of targets 10-19. Let's say it picks target 10. Starts executing until it hits redo-ifchange 100 ... 109. Blocks again. Now, redo can pick any target from 11-19 and 100-109. We have two more processes open.

Now, it is important at this point that we both can agree that any of the 19 targets can be selected. If you don't agree, chime in here.

Let's continue and say that redo selects target 11, runs until redo-ifchange 110-119, picks target 12, ..., until it picks target 19 which blocks on targets 190-199. Each new 2-digit target opens two more processes that must stay open until enough of the 3-digit targets are finished. We have 23 processes open and blocked.

Let's stop here and jump back to an alternative version. Red can pick from targets 11-19 and 100-109 again and selects target 100, executes it, returns and picks 101 and so on until 109 is finished. It must pick one of 11-19 now, takes 11. Now, we can repeat this argument for each of the two-digit targets. In all these runs, we had no more than six processes running, redo, target 1, redo-ifchange, one 2-digit target, redo-ifchange and one 3-digit target.

In my first example, redo executed known and ready targets breadth first. The targets coming from the top-most redo-ifchange call (2-digit targets) were picked first. In my second example, redo executed targets depth-first. Of all known and ready targets, it prefered those of the most recent or the deepest redo-ifchange call.

I hope I could show that I was not cheating and that the depth-first order was, in fact, saving on the number of processes.

Why is that important to me? I have a project which needs to build 170k targets, distributed over a graph that is 13 layers deep. I observed that redo opens hundreds of targets from higher layers that all block on redo-ifchange.

I hope I could get my point across. I am hopeful that redo could implement some sort of priority queue that favours targets of the last redo-ifchange call over more remote ones.

Thanks for reading. :)

–Michael

  reply	other threads:[~2024-09-05 19:49 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2024-08-19 10:12 Memory exhaustion issues spacefrogg
2024-09-05 18:49 ` Sergey Matveev
2024-09-05 19:49   ` goredo [this message]
2024-09-08 10:11     ` Sergey Matveev
2024-09-09 10:49       ` spacefrogg
2024-09-10  6:50         ` Sergey Matveev