Re: [PATCH] dentry and inode cache hash algorithm performance changes.

From: Raghavan (raghav_at_in.ibm.com)
Date: 05/20/04

  • Next message: Jens Axboe: "Re: dma ripping" 
    Date:	Thu, 20 May 2004 19:04:10 +0530
To: "Jose R. Santos" <jrsantos@austin.ibm.com>

    Hi Jose,

    Did u try the new hashing algorithm with dcache bench?
    dcachebench is focussed entirely on dcache performance.
    I had measured the performance of the dcachebench on
    2.6.6 kernel with and without the new hashing algorithm
    and noticed significant decrease in performance with the
    new hash algorithm. Enclosed is the mail from LKML that dicusses
    this.

    Also I wrote an instrumentation patch that measures the
    number of clock cycles spent by the hash and lookup.
    The hash time saw an increase(obviously) but I did see an
    increase in the time spent in the lookup function too.
    Attached is the patch I used for the instrumentation.

    Thanks and Regards
    Raghav

    On Sat, May 01, 2004 at 10:08:57AM -0500, Jose R. Santos wrote:
    > * Olaf Dietsche <olaf+list.linux-kernel@olafdietsche.de> [2004-05-01 14:08:26 +0200]:
    > > Judging from the graphs (!), I don't see a real difference for
    > > dcache. There's just one outlier (depth 11) for the old hash function,
    > > which seems to be translated to multiple depth 9 entries. The
    > > histograms seem to confirm, that there's at most a minimal difference,
    > > if they'd be equally scaled.
    > >
    > > Maybe this is due to qstr hashes, which were used by both approaches
    > > as input?
    >
    > SpecSFS is not really the best benchmark to show the efficiency of the
    > dentry hash function. I need to come up with a better defense for the
    > this hash functions. While I did not do the study for this hash
    > function, mathematically speaking this hash algorithm should always
    > create a equal or better hash. SFS just shows equal (well, slightly
    > better), so Ill work on getting some more data to back up the "better"
    > claim.
    >
    > > The inode hash seems to be distributed more evenly with the new hash
    > > function. Although the inode histogram suggests, that most buckets are
    > > in the 0-2 depth range, with the old hash function leading slightly in
    > > the zero depth range.
    >
    > Thats a good thing. With the new hash function, we get 25% more bucket
    > usage and most of the bucket are only 1 object deep. This buckets take
    > up memory so we better use them. The old hash functions was no very
    > efficient in spreading the hashes across all the buckets, with the new
    > hash function we have 4.5 times more buckets with only 1 object deep so
    > it scales better as we increase the number of buckets as well.
    >
    > It also provides a 3% improvement on the overall SFS number with half
    > the number of buckets use which I believe its a great improvement from
    > just a hash algorithm change.
    >
    > -JRS
    > -
    > 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/
    >
    >

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

  • Next message: Jens Axboe: "Re: dma ripping"

    Relevant Pages

    • Re: Hash table in C++? STL?
      ... I wouldn't dare claim to be either, without doing some research first. ... by the number of items that hash to that index. ... perhaps you meant "the size measured in number of buckets" and I was ... second hash function is used to determine the sequence of slots to try. ...
      (comp.lang.cpp)
    • Re: maximum size of a hash table
      ... no matter what the hash function. ... that "the number of buckets must be larger than ... the number of keys" to make collisions rare. ...
      (comp.lang.perl.misc)
    • Re: Suggestion for Fastcode challenge "Hash"
      ... >code under test a few million strings? ... from writing a hand-coded hash function. ... rehashing algorithm for insertion). ...
      (borland.public.delphi.language.basm)
    • hash_set : need the location /index where stored .
      ... okay, In hash tables the key is used by a hash function to calculate ... this creates a hash_set with _at least_ n buckets. ...
      (comp.lang.cpp)
    • Re: A different aproach to archiving files
      ... >>md5 is ten times faster than my hash function. ... I tried using the same algorithm with 32 bit values. ... But isn't computation of multiple smaller hash ...
      (comp.os.linux.development.apps)