Hacker News Reader

Comment by lbrandy | Hacker News Reader

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.

View on HN

I 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?

Usually you just pad the rows a bit.

And now I feel silly for not having thought of that :)

Happens 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.

For images, one of the main reasons to have separate bytes-per-row (usually called stride or pitch) is that it allows you to have sub-images that use the same data and stride as the parent image, but a different width and height.

Well, that too of course. :)

You 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.

Reply on news.ycombinator.com