3 ms·

That's good food for thought. My hardware is quite old, but I agree that the numbers seem somewhat suspicious. I believe that RAM can only be RMW'd in cache li

That's good food for thought. My hardware is quite old, but I agree that the numbers seem somewhat suspicious. I believe that RAM can only be RMW'd in cache lines, so modifying just 8 bytes still requires 64 bytes to be transmitted. I'm assuming the 50 GB/s throughput is half-duplex, and 25 GB/s over 64 bytes is ~400 Melems/s, somewhat closer to my result. I tried using non-temporal stores in the straightforward algorithm, but to my surprise, this led to a significant decrease of performance across all input lengths. > When your data is indeed big and the performance actually matters, consider doing something completely different. I'm not sure what you mean by this. Scaling across machines is just ignoring the problem. What do you mean by "something completely different"?

saagarjha 2y ago
Non-temporal stores will not help you if all you do are those accesses. The point of using them is that you don't want them pulled into the caches and pushing out everything else.
bobmcnamara 2y ago
> I believe that RAM can only be RMW'd in cache lines, so modifying just 8 bytes still requires 64 bytes to be transmitted. Ages ago I worked with several different memory controllers, and it depends on the memory controller, cache, and MMU configuration. Plenty of systems do require cacheline updates, then modifying 8B requires reading one or two cachelines, updating them, and writing them out eventually. Some caches track cacheline validity with a bit per byte. This enables a CPU to set a book out in memory without fetching the cacheline. The cache may then try to burst read that line from the memory controller, but if it doesn't get around to it before deciding to flush that cacheline, it may issue a single byte write to the controller. The controller can then issue a makes DRAM write to the memory, which will update only certain bytes in the DRAM column. However, this still takes about as long as sending the full cacheline but it offloads the read-modify. Validity per byte is also useful to implement hit under miss. I bet on newer, bigger systems tricks like this are less useful since the memory busses are faster and wider today.
Const-me 2y ago
> What do you mean by "something completely different"? I mean compute the exact thing you need to compute, optimizing for performance. I’m pretty sure your current code is spending vast majority of time doing malloc / memcpy while moving input elements from the input array into per-bucket collections. To aggregate the data the way you want, you do not have to do any of that. You only need a single number per bucket to compute the minimum. Updating that accumulator is very cheap as there’s no memory allocations involved: just load, compare, and store the updated number. Moreover, that algorithm is easily to parallelize. Compute an array with these per-bucket minimums on different threads, wait for completion of all tasks, then aggregate multiple arrays computed by each thread into a single array with global minimums for each bucket. Then compute the final sum.

saagarjha 2y ago

Non-temporal stores will not help you if all you do are those accesses. The point of using them is that you don't want them pulled into the caches and pushing out everything else.

bobmcnamara 2y ago

> I believe that RAM can only be RMW'd in cache lines, so modifying just 8 bytes still requires 64 bytes to be transmitted. Ages ago I worked with several different memory controllers, and it depends on the memory controller, cache, and MMU configuration. Plenty of systems do require cacheline updates, then modifying 8B requires reading one or two cachelines, updating them, and writing them out eventually. Some caches track cacheline validity with a bit per byte. This enables a CPU to set a book out in memory without fetching the cacheline. The cache may then try to burst read that line from the memory controller, but if it doesn't get around to it before deciding to flush that cacheline, it may issue a single byte write to the controller. The controller can then issue a makes DRAM write to the memory, which will update only certain bytes in the DRAM column. However, this still takes about as long as sending the full cacheline but it offloads the read-modify. Validity per byte is also useful to implement hit under miss. I bet on newer, bigger systems tricks like this are less useful since the memory busses are faster and wider today.

Const-me 2y ago

> What do you mean by "something completely different"? I mean compute the exact thing you need to compute, optimizing for performance. I’m pretty sure your current code is spending vast majority of time doing malloc / memcpy while moving input elements from the input array into per-bucket collections. To aggregate the data the way you want, you do not have to do any of that. You only need a single number per bucket to compute the minimum. Updating that accumulator is very cheap as there’s no memory allocations involved: just load, compare, and store the updated number. Moreover, that algorithm is easily to parallelize. Compute an array with these per-bucket minimums on different threads, wait for completion of all tasks, then aggregate multiple arrays computed by each thread into a single array with global minimums for each bucket. Then compute the final sum.