4 ms·

> Iterating over a two dimensional array by row is much faster than by column. Another fun fact is staggering array accesses is faster then linear acesses.

Swizec 10y ago
I wonder if this is language or even compiler dependent. Are there things that transpose memory organization? I for one always get confused which index is the row and which is the column when coding. Every damn time I've done a 2D iteration in the last 15+ years. Is it [col][row] or [row][col] ... I imagine it depends.
- yaantc 10y ago
  Indeed it does depend, some languages are row major (C, C++) while others are column major (Fortran, and some common HPC libraries are in Fortran). https://en.wikipedia.org/wiki/Row-_and_column-major_order https://en.wikipedia.org/wiki/Row-_and_column-major_order
- patrickdavey 10y ago
  I'm not alone!!!!!! :) I was having brain melting with today's http://adventofcode.com/2016/day/8 http://adventofcode.com/2016/day/8 I'm attempting everything in Elixir and it's quite different from what I'm used to!
- andrioni 10y ago
  >Are there things that transpose memory organization? Not exactly what you asked, but if you look at most subroutines in linear algebra libraries like LAPACK, they tend to have extra arguments so you can tell if your inputs are already transposed and/or conjugate in order to have more efficient memory access.
Namrog84 10y ago
Can someone elaborate on this? I tried searching and wasn't having any luck. I always thought sequential linear access was fastest?
- dozzie 10y ago
  I'm not that low-level programmer, but my guess would be loading to CPU cache a whole memory segment at once.
- dreta 10y ago
  This is all nonsense. Accessing linear memory in a linear fashion is the way to go. You gain absolutely nothing by staggering memory accesses, because you’re waiting for memory to come into cache while the CPU idles, and since you have little control over how cache is utilised across a span of time, the whole concept of doing this to pre-load anything is just bogus, unless you’re doing specific optimisations for a specific architecture, even then there are cache pre-loading instructions for that.
- gravypod 10y ago
  This will technically only work on pipelined architectures of which all major CPU architectures are one. You will be able to see a significant boost to performance given the following are all true: * You have no inter dependancy of information across the lines * All your data is in the cache * You don't have instructions generated between the two lines that will require some sort of operand forwarding Basically, if you already have the stuff in the cache, the calculation is invarent to the last calculation, and you have a processor capable of it you'll see a large speed improvement. There is a great talk about this [0] (for the exact moment go to [1]). If you're interested further I'd very much recommend finding some sort of GOOD computer architecture class. Luckily now we have a fantastic resource to locate these such courses [2]. This seems like dark magic and many programmers refuse to come to terms with it's existence. Check out `dreta`'s comment to see an example. Now I do agree with dreta, this is VERY much architecture dependant but most architectures would benifit from this sort of optimization. Pretty much all modern Intel and AMD CPU's caches are large enough, they support a big enough cache, and they also all have pipelines under the hood. Intel started this in the pentium series with a 5-stage-pipeline (which I find very funny due to the GHz wars that came from that time period desipte the pipeline being probably the pargest performance boon in most cases that you would want to brag about). [0] - https://www.youtube.com/watch?v=e08kOj2kISU https://www.youtube.com/watch?v=e08kOj2kISU [1] - https://youtu.be/e08kOj2kISU?t=26m50s https://youtu.be/e08kOj2kISU?t=26m50s [2] - https://github.com/Developer-Y/cs-video-courses#computer-organization-and-architecture https://github.com/Developer-Y/cs-video-courses#computer-org...

Swizec 10y ago

I wonder if this is language or even compiler dependent. Are there things that transpose memory organization? I for one always get confused which index is the row and which is the column when coding. Every damn time I've done a 2D iteration in the last 15+ years. Is it [col][row] or [row][col] ... I imagine it depends.

yaantc 10y ago
Indeed it does depend, some languages are row major (C, C++) while others are column major (Fortran, and some common HPC libraries are in Fortran). https://en.wikipedia.org/wiki/Row-_and_column-major_order https://en.wikipedia.org/wiki/Row-_and_column-major_order
patrickdavey 10y ago
I'm not alone!!!!!! :) I was having brain melting with today's http://adventofcode.com/2016/day/8 http://adventofcode.com/2016/day/8 I'm attempting everything in Elixir and it's quite different from what I'm used to!
andrioni 10y ago
>Are there things that transpose memory organization? Not exactly what you asked, but if you look at most subroutines in linear algebra libraries like LAPACK, they tend to have extra arguments so you can tell if your inputs are already transposed and/or conjugate in order to have more efficient memory access.

Namrog84 10y ago

Can someone elaborate on this? I tried searching and wasn't having any luck. I always thought sequential linear access was fastest?

dozzie 10y ago
I'm not that low-level programmer, but my guess would be loading to CPU cache a whole memory segment at once.
dreta 10y ago
This is all nonsense. Accessing linear memory in a linear fashion is the way to go. You gain absolutely nothing by staggering memory accesses, because you’re waiting for memory to come into cache while the CPU idles, and since you have little control over how cache is utilised across a span of time, the whole concept of doing this to pre-load anything is just bogus, unless you’re doing specific optimisations for a specific architecture, even then there are cache pre-loading instructions for that.
gravypod 10y ago
This will technically only work on pipelined architectures of which all major CPU architectures are one. You will be able to see a significant boost to performance given the following are all true: * You have no inter dependancy of information across the lines * All your data is in the cache * You don't have instructions generated between the two lines that will require some sort of operand forwarding Basically, if you already have the stuff in the cache, the calculation is invarent to the last calculation, and you have a processor capable of it you'll see a large speed improvement. There is a great talk about this [0] (for the exact moment go to [1]). If you're interested further I'd very much recommend finding some sort of GOOD computer architecture class. Luckily now we have a fantastic resource to locate these such courses [2]. This seems like dark magic and many programmers refuse to come to terms with it's existence. Check out `dreta`'s comment to see an example. Now I do agree with dreta, this is VERY much architecture dependant but most architectures would benifit from this sort of optimization. Pretty much all modern Intel and AMD CPU's caches are large enough, they support a big enough cache, and they also all have pipelines under the hood. Intel started this in the pentium series with a 5-stage-pipeline (which I find very funny due to the GHz wars that came from that time period desipte the pipeline being probably the pargest performance boon in most cases that you would want to brag about). [0] - https://www.youtube.com/watch?v=e08kOj2kISU https://www.youtube.com/watch?v=e08kOj2kISU [1] - https://youtu.be/e08kOj2kISU?t=26m50s https://youtu.be/e08kOj2kISU?t=26m50s [2] - https://github.com/Developer-Y/cs-video-courses#computer-organization-and-architecture https://github.com/Developer-Y/cs-video-courses#computer-org...