Jump to content
The Dark Mod Forums

Recommended Posts

I have switched our Matrix4 class to use the Eigen library internally (more specifically, an Eigen::Transform which can represent geometric transformations which decompose to a 4x4 Matrix). The advantages of Eigen are:

  1. It's a well-tested and respected linear algebra library, which means we don't need to maintain our own code to perform already-solved problems like matrix multiplication.
  2. It can potentially use SIMD instructions (SSE, AVX etc) to improve performance. I haven't yet looked into whether this happens automatically or whether we have to explicitly enable these optimisations.
  3. It is header-only, so should not present any build issues on the various platforms.

Our Matrix4 class still exists but it is now just a syntactic wrapper around the Eigen implementation, and several methods which performed matrix maths manually have now been changed to forward directly to Eigen methods like inverse(), transpose() etc. Since Matrix4 is now well covered by unit tests, I am pretty confident that nothing is broken because of this change, although it's still possible of course.

@greebo Next time you pull from my master branch, you will need to do two things:

  1. Issue the git submodule update -i command (or GUI equivalent, if you're using one) to populate the external/eigen directory with the Eigen git repository.
  2. Update include paths in the VS project so that external/eigen is added to the header file search paths.

Since it's already cross-platform and header-only, and the only current usage is with an existing class wrapper, I hope no other changes should be required on Windows.

  • Like 2
Link to comment
Share on other sites

Nice, and interesting too. Thanks for the heads up, I'll be happy to do the necessary steps in studio once I'm updating the master again. Plus thanks for carving out all the unit tests, the test suite is really starting to grow!

With regards to the external submodule, is there a strong reason to include it through git? So far all the third-party libs have been specified as (cmake) package dependency (like libpng, libvorbis, etc.), and the Windows side has been handled by extracting the windeps zip to the working tree. Has Eigen different requirements? Or should we move more stuff to submodules?

  • Like 1
Link to comment
Share on other sites

1 hour ago, greebo said:

With regards to the external submodule, is there a strong reason to include it through git? So far all the third-party libs have been specified as (cmake) package dependency (like libpng, libvorbis, etc.), and the Windows side has been handled by extracting the windeps zip to the working tree. Has Eigen different requirements? Or should we move more stuff to submodules?

There is no specific requirement for it to be a submodule — there is a package available on Ubuntu through APT, and the headers could of course be included in the windeps package. But given that it is header-only and never requires any actual library file or changes to compile/link flags, it seemed simpler to me to include it (in)directly in the source much as we do already with the libfmt library, rather than requiring changes to the windeps package. With a submodule it is very easy to update to a new version just by changing the commit hash of the submodule to point to a new tag, whereas other approaches would require more maintenance at our end (either regenerating windeps or copying a complete new Eigen tree into the source if we were using source inclusion without a submodule).

I don't suggest moving to submodules for everything though. This would not work well for things that require an actual library like libpng (and we certainly don't want to build everything from source[1]), so the windeps approach is still ideal here. It would be possible to make libfmt a submodule too, but given that it is small and unlikely to need much updating, there isn't a strong reason to do so. And of course if we find that submodules cause some unanticipated headaches, like changing their GitHub URL or regularly rewriting their history so our target commit hash no longer works, it will always be an option to fall back to treating Eigen like any other dependency (just without a library file).

[1] It has crossed my mind that perhaps we should include wxWidgets as a submodule and build it from source, given the slow release cycle on Linux and the variety of annoying GTK-related bugs. But that's a big can of worms.

Link to comment
Share on other sites

Ok, I'll also update the wiki compilation articles then, because including the submodules while cloning is something I tend to forget myself. It left me scratching my head two times when trying to build something from source in the past, until I realized I might be missing something the sources expect to be there from the start.

Re libfmt: in this case I was forced to include it in the source tree, because I couldn't get it to compile with the Ubuntu libfmt package. It can be configured as header-only (by #DEFINE) or as static library, but the debian package somehow had conflicting linker flags, and I couldn't get it to link (I think it was due to the -fPIC setting).

On a related note, I obviously haven't googled yet, but would it be possible to configure the windeps as optional submodule and have Windows coders check it out on purpose? I have all the binaries in a separate repository, so this would make the compilation instructions a bit easier.

Link to comment
Share on other sites

Not sure that Eigen is needed.

If you wanted to compute SVD of NxM matrix, then indeed writing it yourself would be a problem.
But what problems you can't solve easily with a 4x4 matrix? Do you perform something like Principal Components Analysis?
Does 4x4 matrix multiplication pose a problem to anyone? 😲

