bug#8824: sort occasionally hangs - appears to be in a merge-sort loop

[Paul Eggert]

On 06/08/11 13:16, Mina Naguib wrote:

> I may be mistaken, but I don't think this is normal behaviour - once
> the 16-way merge sort is done, I see no reason to observe this whole
> process happening over and over.

Thanks for your bug report.  If 'sort' is breaking up its input into 4
MiB chunks, sorting them, creating a separate temp file for each
chunk, and then merging the results with a 16-way merge, then the
first level of 16-way merges will produce 64 MiB files, and the second
level will produce 1 GiB temp files, which is about the size you're
observing.  Since your input is about 18 GiB in size (is that right?),
I'd expect to see two third-level merges.  The first would be a 16-way
merge, generating about 16 GiB total.  The second would be a roughly
2-way merge, generating about 2 GiB.  Then there would be a single
fourth-level merge of these two big files into the final 18 GiB of
output.

But you're observing a second third-level merge that's the same
size as the first.  So something is wrong here.

I just now tried to reproduce your bug on my host (Fedora 14 x86-64
with 8 GiB RAM) as follows:

shuf -i 1-350000000 -o col1
shuf -i 1-350000000 -o col2
paste col1 col2 |
  awk '{printf "%s|direct_count|2049|63581|15090|%s\n", $1, $2}' |
  sort -t '|' -k1,1 -k6,6n |
  cat >sortout

Alas, this didn't reproduce the problem; it worked just fine.

Can you modify the above recipe somehow and make the problem
happen on your host?

How much RAM do you have?  Is your host x86 or x86-64 or what?
(That "4 MiB" in my example is an absurdly small number, and
this is a performance bug in 'sort', but that's a different
matter I think.)