Re: [PATCH 1/2] perf: compare diff algorithms

From: René Scharfe <rene.scharfe@lsrfire.ath.cx>
Date: Mar 10, 2012, 07:13 UTC
Message-ID: <4F5AFF33.7090900@lsrfire.ath.cx>
In-Reply-To: <f113867bcf2fec3210cd1a997e1398903b3bdd76.1331039505.git.trast@student.ethz.ch>

Am 06.03.2012 14:15, schrieb Thomas Rast:

Show 22 quoted lines

> 8c912ee (teach --histogram to diff, 2011-07-12) claimed histogram diff
> was faster than both Myers and patience.
>
> We have since incorporated a performance testing framework, so add a
> test that compares the various diff tasks performed in a real 'log -p'
> workload.  This does indeed show that histogram diff slightly beats
> Myers, while patience is much slower than the others.
>
> Signed-off-by: Thomas Rast<trast@student.ethz.ch>
> ---
>
> The 3000 is pretty arbitrary but makes for a nice test duration.
>
> I'm reluctant to put numbers into the message, since the whole point
> of the perf test framework is that you can easily get them too.  But
> here's what I'm seeing:
>
>    4000.1: log -3000 (baseline)          0.04(0.02+0.01)
>    4000.2: log --raw -3000 (tree-only)   0.49(0.38+0.09)
>    4000.3: log -p -3000 (Myers)          1.93(1.75+0.17)
>    4000.4: log -p -3000 --histogram      1.90(1.74+0.15)
>    4000.5: log -p -3000 --patience       2.25(2.07+0.16)

Just a data point: --histogram is slightly slower for me:

    Test                                  this tree
    -----------------------------------------------------
    4000.1: log -3000 (baseline)          0.07(0.07+0.00)
    4000.2: log --raw -3000 (tree-only)   0.35(0.31+0.04)
    4000.3: log -p -3000 (Myers)          1.50(1.40+0.08)
    4000.4: log -p -3000 --histogram      1.54(1.48+0.05)
    4000.5: log -p -3000 --patience       1.79(1.71+0.06)

(baseline with -3000)

René