I'm very skeptical about any performance improvements due to this change.
Yes, you have 4xfloat and 2xdouble with SSE2, but it seriously matters only when you have arrays of data and do purely numeric operations with them.

The submodule is of course a nuisance. For instance, having a submodule breaks GitHub's integration with Hg and Svn: only Git client can fetch them.
Luckily, nobody will need to actually work with the submodule, so it won't add much confusion.

To me it looks like adding dependency without reason.

Link to comment
Share on other sites

2 hours ago, greebo said:

Re libfmt: in this case I was forced to include it in the source tree, because I couldn't get it to compile with the Ubuntu libfmt package. It can be configured as header-only (by #DEFINE) or as static library, but the debian package somehow had conflicting linker flags, and I couldn't get it to link (I think it was due to the -fPIC setting).

Right, I recall having to set a #define to get it to work as header-only when I was setting up the CMake build. I think the current arrangement is fine, since it is small enough that including it in the main source tree isn't a problem.

2 hours ago, greebo said:

On a related note, I obviously haven't googled yet, but would it be possible to configure the windeps as optional submodule and have Windows coders check it out on purpose? I have all the binaries in a separate repository, so this would make the compilation instructions a bit easier.

Yes, that would certainly be an option, although Git isn't particularly suited to maintaining large binary files (checking out could become very heavy since the entire history would be downloaded, and there isn't an efficient way of tracking diffs between binaries). I don't know how large the current windeps archive is, but as a Git repository it would grow over time, and I could imagine it becoming quite large after several major updates like switching to a new wxWidgets version.

Of course if you're already maintaining the archive in a Git repository and don't encounter any problem with size, then these concerns are less relevant, but it might still make things slightly more complicated to checkout (Linux users would not want the windeps at all, but if they ran "git submodule update -i" they would get everything).

Link to comment
Share on other sites

49 minutes ago, stgatilov said:

Not sure that Eigen is needed. To me it looks like adding dependency without reason.

