Three Big Lies of Software Development

(Lie #1) Software is a platform

I blame the universities for this one. Academics like to remove as many variables from a problem as possible and try to solve things under ``ideal'' or completely general conditions. It's like the old physicist jokes that go ``We have made several simplifying assumptions... first, let each horse be a perfect rolling sphere...''

The reality is software is not a platform. You can't idealize the hardware. And the constants in the ``Big-O notation'' that are so often ignored, are often the parts that actually matter in reality (for example, memory performance.) You can't judge code in a vacuum. Hardware impacts data design. Data design impacts code choices. If you forget that, you have something that might work, but you aren't going to know if it's going to work well on the platform you're working with, with the data you actually have.

(Lie #2) Code should be designed around a model of the world

There is no value in code being some kind of model or map of an imaginary world. I don't know why this one is so compelling for some programmers, but it is extremely popular. If there's a rocket in the game project for example, rest assured that there is a ``Rocket'' class (Assuming the code is written in C++ or some other language that emphasizes OOP -- even in C the programmer will often attempt to create a rocket_t and an OO-like interface of free functions) which contains data for exactly one rocket and does ``rockety'' stuff. With no regard at all for what data transformation is really being done, or for the layout of the data. Or for that matter, without the basic understanding that where there's one thing, there's probably more than one.

Though there are a lot of performance penalties for this kind of design, the most significant one is that it doesn't scale. At all. One hundred rockets costs one hundred times as much as one rocket. And it's extremely likely it costs even more than that! Even to a non-programmer, that shouldn't make any sense. Economy of scale. If you have more of something, it should get cheaper, not more expensive. And the way to do that is to design the data properly and group things by similar transformations.

(Lie #3) Code is more important than data

This is the biggest lie of all. Programmers have spent untold billions of man-years writing about code, how to write it faster, better, prettier, etc. and at the end of the day, it's not that significant. Code is ephemeral and has no real intrinsic value. The algorithms certainly do, sure. But the code itself isn't worth all this time (and shelf space! -- have you seen how many books there are on UML diagrams?) The code, the performance and the features hinge on one thing -- the data. Bad data equals slow and crappy application. Writing good software means first and foremost understanding the data.

The above is a repost from Mike Acton from Insomniac Games

We could all just put our computers in vacuums and accelerate the electrons faster than the speed of light. How would you like that, asshole?

We could all just put our computers in vacuums and accelerate the electrons faster than the speed of light.
Not possible.

How would you like that, asshole?
Confirmed for a Jew or Jew sympathizer who meticulously and religiously follows his set theory dogma and object-oriented programming scriptures.

Lie1:
Big O notation is just a type of analysis that you can use if you want to, and it picks up important things, and also leaves out things that may be important in another sense, but to take that into consideration would complicate the analysis. The fact that it is an abstraction should be obvious to anyone who understands what it is.

Lie2:
I don't understand the problem with creating a rocket class. Lots of games have random pieces of code that are used by only certain types of things in the game, and oo is a pretty good method for organizing all of that. I mean, where else would it all go, and how would it all get called without using some form of polymorphism?

Lie3:
Does this just say to use databases effectively? Then that will take some effort to integrate that in the code...both for producing the data and for reading it.

>>4
A database is simply a store of data. I don't really know why he would assert that data is more important than code when they are both equally essential. You have input data to input into the system, a software process to manipulate the input and finally some data output that is usually intended for human interpretation.

>>4
Big O notation is just a type of analysis that you can use if you want to, and it picks up important things, and also leaves out things that may be important in another sense, but to take that into consideration would complicate the analysis. The fact that it is an abstraction should be obvious to anyone who understands what it is.
You missed the point. The point was that software as a platform is a lie. You got distracted.

I don't understand the problem with creating a rocket class. Lots of games have random pieces of code that are used by only certain types of things in the game, and oo is a pretty good method for organizing all of that. I mean, where else would it all go, and how would it all get called without using some form of polymorphism?
That's because you're just following what everyone else is doing, because you learned how to program the OOP way. It's not your fault that you don't know any better. It essentially boils down to how all languages implement OOP, class objects are implemented in array-of-structure order which just does not respect CPU cache utilization period. What the original author is pushing for is structure-of-array order where each field is stored in it's own homogeneous array representing all such objects of that type. And this is where OOP breaks down, and really what you're doing is a hybrid of functional and flow-based programming where you compose transformations over sets of data. This approach is known as data-oriented design.

Here's what a rocket implementation in DOD would look like in a stripped down subset of C++. You might see I'm violating principles of encapsulation and what not, but I warn you don't subscribe to such nonsense:

struct rockets
{
   size_t count;
   int *type;
   int* stage;
   float4* position;
   float4* velocity;
   float4* acceleration;
   float4* force;
   float* mass;
   float* fuel;
   mesh_handle* mesh;
   material_handle* material;
   // more fields...

   // ctor/dtor, other functions here

   void update(float time_delta);
}

void rockets::update(float time_delta) {
    for (size_t i = 0; i < r.count; ++i) {
       float4 delta_impulse = multiply(force[i], time_delta);
       delta_impulse = divide(delta_impulse, mass[i]);
      
       float4 accel = add(acceleration[i], delta_impulse);
       acceleration[i] = accel;

       float4 delta_velocity = multiply(accel, time_delta);
       float4 vel = add(velocity[i], delta_velocity);
       velocity[i] = vel;

       float4 delta_position = multiply(vel, time_delta);
       position[i] = add(position[i], delta_position);
    }
}

The above update will often be much faster than the equivalent fine-grained AoS OO method because it doesn't pollute cache lines with with fuel, type, stage, mesh, material, etc. You don't need polymorphism/virtual functions either, you can pull those out of the transformation/update loops and eliminate branching/switch statements/polymorphic dispatch completely by sorting different types of objects into their own sets of arrays and updating each in sequence (or in parallel if you apply task-oriented parallelism strategies). It often results in much simpler code too. How much faster is this approach? Try 10-20x faster. I'm not joking. The biggest bottleneck with modern CPUs and GPUs isn't the instruction pipeline, it's memory latency. A lot of software just causes CPUs to spend most of their time spinning idly while waiting for cache line fetches or flushes.

I use similar code in my own projects, except I'm often dealing with thousands or tens of thousands of actors, and many of my for loops are actually invocations of a parallel_for template function which partitions the work into work units and offloads them to other threads/CPU cores through a task scheduler/thread pool.

Does this just say to use databases effectively? Then that will take some effort to integrate that in the code...both for producing the data and for reading it.
No, it's about understanding how the hardware works with the data and what data you need for each unrolled transformation, and designing your data structures so that you're doing the minimum amount of work necessary on the CPU or GPU to accomplish your task. The code you need will naturally emerge from the design of your data.

>>6

[quote]
You don't need polymorphism/virtual functions either, you can pull those out of the transformation/update loops and eliminate branching/switch statements/polymorphic dispatch completely by sorting different types of objects into their own sets of arrays and updating each in sequence
[/quote]

Thanks for the tip. I can see how that would be a lot faster. Kind of like doing:


for(int i = 0; i < MAX; i += 2) {
  printf("%d is even\n", i);
}
for(int i = 1; i < MAX; i += 2) {
  printf("%d is odd");
}

instead of:


for(int i = 0; i < MAX; i++) {
  if(i%2) {
    printf("%d is odd\n", i);
  } else {
    printf("%d is even\n", i);
  }
}

>>7
Yep, pretty much, or in a more classical OO sense:

std::vector<alien> aliens;
std::vector<rocket> rockets;
std::vector<car> cars;
std::vector<cdr> cudders;

float time_delta = get_time_delta();

for (alien& a : aliens) {
    a.update(time_delta);
}

for (rocket& r : rockets) {
    r.update(time_delta);
}

for (car& c : cars) {
    c.update(time_delta);
}

for (cdr& c : cudders) {
    c.update(time_delta);
}

Except, with data-oriented design, you don't stop at the class object level, you go inside each class and you pull out each member variable/field (or dependent groups of fields if that dependency always holds) and put it in its own homogeneous array.

Now, to the seasoned OOP programmer who has been sipping the koolaid for far too long, he will see all of this as wrong wrong wrong. Pulling out the polymorphic dispatch and replacing it with what he would refer to as ``nasty hard-coded loops'' is evil to him as it seemingly makes it ``more difficult'' to maintain. The may be true in some circumstances. Maybe in traditional GUI or enterprise architectures it might be true to some degree where you want some loose coupling, but not in game development, simulations, artificial intelligence, automation, etc. programming where you often have full control over the software.

And in my previous example, I only had a single struct rockets but in a much larger real-application of data-oriented design to a scene graph, what would traditionally be considered an object is actually spread out over a whole bunch of unrelated modules (typically implemented as structs/classes themselves), and you may have non-member functions which perform compositional transformations and the likes. You usually break it down into different modules that you can compose in an ad-hoc manner, or reuse on different projects or sequels, etc.

And this isn't just some esoteric approach, this is and has been used in big-budget multi-million dollar projects.

For example, DICE has been using it in Battlefield Bad Company 2 and Battlefield 3: http://www.slideshare.net/DICEStudio/introduction-to-data-oriented-design

Pretty much any big-budget triple-A title that has come out in the last couple of years applies such an approach in their engine and code base. It's really the only way they've managed to maximize the languishing console hardware.

>>8
Lisp (DSL):

map 'update [@aliens @rockets @cars @cudders]

C/C++:

std::vector<alien> aliens;
std::vector<rocket> rockets;
std::vector<car> cars;
std::vector<cdr> cudders;

float time_delta = get_time_delta();

for (alien& a : aliens) {
    a.update(time_delta);
}

for (rocket& r : rockets) {
    r.update(time_delta);
}

for (car& c : cars) {
    c.update(time_delta);
}

for (cdr& c : cudders) {
    c.update(time_delta);
}

>>6
Context changing:
massive amount of homogeneous data + resource managers/pools + prefetch

>>9
C++11 tuples and template algorithms:

struct apply_update
{
   template <class T> void operator()(T& c) { c.update(); }
};

std::tuple_for_each(std::make_tuple(aliens, rockets, cars, cudders), apply_update());

Sadly, C++11 lambdas can't directly parameterized with templates (you can if you nest them inside of a template class or template function), otherwise I would have used a simple lambda instead of apply_update.

>>8

Thanks for all the info. I've never put very much thought into what would be best for utilizing the cache, and this would definitely be it.

I suppose if one wanted to get the same type of polymorphism one would be used to in the oo style, they could have an array of type specifiers for the objects, and do switches off of their values.

It seems like if the objects were being allocated and deallocated continuously, that things might get messy. Like if the fields of an object where spread out into 7 different arrays, then a deletion of that object would require removing a slot from 7 different arrays. A linked list could help with that, but then the fields couldn't be indexed into very quickly which would be very important if there were functions that operated on two fields of an object that were stored in separate collections. But I guess if that was the case, then those two fields would have been stored together.

>>11
std::tuple_for_each(std::make_tuple(aliens, rockets, cars, cudders), apply_update());
Static typing hogs a lot of brain resources. Syntax is complex (syntax of typed languages tends to be more complicated than that of untyped languages), and together with static typing it forces programmer to spend more resources on dealing with language than with dealing with the problem. Haskellers of all levels are sometimes frustrated by not being able to understand the clever code produced by more advanced Haskellers. They see that the suggested solutions work, but either they can't see how, or they wouldn't have been able to come up with that kind of solution themselves.

>>12

err, nevermind about the array deletion thing. There's probably no reason for why it would need to be compacted, and you could just keep track of the unoccupied slots in the arrays, and then use them for the new objects. I'll be practicing this style.

Actually, now that I think about it, C++11 basically has enough functionality where you can build car and cdr compile-time template classes.

namespace detail
{
    template <typename List...> struct car_cdr_impl;
    template <typename Car, typename... Cdr>
    struct car_cdr_impl
    {
        typedef Car car_type;
        typedef std::tuple<Cdr...> cdr_type;
    };
}

template <typename... List>
struct car
{
    typedef typename detail::car_cdr_impl<List...>::car_type type;
};

template <typename... List>
struct cdr
{
    typedef typename detail::car_cdr_impl<List...>::cdr_type type;
};

static_assert(std::is_same<car<prog, xarn, haxus, sussix>::type, prog>::value, "this assert passes");
static_assert(std::is_same<cdr<prog, xarn, haxus, sussix>::type, std::tuple<xarn, haxus, sussix>>::value, "this assert passes");

Actually, one more fix, I'd have to add a template specialization for car_cdr_impl so you could also pass it a tuple, that way you could chain car and cdr together.

namespace
{
    template <typename Car, typename... Cdr>
    struct car_cdr_impl<std::tuple<Car, Cdr...>>
    {
        typedef Car car_type;
        typedef std::tuple<Cdr...> cdr_type;
    };
}

>>12
You might also want to read this series of articles, Ulrich Drepper may be an asshole, but this series is very authoritative.

http://lwn.net/Articles/250967/

It explains how cache-coherent memory controllers work on modern hardware and why things work the way they do and the consequences of that.

>>17

thanks for the link.

>>16
Oh and silly me, I forgot my base case. See what all of these years of sepples programming has done to my brain?
[code]
namespace details
{
    struct nat_t { };

    template <>
    struct car_cdr_impl<nat_t>; // undefined so we get a compile-time error

    template <typename Tail>
    struct car_cdr_impl<Tail>
    {
        typedef Tail car_type;
        typedef nat_t cdr_type;
    };
}

>>19
polecat kebabs

>>20
Rest assured, I've never hung out on that board. Ever. Sorry, I'm tired and made some sloppy posts without double checking.

Please don't HMA!

The "group data by use" methodology has been around since the early days of the demoscene, when it made it easier to create compact loops using lodsb and lodsw.

>>22

nice dubs

>>21
tryin/g/ too hard

>>22
since the early days of the demoscene
It was around since before Intel was even a company, stupid kike.