Re: [PATCH] Use a heap for the internal merge.

[Jim Meyering]

Jim Meyering wrote:

> Paul Eggert wrote:
>> With random data and a 64-way merge this sped up 'sort' by 5% on our tests.
>
> With my relatively small tests, (total input size is 76MiB,
> very short lines) this patch makes sort about 10% slower:
> (on an Intel(R) Core(TM)2 Quad CPU Q9450 @ 2.66GHz, w/6MB cache per core):
>
>     N=10000000
>     m=64
>     rm -rf in--*
>     shuf -i 0-$N > in
>     split -C $(echo $N / $m|bc) in in--
>     for i in in--*; do sort -o $i $i; done
>
>     before patch
>     $ for i in $(seq); env time --format=%e src/sort -m --batch-size=64 in--* 
> \
>         > /dev/null; done

Oops.  I inserted that before it actually worked.
10 trials:

  for i in $(seq 10); env time --format=%e src/sort -m --batch-size=64 in--* \
    > /dev/null; done

>     5.12
>     5.12
>     5.18
>     5.14
>     5.10
>     5.13
>     5.12
>     5.11
>     5.12
>     5.13
>
>     after patch
>     5.83
>     5.78
>     5.77
>     5.76
>     5.77
>     5.75
>     5.78
>     5.78
>     5.77
>     5.81
>     E.g., with more detail:
>     env time src/sort -m --batch-size=64 in--* > /dev/null
>     5.57user 0.18system 0:05.75elapsed 99%CPU (0avgtext+0avgdata 
> 0maxresident)k
>     0inputs+0outputs (0major+4572minor)pagefaults 0swaps
>
> What did your input look like?