Realtime-safe matrix library?

Submitted by johnathanvanwhy on Fri, 2012-08-24 00:44

Orocos-users

In the near future, we will need a library for manipulating matrices.
However, it is difficult to find a hard realtime-safe matrix library.

It seems as if Eigen may be realtime-safe for fixed-size matrices --
can anyone confirm this? If not, what is a realtime-safe alternative?

Thank you for any help,
Johnathan Van Why
Dynamic Robotics Laboratory
Oregon State University

Realtime-safe matrix library?

Submitted by peter on Fri, 2012-08-24 22:04.

On Fri, Aug 24, 2012 at 1:44 AM, Johnathan Van Why <jrvanwhy [..] ...>wrote:

> In the near future, we will need a library for manipulating matrices.
> However, it is difficult to find a hard realtime-safe matrix library.
>
> It seems as if Eigen may be realtime-safe for fixed-size matrices --
> can anyone confirm this? If not, what is a realtime-safe alternative?
>

Since Eigen uses expression templates, they can pre-compute the required
size of a 'result' (or temporary) matrix at compile time, *given* that all
sizes of all used matrixes are also known at compile time. So if you use
exclusively fixed size matrixes, I believe no allocations would happen.
Skimming through eigen's docs suggests that they indeed use this mechanism.

Peter

Realtime-safe matrix library?

Submitted by Erwin Aertbelien on Mon, 2012-08-27 08:08.

On 08/24/2012 11:59 PM, Peter Soetens wrote:
> On Fri, Aug 24, 2012 at 1:44 AM, Johnathan Van Why <jrvanwhy [..] ...
> <mailto:jrvanwhy [..] ...>> wrote:
>
> In the near future, we will need a library for manipulating matrices.
> However, it is difficult to find a hard realtime-safe matrix library.
>
> It seems as if Eigen may be realtime-safe for fixed-size matrices --
> can anyone confirm this? If not, what is a realtime-safe alternative?
>
>
> Since Eigen uses expression templates, they can pre-compute the
> required size of a 'result' (or temporary) matrix at compile time,
> *given* that all sizes of all used matrixes are also known at compile
> time. So if you use exclusively fixed size matrixes, I believe no
> allocations would happen. Skimming through eigen's docs suggests that
> they indeed use this mechanism.
>
> Peter
>
>
>
My own experience ( from KDL) is that it is relatively easy to write
Eigen code that does not allocate memory.
Some caveats:
- You'll have to use fixed size matrices or preallocate all your
matrices.

- You also have to be careful to write matrix expressions that can be
evaluated without temporaries.
http://eigen.tuxfamily.org/dox/TopicWritingEfficientProductExpression.html

- use .noalias() to indicate that aliasing is not a problem in your
expressions:

http://eigen.tuxfamily.org/dox/TutorialMatrixArithmetic.html#TutorialAri...

- valgrind can be used to check whether you allocate unintentionally
memory on the heap, or you can use
the suggestions in
http://eigen.tuxfamily.org/index.php?title=FAQ#Where_in_my_program_are_t...

You can guarantee that your code does not allocate temporary objects.

- Eigen is faster than the original Fortran Lapack, and even rivals
the ATLAS Lapack implementations ( both
these implementations are also not really transparent, certainly not ATLAS).

- Also with Lapack/Atlas, memory allocations are not transparent ( and
there are sometimes memory allocations inside the computational routines
!), and I remember being bitten by some
non-reentrant error handling in Lapack (albeit more then 10 years ago...
I do not know the current situation).
What is certain: Lapack/Atlas is a library designed for _large_
matrices. For these matrices, memory allocation
is not a big issue. Eigen is also designed for small and mid-range
matrices.

- You have to take care of memory alignment in some cases when using
fixed size matrices. This is due
to the fact that fixed matrices are put on the stack and due to some
deficiencies in C/C++ regarding
the specification of alignment.
http://eigen.tuxfamily.org/dox/TopicUnalignedArrayAssert.html

Realtime-safe matrix library?

Submitted by gah on Fri, 2012-08-24 07:40.

Johnathan Van Why wrote:
> In the near future, we will need a library for manipulating matrices.
> However, it is difficult to find a hard realtime-safe matrix library.
>
> It seems as if Eigen may be realtime-safe for fixed-size matrices --
> can anyone confirm this? If not, what is a realtime-safe alternative?
I've not experienced any mode switches using statically allocated matrices with Eigen (v2).

That does not mean it it real-time safe though; it might still be dynamically allocating memory, just not enough to cause page-faults.

Realtime-safe matrix library?

