Today we released Eigen 2.0.1 with a nice amount of fixes. Speaking of which, Eigen will see much more usage in KDE 4.3.

First, Gael ported Step to use Eigen, making it easier to build by removing the dependency on GMM++.

Then, I just submitted the Mandelbrot Plasma Wallpaper plugin to kdereview. This allows you to navigate through the Mandelbrot set as a 'live' wallpaper, and you can also 'lock' the view so it behaves like a plain wallpaper. It uses Eigen to emit SIMD instructions in a portable way -- or none at all if they are not available. On the x86 platform where SSE2 may or may not be available, we compile both paths and choose between them at runtime using the excellent Solid library. Perhaps the best part is that the source code is only 840 lines of C++, and the stripped binary size is only 68 kB on x86, all inclusive, with the 2 paths compiled in.

Screenshot (click for full size):


This is shown at "Highest" quality level, which is not very fast, but at Medium level it really flies and in any case the rendering is completely non-blocking and is tiled starting with the tiles you're most interested in, so it gives a good speed impression.

We just released Eigen 2.0 !

Our mailing list is bubbling with activity right now and we're scheduling the 2.1 release for July.

That's all :)

I had to change the release date that I announced in this blog entry: the Eigen 2.0 release is happening on Monday after all! Sorry about the confusion.

The release of Eigen 2.0 will happen this Sunday Monday!

EDIT: The release will happen on Monday after all!

