bug#24937: "deleting unused links" GC phase is too slow

[Mark H Weaver <mhw@netris.org>]

ludo@gnu.org (Ludovic Courtès) writes:

> Mark H Weaver <mhw@netris.org> skribis:
>
>> I think we should sort the entire directory using merge sort backed to
>> disk files.  If we load chunks of the directory, sort them and process
>> them individually, I expect that this will increase the amount of I/O
>> required by a non-trivial factor.  In each pass, we would load blocks of
>> inodes from disk, almost all of which are likely to be present in the
>> store and thus linked from the directory, but in this scheme we will
>> process only a small number of them and drop the rest on the floor to be
>> read again in the next pass.  Given that even my fairly optimal
>> implementation takes about 35 minutes to run on Hydra, I'd prefer to
>> avoid multiplying that by a non-trivial factor.
>
> Sure, though it’s not obvious to me how much of a difference it makes;
> my guess is that processing in large chunks is already a win, but we’d
> have to measure.

I agree, it would surely be a win.  Given that it currently takes on the
order of a day to run this phase on Hydra, if your proposed method takes
2 hours, that would be a huge win, but still not good, IMO.  Even 35
minutes is slower than I'd like.

>> Why not just use GNU sort?  It already exists, and does exactly what we
>> need.
>
> Does ‘sort’ manage to avoid reading whole files in memory?

Yes, it does.  I monitored the 'sort' process when I first ran my
optimized pipeline.  It created about 10 files in /tmp, approximately 70
megabytes each as I recall, and then read them all concurrently while
writing the sorted output.

My guess is that it reads a manageable chunk of the input, sorts it in
memory, and writes it to a temporary file.  I guess it repeats this
process, writing multiple temporary files, until the entire input is
consumed, and then reads all of those temporary files, merging them
together into the output stream.

>> If you object to using an external program for some reason, I would
>> prefer to re-implement a similar algorithm in the daemon.
>
> Yeah, I’d rather avoid serializing the list of file names/inode number
> pairs just to invoke ‘sort’ on that.

Sure, I agree that it would be better to avoid that, but IMO not at the
cost of using O(N) memory instead of O(1) memory, nor at the cost of
multiplying the amount of disk I/O by a non-trivial factor.

> Also, what algorithm are you referring to?

The algorithm I described above, which I guess is close to what GNU sort
does.

    Thanks,
      Mark