4 ms·

That's a bold claim; Sure it is theoretically possible, to have two versions of the same C program take either 500ms or 8ms purely due to memory layout. But I

That's a bold claim; Sure it is theoretically possible, to have two versions of the same C program take either 500ms or 8ms purely due to memory layout. But I would like to challenge you to actually do it! I.e. same number of calculations, on same amount of data and a factor of 60 run time difference, with only the memory layout as actual difference between the two implementations. Up for it?

Tunabrain 10y ago
Any entry level optimization course will make you implement something like that; do a matrix+matrix addition, but traverse it in row-major order in one program, and column-major in the other. If the matrix is big enough, you will easily get a 10x difference. For even larger sizes (once you thrash the TLB), you will get an additional factor. You might not get up to 60, but this is just a simple matrix addition. Even just matrix multiplication might be enough to get a 60x difference just with optimizing for memory hierarchy. I expect that high-performance memory bound programs are more complex than matrix multiplication, so the parent comment's claim doesn't seem too unlikely to me.
- joakleaf 10y ago
  Sorry, I didn't mean to question it whether it is possible. I just think that a factor of 60 sounds tricky to achieve if we are just talking about RAM (no disk involved). The first time I encountered this myself, was doing texture mapping on the 486 back in the mid 90s. Texels would be laid out by row, and the mapper would draw horizontally. Texture maps that would fit within the L1 cache would draw fine no matter which rotation they were drawn it. However texture maps that were larger than the L1-cache, would be drawn fine as long as the texture map wasn't significantly rotated. But, if you rotated the polygon by 90 degrees you'd see a significant drop in frames per second, because you'd skip a while row between drawing each texel, which would effectively cause a lot of cache misses. OK, I didn't manage to explain that well, but I hope it is understable. Obviously, I have encountered this many times since, in many variants (including disk read/write), and I definitely agree that a factor of 10 should be possible. I guess, I am just wondering if the difference between RAM and L1 has reached a factor 60, and how easy it is to come up with something where the cache misses all the time, or if caches have become smarter.
  - FeepingCreature 10y ago
    Googling puts RAM latency avoiding caches on modern processors at 40-60 cycles.
    - joakleaf 10y ago
      Exactly... Now, that alone could make it tricky to get a factor 60 difference.
      - pacaro 10y ago
        Write a simplistic O(N^3) algortihm When N is 100, all fixed costs in the inner loop are multiplied by 1,000,000. So a nanosecond difference is now a millisecond. It's pretty easy to get worse than that by boneheaded data layout (row-major vs column-major is pretty common)
        joakleaf 10y ago
        No... If you use a "bonehead" data structure each memory reference will force a cache-miss, i.e. taking q CPU cycles instead of 1 CPU cycles. If the algorithms has a running time of O(N^3), it means it is using some number of instructions <= c * N^3 to complete. Let's for simplicity sake say 1 operation is identical to 1 CPU-cycle. Now, if each operation takes q CPU cycles instead of 1 cycles due to cache-miss on every operation, the running time of your algorithm is still bounded by q * (c * N^3) operations. For the example with N=100 -> The fast version takes c * 1,000,000 operations to complete, for some value c. For the slow version, as each operation is now q times slower, it will take q * c * 1,000,000 operations to complete for values q and c. I.e. it takes q times as long, not q * q * q. What you were saying is that, if you run a O(N) algorithm on a 100 MHZ CPU, it will take 10 times as long as on a 1000 MHZ CPU, but an O(N^3) algorithm would take 1000 times as long. And that is obviously, not true. Both will take 10 times longer.
        pacaro 10y ago
        No I'm saying that a poor choice of data structure will have an amplified impact on an O(N^3) algorithm. Giving it as an example of where you could have the different implementations of the same algorithm have massively different runtimes on the same processor.