Just in case you want to join our IRC channel (#eigen on irc.freenode.net) and celebrate, here's roughly the timespan in which we expect to make the release, depending on your timezone:

Los Angeles: between 9:00 AM and 10:00.
Toronto/New York: between 12:00 (noon) and 13:00.
London: between 17:00 and 18:00.
Paris/Berlin/Rome/Madrid: between 18:00 and 19:00.
Helsinki: between 19:00 and 20:00.
Moscow: between 20:00 and 21:00.

We now have a release candidate for Eigen 2!

Also, Geoff Hutchison and Carsten Niehaus interviewed us, and Geoff already posted a version of this interview on Macresearch. Thanks a lot!

Testing is more than welcome, as Eigen is quite a stress-test for compilers. Areas where we are desperately looking for testers include:
* The BSDs. Some BSDs do have packages of recent betas, which is a good sign, though.
* Solaris. We haven't heard any report so far.
* AltiVec hardware. This isn't getting tested frequently enough.

We also sometimes hit internal compiler errors in MSVC and ICC, so help working around these compiler bugs is much appreciated.

We have started using CDash and Gael is able to run tests on an amazing number of systems thanks to the INRIA's PIPOL.

The number of projects who are interested in Eigen keeps growing, for example in the past few days there has been discussion at Blender and there have been some very positive messages about Eigen.

Yet another beta for Eigen 2!

Yesterday I released a beta4 but so many issues got fixed since that it's worth making this new beta. I'm starting to be really confident about this being used to build and package KDE 4.2 and KOffice 2.0, not only on Linux but also on Windows and Mac OSX. Just today we've been fixing a Mac OSX issue, several Windows issues, and a couple more generic problems. It's really good to have many users and I must say that in Eigen we're rather spoiled, our users are very active in helping tracking the bugs down -- probably that's the upside of a project being technical in nature.

The API should be 100% stable now -- except of course for the parts of Eigen that we're calling experimental. For the 2.0 release we'll just remove the deprecated stuff (so check your warnings NOW!).

In other news, the forum is very active already so I'm optimistic that we'll reach pretty soon the point where users start helping each other -- something I'm eagerly looking forward to! Like I expected, we're seeing a new group of users on this forum whom we didn't see on the mailing list. So it's great to reach new people. On the other hand there's the risk of balkanization if instead of one we get two disjoint Eigen communities -- that would be pretty bad! We'll see.

I don't normally post non-coding stuff there but today I feel like it....

WHY is it impossible to find good carrots in Toronto??? There are at least 3 or 4 different varieties of carrots available here, some small, some big, but none makes for good grated carrots. I mean, grated carrots should be very juicy, with a sharp taste. Here in Toronto, they are dry and bland (doesn't make much of a difference when you cook them, but the difference is huge with raw grated carrots). I tried at least 3 varieties, organic/farmer's markets, etc, so I'm quite desperate. Anyone knows if one can find the same kinds of carrots here as we have in France? I don't even know the name of the variety I was used to in France... (see here a list of varieties)

Otherwise I guess I should get used to the idea that different continents have to mean different plants but still I thought that fresh grated carrots was a kind of universal simple pleasure, turns out it's not.

We just released the third beta of Eigen 2. Like the rest of the KDE community we are in heavy bug-fixing and polishing mode and this new beta gets us quite close to what we'll soon be calling a release candidate. This is really a result of Eigen's increasing number of users: useful bug reports have been flowing in continuously in the past 3 weeks.

Documentation-wise, here is a FAQ section on vectorization.

Also, we now have a Eigen users forum and I must say that the guys at forum.kde.org, especially Neverendingo, are very helpful.

We just released the second beta of Eigen 2, the new C++ math library that is being used at various places in KDE 4.2 and KOffice 2.0.

It's exciting times for Eigen 2 as many projects are starting to use it. For now, outside of KDE, it's mostly robotics and computer graphics, but there's also a couple of chemistry projects.

People seem to appreciate particularly our very nice API.

Before somebody asks again the usual questions "why does Eigen exist" and "how does it compare to BLAS" let me link to the FAQ...

There are actually more and more open TODO items, with a lot of open jobs, and we now have some introduction to Eigen internals aimed specifically at newcomers. So if you know C++ and some math, consider joining this exciting project!

Anybody here interested in understanding how Eigen works? Or interested in learning about C++ techniques such as expression templates? Or interested in SSE2 vectorization?

I just wrote a documentation page where we look at this very simple example program:

#include<Eigen/Core>

int main()
{
  int size = 50;
  // VectorXf is a vector of floats, with dynamic size.
  Eigen::VectorXf u(size), v(size), w(size);
  u = v + w;
}

Read on to discover why coding a Vector class making this compile to efficient assembly was a nontrivial problem, and to understand how Eigen does it!

PS. Eigen 2.0-beta2 is only a few days away, so the whole online dox will see a massive update very soon.

PPS. We now have many users! Even before our actual release! Seems like we're really filling a big gap.

PPPS. Did I mention that C++ is a wonderful language? I think that the above-mentioned example is a good illustration of that. Incidentally, there recently was a discussion at Reddit about "why C++ doesn't suck" and one commenter mentioned Eigen!

We just released the beta version of Eigen 2.0. It has matured a lot over recent weeks as quite a number of apps have been ported to it: Avogadro, KOffice (mainly Krita and a little KSpread), KGLLib, SolidKreator, KGLEngine. I have started working on a Mandelbrot fractal wallpaper-plugin for Plasma, using Eigen 2.0 for portable vectorization. We also have people on the mailing list doing very interesting things with Eigen 2.0: one is an engineer using it to design airplane engines, a few others use it for advanced computer graphics/vision. We plan to release 2.0 later this fall, in time for KOffice 2.0 and KDE 4.2.

There is now a quite decent Tutorial which is a good starting point if you're interested in Eigen.

Besides polishing for the upcoming 2.0 release, we are already making big plans for the future. Version 2.1 will have a complete Sparse module, which will be very useful for Krita and Step. Gael has been doing the ground work for this module, and recently Daniel Gomez joined us and contributed several improvements.

We still are very few developers -- Daniel is basically the 3rd one, with Gael and me, although a few guys have been helping occasionnally in the past. We definitely can use more help (hint, hint). For that reason we try to polish the documentation a lot, and we can mentor any prospective contributor. Here is a TODO listing many available jobs, all you need is C++ and some math background.

Here's something unrelated to KDE or Free Software, but which I still allow myself to blog about because every nerd here will agree it'd insanely cool.

A team led by famous mathematician Etienne Ghys has produced a series of 9 short videos explaining some very cool geometry and topology. If you ever wanted to get a feel of what 4D geometry is like, this is what you've been looking for. The project is called Dimensions and is translated into several languages already.

The videos are Creative Commons licensed and can be watched online or downloaded. If you have some math background you might want to start directly at Chapter 3 or 4.

You can have a quick tour of screenshots here.

Here is one of these pics... (yes, pics are the only way to attract your attention...)



Update: For the laziest who might not bother to browse the videos... here is chapter 6 explaining all you ever wanted to know about Fractals (Julia and Mandelbrot sets). It requires familiarity with complex numbers which are very well explained in the previous chapter 5 -- which I let you browse for.

It's been some time since I last updated you on Eigen2...

We just released alpha6. At this point, Eigen2 can do all what Eigen1 did (and much, much more) so everyone is encouraged to use it for new code, and to port existing code to it.

We plan to release Eigen 2.0 during this fall, in time for the releases of the software projects which plan to use it (tentatively: KDE 4.2, Avogadro 1.0, KOffice 2.0, OpenBabel 3.0).

Eigen2 is a c++ pure-template-library (all the code in headers) for matrix/vector math (linear algebra) developed by Gael Guennebaud and myself.

Usually I get questions about "how is it different from other libraries" and "you'll never have the resources to compete against $OTHER_LIBRARY which is developed by a huge team". So let me answer them here...

"how is it different from other libraries?"

Other libraries tend to each be specialized on a particular aspect of linear algebra. The first specialization is between fixed-size and dynamic-size: most libraries handle only dynamic-size objects ("vector = new float[n]"), a few others do only fixed-size ("float vector[N]"). Another specialization is between dense and sparse objects. Yet another specialization is between libraries which focus on storage and basic algorithms, libraries which provide advanced algorithms, and libraries which provide convenience features which are not exactly part of linear algebra but very useful to applications.

Eigen2 does all; of that -- though the sparse part is still experimental and not planned for the 2.0 release. For advanced sparse algorithms we plan to let the user choose a backend, be for the rest Eigen2 is entirely self-contained.

Thus, one of Eigen2's main distinguishing features is to be versatile. This was commanded by KDE's needs: KDE is a huge metaproject with very very diverse needs, and Eigen started as an attempt to fulfill them (at that time we wrongly believed that KDE had only simple needs!)

Another distinguishing feature of Eigen2 is that is it thoroughly based on expression templates. Roughly, this means that when you do "v3 = v1 + v2;", instead of computing the sum v1+v2 and then copying it to v3, Eigen first constructs a "sum expression" object representing v1+v2, storing some "metadata" on this algebraic expression. In the "v3=v1+v2" example this allows to avoid the unneccessary temporary returned by "v1+v2". In more complex expressions, it becomes nontrivial to know which temporaries to remove and which to keep; Eigen has a lot of compile-time logic to determine that intelligently. We believe that we are the only library around to do that; other expression templates libraries tend to always remove temporaries, even when evalutating the temporary is actually a good thing. Non-expression-templates libraries have no choice but to always evaluate, and thus miss huge optimization opportunities.

Expression templates don't stop here -- at least not in Eigen2! First, the compile-time metadata which they convey is used to perform more optimizations: generic vectorization (SSE2 to SSSE3, and experimental AltiVec support), and generic loop unrolling. Second, expression templates allow zero-cost method chaining and allows return values to be lvalues. This means that you can write "matrix.row(i) += something" or "matrix.diagonal().start(n).setZero()" and when you look at the generated asm, it is really like handwritten, vectorized, minimal assembly -- nothing remains of the syntactic sugar.

"you'll never have the resources !"

Eigen2 is mostly a 2-persons project and currently has only 11000 LOC, and that includes some experimental code that i'm not even discussing here (Sparse matrices...). By contrast the other libraries (BLAS/LAPACK implementations) are typically developed by large academic teams or, in the case of MKL, by Intel's own engineers, and they are huge:

• the Intel MKL linux/x86 package weighs 250 MB (can't tell how many LOC, it's closed-source).
• GOTO has 750,000 LOC (and it's barely "open source" as its license does not even allow redistribution! makes me wish the term "open source" had not been coined, it's too easily abused)
• ATLAS, the best of the existing truly free libraries, has 400,000 LOC.

So, we can't stand a chance against them, can we?

Well, the first thing to be said is that none of these libs handles fixed-size objects. Yet, this is the majority of use cases for a non-scientific project like KDE. So the above libraries can't be used for these use cases (they are then 20x slower than a library optimized for fixed-size objects like Eigen).

Ok ok, you'll tell me, but what about dynamic-size objects, which is the area in which the above big libraries specialize? A tiny library like Eigen can't compete against them on their own ground, right?

Well, since we have such a generic framework for matrix computations, with a great c++ API and generic optimizations, implementing and optimizing all the usual linear algebra algorithms doesn't take us as long as it takes other projects, nor does it take as many lines of code. In some cases, special care is needed to be cache-friendly (a crucial aspect with very large objects), and fortunately, Gael is extremely good at that.

Here are some benchmark results (dynamic-size, higher is better), details and more results here :



I should say that the benchmarking effort and subsequent optimizations was entirely by Gael. Also, 3 of the 4 benchmarks presented above (matrix-vector, matrix-matrix and triangular solver) are benchmarking solely code written by him (just so you know that eigen is not at all anymore the one-person project it used to be until 6-7 monthes ago).

A big issue for any math-oriented software is vectorization i.e. how to make use of instruction sets such as SSE or AltiVec. Unfortunately this seems to be very hard for the compiler to do automatically, and even with Intel's own compiler, with complicated C++ code such as ours, the benefits were small (like +25% with ICC and +5% with GCC).

Yet, the theoretical benefit of vectorization is huge: with SSE, computations of floats can become 4x faster, and more in certain cases. So what math libraries tend to do, is to write their own explicitly vectorized paths for each architecture (SSE, AltiVec...) they support.

This is what Gael Guennebaud did a few monthes ago in Eigen2. We now have generic wrappers for vectorized operations: they abstract the underlying architecture and packet format, and are template in the numeric type. They got specialized by Gael for SSE2 and SSE3 and by Konstantinos Margaritis for AltiVec. Gael went on and made many parts of Eigen2 use these when applicable, so the end result is that Eigen can draw a large benefit form vectorization instructions when they are available (SSE or AltiVec), in a way that's completely transparent to the user, with graceful fallback to non-vectorized paths.

So we are now getting nice speedups like 4.7x for dot products of large vectors of floats, and 4x for the sum of coefficients of a vector. Gael also wrote a super optimized cache-friendly matrix product also taking full advantage of vectorization (3.5x for large matrices).

But what if Eigen2's vectorization could be used for more than just vector/matrix computations? Its expression templates allow it to be used even for very small computations without any overhead, which makes it an ideal candidate for being used as a generic vectorization framework. Calling 'Real' the type of the numbers we're dealing with, one can proceed as follows:

  enum { packetSize = Eigen::ei_packet_traits<Real>::size }; // number of reals in a Packet
  typedef Eigen::Matrix<Real, packetSize, 1> Packet; // wrap a Packet as a vector

And one can then use this Packet type to abstract the packets of the vectorization architecture. If there is no vectorization, a Packet will contain just one number.

So what I did was to start from here and do a little demo: a Mandelbrot Set viewer. It is up to 2.3x faster thanks to vectorization. It switches automatically between single and double precision. Normally that would have required one to write the vectorized paths twice for each architecture, but not so thanks to Eigen2, all that is abstracted.

If you're interested in checking it out:

svn co svn://anonsvn.kde.org/home/kde/branches/work/eigen2
mkdir eigen2-build
cd eigen2-build
cmake -DTEST_SSE2=ON -DBUILD_DEMOS=ON ../eigen2
make
demos/mandelbrot/mandelbrot

Some notes... it uses Qt's great threading framework to use as many threads as necessary to take advantage of your multi-core CPU; nevertheless the code is so small -- about 200 lines of code all in all, of which about 50 lines for the actual rendering -- that I am thinking that it could be a nice little plasma background-painter (or whatever plasma gurus call that!) for the KDE 4.2 timeframe! I for one would like my fractal wallpaper to come to life. Something's badly needed though: to make the rendering not block the user interaction. If you wish to help with that you're welcome! Another note: if you're serious about fractals be sure to check out Fraqtive! Of course the little toy program I'm presenting here is no match for Fraqtive.

Mandatory screenshot:

This is a followup to my two previous blog entries...

In order to measure the speed overhead of virtual function calls, I wrote a simple 3-float vector class with a dot-product method. One version is done without virtual functions, all in a single Vector class. The other version uses a pure virtual base class VectorBase implementing the dot product, and the vector coordinates accessors are virtual. Aside from that, there is no difference in the code.

The benchmark is here, and archive is here.

The results are impressive: the virtual version runs 3x slower than the no-virtual version.

Cool, now I'll have firm numbers to back up my design choices in Eigen :)

Simon, I hope that answers your request :)

Update:Gael found out that the big speed difference is in fact explained by the fact that the non-virtual function gets inlined. That also explains why more people get the same result with -O3 than with -O2. So that benchmark is not really measuring virtual function calls, instead it's more measuring the fact that virtual functions are less often inlined (and inlinable at all) than non-virtual functions, which is also a good reason not to use them in certain cases, like in the Eigen library for example where inlining of trivial functions is crucial.

My previous blog entry started a debate on the overhead of virtual classes in c++.

First of all let's recall some facts, which I already recalled in my previous blog entry:

In most cases, the overhead of virtual classes in c++ is negligible. In most cases, there is no reason not to use virtual.

There. So if you're coding a GUI application or even many kinds of libraries, there is nothing to see here, move along and keep using the wonderful c++ feature that is virtual classes.

Now let's state the reasons why one might want in certain special cases to avoid 'virtual'.

1. It increases the "sizeof" of your class by the "sizeof" of a pointer, which is 4 or 8 bytes depending on your arch. In most cases you don't care. But if your classes have a small "sizeof" and you are going to create whole arrays of objects of it, then it suddenly becomes a big deal. In Eigen, the Vector2f (vector of two floats) has sizeof==8. If it were implemented as a virtual class, its sizeof becomes 12 (on x86 architecture) or even 16 (on x86_64). This means that an application storing large arrays of such vectors could see its memory usage double.

Note: I am not a c++ expert, so I checked before posting, and the sizeof of virtual classes indeed did increase by the sizeof of a pointer.

2. "Virtual inline" makes no sense, so if the compiler decides to inline a virtual function, it has to strip away its virtualness. There are circumstances under which it just can't allow itself to do that. If you rely heavily on inlining of trivial functions (like Eigen does) and are coding a library or template library (which is the case where inlining a virtual function might be problematic) then just be aware that sometimes the compiler won't inline your virtual functions.

3. (Updated several times -- will blog again to clarify) Even leaving aside inlining considerations, a virtual function call is slower because it requires first a lookup in the class's vtable; Here is a benchmark for that, here is an archive; I first believedthat it was showing the virtual version running more than 3x slower than the non-virtual version, but it turns out to just be that the non-virtual version gets inlined (which supports point 2 above). It seems hard and perhaps pointless to measure the raw cost of virtual calls.

4. Virtual function calls are indirect calls to locations computed at runtime. This may or may not cause trouble to the CPU's branch prediction mechanism. What I heard is that it used to, but modern CPUs don't have much trouble anymore with that. Anyway, this is very hard to quantify in a simple benchmark; if the issue exists at all on modern CPUs then it will probably show up only in involved examples.

Conclusion : There is absolutely no problem about "virtual" for non-computation-intensive code, like e.g. GUI code. In computation-intensive code, like e.g. in the back-end of an OpenGL application, things may be different.

That's all :)

I've been thinking for a while that I should be blogging about some c++ metaprogramming techniques that I learned while coding Eigen:

1. the curiously recurring template pattern

2. "meta" versions of "if", "==", and other things

3. expression templates

Of course these techniques have been "known" for a long time, since they were discovered in the 90's. Some of them are already used in KDE; I saw some use of 1. in KHTML/KJS (edit: although not used for the same thing as discussed in this post), and 2 is quite commonplace anyway. Perhaps 3 is the least-known one, and the only one in which I'd have anything original to say.

Today let's talk about the curiously recurring template pattern.

Executive summary: this technique allows you, in certain cases, to get rid of "virtual" keywords, thus avoiding the overhead of a vtable and indirect function calls (edit: note that this is only one use of this technique, there are other uses which I don't discuss).

( Read more... )

Update: as some nitpickers at reddit pointed out, there is a good Wikipedia page on this technique here.

Dear Lazyweb,

Short version: do you know any way to limit the size of debugging info generated by g++ when compiling code that uses a c++ template library?

Long version: currently, with simple example programs using Eigen2 (a c++ pure template lib) the code generated by g++ at -g2 debugging level is 10x-30x bigger than the code generated at -g1 level, which itself is up to 1.3x-2x bigger than the code generated at -g0 level (no debugging).

The problem is that g++ -g2 emits line number and local variable info not only for the application, but also for the template library itself. Which is not really needed.

What would be cool would be to have g++ suddenly downgrade to -g1 when compiling code from the template library. So ideally, something like a set of #pragmas for controlling debugging levels, would be cool. Unfortunately that doesn't seem to exist. The closest thing that I have found, is the -femit-struct-debug-detailed option, which allows per-file tuning and in some case halves the executable size. However that still leaves the line number info and part of local variables info.

An overkill solution at least to the line-number-info problem would be to install preprocessed versions of our template lib's headers, removing as many linebreaks as possible. Of course that's not optimal, and that wouldn't remove the local variables info.

Any idea?

P.S. Eigen 2.0 is going to rock extremely hard now that Gael Guennebaud has been hugely contributing for monthes now, and Konstantinos Margaritis lent a helping hand. Some teasers -- explicit SSE2/SSE3/AltiVec vectorization ; compile-time intelligent determination of which temporaries to remove and of which loops to unroll ; the list goes on very very long. Gael is already heavily using Eigen 2 in his own 90,000 SLOC project, and I aim to make sure Avogadro can port to Eigen 2 in about one month. From KDE's point of view, this should be 4.2 stuff.

A while ago I asked for proposals for Eigen's mascot owl. We got excellent proposals from 5 artists and exchanged many e-mails on Eigen's mailing list. Finally I uploaded the best pics from each artist and we voted. The vote occurred on the mailing list in order to ensure that mostly people with a true interest in Eigen, and who followed the discussions, participate. Other than that it was open to anyone. 9 people voted.

Note that the drawings below are 'only' sketches (!)

drumroll...dzing! The winner, and personally my favorite, is the "Silly Professor" in the top-right of this pic (Copyright 2008 David Benjamin, licensed under CC-BY-SA):

We'll be sure make use of the 'todo' and 'bugs' owl sketches. The 'engineer' is also very nice for a documentation section on internals.

The very close second (only 1 voice behind out of 9) is this one (Copyright 2008 Ronnie Tucker):


Again, you can see here the other candidates.

According to this, the ISO are now calling a "standard" the Microsoft Office format (which is cynically called "Office Open XML"). I won't elaborate on the reasons why this thing is the opposite of what a standard should be, as this is clear to anybody not influenced by Microsoft.

What is interesting is that TeX, LaTeX, OGG/Vorbis, OGG/Theora, Perl, Python, PHP, Ruby, OCaml, are not standardized by any organization. Yet everybody knows that they are "self-standardized" by the free availability of extensive documentation and/or a by free-as-in-freedom unobfuscated reference implementation.

This shows that standardization organizations are no longer relevant in the software field. What really matters is free full documentation, free full implementation source code, and of course the absence of any patent risk. In other words, coming back to the fundamentals of what a standards is, what matters is evidence that any independent third-party can create and distribute a fully-conforming implementation. When this is the case, nobody needs an organization to certify that it is a standard.

That the ISO just proved itself open to the influence of special interests, is the consequence, not the cause, of its present irrelevance (again, in the software field). Since it is not needed anymore, nobody knows exactly what its mission is, what role it should play. Which allowed Microsoft to redefine that to its own advantage.

I think that the best move the ISO could now make is to acknowledge the limits of its own domain of application, which is the traditional industry, and to acknowledge that the software area is no longer such a traditional industry. In other words, ISO (and other standards organizations) should leave the whole software area, where they are not needed anymore.

Thinking further about this, here is perhaps the deep reason why in the end, software is beyond the field of application of standards organizations. This reason is that software is actually "just" mathematics. That was not obvious in the first decades of the computer industry, but it is becoming a concrete reality. Publishing the source code of a program is the equivalent of publishing the proof of a theorem. This is why the free software movement is changing the rules regarding standardization of software. In mathematics, once the proof of a theorem is published, there is no need for any authority to certify that the theorem is true. Everybody can independently look at the proof and realize that it is. And everybody can use the theorem without consulting its author. Likewise, once a free format specification is published with a free software implementation, there is no need for any authority (i.e. any standards organization) to certify that it can be used independently by any third-party (i.e. that it can be considered a standard). Thus, in the 21st century, a "standard" is just anything that has a full, free software implementation.