[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

Re: heh

From: Branko Èibej <brane_at_xbc.nu>
Date: 2000-11-13 03:06:10 CET

Jim Blandy wrote:
> May I ask a favor? Could you modify the code to count the number of
> collisions, and run that with both hash functions?

Ask, and ye shall be heard. :-)

> I've had weird experiences with benchmarking. I never really feel
> comfortable until I've got a concrete explanation for the improvement.

Good point. What follows isn't really an explanation, but my guess
is that the one in the comment in APR is actually right -- one
function is simply so much faster than the other. When I've a bit
of time, I'll run the two tests through Quantify to make sure.

What's interesting is that the number of collisions doesn't change
significantly. I just committed a fix to vdelta.c that adds some
hash statistics code (ifdef'd out), and here are the results for my
test files with the current and previous versions of the hash
function:

    [brane@lux tests]$ perl stat.pl < stats-1 # h = h * 127 + *k++
    Average load: 51.21
    Average collisions: 59728.10
    Corrected collisions: 1158.74
    [brane@lux tests]$ perl stat.pl < stats-2 # h = h * 97 + *k++ + 41
    Average load: 51.22
    Average collisions: 59716.55
    Corrected collisions: 1157.68

Now if someone will volunteer to add some /real/ analysis code
(average chain length, deviation, etc., etc.), I'd be interested
to see the results. :-)

But for now, I'm convinced -- especially as the results for the two
functions are similar not only on average, but for each window, too.

-- 
Brane �ibej
  home:   <brane_at_xbc.nu>            http://www.xbc.nu/brane/
  work:   <branko.cibej_at_hermes.si>  http://www.hermes-softlab.com/
   ACM:   <brane_at_acm.org>           http://www.acm.org/

Hash stats: load 61, collisions 52132
Hash stats: load 57, collisions 67172
Hash stats: load 55, collisions 65468
Hash stats: load 52, collisions 61541
Hash stats: load 48, collisions 60933
Hash stats: load 47, collisions 62729
Hash stats: load 46, collisions 60246
Hash stats: load 47, collisions 50128
Hash stats: load 51, collisions 58343
Hash stats: load 57, collisions 68903
Hash stats: load 57, collisions 66669
Hash stats: load 53, collisions 66751
Hash stats: load 51, collisions 62062
Hash stats: load 53, collisions 61149
Hash stats: load 51, collisions 61745
Hash stats: load 55, collisions 67951
Hash stats: load 53, collisions 63287
Hash stats: load 51, collisions 58059
Hash stats: load 54, collisions 59351
Hash stats: load 51, collisions 55343
Hash stats: load 43, collisions 58664
Hash stats: load 47, collisions 61143
Hash stats: load 55, collisions 66999
Hash stats: load 55, collisions 68331
Hash stats: load 57, collisions 69986
Hash stats: load 53, collisions 65587
Hash stats: load 47, collisions 55294
Hash stats: load 52, collisions 65280
Hash stats: load 58, collisions 64571
Hash stats: load 57, collisions 66419
Hash stats: load 57, collisions 72154
Hash stats: load 53, collisions 59232
Hash stats: load 54, collisions 63070
Hash stats: load 55, collisions 66030
Hash stats: load 55, collisions 64805
Hash stats: load 52, collisions 63765
Hash stats: load 49, collisions 61291
Hash stats: load 54, collisions 67996
Hash stats: load 54, collisions 66791
Hash stats: load 50, collisions 63236
Hash stats: load 51, collisions 66426
Hash stats: load 53, collisions 67960
Hash stats: load 57, collisions 64745
Hash stats: load 56, collisions 64764
Hash stats: load 55, collisions 63926
Hash stats: load 53, collisions 62053
Hash stats: load 51, collisions 60249
Hash stats: load 56, collisions 63248
Hash stats: load 62, collisions 68487
Hash stats: load 63, collisions 65327
Hash stats: load 62, collisions 68135
Hash stats: load 58, collisions 67169
Hash stats: load 45, collisions 33328
Hash stats: load 29, collisions 15989
Hash stats: load 26, collisions 24378
Hash stats: load 26, collisions 33343
Hash stats: load 30, collisions 35323
Hash stats: load 30, collisions 18774

Hash stats: load 61, collisions 52205
Hash stats: load 57, collisions 67297
Hash stats: load 55, collisions 65447
Hash stats: load 52, collisions 61516
Hash stats: load 48, collisions 61090
Hash stats: load 47, collisions 62489
Hash stats: load 46, collisions 60070
Hash stats: load 47, collisions 49899
Hash stats: load 51, collisions 58263
Hash stats: load 57, collisions 68745
Hash stats: load 57, collisions 66583
Hash stats: load 53, collisions 66958
Hash stats: load 51, collisions 62078
Hash stats: load 53, collisions 61282
Hash stats: load 51, collisions 61792
Hash stats: load 55, collisions 68114
Hash stats: load 53, collisions 63219
Hash stats: load 51, collisions 57967
Hash stats: load 54, collisions 59357
Hash stats: load 51, collisions 55750
Hash stats: load 43, collisions 58732
Hash stats: load 47, collisions 61236
Hash stats: load 55, collisions 67007
Hash stats: load 55, collisions 68334
Hash stats: load 57, collisions 69793
Hash stats: load 53, collisions 65786
Hash stats: load 47, collisions 55476
Hash stats: load 52, collisions 65411
Hash stats: load 58, collisions 64626
Hash stats: load 57, collisions 66377
Hash stats: load 57, collisions 72362
Hash stats: load 53, collisions 59294
Hash stats: load 54, collisions 62826
Hash stats: load 55, collisions 66014
Hash stats: load 55, collisions 64915
Hash stats: load 52, collisions 63880
Hash stats: load 49, collisions 61305
Hash stats: load 54, collisions 68018
Hash stats: load 54, collisions 66626
Hash stats: load 50, collisions 63183
Hash stats: load 51, collisions 66251
Hash stats: load 53, collisions 67935
Hash stats: load 57, collisions 64657
Hash stats: load 56, collisions 64906
Hash stats: load 55, collisions 64030
Hash stats: load 53, collisions 62049
Hash stats: load 51, collisions 60149
Hash stats: load 56, collisions 63113
Hash stats: load 62, collisions 68473
Hash stats: load 64, collisions 65027
Hash stats: load 62, collisions 68075
Hash stats: load 57, collisions 67239
Hash stats: load 45, collisions 33489
Hash stats: load 29, collisions 15790
Hash stats: load 26, collisions 24128
Hash stats: load 26, collisions 33109
Hash stats: load 31, collisions 34971
Hash stats: load 30, collisions 18847

  • application/x-perl attachment: stat.pl
Received on Sat Oct 21 14:36:14 2006

This is an archived mail posted to the Subversion Dev mailing list.

This site is subject to the Apache Privacy Policy and the Apache Public Forum Archive Policy.