[Pre-RFC] Linear algebra primitives (vectors,matrices,...)

language design
1

[Pre-RFC] Native support for linear algebra primitives: vectors, matrices, ...

Looking for comments here to not open RFC for something that could be instantly rejected / can be easily improved. I am somewhat new to Rust - sorry if i missed some features this conflicts with. Closest existing RFCs/rustc PRs to this i found were all about SIMD

Summary

Add built-in vector, matrix and quaternion types with swizzles (.xyzw/.rgba), indexing, math overloads and SIMD backend.

Motivation

Fragmented ecosystem (nalgebra, glam, vek, cgmath, dozen others and manual implementations (to not add dependencies)) cause duplication, conversion overhead (cognitive and performance), extra deps, inconsistent and inconvenient syntax. Vectors match SIMD. Builtins would unify, optimize, cut compile times for graphics (realtime, offline for 3d software, image processing, game engines)/physics (both 2d and 3d)/ML.
This would make Rust a step closer to being adopted by gamedev industry, including its usage as GPU shading language.
Value of syntax sugar for mathematics is high*, some features of e.g. C++ (templates/overloads) are often the only used features and used for math (e.g. GLM).
* Mathematicians/physicists invent new symbols just to shorten expressions all the time, we use one-letter notations to type less, etc.

Guide-level explanation

New types; aliases f32vec4=vec4, vec4=f32vec4.

let v: vec4<f32> = vec4(1 as isize, 2.0, 3.0_f64, 4u32); // implicit casts
let swizzled: vec4 = v.xyzw; // .xyzw swizzled in same order as original elements 
let mut sw2: f32vec3 = v.xyx; // .xyx swizzled first three elements
let v2: f32vec4 = vec4(v); // v2 is constructed from entire v
let v3: f32vec4 = vec4(v.xx, v.yy); // v3 is constructed from two copies of first and two copies second elements of v
let v4: f32vec4 = vec4(v.zzz, 42); // v4 is constructed from three copies of third elements of v and 42_f32
sw2.xz += 100.0; // add 100.0 to first and third elements
let color = v.rgba; // alternative syntax for swizzles, corresponding to .xyzw. Represents color
let elem = v[1]; // access second element with indexing syntax
let sum = v + vec4(5.0, 6, 7, 8.0); // element-wide math
let dot = v.dot(sum); // method `dot` represents mathematical dot product

let m: mat4x4<f32> = mat4x4::identity();
let col = m[2];
let val = m[2][1];
let mul = m * v; // multiplies vector by matrix, e.g. 3d geometry transformations in rasterization 

let q: quat<f32> = quat(0.0,0.0,0.0,1.0);
let rotated = q * v; // rotation by quaternion

let casted: vec4<i32> = v as i32vec4; // same as per-element `as` cast

Reference-level explanation

N=2-4; T=f32/f64/i8-i64/u8-u64
vecN<T> (aliases to TvecN); matMxN<T> (major?, aliases to TmatMxN); quat<T> (aliases to Tquat)

  • writable/readable swizzles; indexing; element-wise ops; matrix/quat mul and other overloads
  • casts: 'as' same-size; From/Into arrays
  • backend: std::simd

Drawbacks

Extra complexity, syntactical exceptions, "magic", compiler speed/size, some work needs to be done to existing vector libraries.

Rationale and alternatives

Built-ins enable syntax that libs can't have. Fixed 2-4D covers 99% of usecases. In many projects linear linal is primary reason for operator overloads usage (many C-like C++ projects with GLM). Pretty much every Rust game/graphics/physics lib depends on one or more linal libs, and when combining those you have to "glue" them together. Adding this feature would make gamedev a lot more appealing in Rust, make graphics programming less painful, help projects like Rust-GPU (and integrate with things like std::offload).

