Const generics (RFC 2000) refactor

[vadixidav]

Const generics rust-lang/rust#44580 need to be added into nalgebra, since it is one of the greatest beneficiaries from this feature. I propose that we maintain a nalgebra-cg crate on crates.io that depends on nightly until the feature is merged. The reason this might be preferable over using a feature flag is that almost everything in this library is going to need to be refactored to use const generics.

Although const generics are not yet in nightly, I propose using rust-lang/rust#53645 (varkor's branch) to start development now so that it can be available on merge and to assist in finding bugs via integration.

[vadixidav]

I will be present in the comments here and in the rustsim Discord server if anyone wants to work with me on this refactoring.

[Ralith]

Publishing transient crates to crates.io for experimental work seems unnecessary when interested downstream users can just use git dependencies targeting a branch.

[vadixidav]

Perhaps, I assumed that it might be up to a year before const generics become stable, so I figured that it might be good to have it available till then. What does everyone else think?

[sebcrozet]

I think publishing a new crate will be confusing. As @Ralith points out, having this on a branch here will be much more convenient because we will be able to see how it diverges from master, and perhaps backport to this "const generics branches" some new features we add to master progressively. Doing all this through git seems cleaner and more convenient.

[vadixidav]

This also will unblock #286 and solve #222 and #324.

[vadixidav]

@sebcrozet In case you might have misunderstood, I was still thinking that we would maintain this as a long-lived feature branch in this same repository, but just publish it to crates.io separately as well. I am fine with just using it through git though. We could also publish it as version x.y.z-cg, which would not get used by default.

[ChristopherRabotin]

Has there been a decision yet as to whether or not to refactor nalgebra to use const generics? There seems to be at least two other linear algebra libraries which are experimenting with it: aljabar and const-alg.

[jswrenn]

@ChristopherRabotin, my feeling is that this will almost certainly happen eventually. At the moment, however, const generics are a bit less expressive than typenum. In particular, with typenum, we can express less-than and greater-than dimensionality constraints. We use this in nalgebra to place dimensionality bounds on the swizzling methods (which I consider an ergonomic bright spot of this library).

So, unfortunately, it's not quite so simple as just switching to const generics. I've been toying with a mixed approach, but const generics are still a bit too buggy to make much progress.

[ChristopherRabotin]

Thanks for the quick response.

Should we expect that const generics make nalgebra smaller than it is with typenum? And what would be the general expectations from switching to const generics?

[jswrenn]

It depends what sense you mean "smaller". If we were to switch to straight const generics now, the swizzling API (and other parts of nalgebra that rely on complex dimensionality constraints) would either have to be removed wholesale, or limited to particular concrete dimensions, or loose their compile-time guarantees (and have runtime assertions instead).

I doubt nalgebra's binary footprint would change much at all by switching. If we had to exchange compile-time checks for runtime checks, its footprint would perhaps increase slightly.

[vadixidav]

@ChristopherRabotin The main benefits would be:

• We could define complicated chains of matrix multiplications, additions, etc that are needed for ML and have the output type chosen for type checking, which if you try to do now results in enormous trait bounds and sometimes becomes impossible if you try to do anything too complicated.
• Compilation would be much faster
• We could support much larger numbers without worrying about recursion limits
• Trait bounds could be just the dimensions of the input and the amount of where clause boilerplate would decrease dramatically
• We would get out significantly better errors from the compiler than the strange trait bound errors we get now

[vadixidav]

@ChristopherRabotin I actually just took a look at aljabar and I was highly impressed that they were able to achieve what they have so far. Admittedly, I haven't tried the const generics in the last month, so I might be a bit behind in knowing what works now with the feature. I will investigate how they implemented their library this weekend and see if we can use that to get nalgebra to work.

[ChristopherRabotin]

I heavily use nalgebra for astrodynamics simulations. Some of these simulations are long enough that they could be used for some profiling. Hence, if you need demos for profiling cost generic with respect to the current implementation, I'm happy to help. I'm afraid I don't know nalgebra well enough to be useful for the implementation of const generics though.

[vadixidav]

Status update. When I last commented, const generics still wasn't usable for linear algebra. However, that seems to be changing now. While it isn't perfect (I don't think the matrix storage can use M * N, sadly), it seems like we might be able to proceed soon with an implementation. The following blog post was added to Reddit today that provides a clear path for a linear algebra crate:

https://djugei.github.io/optimath-0-3-0/

I am sure it won't work with everything nalgebra does. For instance, I am not sure it is possible to define VectorN::push(). Once lazy normalization lands in nightly, we will be able to begin the refactor: rust-lang/rust#60471

Looking forward to that issue being resolved!

[vadixidav]

Quick re-update. I just found that a PR is open for lazy normalization of consts: rust-lang/rust#67890. 🎉

[ChristopherRabotin]

Woo-hoo! Christopher Rabotin.

…

On Mon, Jan 13, 2020, 09:43 Geordon Worley ***@***.***> wrote: Quick re-update. I just found that a PR is open for lazy normalization of consts: rust-lang/rust#67890 <rust-lang/rust#67890>. 🎉 — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#526>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABEZV2GPALK3VP6IEYGJK4DQ5SK3VANCNFSM4GQO6ZXQ> .

[vadixidav]

Quick update.

That last PR got axed and turned into another PR that was finally merged: rust-lang/rust#71973

Now const generics actually works well enough to do substantial things. For instance, I have started working on a library to do things similar to ndarray but on the GPU with WebGPU compute shaders: https://github.com/vadixidav/toil. This means that const generics should be good enough for us to start refactoring nalgebra using the nightly compiler. 🎉.

Right now I am busy with some other projects, but anyone that is interested in starting the refactor, now is the time to proceed. If nothing happens for a while, I will probably pick this up.

[djugei]

i did some exploration in this space in my optimath crate, sadly at the time much useful stuff was blocked on const generics getting a bit more well-rounded. especially manually layouting matrices/arrays for easy simd/multithreading.
if i don't misunderstand the merged pr this still does not work, i.e. can't actually set array sizes based on size_of::(). so maybe its a bit too early yet.

im posting this because maybe some of the exploration is useful to nalgebra, and to maybe start contributing if someone points me in the right direction.

wrote down some results in the docs, especially in the insights module.

[djugei]

i just saw that the announcement blog post for optimath is already linked in this thread, a small update on that: i said that a specialization issue was resolved: it was not, the fix was faulty, so no further progress could be made on that front.