Cfrgtkky

I met this question on an online interview assesment.

you notice that your physics code is getting slower as you increase the amount of entities. which of the following could help ?

typedef struct Entity_t{



double pos_x, pos_y;

double vel_x, vel_y;

int health, action, mind;

int level;

void *equipment, *abilities, *effects, 



}Entity;

• A. move the physics data to a structure of arrays to increase cache coherency .


• B. Decrease pointer indirection by moving equipment, abilities, and level into Entity.


• C. Rearrange the data so that pos_x , pos_y, vel_x and bel_y are last to improve access speed.


• D. Move the entities into a linked list so that you can directly access the next item from the current.

My guess is D, But I feel it's not right, because I don't think quicker access to next item is helpful in this scenario. the reason of physics code is getting slower should related to caching. A is related to caching, but I don't know if "move physics data to a structure" can increase cache coherency. I only know hardware solution for cache coherency. both B & C seems doesn't related to the question.

Expected answer is B. Increasing number of dynamically allocated pointers increases cache misses, but more importantly, continious dynamic [de]allocations significantly slow down the program.
But this answer is subjective; without a complete minimal code sample, no accurate solution can be provided and other options might be considered too.

There is quite a bit to cover here as this is going to be a little bit lengthy but I feel it is worth the time and effort to read it. So I will start with some of the basic concepts and move on to the slightly more difficult aspects. I will begin with the code design that pertains to data structures and their byte alignments, the use of pointers versus smart pointers, then move on to containers and their associated algorithms.

Personally I wouldn't have a bunch of individual floats or doubles to represent each coordinate position and coordinate velocity, acceleration etc. It would be easier to create a simple class or structure that represents both points and vectors depending on how you use them. In your particular situation you are only working in 2D space and not 3D space but the concept still applies; the only difference is the mathematical operations that can be performed on them for example a 2D vector can have a dot product but in general doesn't have a well defined cross product although one does exist, where as in 3D both the dot and cross product exist and the cross product in 3D is well defined.

There are many other useful functions that are related to vectors such as finding the length or magnitude, finding the direction of the vector, obtaining the unit vector, checking to see if it is the 0 vector, and all of the basic arithmetic and logical operations that can be done to them: +, -, *, both in unary and binary forms. And for the * this isn't to be confused with the cross and dot products; this would generally be taking a scalar and multiplying it to that vector, and for your logical comparisons ==, !=, <, <=, >=... There are also a few other common functions that are highly used in relation to the dot product which involves the trigonometric form of the dot product through the use of the cos function and the abs of its magnitude. So with this in mind, you can easily extrapolate all of the functionality of points and vectors from the entity and all other positional objects then just have a single variable of that class to represent what is needed. Another thing that allows Mathematical Vectors very useful is that you can perform operations on these vectors not only by scalar and another vector but also by Matrices where this would allow transformations to be done to them; especially affine transformations, rotation, translation, scaling...

Example of a Vector2f class:

class Vector2f {

public:

    union { // nameless union to designate both the array elements and the

            // individual elements have the same memory location: helps

            // with different way of accessing the individual vector components

        float f2_[2]; // internal array of float with size 2 

        struct { // nameless struct 

            float x_;

            float y_;

        };

    };



    // Different ways to construct a vector

    inline Vector2f();

    inline Vector2f( float x, float y );

    inline Vector2f( float* vp );



    // operators

    inline Vector2f  operator+( const Vector2f& v2 ) const;

    inline Vector2f  operator+() const;

    inline Vector2f& operator+=( const Vector2f& v2 );

    inline Vector2f  operator-( const Vector2f& v2 ) const;

    inline Vector2f  operator-() const;

    inline Vector2f& operator-=( const Vector2f& v2 );

    inline Vector2f  operator*( const float& value ) const;

    inline Vector2f& operator*=( const float& value );

    inline Vector2f  operator/( const float& value ) const; // check for divide by 0

    inline Vector2f& operator/=( const float& value );      //  same as above



    // Common Functions

    inline void   normalize();

    inline void   zero();

    inline bool   isZero(); // use an epsilon value