This proposal looking unexpected is understandable. But consider something you are very familiar with - floats. Floats existed in before IEEE 754 standard, and pretty much every language has them. As well as integer mathematics. Even if operations on those do not end up as trivial assembly (e.g. integer division in Rust produces a branch with zero-division check). Yet everyone understands and expects "builtin sugary" syntax for both floats and integers.
Imagine the ecosystem if there were no builtin floats. "Yes, we have instructions that map directly to float operations, but we also have vector instructions - so what? There is million ways one could implement floating point numbers - have or not have checks, precision, comparisons, pretend as if it associative or not, NaN policy, zero policy, etc. Someone could want 128 integer fixed point floats, someone could want packed 24-bit floats in range from 0 to 1. Something as complex and variable as floats could and should be implemented as a library"

Could this be done in a library or macro instead? Yes, this is mostly syntactical change. I do think, however, this syntactical sugar is worth way more than added complexity. Alternatively, something could be done to:

  • allow creation of as casts / implicit casts
  • allow writeable swizzles to exist (e.g. struct that contains compile-time known zero-size mutable reference to memory sections of its owner)
  • allow some sort of overloads (or deal with macro expansions)

Currently, if someone wants nice linal syntax, they can:

  • use some other language (complicated build, potentially glue code). That is what most people currently do with GLSL, HLSL, WGSL, etc.
  • create a preprocessing system for desugaring, that would run before compilation (complicated build, error-prone, slow, no rust-analyzer integration)
  • pay compile & runtime fee (for half the syntax) but keep everything in Rust

Prior art

Language Swizzles syntax sugar Constructors Elementwise operations Matrix * Vector Mul Vector casts
Odin Yes, with writes explicit elements Yes Yes (m * v) explicit per-element
GLSL Yes, with writes overloaded fill, implicit casts, from others Yes Yes (m * v) explicit constructors, downcasts
WGSL Yes, reads + single-component writes overloaded fill, from others Yes Yes (m * v) explicit constructors, down/up casts
HLSL Yes, with writes implicit casts, from others Yes Yes (mul(m, v)) implicit/explicit, downcasts
Metal Yes, with writes overloaded fill, implicit casts, from others Yes Yes (m * v) explicit
C (GCC/Clang extensions) No expli cit elements Yes No (manual) implicit/explicit same-size
Zig No explicit elements Yes No (manual) explicit

Odin (which many people know as gamedev-oriented language). Shading languages have obvious success (no one really writes their shaders in C, even when programming a language that supports SPIR-V via LLVM).

It is hard to compare languages in that regard because of unique differences and the fact we are comparing syntax.

Unresolved questions

Dims limit; quats/complex; alignment (possibly just std::simd?); (row/column) major; at which level is this implemented.

Future possibilities

Arbitrary-sized integers/floats in vectors and integer vector sizes.

3 Likes
2

Ok, so here is something I always meant to create a pre-RFC, but never got around collecting references (such as the exact number of crates that implement this, and how they are used, and pain points in interop) and prior discussion. But

In this area, what I really want out of the stdlib is a type that represents a dense, row-major 2D matrix with dynamic size and contiguous elements - something as analogous to a 2D version of Vec as possible. Possible names include Vec2D and DMat.

This exact same type has a lot of usage in the Rust ecosystem (much more than a chiral variant like a column major matrix with the same characteristics - maybe because row major is C's default), and it's not just in linear algebra but whenever people want tabular data to be densely packed. So this type has been defined dozens of times. I once saw even an interoperability crate (that ~nobody uses so they are pointless n+1 standards), but I can't find i right now.

Fortunately, due to the very precise data layout requirements such a type has, usually you can cheaply convert between them (usually by passing around raw pointers and calling an unsafe API), Even if one type is row-major and the other colum-major, such conversion is also cheap (though it may be expensive to iterate in the non-preferred dimension). It's like if Vec didn't exist in the stdlib, the multiple implementations would normally be convertible to each other cheaply, because the heap-allocated buffer (the expensive thing to copy) would always be laid out the same in memory. So this issue is more like a papercut rather than a showstopper.

But it's exactly because it's a papercut that it got unaddressed for so long, and papercuts compounds over time.

And I don't think that Rust should wait so that custom DSTs are available. It would make borrowing such a type more ergonomic, but in absence of that there is already precedent in the Rust ecosystem to make Something and SomethingRef types. And if custom DSTs ever land, just make the ref type an alias, like the situation between Infallible and !.

I remember seeing a very old discussion about this, and it stalled because there's more than one way to describe 2D slices. I think that the conventions Rust Index trait naturally leads to a 2D slice with strides, similar to the imgref crate, and that's because in Rust it's usual to be able to index with ranges, and with a pair of ranges you can index a small rectangle inside the matrix (see the image in that crate's readme). That's not the absolutely most efficient a slice can be, but it's just one word for greatly added flexibility, exactly the cost of passing around Vec<T> with fixed size vs Box<[T]>.