You're right, it's definitely not needed, and I am aware of your dislike for external dependencies (which is why I'm certainly not suggesting incorporating Eigen or anything else into the main game).

However:

  • It's header-only, so we don't pay for anything we don't use at either compile or runtime.
  • I really, really don't like re-inventing wheels (or maintaining badly-reinvented wheels by others).
  • It simplifies the code at our end, since we don't need our own implementation of common functionality. Until a few weeks ago we didn't even have an operator* for matrix multiplication (I had to add one), and I'm still not sure if we have an operator+. None of these are difficult or complicated but it's just more lines of code that we shouldn't need to write because it's already a well-understood problem.
  • It has the potential to be faster due to the use of SIMD instructions. Again, we could do this ourselves but I'd rather have experts work on it rather than risk screwing it up myself.

Still, it's somewhat experimental at this stage and if it does turn out to cause some unexpected difficulties we can always back it out. I hope that won't be necessary though, since all the unit tests pass and we actually use Eigen at work so I know it is fully supported cross-platform.

49 minutes ago, stgatilov said:

If you wanted to compute SVD of NxM matrix, then indeed writing it yourself would be a problem.
But what problems you can't solve easily with a 4x4 matrix? Do you perform something like Principal Components Analysis?
Does 4x4 matrix multiplication pose a problem to anyone? 😲

It's not just the basic multiplication functionality that can be/has been replaced. This is what our getInverse() method (which calculates the affine inverse, not the matrix inverse) used to look like:

Matrix4 Matrix4::getInverse() const
{
  Matrix4 result;

  // determinant of rotation submatrix
  double det
    = _m[0] * ( _m[5]*_m[10] - _m[9]*_m[6] )
    - _m[1] * ( _m[4]*_m[10] - _m[8]*_m[6] )
    + _m[2] * ( _m[4]*_m[9] - _m[8]*_m[5] );

  // throw exception here if (det*det < 1e-25)

  // invert rotation submatrix
  det = 1.0f / det;

  result[0] = (  (_m[5]*_m[10]- _m[6]*_m[9] )*det);
  result[1] = (- (_m[1]*_m[10]- _m[2]*_m[9] )*det);
  result[2] = (  (_m[1]*_m[6] - _m[2]*_m[5] )*det);
  result[3] = 0;
  result[4] = (- (_m[4]*_m[10]- _m[6]*_m[8] )*det);
  result[5] = (  (_m[0]*_m[10]- _m[2]*_m[8] )*det);
  result[6] = (- (_m[0]*_m[6] - _m[2]*_m[4] )*det);
  result[7] = 0;
  result[8] = (  (_m[4]*_m[9] - _m[5]*_m[8] )*det);
  result[9] = (- (_m[0]*_m[9] - _m[1]*_m[8] )*det);
  result[10]= (  (_m[0]*_m[5] - _m[1]*_m[4] )*det);
  result[11] = 0;

  // multiply translation part by rotation
  result[12] = - (_m[12] * result[0] +
    _m[13] * result[4] +
    _m[14] * result[8]);
  result[13] = - (_m[12] * result[1] +
    _m[13] * result[5] +
    _m[14] * result[9]);
  result[14] = - (_m[12] * result[2] +
    _m[13] * result[6] +
    _m[14] * result[10]);
  result[15] = 1;

  return result;

versus what it now looks like:

Matrix4 Matrix4::getInverse() const
{
    return Matrix4(_transform.inverse(Eigen::Affine));
}

Reducing dozens of lines to a single line is a big win in my book. Of course I am aware that the code still exists somewhere, but it's no longer code that we ourselves have to maintain (or even read).

49 minutes ago, stgatilov said:

I'm very skeptical about any performance improvements due to this change.
Yes, you have 4xfloat and 2xdouble with SSE2, but it seriously matters only when you have arrays of data and do purely numeric operations with them.

I'm not expecting any massive performance improvements either. Performance is only a secondary concern. Even if the code runs at exactly the same speed I will be happy with the LoC reduction and the improved maintainability at our end. If a few SSE instructions here and there can slightly improve the performance of a particular operation, that's just icing on the cake.

49 minutes ago, stgatilov said:

The submodule is of course a nuisance. For instance, having a submodule breaks GitHub's integration with Hg and Svn: only Git client can fetch them.
Luckily, nobody will need to actually work with the submodule, so it won't add much confusion.

As Greebo and I discussed earlier, avoiding the submodule and using the existing dependency mechanism would be possible if it turns out to be a problem. And honestly if people are trying to interact with our Git repository using something other than Git, that's really their problem. I don't think we should avoid useful Git features just because someone somewhere might still think it's 2008 and want to check out our code using their SVN client.

Link to comment
Share on other sites

30 minutes ago, OrbWeaver said:

Linux users would not want the windeps at all, but if they ran "git submodule update -i" they would get everything

That was my main concern. The whole reason the windeps are kept separate is that Linux users don't need to check out all these windows binaries. If there is no easy distinction and Linux users have to unconditionally checkout all submodules, then the point is moot.

Link to comment
Share on other sites

1 minute ago, greebo said:

That was my main concern. The whole reason the windeps are kept separate is that Linux users don't need to check out all these windows binaries. If there is no easy distinction and Linux users have to unconditionally checkout all submodules, then the point is moot.

They don't have to, but there does not seem to be a convenient way for us to specify which modules should be checked out by default and which shouldn't. Either you run the command to checkout everything, or you would have to manually specify which ones to checkout (e.g. "git submodule update -i externals/eigen"), which would rapidly become annoying if we ever had more than one submodule. So I agree that it would be preferable to keep the dependency package separate for now.

Link to comment
Share on other sites

  • 2 weeks later...

Ok, got everything merged, and as a bonus, it's even compiling now. 😑

That submodule is *huge*, it took me 2 minutes to get it fetched and checked out. Not sure I really like that huge tree lying around, it reminds me a bit of the boost times. But I can live with it.

For VC++ I added a pre-build script to check for the eigen sources, and if they're not present in the expected path, it will try to init the submodule itself by calling git submodule update -i. The wiki articles and the README.md file have been adjusted too for clarification.

Link to comment
Share on other sites

15 minutes ago, greebo said:

That submodule is *huge*, it took me 2 minutes to get it fetched and checked out. Not sure I really like that huge tree lying around, it reminds me a bit of the boost times. But I can live with it.

That's odd, it shouldn't be that big. I just did a clean clone of Eigen into a temporary directory and it takes me just under 17 seconds, with a total of 101.68 MB downloaded (which I agree is a little heavy for some linear algebra headers). But I guess this is heavily affected by internet speed and disk performance.

However, if I do a "shallow clone" with "git clone --depth 1" it makes a huge difference: 2.4 seconds to download and only 3.14 MB. I wonder if we can make the submodule shallow by default.

Link to comment
Share on other sites

I felt the urge to check the network activity when it kept me waiting, to make sure it didn't just stall - I got around 500k/sec cloning from gitlab. I probably just ran into a bad mirror.

A shallow clone of the submodule is probably a good move, since we're not really interested in the history anyway, count +1 for that. But it's not just the git pack, it's also the checkout which is fairly large, it's 1600 files (14 MB). As you put it, it's not exactly on the lightweight side for algebra :) I guess we're not really using all of that tree, are we?

Link to comment
Share on other sites

1 hour ago, greebo said:

A shallow clone of the submodule is probably a good move, since we're not really interested in the history anyway, count +1 for that. But it's not just the git pack, it's also the checkout which is fairly large, it's 1600 files (14 MB). As you put it, it's not exactly on the lightweight side for algebra :) I guess we're not really using all of that tree, are we?

No, we really don't want anything outside of the top-level Eigen directory, where the headers are. But you are right, the repo contains a lot of other crud: an entire "unsupported" directory with another copy of the whole header tree, 2 megabytes of documents, tests, demos, a directory full of Fortran files...

To be honest, the main reason I went for a submodule was for simplicity, and the fact that I wouldn't be imposing extra work on you to update the dependencies package on Windows. But if you're happy to do that and would rather avoid the cruft involved in importing a whole external repo into the source tree, I'm fine with treating Eigen just like any other external dependency and skipping the submodule entirely. I'll need to check that the Ubuntu package provides what we need, but if so it should be pretty easy to update the CMake scripts to check for this rather than looking in the external/eigen directory.

Link to comment
Share on other sites

That was very straightforward. As expected, the Ubuntu package worked fine and updating the CMake was trivial, since we can just use pkg-config to locate the headers. As of 131139539c3a799540 the submodule is gone (i.e. I deleted the .gitmodules, but you may still need to manually delete the external/eigen directory if it's checked out at your end).

Link to comment
Share on other sites

DarkRadiant is not compiling for me:

In file included from /home/thebigh/Games/DarkRadiant/libs/math/AABB.cpp:4:
/home/thebigh/Games/DarkRadiant/libs/math/Matrix4.h:18:10: fatal error: Eigen/Geometry: No such file or directory
   18 | #include <Eigen/Geometry>
      |          ^~~~~~~~~~~~~~~~
compilation terminated.
make[2]: *** [libs/math/CMakeFiles/math.dir/build.make:63: libs/math/CMakeFiles/math.dir/AABB.cpp.o] Error 1
make[1]: *** [CMakeFiles/Makefile2:430: libs/math/CMakeFiles/math.dir/all] Error 2
make: *** [Makefile:130: all] Error 2

 

Is Eigen now something I need to obtain on my end? I'm on Ubuntu 20. I already have libeigen3-dev installed.

Edited by thebigh
add

My missions:           Stand-alone                                                      Duncan Lynch series                              

                                      Down and Out on Newford Road              the Factory Heist

                                                                                                  A House Call

                                                                                                  The House of deLisle                                                                                                  

                              

Link to comment
Share on other sites

In case you cloned my repository, I haven't integrated the latest changes yet, so you still need to update the submodule first. This step can be skipped once I integrated OrbWeaver's master branch.

Link to comment
Share on other sites

No problem, I'll wait for the next update :]

My missions:           Stand-alone                                                      Duncan Lynch series                              

                                      Down and Out on Newford Road              the Factory Heist

                                                                                                  A House Call

                                                                                                  The House of deLisle                                                                                                  

                              

Link to comment
Share on other sites

Yep, it compiles now. Cheers.

My missions:           Stand-alone                                                      Duncan Lynch series                              

                                      Down and Out on Newford Road              the Factory Heist

                                                                                                  A House Call

                                                                                                  The House of deLisle                                                                                                  

                              

Link to comment
Share on other sites

  • 1 month later...
16 hours ago, AluminumHaste said:

Man I love seeing 24threads at 100% utilization while compiling, so awesome!

Man.. I just have to do with 4... 😩

Edit: Well, in the meantime I can do the dishes. That's what I call multitasking.

Edited by datiswous
  • Haha 1
Link to comment
Share on other sites

Recently I have learnt about new cool toy for analyzing build time in Visual Studio: C++ Build Insights
Basically, MSVC build tools now generate events for various things, which allows to see timelines, aggregated information, etc. The events are based on Event Tracing for Windows, which is a relatively known framework among some very cool guys.

Since I was thinking about picking up the DarkRadiant side again, I decided to give it a run on DR projects.
To make timings easier to understand, I limited parallelism to 1 project and 6 compiler threads at a time (I have 6 physical cores).
I built vcperf from sources (the latest tag on GitHub), because stock VC2019 build does not include information about templates, and that's the main problem usually.
I used VC2019 to build Debug x64 build. I think release build does not matter much, since developer usually work with Debug and have to wait for it all the time.

I'll try to explain the findings.


Here is the overview of stuff: it explains how much time each part of compiler takes:image.thumb.png.5a9236f7c6afd26bd842cecb028954fc.png

In most cases, I will only look at "Exclusive Direction".
Inclusive stuff is too bad because it takes common stuff into account many times when we sum up the values.
CPU Time is a better metric in general, but most of low-granularity timings don't provide it --- and that's what we want to analyze. Besides, I have specifically ensured that there is one thread per physical core so CPU time and duration should be more or less the same.

So, the whole build takes 986s.
Out of it, C1DLL takes 785s. That is the frontend part of compiler, which most likely contains parsing C++ code and doing template instantiations. At least, an image in this article says that template instantiation is part of frontend. And otherwise numbers simply don't match.
The backend takes something like 175s --- most of the other time.

Clearly, the 80% of the time is spent in frontend, so let's given it a closer look.
 

First of all, let's look at C++ code parsing:
image.thumb.png.7755a36800e8b969b93afc8e4714cba4.png

The whole parsing takes 172s. By filtering items containing some substring, I learned that:

  • Parsing Eigen takes 31.5s
  • Parsing Wx takes 32.6s
  • Parsing MSVC standard headers takes 34.5s
  • Parsing Windows SDK headers takes 24s
  • Parsing w32deps includes except Eigen and Wx takes 11.4s
  • Parsing all the rest takes 38.5s

The number for Wx is OK, since it is very important for DR. Standard includes are also understandable --- that's STL and windows.h. But isn't Eigen excessive here?
Note that parsing time can be reduced almost to zero by using precompiled headers properly. According to the stats I see, windows.h is parsed 63 times, which gives 33s in total. If it is always in PCH, than it would be parsed at most 19 times....

Anyway, parsing takes about 17% of total build, so it is hardly a real problem.
 

Now we come to template instantiations --- the root of evil for slow C++ builds 🤬
image.thumb.png.841bc8796108be1528f8180045df2c6b.png

I computed sum of all Durations in this list, and got 605s --- this approximately matches 785s - 172s  (frontend - parsing). And that's 60% of whole build time.
Quite obviously, Eigen is the king here: all the most expensive instantiations come from Eigen. Here is breakdown:

  • Eigen::* takes 461s
  • std::* takes 122s
  • All the rest takes 22s

Unless someone decides to use boost, STL is usually the most offensive part of template bloat. However, Eigen manages to top it in 4x times.


So the conclusion is: adding Eigen slowed down build in at least two times.
If it was wxWidgets, it would be OK, since GUI is the most important part of DarkRadiant.
But such cost for 4D vectors and matrices? Seriously?!
Does it even offer any added value in DR?

UPDATE: Given that backend most of the time generates machine code for the template instantiations, I bet the real slowdown can be even 2.5-3 times. If someone remembers when Eigen was integrated, it can be checked directly.

Link to comment
Share on other sites

Most likely there is another problem with Eigen: very slow Debug performance.

I have no idea what are typical CPU-intensive workloads in DR, but my impression was that they rarely have numeric nature. If this is true, then slow Debug performance is not a problem (and potentially faster Release performance is not a benefit).

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recent Status Updates

    • Petike the Taffer

      I've finally managed to log in to The Dark Mod Wiki. I'm back in the saddle and before the holidays start in full, I'll be adding a few new FM articles and doing other updates. Written in Stone is already done.
      · 4 replies
    • nbohr1more

      TDM 15th Anniversary Contest is now active! Please declare your participation: https://forums.thedarkmod.com/index.php?/topic/22413-the-dark-mod-15th-anniversary-contest-entry-thread/
       
      · 0 replies
    • JackFarmer

      @TheUnbeholden
      You cannot receive PMs. Could you please be so kind and check your mailbox if it is full (or maybe you switched off the function)?
      · 1 reply
    • OrbWeaver

      I like the new frob highlight but it would nice if it was less "flickery" while moving over objects (especially barred metal doors).
      · 4 replies
    • nbohr1more

      Please vote in the 15th Anniversary Contest Theme Poll
       
      · 0 replies
×
×
  • Create New...