Persistent memory

• HDD
• SSD
• Network Drives
• Removable Drives

Persistent memory

• HDD
• SSD
• Network Drives
• Removable Drives

Temporary memory

• RAM memory
  • Fast

Temporary memory

• RAM memory
  • Fast
• CPU cache
  • L1, L2 and L3
  • Superfast!
• CPU registers
  • Fastest

CPU registers

int main()
{
  int total = 0;
  for(int i = 0; i < 10; ++i)
  {
      total += i;
  }
  return 0;
}

main:
  push rbp
  mov rbp, rsp
  mov DWORD PTR [rbp-4], 0
  mov DWORD PTR [rbp-8], 0
  jmp .L2
.L3:
  mov eax, DWORD PTR [rbp-8]
  add DWORD PTR [rbp-4], eax
  add DWORD PTR [rbp-8], 1
.L2:
  cmp DWORD PTR [rbp-8], 9
  jle .L3
  mov eax, 0
  pop rbp
  ret

CPU registers

So all a CPU does is

• fetch data from memory into registers
• perform some calculation (like add or mul)
• store data from registers into memory

Fetching and storing from memory into registers is slow!

CPU speed vs memory speed

CPU cache

Because memory access is slow, we cache it.

• Keep local copies of main memory in the cache

The cache is faster

• More expensive memory
• Closer to the CPU

If data requested by the CPU is in the cache -> Use it!

• This is called a cache hit

If the data is not in the cache, fetch it from memory

• This is called a cache miss

Cache lines

When we do suffer a cache miss, we must fetch

We fetch an entire “line”

• Instead of loading a single integer, load a larger chunk of memory
• Often we’ll need that extra data too, later in the program
• Resulting in more cache hits.
• "Locality of reference"

CPU cache

CPU cache

We fetch an entire "line"

CPU cache

Cache miss

CPU cache

Cache miss

CPU cache

Cache hit

CPU cache

Cache hit

Question

Which is better?

struct data
{
  int some_int;
  float some_float;
};

std::vector<data*> data_objects;

std::vector<data> other_data_objects;

Multiple levels

Hit rate
= how often the program hits the cache
= how often can it use data that is already in the cache

The larger the cache, the higher the hit rate

But larger caches are not that close to the CPU

• Thus slower

That’s why we have multiple levels

Multiple levels

I-cache and D-cache

Instructions for the CPU must be fetched from memory as well

• Instruction cache : I-cache or I$

We do not want to mix those fetches with the data fetches

• Hence a separate data cache : D-cache or D$

For example, which (might) be faster?

float v = std::powf(a, 2);

float w = a * a;

Multiple levels

Cache size

Quick exercise: check yours!

• https://docs.microsoft.com/nl-nl/sysinternals/downloads/coreinfo
• (or simply google ‘coreinfo’)

Cache size

This is mine (@desktop)

Logical Processor to Cache Map:
*---  Data Cache          0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Instruction Cache   0, Level 1,   32 KB, Assoc   8, LineSize  64
*---  Unified Cache       0, Level 2,  256 KB, Assoc   4, LineSize  64
****  Unified Cache       1, Level 3,    6 MB, Assoc  12, LineSize  64
-*--  Data Cache          1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Instruction Cache   1, Level 1,   32 KB, Assoc   8, LineSize  64
-*--  Unified Cache       2, Level 2,  256 KB, Assoc   4, LineSize  64
--*-  Data Cache          2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Instruction Cache   2, Level 1,   32 KB, Assoc   8, LineSize  64
--*-  Unified Cache       3, Level 2,  256 KB, Assoc   4, LineSize  64
---*  Data Cache          3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Instruction Cache   3, Level 1,   32 KB, Assoc   8, LineSize  64
---*  Unified Cache       4, Level 2,  256 KB, Assoc   4, LineSize  64

Object layout in memory

struct Data
{
    unsigned int m_Number{};
    float m_Value{};
    bool m_IsTest{};
    unsigned int m_AnotherNumber{ 10 };
    char m_ACharacter{ 'a' };
    const char* m_AString{ "test" };
};

Object layout in memory

struct Data
{
    unsigned int m_Number{};
    float m_Value{};
    unsigned int m_AnotherNumber{ 10 };
    char m_ACharacter{ 'a' };
    bool m_IsTest{};
    const char* m_AString{ "test" };
};

Object layout in memory

struct Data
{
    unsigned int m_Number{};
    float m_Value{};
    unsigned int m_AnotherNumber{ 10 };
    char m_ACharacter{ 'a' };
    bool m_IsTest{};
    const char* m_AString{ "test" };
};

What about these fd's?

Memory alignment

Every data type has a natural alignment

• 1-byte aligned objects reside at any address
  • bool and char
• 2-byte aligned objects reside at addresses which end in 0x0, 0x2, 0x4… 0xE
• 4-byte aligned objects reside at addresses which end in 0x0, 0x4, 0x8 or 0xC
  • integer, float and pointer
• 8-byte aligned objects reside at addresses which end in 0x0 or 0x8
  • double
• 16-byte aligned objects reside at addresses which end in 0x0
  • SIMD vector

Memory alignment

Why? We would have to shift and OR the bits if not aligned:

Memory alignment

struct Data
{
    unsigned int m_Number{};
    float m_Value{};
    unsigned int m_AnotherNumber{ 10 };
    char m_ACharacter{ 'a' };
    bool m_IsTest{};
    const char* m_AString{ "test" };
};

Memory alignment

Feature since Visual Studio 17.9:

8 Byte alignment?

Memory alignment

What about these?