3 Likes
3

Most of the (all of the relevant) linalg crates provide feature flags for interoperability via the mint crate. I don't know of an interoperability crate for dynamic matrices.

Of note, for graphics and physics linalg applications, everyone agrees that the matrix representation is basis-major. This means that transformation matrices are always[1] laid out in memory as

{
    .i = { .x, .y, .z, .w },
    .j = { .x, .y, .z, .w },
    .k = { .x, .y, .z, .w },
    .t = { .x, .y, .z, .w }
}

The difference, then, between column-major or row-major is effectively syntactical; whether the xyzw basis vectors are treated as being row or column vectors, and thus which direction the math is done in. If you have use a column-major convention, then the vector is multiplied on the right (pan * rotate * scale * point), but if you use a row-major convention the vector is multiplied on the left (point * scale * rotate * pan) for the exact same mathematical result (modulo the non-associativity of floating point).

You can't even really sidestep the split by using methods instead of *, unfortunately. A chain of pan.and_then(rotate).and_then(scale) could be read to compose in either order, depending on if you read this as applying the transforms relative to the intrinsic origin/basis (which get transformed as the transformation pipeline is applied) or relative to an extrinsic origin/basis (meaning the origin for the transformations is the same for each step of the transformation pipeline).

I believe the Rust ecosystem has consensus on using the column-major convention for linalg math.

However, you're accurate about Vec2D for tabular data being conventionally row-major. So it's really a major initial design decision that needs to be made:

The goal here is specifically for linear algebra pieces like are used for CG and physics simulation, not arbitrary data matrices. Vec2D is an important target as well, but mostly orthogonal to linalg.

Rust is strict about primitive numeric conversions; even for completely lossless integer extension, we require as or .into(). Linalg support wouldn't be any different, and also benefits from that type correctness.

Your vec4 method would be a macro, but otherwise would work fine. Similarly, almost all types in Rust are TitleCase. You'll need a good argument as to why the linalg types should have lowercase names. std::simd uses a Simd<T, N> type with aliases like f32x4 = Simd<f32, 4>.

The correct semantics of swizzling is to immediately pull out a new vecN, not to return some kind of shim which can then be converted by ref to vecN, extracting the right elements. That trick "works" in C++ to fake member syntax if you always do vec3 q = v.yzx with an explicit type result, but if you use the type inference of C++ auto / Rust let, you're going to create a bad time.

So, honestly, what's problematic about swizzles via methods (i.e. v.yzx())? The extra syntax noise is minimal, and the semantics of a method call are clear and already exist as opposed to magic field access syntax swizzling.

I hold that the only reason most C++ linalg implements field syntax swizzling is that's the default in GLM (explicitly to imitate GLSL syntax in C++ as much as possible) despite the technique being incompatible with the C++ standard memory model.

If we do swizzles via method syntax, the only reason left for these types to be builtins is as casting. And there, most of the people working on the language are roughly in consensus that we want to deprecate as — it does too many disparate things. What the replacements will look like is still an open question, but it's unlikely that we'll give as even more uses.

Ultimately I think that Rust doesn't need an RFC for linalg support in core. It does want an ACP (basically an RFC for pure library API), but I don't think we're quite ready yet.

The Rust-GPU work will likely get the data parts into core in some form, but I expect operations to be not in core for a while yet.

  1. At least, in any sane implementation. Determining the sanity of shading languages is left as an exercise to the reader. ↩ī¸Ž

8 Likes
4

Why linalg for graphics specifically? Why not also support tensores for ML or big sparse matrices for number crunching? Seems rather strange to me to why graphics/physics in particular should be favoured here.

2 Likes
5

