[quagga-dev 10277] Re: [PATCH 2/4] hash: force size to be a power of 2

David Lamparter equinox at opensourcerouting.org
Sun Feb 24 19:48:42 GMT 2013


On Wed, Jan 16, 2013 at 09:59:20AM -0800, Stephen Hemminger wrote:
> On Wed, 16 Jan 2013 09:22:58 -0800
> "Certain, Andrew" <certain at amazon.com> wrote:
> 
> > 
> > 
> > > -----Original Message-----
> > > From: Stephen Hemminger [mailto:stephen at networkplumber.org]
> > > Sent: Wednesday, January 16, 2013 8:04 AM
> > > To: Certain, Andrew
> > > Cc: David Lamparter; Stephen Hemminger; quagga-dev at lists.quagga.net
> > > Subject: Re: [quagga-dev 10194] Re: [PATCH 2/4] hash: force size to be a
> > > power of 2
> > > 
> > > > It seems that you're trading one performance improvement against
> > > another.  The hashing performance of the thread look up will be worse, and
> > > you're arguing that this performance hit isn't as important as removing
> > > the divide.  You may be right, but I would like to see the data.
> > > >
> > > > Obviously, my proposal would be just as bad as yours in impacting the
> > > hashing of the threads.  Without a coherent and comprehensive test suite,
> > > no changes can be made with high confidence, which in my mind raises the
> > > bar for when we should accept change.  Until such a thing exists, I think
> > > that any changes done solely for performance reasons should only be
> > > accepted if there is a clear problem with the current code, rather than
> > > just for general cleanup reasons (I'm not saying you don't have a
> > > quantitative argument; I'm just asking you to share it).
> > > >
> > > > Andrew
> > > 
> > > The simpler fix would be to just use a mix (like jhash) on the function
> > > address.
> > >
> > OK, but why change anything?  Do you have data to show that this is an impacting concern?
> > 
> > Andrew
> 
> With full feed, the hash function is very hot, and the hash chains grow quite long
> especially for BGP attributes. In order to support doubling it is easier to
> use a power of 2.

Here's some raw data for this, using a single BGP peer from the RIPE RIS
bview dataset.

before patches:
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (No unit mask) count 100000
samples  image name               app name                 symbol name
9572     libzebra.so.0.0.0        bgpd                     hash_get
6186     libzebra.so.0.0.0        bgpd                     jhash_3words
5483     libzebra.so.0.0.0        bgpd                     jhash
3005     libc-2.15.so             bgpd                     vfprintf
2174     libzebra.so.0.0.0        zebra                    prefix_match

with power-of-2 hash size:
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (No unit mask) count 100000
samples  image name               app name                 symbol name
9878     libzebra.so.0.0.0        bgpd                     hash_get
6685     libzebra.so.0.0.0        bgpd                     jhash_3words
5667     libzebra.so.0.0.0        bgpd                     jhash
3005     libc-2.15.so             bgpd                     vfprintf
2137     libzebra.so.0.0.0        zebra                    prefix_match

dynamic sizing:
Counted CPU_CLK_UNHALTED events (Clock cycles when not halted) with a unit mask of 0x00 (No unit mask) count 100000
samples  image name               app name                 symbol name
6225     libzebra.so.0.0.0        bgpd                     jhash_3words
5319     libzebra.so.0.0.0        bgpd                     jhash
3049     libzebra.so.0.0.0        bgpd                     hash_get
2796     libc-2.15.so             bgpd                     vfprintf
2275     libzebra.so.0.0.0        zebra                    prefix_match


So, power-of-2 slightly worsens it, but dynamic sizing then improves
down to around two thirds of original cpu cycles.  It's noteworthy
that the output above is indeed the beginning of the profiling report,
i.e. those are the hottest functions.  The config was bare minimum
though, no cpu-hungry features.

Both patches accepted.  Thanks Stephen!


-David
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 230 bytes
Desc: Digital signature
URL: <http://lists.quagga.net/pipermail/quagga-dev/attachments/20130224/ede85a8e/attachment-0001.sig>


More information about the Quagga-dev mailing list