3 ms·
The tldr here is that iterating through large arrays simultaneously with identical alignment can be slower than non-simultaneous access because of cache associa
by lbrandy 15y ago
The tldr here is that iterating through large arrays simultaneously with identical alignment can be slower than non-simultaneous access because of cache associativity. It's basically hash collisions in the cache due to alignment.
I've actually run into this in the "real world" in image processing applications. Given a "magical" width to an image, a pixel directly above (or below) another pixel can have the same alignment with respect to cpu cache. This can mean that things like (large) 2d convolutions are slower on images of very particular sizes.
- tikhonj 15y agoI recently had a class project where we had similar issues. Being lazy students, we just let it perform slower for matrices of the wrong size; what is a good way to handle this sort of thing?
- dpe82 15y agoUsually you just pad the rows a bit.
- tikhonj 15y agoAnd now I feel silly for not having thought of that :)
- dpe82 15y agoHappens to all of us. :) I remember the first time I saw an image data struct that specified bits per pixel, image width and then also had bytes per row. I was a bit perplexed about why you'd store bytes per row if you could just compute it from bpp and width. Turns out you can fix/avoid a lot of performance issues if you can pad the data, so it's good practice to always save the number of bytes per row and use that in your mallocs/copies/iterators/etc.
- buff-a 15y agoYou pad the rows manually. Then you start loading bigger chunks of data at a time. Then you start issuing prefetch instructions with compiler intrinsics or inline assembly. Then you ask "why am I dealing with this at all?" and use Intel's math libraries. And finally you use Octave or Matlab. Unless you are a nutter like me, in which case you hand-roll everything in assembly.