Submitted by bruyninc on Fri, 2012-08-24 07:56.

On Fri, 24 Aug 2012, g ah wrote:

>
> Johnathan Van Why wrote:
>> In the near future, we will need a library for manipulating matrices.
>> However, it is difficult to find a hard realtime-safe matrix library.
>>
>> It seems as if Eigen may be realtime-safe for fixed-size matrices --
>> can anyone confirm this? If not, what is a realtime-safe alternative?
> I've not experienced any mode switches using statically allocated matrices with Eigen (v2).
>
> That does not mean it it real-time safe though; it might still be
> dynamically allocating memory, just not enough to cause page-faults.

This is one of the problems I have with this kind of libraries: I just
cannot understand what will be happening _exactly_ at runtime, especially
with respect to realtime determinism.

And I haven't met someone yet who has been able to help increase my
insights.

Summary: modern evolutions in computing (both hardware and software) make
it more and more difficult to comprehend the realtime determinism behaviour
of pieces of code, because "the platforms" do more and more behind the
screens. This is definitely a good evolution for mainstream computing, but
not for realtime.

Herman

Realtime-safe matrix library?

Submitted by snrkiwi on Fri, 2012-08-24 11:12.

On Aug 24, 2012, at 03:51 , Herman Bruyninckx wrote:

> On Fri, 24 Aug 2012, g ah wrote:
>
>>
>> Johnathan Van Why wrote:
>>> In the near future, we will need a library for manipulating matrices.
>>> However, it is difficult to find a hard realtime-safe matrix library.
>>>
>>> It seems as if Eigen may be realtime-safe for fixed-size matrices --
>>> can anyone confirm this? If not, what is a realtime-safe alternative?
>> I've not experienced any mode switches using statically allocated matrices with Eigen (v2).
>>
>> That does not mean it it real-time safe though; it might still be
>> dynamically allocating memory, just not enough to cause page-faults.
>
> This is one of the problems I have with this kind of libraries: I just
> cannot understand what will be happening _exactly_ at runtime, especially
> with respect to realtime determinism.
>
> And I haven't met someone yet who has been able to help increase my
> insights.
>
> Summary: modern evolutions in computing (both hardware and software) make
> it more and more difficult to comprehend the realtime determinism behaviour
> of pieces of code, because "the platforms" do more and more behind the
> screens. This is definitely a good evolution for mainstream computing, but
> not for realtime.

That's a very nice summary of the problem.

With Eigen it is almost impossible to understand what is actually happening under the hood. Too many layers upon layers, both in the code _and_ during compilation. Sigh ...
S

Realtime-safe matrix library?

Submitted by andrewwagner on Fri, 2012-08-24 13:04.

I evaluated Eigen a couple years ago for another project, and asked
this same question:

http://forum.kde.org/viewtopic.php?f=74&t=87490

Confusion about Eigen's internal memory management was the main reason
I kept using MKL. In the absence of documentation, they gave me some
ideas for how I could instrument their code to figure it out, but, at
least at the time, I didn't understand enough about templates and
inheritance to have any hope of figuring out what was going on in
their code.

On Fri, Aug 24, 2012 at 12:07 PM, S Roderick <kiwi [dot] net [..] ...> wrote:
> On Aug 24, 2012, at 03:51 , Herman Bruyninckx wrote:
>
>> On Fri, 24 Aug 2012, g ah wrote:
>>
>>>
>>> Johnathan Van Why wrote:
>>>> In the near future, we will need a library for manipulating matrices.
>>>> However, it is difficult to find a hard realtime-safe matrix library.
>>>>
>>>> It seems as if Eigen may be realtime-safe for fixed-size matrices --
>>>> can anyone confirm this? If not, what is a realtime-safe alternative?
>>> I've not experienced any mode switches using statically allocated matrices with Eigen (v2).
>>>
>>> That does not mean it it real-time safe though; it might still be
>>> dynamically allocating memory, just not enough to cause page-faults.
>>
>> This is one of the problems I have with this kind of libraries: I just
>> cannot understand what will be happening _exactly_ at runtime, especially
>> with respect to realtime determinism.
>>
>> And I haven't met someone yet who has been able to help increase my
>> insights.
>>
>> Summary: modern evolutions in computing (both hardware and software) make
>> it more and more difficult to comprehend the realtime determinism behaviour
>> of pieces of code, because "the platforms" do more and more behind the
>> screens. This is definitely a good evolution for mainstream computing, but
>> not for realtime.
>
> That's a very nice summary of the problem.
>
> With Eigen it is almost impossible to understand what is actually happening under the hood. Too many layers upon layers, both in the code _and_ during compilation. Sigh ...
> S
>
> --
> Orocos-Users mailing list
> Orocos-Users [..] ...
> http://lists.mech.kuleuven.be/mailman/listinfo/orocos-users

