[vorbis-dev] Cache collisions

[dean gaudet]

On Thu, 6 May 2004, Tal wrote:

>
> Vtune sampling showed that the is a lot of cache collisions in
> bark_noise_hybridmp.
> We've read in the manual that each address is mapped to a cache bank by
> the 5:15 bits.
> We've printed out n and it seems to be one of two: 4K, 0.5K.

i think you mean n is 128 or 1024 -- the arrays are 512 bytes or 4096
bytes.  at least that's what i'm seeing when i run it.

> This means that the N array and XY array fall into the same bank in the
> cache.
...
> We've tried allocating 1K more for N array and we got 8% speedup
...
> AMD data cache size is 64K so I guess there might be a similar problem
> there.

k7 and k8 have 2-way associative L1 D$... which means they have aliasing
problems on 64KiB/2 = 32KiB boundaries.

there are 5 arrays on the stack, and two referenced from the caller (f,
noise).  the 5 on the stack are only 20KiB so k7/k8 have no problem with
them aliasing against each other... and clustering them close like this
in 20KiB improves the chance the 2-way associativity can fit the f and
noise arrays from the caller.

p3, p-m have a 32KiB, 8-way associative L1 -- aliasing problems on
4KiB boundaries.  i'm guessing this is the cpu you're using?  but it is
8-way associative and there are only 6 arrays to fit... it shouldn't be
as bad as you're finding.

or perhaps you're on a p4?  8KiB, 4-way associative... this one aliases
on 2KiB boundaries ... and definitely can't fit all the arrays -- so
staggering some is going to help L1 usage (since the arrays are accessed
in-sync with each other).

i bet if you tried staggering each array by 64 or 128 bytes you'll see
the same benefit you've seen now and it'll be a fairly portable benefit.
64B is a really common line size today (it's dictated by the minimum
transfer of a dual channel DDR memory controller).

that whole routine is begging for SSE vectorization :)

-dean
--- >8 ----
List archives:  http://www.xiph.org/archives/
Ogg project homepage: http://www.xiph.org/ogg/
To unsubscribe from this list, send a message to 'vorbis-dev-request at xiph.org'
containing only the word 'unsubscribe' in the body.  No subject is needed.
Unsubscribe messages sent to the list will be ignored/filtered.