Discussion: Stack allocated linear algebra template structs

[johnwason]

In robotics and automation engineering, determinism is extremely important for many control tasks. Because of this, most control code is written in C, C++, or ADA where variables can be easily allocated on the stack to avoid non-deterministic memory allocations. With the new Span, stackalloc, and ref struct capabilities, C# should be capable of deterministic behavior.

One major limitation in the current C# language design is the inability to develop a stack allocated ref struct that can have a stack allocated data array with a fixed size based on template arguments. This design pattern is used extensively in linear algebra packages like Eigen and Armadillo. For instance, a C++ Eigen matrix on the stack could be declared as follows [1]:

Matrix<float, 4, 4> my_matrix;

How could this be accomplished in C#?

[svick]

With the new Span, stackalloc, and ref struct capabilities, C# should be capable of deterministic behavior.

I'm not sure that's true. I think C# generally treats allocations as a performance issue, not as a correctness issue. Because of that, I think it would be pretty hard to avoid all allocations in any non-trivial code since you wouldn't be allowed to use most C# features. You're probably better off with a language that doesn't rely so much on GC.

How could this be accomplished in C#?

I think the closest way would be something like:

Span<float> buffer = stackalloc float[16];
var myMatrix = new Matrix<float>(buffer, 4, 4);

Though I think it's not a very nice pattern.

If you're willing to have some allocations at startup, it might make sense to use a fixed-size memory pool. That could look something like (the using is there to make sure myMatrix returns the memory to the pool after it's finished):

using (var myMatrix = new Matrix<float>(MyMemoryPool, 4, 4))
{
    …
}

[johnwason]

I'm not sure that's true. I think C# generally treats allocations as a performance issue, not as a correctness issue.

Any deterministic code would have to be run through the native compiler or a transpiler to C or C++. These compilers/transpilers can be modified to use stack allocation fairly easily. A JVM is not deterministic so it can't be used anyway.

I think it would be pretty hard to avoid all allocations in any non-trivial code since you wouldn't be allowed to use most C# features.

The same is true for any time critical code in any language.

You're probably better off with a language that doesn't rely so much on GC.

In practice most code in C or C++ results in non-deterministic behavior. Proving determinism in C and C++ is quite difficult, and requires specialized knowledge and expensive static analysis software. Interestingly I suspect that C# would be much easier to prove determinism due to the cleaner design and lack of pointers*. ADA is better at being analyzed, but has its own disadvantages when compared to newer languages like C#.

I suspect that the stackalloc example is the answer I will end up with, but it is pretty ugly. Maybe there is a T4 code generation that would help? The memory pool is not really a good solution for the uses I am considering.

[4creators]

There is a proposal to support syntax you are looking for. Gathering more examples of use cases may be crucial for getting it implemented see #749

[Proposal] Const blittable parameter as a generic type parameter - constexpr used for blittable type parametrization

[johnwason]

@4creators interesting, looks like other people have encountered the same dilemma. Wouldn't it make sense to constrain the compile time template evaluation to ref structs? If you are already using the GC there isn't much performance penalty to using standard arrays. My goal is to avoid the GC completely and just use the stack.

[4creators]

Proposal which maybe better reflects on your needs: #761

[Proposal] Real-Time specification for C#

In general RT specification has to achieve determinism at the time level which cannot be guaranteed without determinism (at least for time critical code) at memory level. The issue could be an umbrella for large number of proposals revolving around time and memory determinism and code performance.

[johnwason]

@4creators I don't see any mention of stack allocated types or memory pools in the proposal. For any practical hard real time system, the GC will be off limits except for initialization/cleanup steps. I haven't seen real time Java used for this purpose due to the lack of stack allocated types.

Most of the other features discussed are more a function of the operating system rather than the software itself, ie QNX, VxWorks, Xenomai, PREEMPT_RT all have their own way to solve scheduling issues. They will just require a P/Invoke wrapper or something similar.

The stack allocated matrix types suggested here also have application in HPC so it isn't specific to real-time.

[CyrusNajmabadi]

It's unclear ot me why the option mentioned by svick woudl not be suitable for your needs. Could you expand on that?

[johnwason]

It would probably work to use the stackalloc keyword for the array and then pass it to a ref struct representing the matrix, but it isn't very readable. Keep in mind that some of these calculations may have dozens of matrices involved.

The following files are written in Python using numpy, but they contain the type of calculations that are commonly done for robots. Some or all of these functions are called periodically at a fixed rate. The goal is to move these calculations onto the stack so that no allocations or deallocations occur during each iteration. This can be done in C++ using templates, however in practice writing C++ takes longer and is harder to analyze than C#.

