4 ms·

I wonder if one could write a truly statically typed tensor implementation with something like this. Where you can then say Tensor<f64, 16, 16, 2000> but also T

by panzi 3y ago

I wonder if one could write a truly statically typed tensor implementation with something like this. Where you can then say Tensor<f64, 16, 16, 2000> but also Tensor<bool, 32> and Tensor<f32, 4, 4> etc. Then some way of specializing for certain sizes to better use SIMD instructions etc. Even if it's just via something like `const if` inside of a single method, but with the assurance that the if is applied at compile time and thus e.g. illegal element access in the other branch is ignored etc.

eru 3y ago
Why not something like Tensor<element_type, index_type> where index_type can then be your 16 x 16 x 2000 or 32 or 4 x 4 etc?
- panzi 3y ago
  How would that work in Rust?
nerdponx 3y ago
From the perpsective pure type checking, Python/Numpy is heading in this direction: https://peps.python.org/pep-0646/#motivation https://peps.python.org/pep-0646/#motivation. However what you can't do without dependent types (as far as I know) is infer or verify statically that the transpose of a Tensor<f64,20,10> is a Tensor<f64,10,20>.
- gpderetta 3y ago
  Something like this you mean: https://gcc.godbolt.org/z/P8475n4sc https://gcc.godbolt.org/z/P8475n4sc? Edit: I think that dependent typing is needed only of the matrix bounds are only known at runtime.
cpgxiii 3y ago
In C++, Eigen comes pretty close to this interface for defining vectors and matrices and mixing size-at-compile-time and dynamically sized quantities. And then, given the size of the vectors/matrices being used, dispatching the appropriate SIMD implementation.
- panzi 3y ago
  You can do all except for the specialization in Rust for matrix + vector. You can do more in Rust about re-using temporaries (when one parameter to Add/Mul/... is a move). But you can't do arbitrary dimensional tensors or specialization for certain sizes in Rust. Also: Didn't know Eigen has tensor support now. I'm not actually very into this stuff, just recently played around what is possible in Rust in that context (and ran into compiler bugs in nightly).
rdedev 3y ago
I know about dfdx in rust that has type checked tensors for rank and shape. Don't know if it ticks all your boxes
hansvm 3y ago
That high-level idea is viable in many languages. I particularly like Zig's comptime as a clean way to implement it. You often don't want that sort of specialization. Code like deep neural nets is a pain to handle (unless each layer is identical, which is admittedly moderately common) even with variadic generics and especially without, and it's hard for the compiler to generate the right specializations for (and the right number of specializations; anecdotally, you can expect enough code bloat that it causes problems). Using branded types you can get a weak form of dependent typing and use that to get features like Tensor<f64, Dim<16>, Dim<MultipleOf<8>>, Dim<SensorChannel>>, where you're allowed to pass in concrete numbers, comptime-known constraints on runtime-known values, or even just weak information like that there's a particular brand (SensorChannel) on the type which allows you to match fully runtime-known values at compile-time and let the type-checker handle it (think of functions like matmul(Mat(A,B), Mat(B,C)), where the B has to be the same for both, but you very well might want to know it at runtime). It's still the library writer's job, unfortunately, to use `inline` and other such keywords appropriately to guide the compiler to the right number of specializations, but the API presented to people using that tensor library can be reasonably nice. Incidentally, Zig _also_ makes that second thing (branded types) easy to write. I hacked a demo together [0] if you'd like to play around with the concept, but a dedicated tensor library should eventually offer something less verbose IMO. If you're doing this with ML, my preferred strategy is to go the other way. Only write specializations that are easy for the chip to execute (e.g., appropriately aligned and length-aligned large powers of 2), and build code on top of that. If the computational kernel has to do padding or shifting or other garbage, even at the head/tail of a vector, then something in your model is horribly wrong anyway; just make that unrepresentable. [0] https://github.com/hmusgrave/pdv https://github.com/hmusgrave/pdv
menaerus 3y ago
Since the early 90's but in C++ through TMP and class template specializations. If you don't have many specializations, and those are sharing most of the code, you can simplify writing this code through if-constexpr since C++17. But soon after you will realize that you need to do some operations with those tensors such as A + B + C. To compute this expression compiler will first need to compute (A + B) sub-expression and store the result into the temporary tensor. Only then it will be able to use this temporary result to compute the final expression by adding the C tensor. When you have a lot of such expressions to compute, and expressions are arbitrarily complex, you will want to avoid inefficiencies caused by creating many temporaries - there's an attached cost to them both in memory and in compute. And sometimes you will be able to fuse multiple operations into a single one. This is a problem that can be solved with lazy evaluation and in C++ this can be done in compile-time through expression templates. And this is what basically all linear algebra C++ libraries are famous of doing.
- panzi 3y ago
  In Rust you can implement Add for all kinds of combinations of types. I.e. when one of the parameters moves it's ownership you can just perform the operation in-place in that parameter and return it. So you can eliminate temporaries at compile time. It means much more work in the library, but the library user can just write A + B + C. So Rust has that and C++ has template specialization, const if, and variadic templates. Would be cool to have all in one language.
  - menaerus 3y ago
    But we already do. > So you can eliminate temporaries at compile time. > ... but the library user can just write A + B + C ... > So Rust has that. Eliminating temporaries in C++ is also done in compile-time through expression templates or more generally through TMP. I'm pretty sure Rust type system is incapable to express many (?) of the TMP things from C++ - it does not even support partial specializations to begin with so it's hard to imagine that you can do a lot of TMP gymnastics. I think that this is an area where it is generally accepted that Rust is lacking against C++.

