Shifting to lists

I realize this post is a bit “raw”, since I didn’t take the time to explain all the concepts here. Read further only if you’re a programmer, or at your peril.

As stated in that long awaited progress report, I experienced some major re-shifting of my way of thinking about computer code. This shift comes from the read of the online book Data-Oriented Design
For me, this was a very insightful read. I don’t want to paraphrase the author(s?), but in short, he advocates the use of Database-style tables for practically everything, and he does so as a game programmer. This seemed really counter-intuitive for me at first (I’m way more familiar with OO than DB), but he makes a lot of valid points, when it comes to the underlying modern hardware strengths and weaknesses (Central to the thesis is the attempt to minimize cache misses for both code and data), as well as the inherent better opportunities at parallelization when organizing data and logic in this database manner.

And all this, on top of the (debated) advantage of better code reuse/maintainability/reaction to design changes, shared by Entity-Component systems. But this “table-only” philosophy really goes one step further than a mere Entity-Component architecture. I don’t know if everyone would agree on this approach, but for me it seems worth the effort to at least try applying those advices on critical parts of a system. And, when early in the development phase of a new project, why not on everything ? Oh, I’m well aware of the hammer looking for a nail here, me discovering this with a new eye, but there seem to be valid points at almost every level, and this philosophy is quite reminiscent of the state of mind one must embrace when dealing with GPU shaders.

The author also pushes for the use of the Structure of Arrays (SoA) over the Array of Structure (AoS) as a layout.
AoSvsSoAThe Structure of Arrays allows better opportunities for type and usage coherency

While it is trivial to convert a single AoS to a SoA in C or C++, if we had to rely on this SoA pattern every time, we’d really want something like a generic container which would behave like a SoA. And what about sparse versions, where one could index all this data the way a hash-table does ? Well, I craved for a generic solution, so I looked around in the hope of borrowing an existing algorithm for this.
And I found nothing.
I mean, really nothing.

Alright, so, let’s try and deal with those tables ourselves, now, shall we ?

I started to mess around with this, and made several shots at defining a generic sparse Structure of Arrays with the help of C++ templates and even a little bit of macros… This was tough. This was reinventing the wheel on some parts while coming up with an entire new design on other parts, learning and dealing with new C++11 variadic templates along the way. Time had passed when I finally came up with an implementation of a generic container of any-number of any-typed “colums”, each one arranged as an array sharing the same index (lightning-fast iterations), which supported random-access from a common key, all the while using the least amount of memory space (to minimize those expensive cache misses), contrary to the more common alignment-friendly structures. This was a LOT of work.

But I did it. I guess. It is not really extensively covered with tests yet. But I ran a few still, and performance-wise, on the insertion and random-access searches, I’m not ashamed compared to stl containers. Functionality-wise, of course, I know of nothing similar at present (yeah, that’s why I undertook this work in the first place).

I still have to design a nice homogenous interface for all types of tables I’ve come up with (indexed or not on a key / holding their own internal transformed data during parallel processes or not, etc.) but the core is ready.
That code won’t even compile with VS2012, as variadic templates are used, so I’ll have to switch to VS2013 if I really am to embrace this “all-about-list” paradigm. But now that the main problems are tackled, this is tempting to give this paradigm a real try for NeREIDS, as it will allow me to switch more heavily towards parallel algorithms, the current grail of computer code.

Leave a Reply

Your email address will not be published. Required fields are marked *