4 ms·

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 an

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.
- Coding_Cat 10y ago
  >Sorry, I don't quite understand the explanation... define a struct S{char flag, data[63];} then do foreach s in std::vector<S>(big number){ if s.flag == 0{ //set this variable to be very rarely 0 do_something_with(s.data); } this will load the entire struct into memory each iteration because loads from memory happen on cacheline granularity (i.e. 64 bytes at a time) then the optimized version is >And are you using the same number of instructions in both cases? //define S as struct of arrays now struct S{char* flags, (*data)[63];} s = initialize_S(big number); for(i = 0; i < big number; i++){ if s.flags[i] == 0{ //set this variable to be very rarely 0 do_something_with(s.data, i); } This one will load 64 flags into the L1 cache at a time. because the L1 cache is much much faster than main memory access time will be ~64x faster for the checking of the flags. Because it is rare for the loop to enter the if, this means the overal speed will be ~64x faster. As proven by the graph I posted where it is about 16x faster (because I use an int instead of a byte as flag). Syntax is slightly different between SoA and AoS, but functionally they are the same except for how multiple S's are laid out in memory. >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. The same number of instructions is an arbitrary and impossible task. I'm not going to handwrite assembly for some internet points, I only do that for fun ;). Do they perform the same amount of cpu work though, yes. They are functionally the same and use the same types of instructions. That's about as good as anyone can get it. In any case, the program is completely limited by memory throughput not computation. I could make one of the inner loops a sqrt and the other a nop and the difference would be the exact same. If you really want to see it in assembly to prove it uses the same amount of instructions, then it's just a mov rax, [rcx], cmp rax, r8, je INNER_FUNCTION, inc rcx {sizeof(S),1} depending on the method. Add 0x90 where appropriate to match instruction counts. The rest is left as an exercise to the reader.
  - deleted 10y ago
    [deleted]

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.

Coding_Cat 10y ago
>Sorry, I don't quite understand the explanation... define a struct S{char flag, data[63];} then do foreach s in std::vector<S>(big number){ if s.flag == 0{ //set this variable to be very rarely 0 do_something_with(s.data); } this will load the entire struct into memory each iteration because loads from memory happen on cacheline granularity (i.e. 64 bytes at a time) then the optimized version is >And are you using the same number of instructions in both cases? //define S as struct of arrays now struct S{char* flags, (*data)[63];} s = initialize_S(big number); for(i = 0; i < big number; i++){ if s.flags[i] == 0{ //set this variable to be very rarely 0 do_something_with(s.data, i); } This one will load 64 flags into the L1 cache at a time. because the L1 cache is much much faster than main memory access time will be ~64x faster for the checking of the flags. Because it is rare for the loop to enter the if, this means the overal speed will be ~64x faster. As proven by the graph I posted where it is about 16x faster (because I use an int instead of a byte as flag). Syntax is slightly different between SoA and AoS, but functionally they are the same except for how multiple S's are laid out in memory. >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. The same number of instructions is an arbitrary and impossible task. I'm not going to handwrite assembly for some internet points, I only do that for fun ;). Do they perform the same amount of cpu work though, yes. They are functionally the same and use the same types of instructions. That's about as good as anyone can get it. In any case, the program is completely limited by memory throughput not computation. I could make one of the inner loops a sqrt and the other a nop and the difference would be the exact same. If you really want to see it in assembly to prove it uses the same amount of instructions, then it's just a mov rax, [rcx], cmp rax, r8, je INNER_FUNCTION, inc rcx {sizeof(S),1} depending on the method. Add 0x90 where appropriate to match instruction counts. The rest is left as an exercise to the reader.
- deleted 10y ago
  [deleted]