https://github.com/rpiRobotics/rpi_general_robotics_toolbox_py/blob/master/src/general_robotics_toolbox/general_robotics_toolbox_invkin.py
https://github.com/rpiRobotics/rpi_general_robotics_toolbox_py/blob/master/src/general_robotics_toolbox/general_robotics_toolbox.py

[CyrusNajmabadi]

It would probably work to use the stackalloc keyword for the array and then pass it to a ref struct representing the matrix, but it isn't very readable. Keep in mind that some of these calculations may have dozens of matrices involved.

I'd like to see before making judgement. Adding highly specialized language features shouldn't be done with actually investigating and exhausting all possible existing options.

[benaadams]

Main issue I see is you always have to do the localloc in the caller, rather than callee (as the stack gets unwound after the callee returns and would become invalid)

But then you are in the messy syntax in the caller; as highlighted.

So as well as construction with implicit stackalloc; you'd want similar for methods that return new items (e.g. quatproduct, q2R, screw_matrix in the examples).

Implicit conversion from Span doesn't help make it less messy as it needs extra data (the dimensions; e.g. is a 12 element span 3x4 or 4x3)

[alrz]

In C# 8.0 you won't need to capture buffer in a local (#1412),

new Matrix<float>(stackalloc float[16], 4, 4)

You could even declare an extension on span,

Matrix<float> m = stackalloc[] { 1f, 0f, 0f, 1f }.AsMatrix(2, 2);

And with help of #1757, you could skip stackalloc syntax entirely,

var m = (2, 2).Matrix(1f, 0f, 0f, 1f);

[4creators]

@johnwason

Going back to real-time system programming with Java and perhaps C# there are two criteria which are not met by current non real-time runtimes:

1. Maximum/minimum execution interval between time critical task invocations.
2. Maximum execution time guarantees for code which is executed periodically.

AFAIU robot systems operate in time critical manner so some calculations have to be done with real time guarantees. All garbage collected runtimes will run Garbage Collector from time to time. what will cause stop the world event. I do not know .NET Core GC details enough to predict how will it work with allocations going only on the stack but I would expect that GC would run from time to time.

You can try to guard you code with:

if (GC.TryEnterNoGCRegion())
{
    // do some work periodically
    GC.EndNOGCRegion();
}

but I doubt it would provide guarantees you need.

Java RTM specification assumes creation of separate threads with native-like memory management. But you cannot interact with code running on threads using GC.

It is possible to achieve similar properties in .NET Core runtime, however, this would require replacing current GC with either ownership based memory management (rust like) or explicit memory management (explicit allocations and deletes C++ like). The other problem would be replacement of current scheduler with single or multi threaded real time scheduler. Having this two elements done it is easy to run soft real time .NET Core apps on soft real time Linux.

If you intend to run on hard real time system we should think about porting .NET Core to RT OS of our choice.

Everything is doable, however, I would estimate time required as roughly 2 developer-years of work.

[johnwason]

@alrz neat! That is probably a workable solution. Is #1757 likely to be adopted?

@4creators For my purposes, the GC would not be required except for during startup and shutdown. A digital control system is essentially just a while loop that runs an algorithm periodically. If there are threads that require more memory, they can use a memory pool. I agree that making C# realtime is possible, and likely to result in a powerful tool. I am personally not much help at this level of development because my background is in electrical and mechanical engineering rather than computer science.

[svick]

@CyrusNajmabadi Highly specialized language features are problematic? Let's make a feature that's marginally more general, but also significantly more complicated! I opened #1817 to discuss allocating from the caller's stack frame. With that, the example code could look like this (placeholder syntax):

var myMatrix = new Matrix<float>(4, 4, stackalloc);

Here, the stackalloc keyword on its own gives the constructor permission to allocate from the current stack frame. In effect, this would mean the Matrix constructor could allocate its own dynamically-sized storage without allocating from the heap and it would still be valid after the constructor returns.

[johnwason]

@svick would it make more sense to create a new keyword like "structalloc" that allocates memory on the stack of the owner of the struct? It seems like #1817 is trying to replicate the functionality of C++ return optimizations rather than memory ownership within a struct.

[johnwason]

@svick For the parse example, couldn't this algorithm be implemented as a struct and then do a ref return at the end? That way the lifecycle of the buffer can be managed by the struct rather than trying to hand off ownership.

Good point on the C++ return opts, I guess I didn't realize that stackalloc was dynamically sized.

[CyrusNajmabadi]

@CyrusNajmabadi Highly specialized language features are problematic?

As i said:

I'd like to see before making judgement. Adding highly specialized language features shouldn't be done with actually investigating and exhausting all possible existing options.

