4 ms·
This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on
by e-dant 5y ago
This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack.
MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abseil code last night that did some funky bit twiddling on ARM: https://github.com/abseil/abseil-cpp/blob/master/absl/hash/internal/low_level_hash.cc https://github.com/abseil/abseil-cpp/blob/master/absl/hash/i...
Off the top of my head, isn’t it about 200ns [edit, not ms] to query, bus, and read something from memory? Just a thought, perhaps the cache and memory is where we should focus our efforts.
- evandwight 5y ago> We nevertheless stress that such improvements are only of theoretical interest, since the huge constants involved in the complexity of fast matrix multiplication usually make these algorithms impractical. It's only for mathematical interest
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- nynx 5y ago200ns, not 200ms
- deleted 5y ago[deleted]
- gameswithgo 5y agothis article isn’t at all about doing it faster on actual hardware, and everyone has worried a lot about cache for decades now.
- gnufx 5y agoNot relevant to the article, but well-written single and double precision floating point large matrix GEMM on mainstream CPUs is basically computation-bound -- look at performance figures -- and is relatively unusual in that. (You probably need to worry about prefetching to get there, though.)
- kadoban 5y agoThis is kind of like "doctors are spending too much time curing cancer, they should worry about my bathroom, which is flooding!" Theoretical Computer Scientists aren't going to increase the size of your cache, that's just not what they're into or what they know anything about.