It could be a macro, sure. In fact, i have a decl macro library to do exactly that - cast via as elements of vectors of different types. It adds some compilation time tho. I imagine math-heavy code could suffer from more feature-full macro expansion bloat.

Right, makes sense. We could have "untyped vector" (not sure whats the correct term), like integers, with implicit conversion to the needed type. E.g.

let v: vec2<f32> = vec2(1, 2.0);

Since vectors contain multiple values (like nothing else among Rust primitives), we could also have "non-finished vec of values with exact type, that does not necessarily match target element type" that later can be explicitly (but implicitly on per-element level) be casted to target type. E.g.

let v: vec2<f32> = vec2(1 as usize, 2.0 as f64) as _;

No ability to write to swizzles. E.g.

let v = vec4<f32>(1,2,3,4);
let s = v.grab();
assert_eq(s, vec4(2,1,4,3));

Would is possible with swizzles-are-functions (current). But not this:

let v = vec4<f32>(1,2,3,4);
v.grab = vec4<f32>(5,6,7,8);
assert_eq(v, vec4(6,5,8,7));

Maybe a good idea (syntactically) is to allow tuples here:

let v = vec4<f32>(1,2,3,4);
v.grab = (5.0,6.0,7.0,8.0);

I understand how this makes sense from some philosophy point of view, but im not sure if this should be a valid argument against such proposal.

Syntax is the point. Maybe a better argument would be some statistics on gamedev people opinion, but i have no idea how to get it. Anyone reading this, please comment if this could (or not) remove friction from your development.
To most people who would be interested in this change, swizzle syntax is not new. Also, returning back to a comparison with floating point numbers, their quirks (multiple NaN invariants, multiple different zeros, Infinities, associativity) are obvious to pretty much no one, yet we have them as primitive types.
Syntax is just syntax. But compare set of shaders in Rust and same shaders in GLSL and

I absolutely understand how such simple syntax changes look unnecessary to regular systems programming people.

I am not sure if that is "allowed", but the feature could be forever feature-gated.

6

Also reply to @dlight
This proposal is for compile-time sized, "value types", which Copy and Clone (sorry if did not make it clear in rfc text). It only (currently) covers up-to-4 "const" dimensions (i.e. no runtime-sized vector or matrix), and " Future possibilities" implies compile-time sizes only, too.
As i said, it covers 99% of usecases for some specific areas (gamedev). It might be useful for ML, but it is not targeted at it.
Why no ML runtime sized primitives:
they do not map to hw directly (i.e. amount of executed instructions varies substantially, a lot of instructions are generated, and memory is not in some specialized registers). This is a better fit for library in terms of functionality, but as far as i can see (not far lol), ML also usually likes short, concise syntax (thats why their interfaces are all python/ic). So there is some value for Rust. However

  • ML-related things are usually not-as-integrated into something else (as far as i understand), unlike gamedev/graphics
  • ML algorithms are not 1 specific algorithm, but they are all different, and every library (pytorch) has a ton of magic to execute different algorithms with different data layouts and interoperate between them.
  • ML is still evolving (whereas 4-component f32 vectors have been used in gamedev for longer than i have been alive)
7

Speaking of complex numbers, there is already an RFC proposed for the standard library. Just bringing it to notice. RFC 3892

4 Likes
8

I would say that the ideal would be a generic d dimantion tensor with generic shape a_1...a_d. This is (I presume) the most general extension for vectors, and would be extremely nice for ML for example (as well as other "math" things). The problem is that (as far as I know) this ideal solution is impossible as it has arbitrary number of generic values. Btw, unbounded number of generic parameters would be really, really usefull in general.

1 Like
9

I think the core problem that you're going to run into is scoping this.

For something to be in the standard library, it needs to be, in a sense, the "obvious" thing. If you look at the current conversations about adding a complex type, it can plausibly happen because everyone seemingly agrees that the only real option is the Cartesian version.

For matrices, though, you'll quickly run into a bunch of problems around how differently you want them to work for something like images vs scientific computing vs something like ML vs something like game projection matrices. Said otherwise, there are lots of different existing crates that work differently, and thus it's not obvious that any of them are the right choice for std.