Realtime-safe matrix library?

Submitted by Dominick Vanthienen on Mon, 2012-09-03 10:44.

hi,

FYI:
http://www.ros.org/wiki/EigenInRealtime

Realtime-safe matrix library?

Submitted by bruyninc on Mon, 2012-09-03 10:56.

On Mon, 3 Sep 2012, Dominick Vanthienen wrote:

> hi,
>
> FYI:
> http://www.ros.org/wiki/EigenInRealtime

Interesting... Especially the insight that the EIGEN SVD does runtime
allocations, since this SVD is part of multiple Orocos implementations.

Herman

Realtime-safe matrix library?

Submitted by Dominick Vanthienen on Mon, 2012-09-03 12:24.

On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
>
>> hi,
>>
>> FYI:
>> http://www.ros.org/wiki/EigenInRealtime
>
> Interesting... Especially the insight that the EIGEN SVD does runtime
> allocations, since this SVD is part of multiple Orocos implementations.
FYI: there is a SVD implementation under 'utilities' of KDL
>
> Herman

Realtime-safe matrix library?

Submitted by bruyninc on Mon, 2012-09-03 15:16.

On Mon, 3 Sep 2012, Dominick Vanthienen wrote:

>
>
> On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
>> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
>>
>>> hi,
>>>
>>> FYI:
>>> http://www.ros.org/wiki/EigenInRealtime
>>
>> Interesting... Especially the insight that the EIGEN SVD does runtime
>> allocations, since this SVD is part of multiple Orocos implementations.

> FYI: there is a SVD implementation under 'utilities' of KDL

I know. _the_ major reason why it is there is to have control over its
realtime memory allocations. (I do not remember _exactly_ to what extent
that goal was achieved....). The other reason for having "one's own"
implementation is the difference in use cases between the "Householder
reflections" and "Jacobi transformations" approaches. (I also do not
remember by heart which approach is better in which use cases...)

Herman

Realtime-safe matrix library?

Submitted by Erwin Aertbelien on Mon, 2012-09-03 12:12.

Before reaching any conclusions, I did a check on an svd with all fixed
sizes.
Here you can see that these conclusions are premature.

Checking this with valgrind shows that there are no heap allocations at all.

I include the small cpp file in attachments.

you can compile the test file with:
g++ svd_eigen.cpp -I/usr/include/eigen3

Best regards

Erwin.

On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
>
>> hi,
>>
>> FYI:
>> http://www.ros.org/wiki/EigenInRealtime
> Interesting... Especially the insight that the EIGEN SVD does runtime
> allocations, since this SVD is part of multiple Orocos implementations.
>
> Herman

Realtime-safe matrix library?

Submitted by fosini on Tue, 2012-09-04 09:28.

On Mon, Sep 3, 2012 at 2:11 PM, Erwin Aertbelien <
Erwin [dot] Aertbelien [..] ...> wrote:

> Before reaching any conclusions, I did a check on an svd with all fixed
> sizes.
>

Indeed, those results were obtained against Eigen 2.0.14, which is more
than two years old, and one major-version behind (currently 3.1.1). Many
things have changed since then, especially regarding real-time friendliness
[1, 2, 3]. I currently don't have use cases that performs unexpected
allocations (there still might exist though, I just haven't bumped into it).

[1]
http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2010/03/msg000...
[2]
http://listengine.tuxfamily.org/lists.tuxfamily.org/eigen/2010/04/msg001...
[3] http://eigen.tuxfamily.org/bz/show_bug.cgi?id=206

Here you can see that these conclusions are premature.
>
> Checking this with valgrind shows that there are no heap allocations at
> all.
>

This older post mentions a programmatic alternative to check heap
allocations without introducing additional dependencies. It incidentally
provides code for testing SVD against allocations:

http://www.orocos.org/forum/rtt/rtt-dev/nice-trick-those-using-eigen-rea...

Adolfo.

>
> I include the small cpp file in attachments.
>
> you can compile the test file with:
> g++ svd_eigen.cpp -I/usr/include/eigen3
>
>
>
> Best regards
>
> Erwin.
>
>
> On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
>
>> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
>>
>> hi,
>>>
>>> FYI:
>>> http://www.ros.org/wiki/**EigenInRealtime<http://www.ros.org/wiki/EigenI...
>>>
>> Interesting... Especially the insight that the EIGEN SVD does runtime
>> allocations, since this SVD is part of multiple Orocos implementations.
>>
>> Herman
>>
>
>
> --
> Orocos-Users mailing list
> Orocos-Users [..] ...
> http://lists.mech.kuleuven.be/mailman/listinfo/orocos-users
>
>

Realtime-safe matrix library?

Submitted by bruyninc on Mon, 2012-09-03 15:20.

On Mon, 3 Sep 2012, Erwin Aertbelien wrote:

> Before reaching any conclusions, I did a check on an svd with all fixed
> sizes.
> Here you can see that these conclusions are premature.
>
> Checking this with valgrind shows that there are no heap allocations at all.

So, is my interpretation correct when I say that you are a lot more
optimistic then the ROS report about the realtime appropriateness of Eigen?

And maybe you also have "non premature" conclusions?

That would be good news... :-)

