|
From: ozgun e. <ku...@ho...> - 2004-06-11 08:05:10
|
hi,
I'm testing a program that uses bloom filters (a bit array used like a hash
table). Performance is very dependent on the CPU's cache size, and drops
down dramatically as I increase the bloom filter size. So, I need to know
the rate of cache hits/misses. Cachegrind seems to be exactly what I am
looking for, so I downloaded and ran it on my AMD 1.8 Ghz (64 KB L1 data
cache, 128 KB L2 cache).
Basically, the program goes through 15,388,813 blocks of input, and for
every block, takes its mod with some very large prime. It then checks this
bit array to see if there is a match. When the bloom filter size is 256 KB,
Cachegrind tells me there are 477,221 L2 cache misses. (I know that
Cachegrind models Pentium's cache, so that number is pretty reasonable.)
Then, when I go ahead and try it on a 32 MB bloom filter, I get this:
Dr D1mr D2mr Dw D1mw D2mw
file:function
---------------------------------------------------------------------------------------------
76,944,065 7,684,264 4,626,161 15,388,813 0 0
scanner.c:ba_value
Now, this means the data miss rate on my cache is only ~27%. Given the
filter size and the even distribution, this doesn't make any sense to me. I
must be missing something. I compiled with -g and no optimizations. Here is
ba_value's code:
boolean ba_value(const bit arr[], const elem_t elem)
{
return( (arr[elem / BITS_SZ] & (1 << (elem % BITS_SZ))) ? TRUE:FALSE );
}
What may be going on? Any help would really be appreciated. Thanks,
Ozgun.
_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE*
http://join.msn.com/?page=features/junkmail
|
|
From: Nicholas N. <nj...@ca...> - 2004-06-14 09:23:34
|
On Fri, 11 Jun 2004, ozgun erdogan wrote: > Now, this means the data miss rate on my cache is only ~27%. Only 27%!? That's really bad, especially if its L2 -- remember that an L2 miss can cost 100s of cycles (206 in the worst case on my Athlon). > I was testing Cachegrind on an executable file (60 MB) constructed from > /usr/bin. Trying it on a random file, I get around 99.2% cache misses. > This is really amazing! Thanks to Cachegrind I realized there were some > fundamental problems with my assumptions. 99%? That is amazing. Either your program is pathologically bad, or Cachegrind is doing something wrong. N |
|
From: Josef W. <Jos...@gm...> - 2004-06-14 13:22:42
|
On Friday 11 June 2004 10:04, ozgun erdogan wrote:
> Basically, the program goes through 15,388,813 blocks of input, and for
> every block, takes its mod with some very large prime. It then checks this
> bit array to see if there is a match. When the bloom filter size is 256 KB,
> Cachegrind tells me there are 477,221 L2 cache misses. (I know that
> Cachegrind models Pentium's cache, so that number is pretty reasonable.)
> Then, when I go ahead and try it on a 32 MB bloom filter, I get this:
>
> Dr D1mr D2mr Dw D1mw D2mw
> file:function
> ---------------------------------------------------------------------------
>------------------ 76,944,065 7,684,264 4,626,161 15,388,813 0
> 0
> scanner.c:ba_value
>
> Now, this means the data miss rate on my cache is only ~27%. Given the
> filter size and the even distribution, this doesn't make any sense to me. I
Hi,
what is the exact number that makes no sense to you?
I suppose ba_value is called 15 mio. times, and you wonder why this only makes
it to 4.6 mio. L2 misses? Perhaps the access order to the array is not as
random as you thought?
What would you like cachegrind to show you to have more trust into its
results?
Josef
> must be missing something. I compiled with -g and no optimizations. Here is
> ba_value's code:
>
> boolean ba_value(const bit arr[], const elem_t elem)
> {
> return( (arr[elem / BITS_SZ] & (1 << (elem % BITS_SZ))) ? TRUE:FALSE );
> }
>
> What may be going on? Any help would really be appreciated. Thanks,
>
> Ozgun.
>
> _________________________________________________________________
> The new MSN 8: advanced junk mail protection and 2 months FREE*
> http://join.msn.com/?page=features/junkmail
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by the new InstallShield X.
> From Windows to Linux, servers to mobile, InstallShield X is the
> one installation-authoring solution that does it all. Learn more and
> evaluate today! http://www.installshield.com/Dev2Dev/0504
> _______________________________________________
> Valgrind-users mailing list
> Val...@li...
> https://lists.sourceforge.net/lists/listinfo/valgrind-users
|