class Base
{
    Base* m_parent{};
    bool m_isActive{true};
    int m_health{100};
  public:
    virtual const char* get_name() = 0;
};

class NPC : public Base
{
    const char* m_name{};
  public:
    const char* get_name() override {
        return m_name; 
      }
};

What will sizeof(NPC) return? What is the alignment?

Memory alignment

class Base
{
    Base* m_parent{};
    bool m_isActive{true};
    int m_health{100};
  public:
    virtual const char* get_name() = 0;
};

class NPC : public Base
{
    const char* m_name{};
  public:
    const char* get_name() override {
        return m_name; 
      }
};

x86

class Base
{
    Base* m_parent{};
    bool m_isActive{true};
    int m_health{100};
  public:
    virtual const char* get_name() = 0;
};

class NPC : public Base
{
    const char* m_name{};
  public:
    const char* get_name() override {
        return m_name; 
      }
};

x64

class Base
{
    Base* m_parent{};
    bool m_isActive{true};
    int m_health{100};
  public:
    virtual const char* get_name() = 0;
};

class NPC : public Base
{
    const char* m_name{};
  public:
    const char* get_name() override {
        return m_name; 
      }
};

Cache alignment

Consider this example:

char a[10];
char b[10];

start_thread_that_works_on_a;
start_thread_that_works_on_b;

Odds are that a and b will be contiguous in memory and fit in the same cache line.

• Both threads will invalidate each others cache line
• This is called “False sharing”

Solution: align the data to the cache line size,
Processes and threads can be designated to a specific core

• Windows: SetProcessAffinityMask and SetThreadAffinityMask

To make sure the threads stay away from each others cache

• They’ll meet again in the Level 2 cache though.

Exercise

1. Allocate a very large buffer of integers on the heap.
2. Iterate over it with stepsize = 1, doubling the value each time

for(stepsize = 1; stepsize <= 1024; stepsize *= 2)
{
  for (int i = 0; i < arr.length; i += stepsize) 
  {
    arr[i] *= 2;
  }
}

3. Measure the time it takes.
4. Repeat 2-3 with stepsize = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
5. Take timinigs, in release mode, and put them in a graph
   Ideally, we would expect a graph that looks like the one on the right.

Exercise

Take good timings!

• Measure in Release mode
• Take multiple samples per stepsize (10+)
• Remove the highest and the lowest value
• Take the average
• That is your timing for that stepsize

Use std::chrono for this (as you've been taught in Prog 3)

auto start = high_resolution_clock::now();

// do whatever you need to

auto end = high_resolution_clock::now();
auto elapsedTime = duration_cast<microseconds>(end - start).count();
cout << "operation took " << elapsedTime / 1000.f << "ms" << endl;

Exercise

The blue line is the graph for my pc @ home:

What happened?

Exercise

The blue line is the graph for my pc @ home:

What happened?

• An int takes 4 bytes -
• A step of 16 x 4 jumps 64 bytes - we need every cache line
• A step of 32 x 4 jumps 128 bytes - we need every other cache line

What happened?

What happened?

What happened?

What happened?

This time we finally skip 50% of the cachelines!

What happened

Examples

Imagine we have a particle class

class particle
{
    float remaining_duration;
    vec3f pos;
    vec3f velocity;
  public:
    particle() = default;
    void init(vec3f position, vec3f velocity, float duration);
    bool update(float delta_time); // move around, grow/shrink, etc...
    bool is_alive() const;
};

Used by a particle_system

void particle_system::update(float delta_time) 
{
  for(auto& particle : m_particles) 
  {
    particle.update(delta_time)
  }
}

Examples

But not all particles are active at the same time, so:

void particle_system::update(float delta_time) 
{
  for(auto& particle : m_particles) 
  {
    if(particle.is_active())
      particle.update(delta_time)
  }
}

Examples

class animation;

enum class loot_type {
  gold,
  silver,
  chicken
};

class npc : public component {
  animation* m_current;
  vec3f m_goal;
  loot_type m_drop;
  int m_min_drops;
  int m_max_drops;

public:
  void update() {
    // walk towards goal, play anims, etc.
  }
}

Examples

class animation;

enum class loot_type {
  gold,
  silver,
  chicken
};

struct loot_drop {
  loot_type m_drop;
  int m_min_drops;
  int m_max_drops;
}

class npc : public component {
  animation* m_current;
  vec3f m_goal;
  lootdrop* m_loot;
 
public:
  void update() {
    // walk towards goal, play anims, etc.
  }
}

Exercise

Do the same exercise as before, but now with this class instead of integers:

struct transform 
{
  float matrix[16] = {
    1,0,0,0,
    0,1,0,0,
    0,0,1,0,
    0,0,0,1
  };
};

class gameobject
{
  transform local;
  int id;
}

What does de graph look like now? Why? How do you fix it?

Exercise

Our graph now looks like this:

What’s wrong with it?
Why? How do we fix it?

Exercise

With this alternative:

class gameobject
{
  transform* local;
  int id;
}

We get these results:

User interface programming

There are mainly two types of UI

Dear ImGui

Is a popular immediate mode GUI library, often used in game engines.

_{Rainbow Six, Ubisoft. https://github.com/ocornut/imgui/wiki/software-using-dear-imgui}

Dear ImGui

Is a popular immediate mode GUI library, often used in game engines.

Check out this (very) short overview:

https://www.youtube.com/watch?v=LSRJ1jZq90k

Let’s set this up! Check out the Dear ImGui assignment on Leho

Exercise

Using the results of the previous exercise, instead of writing the timings to cout, plot them in a graph.

Hint: https://github.com/soulthreads/imgui-plot