[ccache] [Patch] Faster direct-mode hash

[Justin Lebar]

Here's my earlier patch split in two.

Unfortunately, the faster search algorithm doesn't seem to help much
on its own -- looks like you really need the faster hash, too.  The
results below are from

   perf.py gcc-4.5 c++_includes.cpp


*** All patches:

Without ccache:                               6.51 s (100.00 %) ( 1.00 x)
With ccache, preprocessor mode, cache miss:   7.76 s (119.11 %) ( 0.84 x)
With ccache, preprocessor mode, cache hit:    1.65 s ( 25.34 %) ( 3.95 x)
With ccache, direct mode, cache miss:         7.78 s (119.50 %) ( 0.84 x)
With ccache, direct mode, cache hit:          0.13 s (  1.96 %) (51.06 x)

*** Just temporal macro search:

Without ccache:                               6.50 s (100.00 %) ( 1.00 x)
With ccache, preprocessor mode, cache miss:   7.74 s (118.99 %) ( 0.84 x)
With ccache, preprocessor mode, cache hit:    1.65 s ( 25.37 %) ( 3.94 x)
With ccache, direct mode, cache miss:         7.86 s (120.81 %) ( 0.83 x)
With ccache, direct mode, cache hit:          0.23 s (  3.47 %) (28.82 x)

*** unpatched:

Without ccache:                               6.51 s (100.00 %) ( 1.00 x)
With ccache, preprocessor mode, cache miss:   7.73 s (118.75 %) ( 0.84 x)
With ccache, preprocessor mode, cache hit:    1.66 s ( 25.56 %) ( 3.91 x)
With ccache, direct mode, cache miss:         7.94 s (121.95 %) ( 0.82 x)
With ccache, direct mode, cache hit:          0.28 s (  4.34 %) (23.04 x)

On Mon, Nov 8, 2010 at 2:06 PM, Justin Lebar <justin.lebar at gmail.com> wrote:
>> The improved search for __{DATE,TIME}__ is uncontroversial, so that can be
>> applied right away. However, I would like to make the
>> LFG-based digest opt-in, at least for now, since I think we
>> need time to test it and to collect hash-savvy people's opinions.
>
> That sounds pretty reasonable to me.  In this case, you'll probably
> just want to substitute the patch's fast_hash_buffer() call with
> hash_buffer() -- that is, don't accumulate the string to hash one
> character at a time like the code currently does.
>
>> By the way, can you provide some reference to why LFG (and the properties
>> you chose) would work well as a digest for ccache's purpose? What's the
>> expected collision rate? Or in other words: how well can we sleep at night,
>> knowing that we haven't messed up people's builds, if we would introduce the
>> LFG-based algorithm? :-)
>
> I don't have as good a reason as I should; I was just implementing
> Michael Niedermayer <michaelni at gmx.at>'s suggestion from the previous
> thread, as it seemed pretty reasonable.  Hopefully he can justify my
> decision for me.  :D
>
> -Justin
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fast-hash
Type: application/octet-stream
Size: 3471 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/ccache/attachments/20101126/cedc5350/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fast-temporal-macro-search
Type: application/octet-stream
Size: 8821 bytes
Desc: not available
URL: <http://lists.samba.org/pipermail/ccache/attachments/20101126/cedc5350/attachment-0001.obj>