You're not effectively convincing me here :)

[johnwason]

@svick @CyrusNajmabadi perhaps a solution to both problems would be to allow inlining of ref struct functions? The idea is that the function calls would not push/pop the stack, but instead would run in the current stack frame. They would behave in a manner similar to macros in C++. This could probably allow the desired behavior without reworking the stack memory management design.

e: I guess inlining is close to one of the suggestions in #1817, but instead of passing a handle to the calling stack frame it would just remain in the current frame.

[CyrusNajmabadi]

Until coming up with a new solution, i want to understand why existing solutions are insufficient to tackle the problem.

[johnwason]

@CyrusNajmabadi

Let's consider a simple Jacobian kinematic controller for a 6 axis robot. The code in MATLAB would look something like this:

joint_velocity = k_p * pinv(J) * (x_des - x_real)

where k_p is a scalar, pinv is the matrix pseuoinverse, J is a 6x6 matrix, x_des and x_real are 6x1 vectors.

(Control engineers do most analysis work in MATLAB because of the simple syntax. Python numpy is growing in popularity, but the syntax is not always as clean.)

This is one of the simplest linear algebra equations used in robotics, and it still has at least 3 temporary results that would have to be explicitly allocated with the current syntax. You would also need to pre-calculate the dimensions of each matrix, which may not be immediately obvious for more complex equations. Real life calculations are often far more complex, as you can see in the lPython links I attached earlier.

[johnwason]

I have been pondering this problem, and I think I have a possible solution.

C++ has a powerful template system, but it is extremely difficult to use and can have unpredictable results. This template system is an important part of mathematics libraries like Eigen that allows for arrays to be stack allocated within the structure, resulting in "blittable" types. There is the "fixed-size-buffer" proposal and various discussions about using constexpr in generics to achieve similar functionality in C#.

My suggestion is to use compile-time type substitution using T4 templates as the back end. For example, a matrix type might look like this:

Matrix<! 3,3 !>

But would be substituted with a generated class like this:

Matrix_3_3

The class would be generated at compile time when needed using T4, and the template type in the source code would be replaced with real type. Because T4 is being used, it would allow for the "fixed-sized-buffer" proposal to be implemented without changing the language. The use of T4 templates instead of the crazy C++ method would also make it much easier to develop the templates.

Because this would break C# syntax, I suggest creating a different file type extension, such as "cst" to hold the source that contains types for substitution. The real cs files can be generated as part of the compilation process.

This idea probably doesn't require changes to the C# library itself and could be implemented as an add-on, but I wanted to discuss it here. Does something like this exist, and is there any interest in this idea?

[msedi]

I'm having the same issues. I have a few questions if you don't mind, because I think you are pointing to the same problems. I will also show a few of my thoughts.

How do you tackle the problem with matrix algebra when having a matrix defined as you propose?

Matrix<n,m>

Do you internally always have float or double, since math on generics is not possible.

I was also thinking about the problem to define the matrix dimensions in the constructor as you did.
In my case using stackalloc only could cause problems with the stack size, since our matrices are much larger than a regular stack can deal with (e.g. image processing filter kernels). So what would also be necessary in my case that the matrix decides of what memory to use (stack or heap).

Is your matrix a struct or a class?
I would really prefer something like this

public struct Matrix<n,m>
{
  public fixed float Data[n*m];
}

But this is currently not possible. Of course you could also write

public struct Matrix
{
  public readonly float[] Data;

  publix Matrix(int n, int m)
  {
     Data = new float[n*m];
  }
}

But then you always have a regular heap allocation and an additional multiplication in it.
Additionally, the new memory gets nulled (0) which could also cause performance problems when this is done many times (of course also on the example above) and you get an unwanted constructor Matrix() that you cannot hide so either you switch to a class or you have to live with Matrix().

Most of the things that are necessary here are already available in C++

• Math on templates
• Operators on templates
• Different implementation of + and += (and of course all other X and X= operators)
• Templates with predefined values, e. g. Matrix<4,4>

As far as I can remember in C++/CLI you can also distinguish if the object is allocated on the heap or on the stack.

I really don't want to complain, I'm coming from the C++ world and I really love C#, but sometimes there are still gaps in C# that me and my colleagues really like to be filled. I understand that some items might need a CLR change, but something like Matrix<4,4> which is really deterministic could be solved by the compiler, by rewriting the code during compile time..

Of course these things can be solved by creating new specialized type (Matrix4x4, Matrix3x3, Matrix3x2, etc) but from an architectural standpoint this is less than optimal. A good example are the WPF Vector and Vector3D structs. Both of them are almost similar, but implement twice. If some mechanism like Matrix<n,m> would exist this wouldn't have been necessary.

