36 ms·

When you need efficient parallel map or reduction you often go back to low-level C loops wrapped in a pretty map/reduce/array package like numpy or R. I'd argu

When you need efficient parallel map or reduction you often go back to low-level C loops wrapped in a pretty map/reduce/array package like numpy or R. I'd argue that Einstein Summation like `C[i, j] = A[i, k] * B[k, j]` is much more natural than any composition of map reduce you may use to describe the loops of matrix multiplication.

dan-robertson 7y ago
Einstein summation for matrix multiplication isn’t really a great example because we have a perfectly good way to describe matrix multiplication without loops or sufficies or anything else: C = AB Rate is multiplication (and matrix-vector multiplication) is easy to denote. Tensor multiplication (well really tensor contraction) is annoying to denote and that is the point of summation notation. Notation is easier when there is less to denote: - Matrix multiplication: only one thing you can do (well you can add to but this distributes) - Tensor multiplication: all you can do is add, tensor product, and contract. First two are easy, last one you add extra notation for. This notation can also express permuting indices but this is the same as multiplication by a particular tensor and contraction so ok to do. - map,reduce,fold,etc. These can do quite a lot but not everything (eg processing multiple and in particular different data structures is often annoying. Processing things out of the usual order is often annoying. Processing eg consecutive elements is often annoying). One gets convenience for common things by making it impossible/hard to express uncommon things. If you see something that looks like map(f,x), you know the size of the input is the same as the size of the output and (hopefully) f acts independently on each element. - loops/tail recursion these give you more power to do things so looking at a loop there are many things that could possible happen and one must look carefully to find which.
- uryga 7y ago
  > Processing eg consecutive elements is often annoying the only place i saw a higher-order function for this is the K language with its `eachpair` combinator (spelled `':` iirc). i wonder why it isn't more common! (though in Haskell i'd just stick a `tails` somewhere to turn `[a,b,c]` into `[[a,b,c],[b,c],[c],[]]` and map over that)
MayeulC 7y ago
That might be true in some way, but having a map/reduce abstraction could help map the operation on a computing cluster if necessary, or more generally abstractions allow to make use of more complex processing techniques (that take into account cache locality, NUMA, advanced matrix multiplication algorithms [1], etc.). So, I would say that the thing you wrote is easier to understand if you look at the low-level code, but you have to look at it, while you could have the same overview at a high level, which provides a different perspective. In C++, that would be overloading the * operator to perform the loop in a method. It boils down to top-bottom vs bottom-up, I think. And even though I often use the looping technique, I feel like a lot of my code is spent writing these "useless" loops, while caring for the index, boundaries, etc. I really like vectorization as used in Matlab/Octave to deal with that sort of things, and I feel like this is an answer of its own to the topic. [1]: https://en.wikipedia.org/wiki/Matrix_multiplication#Complexity https://en.wikipedia.org/wiki/Matrix_multiplication#Complexi...

dan-robertson 7y ago

Einstein summation for matrix multiplication isn’t really a great example because we have a perfectly good way to describe matrix multiplication without loops or sufficies or anything else: C = AB Rate is multiplication (and matrix-vector multiplication) is easy to denote. Tensor multiplication (well really tensor contraction) is annoying to denote and that is the point of summation notation. Notation is easier when there is less to denote: - Matrix multiplication: only one thing you can do (well you can add to but this distributes) - Tensor multiplication: all you can do is add, tensor product, and contract. First two are easy, last one you add extra notation for. This notation can also express permuting indices but this is the same as multiplication by a particular tensor and contraction so ok to do. - map,reduce,fold,etc. These can do quite a lot but not everything (eg processing multiple and in particular different data structures is often annoying. Processing things out of the usual order is often annoying. Processing eg consecutive elements is often annoying). One gets convenience for common things by making it impossible/hard to express uncommon things. If you see something that looks like map(f,x), you know the size of the input is the same as the size of the output and (hopefully) f acts independently on each element. - loops/tail recursion these give you more power to do things so looking at a loop there are many things that could possible happen and one must look carefully to find which.

uryga 7y ago
> Processing eg consecutive elements is often annoying the only place i saw a higher-order function for this is the K language with its `eachpair` combinator (spelled `':` iirc). i wonder why it isn't more common! (though in Haskell i'd just stick a `tails` somewhere to turn `[a,b,c]` into `[[a,b,c],[b,c],[c],[]]` and map over that)

MayeulC 7y ago

That might be true in some way, but having a map/reduce abstraction could help map the operation on a computing cluster if necessary, or more generally abstractions allow to make use of more complex processing techniques (that take into account cache locality, NUMA, advanced matrix multiplication algorithms [1], etc.). So, I would say that the thing you wrote is easier to understand if you look at the low-level code, but you have to look at it, while you could have the same overview at a high level, which provides a different perspective. In C++, that would be overloading the * operator to perform the loop in a method. It boils down to top-bottom vs bottom-up, I think. And even though I often use the looping technique, I feel like a lot of my code is spent writing these "useless" loops, while caring for the index, boundaries, etc. I really like vectorization as used in Matlab/Octave to deal with that sort of things, and I feel like this is an answer of its own to the topic. [1]: https://en.wikipedia.org/wiki/Matrix_multiplication#Complexity https://en.wikipedia.org/wiki/Matrix_multiplication#Complexi...