Memory and Native Code Performance(infoq.com)
infoq.com
Memory and Native Code Performance
http://www.infoq.com/news/2013/06/Native-Performance
6 comments
I'm a decent coder but don't know about anything near the metal.
Is there a good introductory resource for learning about low-level details like the ones discussed in the post?
Is there a good introductory resource for learning about low-level details like the ones discussed in the post?
Try Drepper's (of GNU library fame) What every programmer should know about memory.
http://www.akkadia.org/drepper/cpumemory.pdf
Slightly dated but still excellent introduction.
http://www.akkadia.org/drepper/cpumemory.pdf
Slightly dated but still excellent introduction.
If you're willing to pay - this is probably the canonical textbook.
http://www.amazon.com/Computer-Organization-Design-Fourth-Ed...
http://www.amazon.com/Computer-Organization-Design-Fourth-Ed...
And this why -Wpadded is always a useful clang/gcc flag to enable when doing optimisations
summary of this and every other article: make sure you're doing sequential scans in your tight inner loop, and ideally also exploit memory alignment and cache sizes while you're at it.
I don't understand the "Multi-core effects" one. Surely the linear memory scans in c[i] = a[i] + b[i] will result in cache prefetch and thus be limited by memory bus bandwidth and not cache size?
I suspect that a better matrix multiplication algorithm would have a much more dramatic effect on performance than improving the memory access pattern:
https://en.wikipedia.org/wiki/Strassen%27s_algorithm
Constant factor improvements are great, but asymptotic improvements are better.
https://en.wikipedia.org/wiki/Strassen%27s_algorithm
Constant factor improvements are great, but asymptotic improvements are better.
You should benchmark, but you are probably wrong. The whole talk was about how hardware (i.e. memory accesses) matters. Even the Wikipedia article you linked to suggests this.
"Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations. However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)."
"Earlier authors had estimated that Strassen's algorithm is faster for matrices with widths from 32 to 128 for optimized implementations. However, it has been observed that this crossover point has been increasing in recent years, and a 2010 study found that even a single step of Strassen's algorithm is often not beneficial on current architectures, compared to a highly optimized traditional multiplication, until matrix sizes exceed 1000 or more, and even for matrix sizes of several thousand the benefit is typically marginal at best (around 10% or less)."
Sure, but that benefit will become increasingly large as the problem size is increased. Benchmarking should be done, of course, but only as a way to determine where Strassen's algorithm begins to dominate. Note also that that quote supports what I said, at least in the limit: Strassen's algorithm does improve performance more dramatically for large problem sizes (though how much more dramatically is certainly debatable).
I am not going to deny that hardware matters, but it is important to know where it matters. Hardware matters in terms of constant factors. For sufficiently large problem sizes, hardware might give you a 10x improvement if you use it correctly -- but that is 10x no matter how large the problem size becomes. An algorithmic improvement will become increasingly beneficial as the problem size increases; that is why we speak of things like "crossing points," where an asymptotically faster algorithm begins to dominate. Even very poor use of hardware features (terrible locality of reference, etc.) will eventually be irrelevant for an asymptotically better algorithm; a large number of really good uses of the hardware is still slower than a small number of really bad uses.
I am not going to deny that hardware matters, but it is important to know where it matters. Hardware matters in terms of constant factors. For sufficiently large problem sizes, hardware might give you a 10x improvement if you use it correctly -- but that is 10x no matter how large the problem size becomes. An algorithmic improvement will become increasingly beneficial as the problem size increases; that is why we speak of things like "crossing points," where an asymptotically faster algorithm begins to dominate. Even very poor use of hardware features (terrible locality of reference, etc.) will eventually be irrelevant for an asymptotically better algorithm; a large number of really good uses of the hardware is still slower than a small number of really bad uses.
Sometimes the problem size doesn't increase. Sometimes you maybe just need to do lots and lots and lots and lots of small matrix multiplications.
Most algorithms complexity is accounting only over ALU ops in assumption that memory load/stores are free. Strassen seems to be using more memory bandwidth than the naive multiplication so it's likely to be even slower.
"Most algorithms complexity is accounting only over ALU ops in assumption that memory load/stores are free."
That is not true. Asymptotic analysis assumes that memory loads/stores have uniform cost, not that they have no cost at all. You do not see loads/stores included explicitly in algorithmic analysis because typically a load/store will appear in conjunction with some other operation, so the cost is just rolled together as part of the constant factor.
"Strassen seems to be using more memory bandwidth than the naive multiplication so it's likely to be even slower."
Only for small problem sizes. As the problem size increases, Strassen's algorithm will dominate. The Wikipedia article suggests that the "crossing point" is somewhere in the thousands range (i.e., an NxN matrix where N is several thousand), and after that Strassen's algorithm becomes increasingly faster. To put it another way, a small number of expensive operations will still be faster than a large number of cheap operations (for some value of "small" and "large," but the difference will increase as the problem size increases).
That is not true. Asymptotic analysis assumes that memory loads/stores have uniform cost, not that they have no cost at all. You do not see loads/stores included explicitly in algorithmic analysis because typically a load/store will appear in conjunction with some other operation, so the cost is just rolled together as part of the constant factor.
"Strassen seems to be using more memory bandwidth than the naive multiplication so it's likely to be even slower."
Only for small problem sizes. As the problem size increases, Strassen's algorithm will dominate. The Wikipedia article suggests that the "crossing point" is somewhere in the thousands range (i.e., an NxN matrix where N is several thousand), and after that Strassen's algorithm becomes increasingly faster. To put it another way, a small number of expensive operations will still be faster than a large number of cheap operations (for some value of "small" and "large," but the difference will increase as the problem size increases).
Well, I will take your word for it - the wiki article is only talking about additions and multiplications and only counting them, even though it mentions that it uses up to four times more memory I don't see where it's been accounted for.
>Only for small problem sizes. As the problem size increases
This is the difference between software engineering and computer science. The real problems do not grow in size quite often. If I am writing a 3D engine I do not expect my matrices suddenly grow. Ditto if I am solving some linear system derived from a real model - it's unlikely that the model properties are going to change any time soon.
>Only for small problem sizes. As the problem size increases
This is the difference between software engineering and computer science. The real problems do not grow in size quite often. If I am writing a 3D engine I do not expect my matrices suddenly grow. Ditto if I am solving some linear system derived from a real model - it's unlikely that the model properties are going to change any time soon.
The memory access cost is part of the cost of arithmetic -- the operands and results need to be read from and written to memory. It is not explicitly counted because the precise sequence of events is very architecture-specific (in a register machine, there will be load/store operations; in a three-address architecture, memory is explicitly accessed by each opcode; in a stack machine, operands need to be pushed onto the stack; etc.), but in any RAM machine the cost of memory access is constant (i.e., it is upper bounded by a constant -- it may be faster if you already have the data in a register or a cache, but the worst case does not depend on the input size or algorithm being run).
As for problem sizes not growing, I think your view is a bit limited. For example, matrices in a financial model might become larger if any number of parameters change -- the time period, the number of instruments, etc. Sure, there are cases where you can guarantee that the problem size will not change -- but one of the big advantages of software is that it can scale arbitrarily (unlike a matrix multiplier circuit).
As for problem sizes not growing, I think your view is a bit limited. For example, matrices in a financial model might become larger if any number of parameters change -- the time period, the number of instruments, etc. Sure, there are cases where you can guarantee that the problem size will not change -- but one of the big advantages of software is that it can scale arbitrarily (unlike a matrix multiplier circuit).
Some problem sizes grow, some don't. Sorry, if you think that asserting that both exist somehow limited my view.
You are both technically correct and at the same time do not have an idea of what you are talking about. The break even point for these algorithm is so huge that even at say Google scale it does not matter. Data access latency plays an overwhelmingly more important role.
The break-even point for Strassen's algorithm is not unrealistic -- it is around the 1000x1000 range. You might be thinking of the best known algorithms:
https://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm
Strassen's algorithm is certainly used in practice.
https://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm
Strassen's algorithm is certainly used in practice.
I guess this is true, but it's sort of misleading. Adding some details as I understand them:
1) On Sandy Bridge, a read from cache takes the same amount of time whether you are reading a single byte or a 32 byte AVX vector. That said, it is often faster though to read integers individually than to read them as a vector and split them.
2) While the L2 latency is comparable to taking a single square root, if using an XMM register, you can also take 4 square roots in the same number of cycles. Viewed this way, if you can use SIMD, you could consider each square root to be comparable to an L1 hit.
3) For DDR3-1600 10-10-10 (current fast standard) a read from main memory will take 12.5 ns to start returning data. At 4GHz, this is 50 CPU cycles. DDR3-1333 10-10-10 is 15 ns --- about 60 cycles. This is about twice as long as a read from L3: longer, but not "far, far longer".
[Note to author: s/26 bytes/26 cycles/]