Coding_Cat 10y ago
I'll take that challenge. Here's how to do it, with a little bit of sneaky interpretation of 'memory layout': have an algorithm which takes a large struct S and looks at a subset Sf to determine what to do with S, for some value of Sf use all of S, otherwise skip it. (e.g. when distance between 2 particles < threshold, calculate force). Now have a very low pass-rate for the filter so that total time ~= time taken to read all of Sf. Make Sf a single byte and S >= 64 bytes (page size if you really want to beat it). And now compare array-of-struct vs struct-of-array ;). You should see ~64x performance difference in the assymptotic case. AoS will use one byte per cacheline read. SoA will use 64 bytes per cacheline. if you're memory bound this will translate to an almost 64x speed difference. There are other ways to achieve the same effect but that is the gist of getting 64x performance. using 1 byte vs 64. if you want to go really crazy, use a single bit and a bitfield array for the SoA. If you use a bitfield the passing chance doesn't have to be that low. I happened to have to present on AoS vs SoA today so I have a less extreme benchmark to show the difference (~16x because it filters over 32 bit ints) http://imgur.com/a/HuXFR http://imgur.com/a/HuXFR
- sqeaky 10y ago
  So you can write code that is 64x times slower when you specifically optimize for a slowdown. Cool. Can you run that in web assembly and get the same slowdown. If so most of the same things that allow C/C++ to faster than other languages on systems will also allow them to be faster in the browser.
  - Coding_Cat 10y ago
    Yeah, this will affect any language that stores structs as POD (plain old data) as long as it has somewhat sensible alignment rules and allocation (i.e. doesn't hide every struct behind a pointer, doesn't align char's to 8 bytes).
- joakleaf 10y ago
  Sorry, I don't quite understand the explanation... Do you have some simple pseudo-code? And are you using the same number of instructions in both cases? Note also: If you are moving data structures of different sizes, you are not using the same number of instructions(calculations), as the challenge required.

Tunabrain 10y ago

Any entry level optimization course will make you implement something like that; do a matrix+matrix addition, but traverse it in row-major order in one program, and column-major in the other. If the matrix is big enough, you will easily get a 10x difference. For even larger sizes (once you thrash the TLB), you will get an additional factor. You might not get up to 60, but this is just a simple matrix addition. Even just matrix multiplication might be enough to get a 60x difference just with optimizing for memory hierarchy. I expect that high-performance memory bound programs are more complex than matrix multiplication, so the parent comment's claim doesn't seem too unlikely to me.

joakleaf 10y ago
Sorry, I didn't mean to question it whether it is possible. I just think that a factor of 60 sounds tricky to achieve if we are just talking about RAM (no disk involved). The first time I encountered this myself, was doing texture mapping on the 486 back in the mid 90s. Texels would be laid out by row, and the mapper would draw horizontally. Texture maps that would fit within the L1 cache would draw fine no matter which rotation they were drawn it. However texture maps that were larger than the L1-cache, would be drawn fine as long as the texture map wasn't significantly rotated. But, if you rotated the polygon by 90 degrees you'd see a significant drop in frames per second, because you'd skip a while row between drawing each texel, which would effectively cause a lot of cache misses. OK, I didn't manage to explain that well, but I hope it is understable. Obviously, I have encountered this many times since, in many variants (including disk read/write), and I definitely agree that a factor of 10 should be possible. I guess, I am just wondering if the difference between RAM and L1 has reached a factor 60, and how easy it is to come up with something where the cache misses all the time, or if caches have become smarter.
- FeepingCreature 10y ago
  Googling puts RAM latency avoiding caches on modern processors at 40-60 cycles.
  - joakleaf 10y ago
    Exactly... Now, that alone could make it tricky to get a factor 60 difference.
    - pacaro 10y ago
      Write a simplistic O(N^3) algortihm When N is 100, all fixed costs in the inner loop are multiplied by 1,000,000. So a nanosecond difference is now a millisecond. It's pretty easy to get worse than that by boneheaded data layout (row-major vs column-major is pretty common)
      - joakleaf 10y ago
        No... If you use a "bonehead" data structure each memory reference will force a cache-miss, i.e. taking q CPU cycles instead of 1 CPU cycles. If the algorithms has a running time of O(N^3), it means it is using some number of instructions <= c * N^3 to complete. Let's for simplicity sake say 1 operation is identical to 1 CPU-cycle. Now, if each operation takes q CPU cycles instead of 1 cycles due to cache-miss on every operation, the running time of your algorithm is still bounded by q * (c * N^3) operations. For the example with N=100 -> The fast version takes c * 1,000,000 operations to complete, for some value c. For the slow version, as each operation is now q times slower, it will take q * c * 1,000,000 operations to complete for values q and c. I.e. it takes q times as long, not q * q * q. What you were saying is that, if you run a O(N) algorithm on a 100 MHZ CPU, it will take 10 times as long as on a 1000 MHZ CPU, but an O(N^3) algorithm would take 1000 times as long. And that is obviously, not true. Both will take 10 times longer.
        pacaro 10y ago
        No I'm saying that a poor choice of data structure will have an amplified impact on an O(N^3) algorithm. Giving it as an example of where you could have the different implementations of the same algorithm have massively different runtimes on the same processor.

Coding_Cat 10y ago

I'll take that challenge. Here's how to do it, with a little bit of sneaky interpretation of 'memory layout': have an algorithm which takes a large struct S and looks at a subset Sf to determine what to do with S, for some value of Sf use all of S, otherwise skip it. (e.g. when distance between 2 particles < threshold, calculate force). Now have a very low pass-rate for the filter so that total time ~= time taken to read all of Sf. Make Sf a single byte and S >= 64 bytes (page size if you really want to beat it). And now compare array-of-struct vs struct-of-array ;). You should see ~64x performance difference in the assymptotic case. AoS will use one byte per cacheline read. SoA will use 64 bytes per cacheline. if you're memory bound this will translate to an almost 64x speed difference. There are other ways to achieve the same effect but that is the gist of getting 64x performance. using 1 byte vs 64. if you want to go really crazy, use a single bit and a bitfield array for the SoA. If you use a bitfield the passing chance doesn't have to be that low. I happened to have to present on AoS vs SoA today so I have a less extreme benchmark to show the difference (~16x because it filters over 32 bit ints) http://imgur.com/a/HuXFR http://imgur.com/a/HuXFR

sqeaky 10y ago
So you can write code that is 64x times slower when you specifically optimize for a slowdown. Cool. Can you run that in web assembly and get the same slowdown. If so most of the same things that allow C/C++ to faster than other languages on systems will also allow them to be faster in the browser.
- Coding_Cat 10y ago
  Yeah, this will affect any language that stores structs as POD (plain old data) as long as it has somewhat sensible alignment rules and allocation (i.e. doesn't hide every struct behind a pointer, doesn't align char's to 8 bytes).
joakleaf 10y ago
Sorry, I don't quite understand the explanation... Do you have some simple pseudo-code? And are you using the same number of instructions in both cases? Note also: If you are moving data structures of different sizes, you are not using the same number of instructions(calculations), as the challenge required.