While I normally advocate the "cheapest" way of implementing a given
solution (and dx_hack_hash is definitely the lowest-cost hash function
we could reasonably have), I would still be inclined to go with half-MD4
for this. A few reasons for that:
1) CPUs are getting faster all the time
2) it is a well-understood algorithm that has very good behaviour
3) it is much harder to spoof MD4 than dx_hack_hash
4) it is probably better to have the most uniform hash function we can
find than to do lots more block split/coalesce operations, so the
extra cost of half-MD4 may be a benefit overall
It would be interesting to re-run this test to create a few million
entries, but with periodic deletes.
Hmm, now that I think about it, split/coalesce operations are only
important on create and delete, while the hash cost is paid for each
lookup as well. It would be interesting to see the comparison with
a test something like this (sorry, don't have a system which has both
hash functions working right now):
#!/bin/sh
DEV=/dev/hda7
TESTDIR=/mnt/tmp
date
for d in `seq -f "directory_name_%05g" 1 10000` ; do
mkdir $TESTDIR/$d
for f in `seq -f "file_name_%05g" 1 10000` ; do
touch $TESTDIR/$d/$d_$f
done
done
date
umount $TESTDIR
mount -o noatime $DEV $TESTDIR
date
for d in `seq -f "directory_name_%05g" 10000 -1 1` ; do
for f in `seq -f "file_name_%05g" 10000 -1 1` ; do
stat $TESTDIR/$d/$d_$f > /dev/null
done
done
date
Having the longer filenames will put more load on the hash function,
so we will see if we are really paying a big price for the overhead,
and the stat test will remove all of the creation time and disk dirtying
and just leave us with the pure lookup costs hopefully.
Cheers, Andreas
-- Andreas Dilger http://www-mddsp.enel.ucalgary.ca/People/adilger/ http://sourceforge.net/projects/ext2resize/- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/