> I include the small cpp file in attachments.
>
> you can compile the test file with:
> g++ svd_eigen.cpp -I/usr/include/eigen3
>
> Best regards
>
> Erwin.

Herman

>
> On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
>> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
>>
>>> hi,
>>>
>>> FYI:
>>> http://www.ros.org/wiki/EigenInRealtime
>> Interesting... Especially the insight that the EIGEN SVD does runtime
>> allocations, since this SVD is part of multiple Orocos implementations.
>>
>> Herman
>
>

--
KU Leuven, Mechanical Eng., Mechatronics & Robotics Research Group
<http://people.mech.kuleuven.be/~bruyninc> Tel: +32 16 328056
EURON Coordinator (European Robotics Research Network) <http://www.euron.org>
Open RObot COntrol Software <http://www.orocos.org>
Associate Editor JOSER <http://www.joser.org>, IJRR <http://www.ijrr.org>

Realtime-safe matrix library?

Submitted by Erwin Aertbelien on Mon, 2012-09-03 19:56.

What I'm saying is that we'll have to check this for the different use cases.
E.g. for dynamically allocated matrices instead of fixed size matrices, there seems to be a problem with unavoidable allocations _during compitations_, although did not uet examine this completely.

My conclusions are:
1 eigen is one of the better libraries wrt rt
2 it is still a good policy to check allocations in your code, because, depending on your knowledge of eigen, you could inteoduce unwanted allocations. There is a macro you can define in eigen that guarantees that there are no heap allocations.

I have no good alternatives, also lapack has problems.

Erwin

Herman Bruyninckx <Herman [dot] Bruyninckx [..] ...> wrote:
On Mon, 3 Sep 2012, Erwin Aertbelien wrote:

So, is my interpretation correct when I say that you are a lot more
optimistic then the ROS report about the realtime appropriateness of Eigen?

And maybe you also have "non premature" conclusions?

That would be good news... :-)

> I include the small cpp file in attachments.
>
> you can compile the test file with:
> g++ svd_eigen.cpp -I/usr/include/eigen3
>
> Best regards
>
> Erwin.

Herman

Realtime-safe matrix library?

Submitted by azamat on Tue, 2012-09-04 07:44.

Hi Erwin,
sorry to butt in, but did you have a look at MTL?
http://www.simunova.com/node/135
Though I could not find any text on its real time aspects, it seems to be used in HPC. There is also a GPU edition.
Sincerely
Azamat

________________________________
From: Erwin Aertbeliën <Erwin [dot] Aertbelien [..] ...>
To: Herman Bruyninckx <Herman [dot] Bruyninckx [..] ...>
Cc: Dominick Vanthienen <Nick [dot] Vanthienen [..] ...>; "orocos-users [..] ..." <orocos-users [..] ...>
Sent: Monday, September 3, 2012 9:52 PM
Subject: Re: [Orocos-users] Realtime-safe matrix library?

I have no good alternatives, also lapack has problems.

Erwin
Herman Bruyninckx <Herman [dot] Bruyninckx [..] ...> wrote:
On Mon, 3 Sep 2012, Erwin Aertbelien wrote:

So, is my interpretation correct when I say that you are a lot more
optimistic then the ROS report about the realtime appropriateness of Eigen?

And maybe you also have "non premature" conclusions?

That would be good news... :-)

> I include the small cpp file in attachments.
>
> you can compile the test file with:
> g++ svd_eigen.cpp -I/usr/include/eigen3
>
> Best regards
>
> Erwin.

Herman

--
   KU Leuven, Mechanical Eng., Mechatronics & Robotics Research Group
     <http://people.mech.kuleuven.be/~bruyninc> Tel: +32 16 328056
   EURON Coordinator (European Robotics Research Network) <http://www.euron.org>
   Open RObot COntrol Software <http://www.orocos.org>
   Associate Editor JOSER <http://www.joser.org>, IJRR <http://www.ijrr.org>

