Subject: Re: Memory exhaustion issues

From: spacefrogg <[email-masked]>
Date: Mon, 09 Sep 2024 12:49:24 +0200

Hi,

> I see you point, ok. But how can we run targets in parallel? The very 
> first process has redo-ifchange with 10 targets. It runs one of them.

I see no problem there. If redo has job tokens left, it spends them as I 
described earlier. Now, that I think more about it, I think it is a 
rather simple graph traversal problem on the dependency graph.

In a graph like this:
a -> b0 -> c00 -> d000
                -> d001
         -> c01 -> d010
                -> d011
   -> b1 -> c10 -> d100
                -> d101
         -> c11 -> d110
                -> d111

Say, redo is started with 'a' and 2 job tokens. Then it picks 'b0' and 
'b1', blocks on 'b1' first and selects 'c10'. Then it blocks on 'b0'. At 
this point, 'c00', 'c01' and 'c11' are available. I would like redo to 
now prefer tasks that are dependencies of 'b1', because it has already 
started 'c10'. Preferring everything coming from the 'b1' sub tree helps 
reducing the number of blocked processes. So, it starts 'c11'. Then it 
blocks on 'c10' and starts 'd100'.
When it blocks 'c11', it, again, prefers 'd101' over 'd110' or 'd111' 
for the same reason. The path a->b1->c10->d100 is already active and 
finishing 'c10' should be preferred over opening anything that goes via 
'c11' or 'b0' (which is still blocked on its 'c0*' targets).

So, the general rules seem to be as follows.
Each target is annotated with the depth at which is was discovered. 
Start at level 0, which are the explicit arguments to redo. With each 
redo-ifchange the levels of its argument list are updated with the 
current level + 1. For example, in the following  graph:
x -> y0 -> z00
   -> z00
   -> v0
Both 'x' and 'y0' depend on 'z00'. 'y0', 'v0' and 'z00' initially get 
level 1. Later 'z00' updated to level 2. This makes 'z00' more valuable 
than 'v0', because it appears deeper in the hierarchy and should 
preferred. (Because finishing 'z00' potentially closes a long chain of 
blocked processes.)

The second important property is: Each node is ordered by order of 
discovery. You may still randomize the order of arguments to 
redo-ifchange, but this may not change the order of already discovered 
targets. Already known targets are just kept in their place and new 
targets are added to the end. This order is important to break ties if 
two targets have the same level.

Coming back to the previous example with 2 job tokens. The order of 
discovered targets annotated with levels looks like this:
a    :0
b0   :1
b1   :1
c10  :2 # because it blocked on b1 first. So these are discovered first.
c11  :2
c00  :2 # discovered later
c01  :2
d000 :3
d001 :3
d110 :3
d111 :3
...

Deeper levels always win. So, after 'a' discovered 'b0' and 'b1' and 
started both, it discovered 'c10' and 'c11' at level 2. They are the new 
deepest level and 'c10' gets executed. Now, at the time 'b0' blocks and 
adds 'c00' and 'c01' to the list, 'c11' is still available and level 2 
is still the highest priority. So, 'c11' is executed first, because it 
is higher on the list. By ordering targets on the same level this way, 
you are grouping targets that are on the same level and come from the 
same redo-ifchange call together. This ensures that, on the same level, 
you compute the dependencies of one redo-ifchange call, first, 
potentially finishing the task altogether and closing the process early. 
This also ensures that you compute deeper dependencies first, again, 
preferring to finish already opened processes before opening new ones on 
shallower levels.

Again, you can order targets on the same level any way you want as long 
as the order does not change later and targets from the same 
redo-ifchange call are grouped together. This also means that if, say, 
'c10' is discovered again on the same level, it is *not* moved in the 
list to group the targets together.

> Of course all of that will not work, if number of allowed jobs is 
> infinite.

True, if you allow infinite jobs, you are also not caring about memory, 
because you cannot know how much memory each process will take. By allow 
infinitely many processes, you already say that you think you have 
enough memory for all of them.

All of this has been very specific, but I hope you get the idea. I am 
sure you have better implementations in mind that fulfill the same 
rules.

Thanks for reading,
–Michael