by panzi 3y ago

eru 3y ago

Why not something like Tensor<element_type, index_type> where index_type can then be your 16 x 16 x 2000 or 32 or 4 x 4 etc?

panzi 3y ago
How would that work in Rust?

nerdponx 3y ago

From the perpsective pure type checking, Python/Numpy is heading in this direction: https://peps.python.org/pep-0646/#motivation https://peps.python.org/pep-0646/#motivation. However what you can't do without dependent types (as far as I know) is infer or verify statically that the transpose of a Tensor<f64,20,10> is a Tensor<f64,10,20>.

gpderetta 3y ago
Something like this you mean: https://gcc.godbolt.org/z/P8475n4sc https://gcc.godbolt.org/z/P8475n4sc? Edit: I think that dependent typing is needed only of the matrix bounds are only known at runtime.

cpgxiii 3y ago

In C++, Eigen comes pretty close to this interface for defining vectors and matrices and mixing size-at-compile-time and dynamically sized quantities. And then, given the size of the vectors/matrices being used, dispatching the appropriate SIMD implementation.

panzi 3y ago
You can do all except for the specialization in Rust for matrix + vector. You can do more in Rust about re-using temporaries (when one parameter to Add/Mul/... is a move). But you can't do arbitrary dimensional tensors or specialization for certain sizes in Rust. Also: Didn't know Eigen has tensor support now. I'm not actually very into this stuff, just recently played around what is possible in Rust in that context (and ran into compiler bugs in nightly).

rdedev 3y ago

I know about dfdx in rust that has type checked tensors for rank and shape. Don't know if it ticks all your boxes

hansvm 3y ago

That high-level idea is viable in many languages. I particularly like Zig's comptime as a clean way to implement it. You often don't want that sort of specialization. Code like deep neural nets is a pain to handle (unless each layer is identical, which is admittedly moderately common) even with variadic generics and especially without, and it's hard for the compiler to generate the right specializations for (and the right number of specializations; anecdotally, you can expect enough code bloat that it causes problems). Using branded types you can get a weak form of dependent typing and use that to get features like Tensor<f64, Dim<16>, Dim<MultipleOf<8>>, Dim<SensorChannel>>, where you're allowed to pass in concrete numbers, comptime-known constraints on runtime-known values, or even just weak information like that there's a particular brand (SensorChannel) on the type which allows you to match fully runtime-known values at compile-time and let the type-checker handle it (think of functions like matmul(Mat(A,B), Mat(B,C)), where the B has to be the same for both, but you very well might want to know it at runtime). It's still the library writer's job, unfortunately, to use `inline` and other such keywords appropriately to guide the compiler to the right number of specializations, but the API presented to people using that tensor library can be reasonably nice. Incidentally, Zig _also_ makes that second thing (branded types) easy to write. I hacked a demo together [0] if you'd like to play around with the concept, but a dedicated tensor library should eventually offer something less verbose IMO. If you're doing this with ML, my preferred strategy is to go the other way. Only write specializations that are easy for the chip to execute (e.g., appropriately aligned and length-aligned large powers of 2), and build code on top of that. If the computational kernel has to do padding or shifting or other garbage, even at the head/tail of a vector, then something in your model is horribly wrong anyway; just make that unrepresentable. [0] https://github.com/hmusgrave/pdv https://github.com/hmusgrave/pdv

menaerus 3y ago

Since the early 90's but in C++ through TMP and class template specializations. If you don't have many specializations, and those are sharing most of the code, you can simplify writing this code through if-constexpr since C++17. But soon after you will realize that you need to do some operations with those tensors such as A + B + C. To compute this expression compiler will first need to compute (A + B) sub-expression and store the result into the temporary tensor. Only then it will be able to use this temporary result to compute the final expression by adding the C tensor. When you have a lot of such expressions to compute, and expressions are arbitrarily complex, you will want to avoid inefficiencies caused by creating many temporaries - there's an attached cost to them both in memory and in compute. And sometimes you will be able to fuse multiple operations into a single one. This is a problem that can be solved with lazy evaluation and in C++ this can be done in compile-time through expression templates. And this is what basically all linear algebra C++ libraries are famous of doing.

panzi 3y ago
In Rust you can implement Add for all kinds of combinations of types. I.e. when one of the parameters moves it's ownership you can just perform the operation in-place in that parameter and return it. So you can eliminate temporaries at compile time. It means much more work in the library, but the library user can just write A + B + C. So Rust has that and C++ has template specialization, const if, and variadic templates. Would be cool to have all in one language.
- menaerus 3y ago
  But we already do. > So you can eliminate temporaries at compile time. > ... but the library user can just write A + B + C ... > So Rust has that. Eliminating temporaries in C++ is also done in compile-time through expression templates or more generally through TMP. I'm pretty sure Rust type system is incapable to express many (?) of the TMP things from C++ - it does not even support partial specializations to begin with so it's hard to imagine that you can do a lot of TMP gymnastics. I think that this is an area where it is generally accepted that Rust is lacking against C++.