    inline float  dot( const Vector2f v2 ) const;

    inline float  lenght2() const; // two ways of calculating the length or magnitude

    inline float  length() const;

    inline float  getCosAngle( const Vector2f& v2, const bool isNormalized = false );

    inline float  getAngle( const Vector2f& v2, const bool isNormalized = false, bool inRadians = true );



    inline friend Vector2f Vector2f::operator*( const float& value, const Vector2f v2 ) {

        return Vector2( value * v2.x_, value * v2.y_ ); 

    }



    inline friend Vector2f Vector2f::operator/( const float& value, const Vector2f v2 ) {

        Vector2f vec2;

        if ( Math::isZero( v2.x_ ) )

            vec2.x_ = 0.0f;

        else

            vec2.x_ = value / v2.x_;



        if ( Math::isZero( v2.y_ ) )

            vec2.y_ = 0.0f;

        else 

            vec2.y_ = value / v2.y_;



        return vec2;

    }        

};

As for the constructors and functions themselves I'm not going to show them here as it would be too much to display and as for the Math::isZero() that is basically a generalized math function that checks if a value is less than some epsilon value to consider it negligible and allow the code to treat it as if it is zero due to floating point arithmetic and round off errors.

Then in your existing class you can simply do this:

#include "Vector2f.h"



struct Stats {

    int health_;

    int mind_;

    int action_;

    int level_;

};



// Since this is C++ and not C there is no need for `typedef` `structs` although it is still valid C++

struct Entity {

    Vector2f position_;

    Vector2f velocity_;

    Stats stats_;



    void *equipment, *abilities, *effects;

}; 

This is fine and all but we can have vectors and points that are also double precision and also integer based. We can also have vectors that have 3 coordinate locations so we can do better by turning our Vector2f class into a template type:

template<class Type, unsigned N>  // Type is float, double, int, etc. N is number of dimensions

class Vector {

    // class body here:      

};

Even better yet, instead of writing the entire vector class, you can use a very easy to use library that works very well with 2D & 3D type applications where their library has the feel of OpenGL and GLSL called glm. You can find it here as it is very easy to use and install as it is a headers only library and there is no linking. Just include the headers and start using it as it is very powerful and versatile.

What makes using a mathematical vector class so useful is the fact that many different kinds of objects can have position, velocity, or acceleration. You could even use these to contain mesh data such as vertex coordinates of a mesh, texture coordinates, color data, for example from the glm library: a glm::vec4<float> color would have r,g,b,a red, green, blue and alpha. Where a glm::vec2<float> textureCoords would have u, v coordinates. And the most powerful part of this, is the ability to simply do math on vectors with scalars, other vectors and matrices.

The best suggestion about your actual question that involves cache coherency would be to make sure that your struct that you create has a 4 byte alignment. So if you have a struct as such:

struct Foo {

    int a;   // assuming 32bit = 4bytes

    short b; // assuming 16bit

};

The above struct would fail on the 4 byte alignment so to fix this:

struct Foo {

    int a;

    short b;

private:

    short padding; // not used

};

This would help to solve your cache problems. The order in which they are stored matters a little bit as it depends on the succession of variables that align to 4 bytes typically found on 32 bit machines. I don't know if the same holds true for 64 bit machines with the 4 byte alignment, but it is something to consider. Another thing that is useful to consider is that the word alignment for some struct Foo may be different from one OS to another and from one compiler to another. Another thing to take into consideration is also the architecture with the internal layout of the data type such as it's endianess, but this is only usually a concern if you are using unions in specific ways, bit fields and doing bit wise operations - manipulations.

Going back to this variation of your code:

#include "Vector2f.h"



struct Stats {   // assuming 32bit

    int health_;  // 4 bytes

    int mind_;    // 4 bytes

    int action_;  // 4 bytes

    int level_;   // 4 bytes

};



struct Entity {

    Vector2d position_;  // float = 8 bytes x 2: 16 bytes

    Vector2d velocity_;  // float = 8 bytes x 2: 16 bytes

    Stats stats_;  // 32 bytes



    void *equipment, *abilities, *effects; // each pointer 4 bytes.

}; 

