Lightning Talk: Let's Fix Sparse Linear Algebra with C++. It'll Be Fun and Easy! - Benjamin Brock
Vložit
- čas přidán 18. 05. 2024
- cppcon.org/
---
Lightning Talk: Let's Fix Sparse Linear Algebra with C++. It'll Be Fun and Easy! - Benjamin Brock - CppCon 2023
github.com/CppCon/CppCon2023
Sparse linear algebra is hard. There are a large variety of different sparse linear algebra formats, and they all require obtuse index arithmetic in order to use. But what if we could fix this? In this talk, I'll present an idea for "fixing sparse linear algebra" using customization points, the ranges library, and high-level multi-dimensional iteration.
---
Benjamin Brock
Ben Brock is a PhD student at UC Berkeley, where he works on building libraries, tools, and algorithms for high-performance computing. His main work focuses on building a cross-platform library of data structures for distributed applications, with a focus on sparse linear algebra and graph algorithms. Ben is also a member of the GraphBLAS Languages Committee and is involved in drafting the C++ GraphBLAS API Specification.
---
Videos Filmed & Edited by Bash Films: www.BashFilms.com
CZcams Channel Managed by Digital Medium Ltd: events.digital-medium.co.uk
---
Registration for CppCon: cppcon.org/registration/
#cppcon #cppprogramming #cpp - Věda a technologie
That guy is a genius
This is nice! I want a modernized Eigen that uses these kinds of techniques.
Did I just see a C++ repl??
Yes. It is implemented in a very brute force way, all is recompiled and executed again after each line. The redundant output is suppressed. See other talks by the same author. It is ok for very small programs. but I guess it doesn’t scale well and it penalizes typos a lot.
the future is now!
I honestly think this looks like an overengineered solution if all you use this for is basically a foreach loop. It would make more sense at that point to just traverse through the values array and use functions like get_i(ptr) and get_j(ptr) if necessary (or equivalently with indices instead of pointers), that would also solve the part of making mistake with various indices. Maybe the compiler will optimize away all those templates, ranges etc., but maybe it won't, and the benefit over those more simple functions just doesn't seem to be there to me (but I also am not very excited about syntax sugar, so maybe I just don't get that part of it).
The benefit of ranges are that they are composable and greedy.
Yeah, the thing about iterators is performance. Hard to say how the thing is going to be optimized. It's better to focus on optimized binary operations between (sparse matrix * sparse matrix), (sparse matrix * dense matrix). Also optimize expressions of those binary operations.
The examples are a bit under-complex, I will give you that. But get_i(ptr) is a binary search with CSR, so your "solution" isn't one. I have found myself implementing a split_by_offsets view adaptor in C++23 which is basically a raw building block of this more thought through abstraction. The great thing is that you can not only do these nested range-based loops but also throw range based algorithms at your sparse problems with minimal boilerplate. If you don't see the point of this kind of abstraction I probably wont be able to turn that around but to me this is great. Because ranges can be views, this makes the APIs compatible with matrix-free methods like finite-difference stencils as well.
Fun, but is it fast?
Yes, it is, more x1000000 faster than your main programming language Javascript.