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

[Jim Meyering]

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
    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?