So here your entity class where variables are concerned all fall on a 4 byte alignment since they are all multiples of 4 and typically in most cases this is cache friendly.

Where your pointers are concerned for indirection, allocation and deallocation. You have a few options. You could either pass in the reference to an object as long as the reference lives longer than this current class (life time expectancy) to avoid using new and delete. You could use smart pointers. You could contain them in a std::vector and don't use pointers at all, you could take all of these pointers and place them in their own struct as such then have a single pointer to that struct in your class, or you could do something like this:

class Entity {

private:

    Vector<float,2> position_;

    Vector<float,2> velocity_;

    Stats stats_;

    std::tuple<Equipment*, Ability*, Effect*> attributes_;

};

Here is a simple example of using class pointers within a tuple:

#include <exception>

#include <iostream>

#include <tuple>



class Equipment { public: int x; };

class Ability   { public: int x; };

class Effect    { public: int x; };

class Player    { public:

    std::tuple<Equipment*, Ability*, Effect*> attributes;

};    



int main() {

    try {

        Equipment eq;

        eq.x = 5;

        Ability ab;

        ab.x = 7;

        Effect ef;

        ef.x = -3;



        Player p;

        p.attributes = std::make_tuple<Equipment*, Ability*, Effect*>( &eq, &ab, &ef );



        std::cout << "Equipment: " << std::get<0>( p.attributes )->x << 'n';

        std::cout << "Ability: " << std::get<1>( p.attributes )->x << 'n';

        std::cout << "Effect: " << std::get<2>( p.attributes )->x << 'n';



    } catch( std::runtime_error& e ) {

        std::cerr << e.what() << std::endl;

        return EXIT_FAILURE;

    }

    return EXIT_SUCCESS;

}

However, you would have to make sure that life time of the previous objects: Equipment, Ability, Effect out lives your Entity or Player object for this to work. This also may be inefficient in some regards because a player may contain more than 1 of each of the above. So the simplest way to do things would be to have a std::vector container of each:

 class Entity {

 private:

     Vector<double, 2> position_;

     Vector<double, 2> velocity_;

     Stats stats_;

     std::vector<Equipment> inventory_;

     std::vector<Ability>   abilities_;

     std::vector<Effect>    effects_;

};

If you truly need pointers then you could have something like this:

 std::vector<std::shared_ptr<T>> objects_;

Within your class. Then you'd have a container of smart pointers that will handle all of the allocation and dellaction for your, if you don't need the pointer information to be shared you can use std::unique_ptr<T> instead.

Once you have your Data Structures designed and know how they are laid out, then it is a matter of either designing an algorithm that is appropriate to fit your needs, or choosing the appropriate already existing algorithm that has already been written from any majorly used libraries such as stl or boost.

I know this is quite long but I think I have covered all of the topics that you have suggested and it may be even possible to choice combinations of the ones you have suggested, but each of them have their tradeoff as there are always pros and cons to specific things you do. Increase container speed look up at the cost of more memory and the loss of direct access, versus less memory used, fast look up but much slower insertion.

Knowing when and where to use which kind of containers and the appropriate algorithm is the key to a having an application that performs efficiently and minimally bug free.

Hopefully; this may be of some help to you.

I'm pretty sure the only thing that will do the opposite is option D. You already have a way to access all entities thats probably perfectly fine. Adding a next pointer will make each entity larger so cache hits will decrease. Also you add another indirection so that's slower too.

For all other options the result depends on the code.

Option A is pretty much a sure bet if entities are not created/destroyed a lot and processed linear. But if the code creates or destroys entities then you often have to copy the array around.

Option B: For example if many entities share the same equipment then moving that into the struct means duplicating the data lots of time. Can't be good for the cache. On ther other hand if the equipment is unique the extra indirection doesn't help.

Option C: This seems to be a complete nonsense answer. Nothing in being last changes the access speed. On the other hand moving member around can have a huge impact on the speed. Members that are used together should be moved so they are in the same cache line. Because access will load a full cache line into the cache and you want to minimize the number of cache lines the algorithm needs to load frequently.