Realtime-safe matrix library?

Submitted by bruyninc on Tue, 2012-09-04 09:04.

On Tue, 4 Sep 2012, Azamat Shakhimardanov wrote:

> Hi Erwin,
> sorry to butt in, but did you have a look at MTL?
> http://www.simunova.com/node/135

The license text agreements are very restrictive, even more so then the old
BSD license which forces users to _display_ the copyright notice on every
binary...

> Though I could not find any text on its real time aspects, it seems to be used in HPC. There is
> also a GPU edition.
> Sincerely
> Azamat

Herman

> ________________________________________________________________________________________________
> From: Erwin Aertbeliën <Erwin [dot] Aertbelien [..] ...>
> To: Herman Bruyninckx <Herman [dot] Bruyninckx [..] ...>
> Cc: Dominick Vanthienen <Nick [dot] Vanthienen [..] ...>;
> "orocos-users [..] ..." <orocos-users [..] ...>
> Sent: Monday, September 3, 2012 9:52 PM
> Subject: Re: [Orocos-users] Realtime-safe matrix library?
>
>
> What I'm saying is that we'll have to check this for the different use cases.
> E.g. for dynamically allocated matrices instead of fixed size matrices, there seems to be a
> problem with unavoidable allocations _during compitations_, although did not uet examine this
> completely.
>
> My conclusions are:
> 1 eigen is one of the better libraries wrt rt
> 2 it is still a good policy to check allocations in your code, because, depending on your
> knowledge of eigen, you could inteoduce unwanted allocations. There is a macro you can define
> in eigen that guarantees that there are no heap allocations.
>
> I have no good alternatives, also lapack has problems.
>
> Erwin
>
> Herman Bruyninckx <Herman [dot] Bruyninckx [..] ...> wrote:
> On Mon, 3 Sep 2012, Erwin Aertbelien wrote:
>
> > Before reaching any conclusions, I did a check on an svd with all fixed
> > sizes.
> > Here you can see that these conclusions are premature.
> >
> > Checking this with valgrind shows that there are no heap allocations at all.
>
> So, is my interpretation correct when I say that you are a lot more
> optimistic then the ROS report about the realtime appropriateness of Eigen?
>
> And maybe you also have "non premature" conclusions?
>
> That would be good news... :-)
>
> > I include the small cpp file in attachments.
> >
> > you can compile the test file with:
> >    g++ svd_eigen.cpp -I/usr/include/eigen3
> >
> > Best regards
> >
> > Erwin.
>
> Herman
>
> >
> > On 09/03/2012 12:55 PM, Herman Bruyninckx wrote:
> >> On Mon, 3 Sep 2012, Dominick Vanthienen wrote:
> >>
> >>> hi,
> >>>
> >>> FYI:
> >>> http://www.ros.org/wiki/EigenInRealtime
> >> Interesting... Especially the insight that the EIGEN SVD does runtime
> >> allocations, since this SVD is part of multiple Orocos implementations.
> >>
> >> Herman
> >
> >
>
> --
>    KU Leuven, Mechanical Eng., Mechatronics & Robotics Research Group
>      <http://people.mech.kuleuven.be/~bruyninc> Tel: +32 16 328056
>    EURON Coordinator (European Robotics Research Network) <http://www.euron.org>
>    Open RObot COntrol Software <http://www.orocos.org>
>    Associate Editor JOSER <http://www.joser.org>, IJRR <http://www.ijrr.org>
>
> --
> Orocos-Users mailing list
> Orocos-Users [..] ...
> http://lists.mech.kuleuven.be/mailman/listinfo/orocos-users
>
>
>
>

Realtime-safe matrix library?

Submitted by bruyninc on Fri, 2012-08-24 06:56.

On Fri, 24 Aug 2012, Johnathan Van Why wrote:

> In the near future, we will need a library for manipulating matrices.
> However, it is difficult to find a hard realtime-safe matrix library.

Indeed. This is a holy grail I have been looking for since a decade already :-)

My conclusion: only the "old" Fortran and C libraries (Lapack etc) are
really realtime safe, at the cost of forcing the users to preallocate all
memory in advance. Personally, I don't find this a problem, but (most of) the
"younger generation" have prejudices against Fortran and C...

> It seems as if Eigen may be realtime-safe for fixed-size matrices --
> can anyone confirm this? If not, what is a realtime-safe alternative?
>
> Thank you for any help,
> Johnathan Van Why

Herman

> Dynamic Robotics Laboratory
> Oregon State University