Lazy evaluation and operation ordering
- Dominant language
- Rust
- Stars
- 4.8k
- Forks
- 565
- PR merge metrics
- No merged PRs in 30d
Description
This questioning stems from how Eigen works.
Eigen heavily relies on lazy evaluation which enables it to be smarter than most linear algebra libraries by dodging a possibly very large number of operations:
https://eigen.tuxfamily.org/dox/TopicLazyEvaluation.html
http://eigen.tuxfamily.org/index.php?title=EigenInternals
### Examples:
`v1 = a*v2 + v3` can be computed faster by not allocating an intermediate array for storing `a*v2`.
On some matrices, `mat1 = mat2 * (mat3 + mat4)` may be computed more efficiently by allocating temporaries, while on others it could be faster to iterate several times.
Also (not sure if that's done in Eigen though) product `A*B*C` may faster/less costly to compute as `(A*B)*C` or as `A*(B*C)`.
### Questions:
It looks like nalgebra doesn't do anything like this (yet?), and instead leaves it to the user to write the operations in the way they believe it will be the most efficient.
1. Would nalgebra have interest in supporting something like this?
2. Is there any work that has already been done on the topic?
3. How much would there be to gain? (I couldn't find references of other libraries than Eigen doing this. Is that because there's almost nothing to gain?)
4. If we wanted something like this, should it be within nalgebra replacing the non-lazy current counterparts, aside to the non-lazy counterparts, or implemented as a wrapper around nalgebra? (this probably depends on the runtime impact of establishing the execution plans, on the complexity of the corresponding type system, and on 3.)
Obviously this would be a very complex topic because there's tons of stuff with an impact on performance that could theoretically be delegated so that would probably be a complex type system to figure out, and there's also a ton of heuristics that could be used to choose the best execution plan: based on matrices sizes (how to handle dynamic?), impact of memory placement (row major order/column major order, sparse/not sparse), whether to optimize computation time or CPU load (user pref. based on how much of these operations run at the same time, maybe choose whether to parallelize matrix multiplications based on this)...
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.