I'm curious about your comments.

[CyrusNajmabadi]

I'm coming from the C++ world and I really love C#, but sometimes there are still gaps in C# that me and my colleagues really like to be filled. I understand that some items might need a CLR change, but something like Matrix<4,4> which is really deterministic could be solved by the compiler, by rewriting the code during compile time..

Of course these things can be solved by creating new specialized type (Matrix4x4, Matrix3x3, Matrix3x2, etc) but from an architectural standpoint this is less than optimal. A good example are the WPF Vector and Vector3D structs. Both of them are almost similar, but implement twice. If some mechanism like Matrix<n,m> would exist this wouldn't have been necessary.

I'm curious about your comments.

This is all true. One important thing to note though is that a deficiency in C# wrt some other language does not mean that anything will happen wrt that deficiency.

Changing the language automatically starts out as something that is unlikely to done. With the cost/complexity often being considered things that are a negative for the langauge, team and ecosystem. So, in order to make any language feature happen (especially one that needs CLR change) there has to be a feeling that there absolutely huge value brought about by such a change.

It is never a question if someone will want hte change. There are always people that will benefit from it. The question is: is the value to the ecosystem as a whole sufficient to do this?

THat's often less clear, and takes a lot of effort and involvement to determine. So far, this area has been one that neither the C# nor runtime teams has felt there is sufficient need for. While unpleasant to have to manually create things like Matrix4x4, that's an acceptable solution for people who find themselves in this position.

[johnwason]

@msedi There would probably need to be another template argument that would specify the type. Note that this would be a template not a generic. It would look something like this:

Matrix<!double,m,n!>

Having default template arguments would also be possible. In terms of the storage, it appears the only way to handle this would be to have multiple scalar fields that emulate an array. Scalar fields are allocated on the stack within the structure. This storage would be another template type, like:

FixedArray<!type,m*n!> data;

Again, this would be a template, not a generic, and would be implemented through T4 generation. Essentially the specific template instantiation would be generated before the C# compilation stage. The specific instantiation would look like

struct FixedArray_double_4_4
{
double a1;
double a2;
double a3;
//etc.

}

There will need to be some extra attributes attached to these objects to help template resolution. Dealing with multiple assemblies defining the same template instantiation is something I haven't figured out yet.

@CyrusNajmabadi This approach would avoid modifying the language by using a pre-compilation code generation step. Runtime template resolution when multiple assemblies instantiate the same type is the main sticking point right now. Do you have any suggestions on how to deal with this?

[msedi]

@johnwason: At least for the rewrite where the workaround is a T4 template (which is currently also my workaround). Is this something that could be solved by roslyn? But I'm not sure if it would go without any language changes since you need to mark it somehow that it can be resolved by your precompilation step.

[msedi]

@CyrusNajmabadi

This is all true. One important thing to note though is that a deficiency in C# wrt some other language does not mean that anything will happen wrt that deficiency.

Sure that's a fair point. The least I want is C++/C# instead of C++/CLI ;-)

The question is: is the value to the ecosystem as a whole sufficient to do this?

Understood. My question here is what input do you need? As far as I can read in many proposals and requests that there is a real need for a better math support in C# (in one or the other area or direction). I'm not quite sure how to subsume the needed requirements. Does it make sense to open a list of all requirements and then see what's needed most, instead of collection the issues where one requests e. g. a better operator support and the other math operations on generics?

[CyrusNajmabadi]

Understood. My question here is what input do you need.

Usually, it's a good idea to go in depth at to:

1. the actual language changes that would be required (i.e. how the spec would change).
2. how this woudl actually be implemented.
3. a deep dive into alternatives about the above, and the relative pros/cons of each. for example, if one proposal needs CLR changes, what the implications of that are.
4. an examinatino of what you can do today as a workaround.
5. investigations into the relative performance of these language changes (i.e. by simulating what they would produce by just mnually doing the work yourself, for example, with manual struct solutions), esp. versus the workarounds.

If things look promising, and someone on the LDM indicates interest, it may also be valuable to then go provide some implementation of the approach to help lower the costs.

[johnwason]

@msedi T4 templates is the first option that I came across. There are certainly numerous other code generation options out there.

In terms of the compiler, my suggestion is that a new file extension be defined like *.cst. This would take the initial code containing templates and then generate the specialized templates into a *.cs file. By making this an add-on option it avoids modifying the language itself, since most users won't ever need this functionality.

@CyrusNajmabadi is a plugin for roslyn a realistic option for this scenario?

[Thaina]

Might be related : #2513

[lostmsu]

Check out https://github.com/losttech/TypeNum