As a result, I think you might be better off trying to come up with maybe some traits or some other simple abstractions that could be unified, without unifying everything. Imagine you found a 2D versions of [_], for example, so that all the different matrix types could deref to that, and thus lots of things could be written over that, even if the different strategies for growing or creating were different. (Like how [_] can be used with both Vec<_> and [_; N].) I don't know what that would be, but if it could exist that'd be nice. (It might also be that without custom DSTs it can't really work yet, which also might keep it out of std for a long time.)

Practically, if you wanted to make progress here you might want to help push portable_simd along, because if you want these things simd-accellerated you probably need that as an underlying thing, so it might be that libs-api wouldn't accept a bigger thing until the building block is in good shape.

5 Likes
10

For additional prior art, the D language supports swizzling through its opDispatch mechanism. See it in use by the gl3n library. I don't know how much Rust can take from it as it inserts itself right into name lookup with user-provided code to conjure up dynamic properties.

1 Like
11

I feel like i named the RFC wrong and made a mistake of mentioning ML. Original proposal is not for runtime-sized matrices/vectors, they are non-trivial and have multiple different implementations out there. I agree that such topic would be a lot harder to get everyone agree on. And syntax (e.g. swizzles) would not even make sense for dynamically sized vectors/matrices. I will explicitly mention this in RFC (good, we found something to improve in RFC).

For proposed changes, i believe, everyone would agree on most of the implementation details. There is no "unsolved" questions, every library in every language does pretty much the same.

I believe portable_simd is already ready enough, but i am not sure.

12

One problem you might run into is that SIMD unfortunately has different floating-point semantics than scalars (just plain floats) on some platforms, e.g. 32-bit Arm SIMD (Neon) will flush denormal values to zero whereas scalar operations will properly use denormal numbers. Luckily 64-bit Arm doesn't have that problem IIRC.

2 Likes
13

What would v.xxyy = (1.0, 1.0, 2.0, 2.0); mean? How would you prevent duplicating-field swizzles on the left-hand-side of an assignment? Would such swizzles always be non-mut? What about v.rxba (using both color and position names)?

14

Either compilation error, or optional warning and desugared into something like:

let temp = (1.0,1.0,2.0,2.0);
v.x = temp.x;
v.x = temp.y;
v.y = temp.z;
v.y = temp.z;

Such swizzles would be mut if needed (ofcourse, if v is not mut, then you cant change its fields with swizzles).
Usually, mixing position/color swizzles is prohibited. They serve no purpose other than syntax, and such letters are chosen because they are most intuitive. Mixed swizzles might not be as intuitive to reason about, and add no value (as far as i can see) so i would prohibit it.

15

This feels like a novel desugaring (though I'm not all that well-versed in the actual desugaring used today; it may well be OK), but it does avoid the (&mut v.x, &mut v.x, â€Ļ) multiple-mut problem I was thinking about when writing it.

16

Greetings! I'm new here (and new to Rust) but wanted to comment a bit on the proposal, based on our experience writing a linear algebra proposal that was voted into C++26.

In that proposal's companion paper, we distinguish "[t]iny matrices and vectors" (3x3, 4x4, all dimensions known at compile time) as a special case that calls for a separate design. It looks like the library you propose intends to cover just that special case. Is that correct? If so, then how would the proposal handle physical units? Is the intent just to cover gaming or would the library be meant for physicists and engineers as well?

Regarding prior art, please also consider the SIMD library that was voted into C++26. P1928 has background and references to design discussions.

Thank you for working to improve Rust!

5 Likes
17

I am not sure what you mean by physical units. If you relate to things like assert!(1m == 100cm), it does not (would be cool to be able to create those in Rust). If you mean hw processing units, it maps well to hardware (hardware was designed around this type of operations).

Yes, this is proposal is not about BLAS with its runtime dimensions, it is about tiny vectors and matrices. I would imagine physicists* and engineers would also be happy to some degree, but i propose it from pov of gamedev.

* its been a while since i've done any physics, but to my understanding computing there nowadays is still mostly about 3d space (same as gamedev), and also interacts with GPUs quite often (when computing is non-trivial perfomance-wise, e.g. liquid sims)

Sorry if i did not make it clear clear, but i dont know if having vectors handled on language level (like integers) or just desugared into std::comptime_linalg would be better.

Compared to C++, this proposal maps closest to GLM library.

In relation to SIMD libraries, Rust exposes type * width, and unrolls accordingly to target instructions. C++ exposes type * supported_target_width. Rust is "portable simd" (which is what its called), and C++ is more of a sugar over simd.

I had substantially better gameplay/graphics related programming experience in C++ compared to what i had in Rust. Simple example:

glm(reduced):

vec4 a = vec4(1, 2, 3, 4);
vec4 b = vec4(a.xx, a.yz);
b.xy = b.zw;

same in Rust: nalgebra (reduced):

let a = Vector4::new(1.0, 2.0, 3.0, 4.0);
let mut b = Vector4::new(a.x, a.x, a.y, a.z);
let zw = Vector2::new(b[2], b[3]); // no .w swizzle
b.x = zw.x;
b.y = zw.y;

glam (reduced):

let a = vec4(1.0, 2.0, 3.0, 4.0);
let mut b = vec4(a.x, a.x, a.y, a.z);
let zw = b.zw();
b.x = zw.x;
b.y = zw.y;

There is also ultraviolet, euclid and pathfinder_geometry (crates not mentioned in Pre-RFC body).

At this point i stopped and tried implementing (thats why answer took so long) syntax as close to GLM as possible (your question about swizzles inspired me in terms of how to do it). Now you can do this:

let a = vec4(1, 2, 3, 4);
let mut b = vec4(a.xx, 5, 6);
b.xy = b.zw;

Which is identical to GLM syntax. However, it is somewhat limited (fine for most usecases), noticeably (like 20%) slower to compile (in synthetic benchmark, i dont have any shipped Rust games to test this in), and will scale horribly (e.g. 8-dimensional vectors are likely un-compileable on my machine). Also, all of your code now has to be processed by proc macro which is changing things (e.g. you cant use any swizzle-like field names anywhere, or horrible things will happen),

Explanation on how it works: proc macro unrolls write swizzles as discussed, converts read swizzles to funcion calls, adds exclamation mark to "convertion functions" converting them to declarative macro invocation, which acts like overloaded function. Then, each argument is decomposed into array with const size, each element gets casted, and they are all assembled back into target type vector.

You can find code at GitHub - platonvin/qvek

This might be a good way to "try out" the syntax. But points in Pre-RFC still stand. Floats and integers could also be just bytes and implemented via macros to some degree.

18

Ok, scoping to "tiny" things does make sense, I agree.

But at the same time, what do you need from it being in core? Is there any reason that these things that everyone "does pretty much the same" couldn't just be a crate that all the different gamedev and such crates agree to use? (And if they can't agree to use one crate, why would they all sign off on putting those types in core?)

Certainly having Simd<_, 4> in core is essential. But then people can wrap that into vector/matrix/point/colour/etc libraries as they so wish, and maybe that's fine?

(Kind like how https://crates.io/crates/color can exist without being in core.)

3 Likes
19

If one of the core arguments linear algebra primitives is for swizzling, then I think a better current way would be to just use destructuring:

let mut v = [1,2,3,4];
let [y,x,z,w] = &mut v;
*x = 8;
println!("{v:?}")

I've been tinkering with geometry processing in Rust for a while, and use standard arrays to represent vectors and small matrices (without newtype wrappers). I would say one major shortcoming is that elementwise operations need a dedicated function.

Edit: I've avoided the linear algebra crates for the most part, since I can't tell which one has consensus, and I've hit bugs in sparse matrix solving when I tried using any of them. I've also had trouble sifting through the type soup docs that they become after being layered with 20 abstractions.

20

Thanks for asking! I specifically mean units of measurement: meters, seconds, grams, etc. I've worked with C++ code that lets physical quantities in 3-D space have units.

Physics computations might often involve 3-D space, but their needs vary a lot. Sometimes they need a mix of large linear algebra (sparse matrices with giant run-time dimensions) and small linear algebra. Even the small case might have matrices larger than 4x4 (e.g., because the matrix size depends on the properties of the partial differential equation discretization).

1 Like