Game Engines 2021W Lecture 5

Notes

Lecture 5
---------
 - project proposal, see class wiki

How will technical scope be graded?
 - clean design
 - doable implementation in time given
 - testing your understanding of Godot
 - so, a mix of ambition and reason

Game engines - memory management

 - does Godot use malloc/standard new?  NO
 - why not?
 - memory allocation is inherently expensive
 - how memory is managed has significant performance implications
   - so, makes sense to make some effort to do it "right" for any
     performance-oriented application

the memory hierarchy
 - systems have a mix of small, fast, low latency memory and slow,
   high latency memory

registers
TLB <- virtual memory
on-CPU cache (L1, L2)
external CPU cache (L3)
main memory
SSD
(Spinning) Hard Drives
Tape

Every memory access starts with a virtual address but must end with a physical address
 - TLB is a cache of virtual->physical mappings at the page level
   (every 4K of memory)
 - OS's manage page tables which define the full virtual->physical mapping,
   most modern chips have hardware walk the page tables to get TLB entries

Part of why memory management is expensive is it ultimately requires
manipulating TLBs and page tables
 - so first rule of memory management in userspace is to ask the kernel
   to do it as infrequently as possible
 - reduce, reuse, recycle!

Classic malloc isn't shy about going to the OS for memory
 - yes, allocates in chunks
 - but, not so good at recycling
   - because of memory fragmentation

Memory fragmentation means memory is used less efficiently
 - you get "holes" in memory that can't be properly used

Example:
 - Let's say you do a bunch of 1K allocations, that are randomly allocated then freed
 - after doing this for a while, you'll have memory with randomly placed 1K holes, the allocations that you later de-allocated
 - then, you need 4K, or 8K, or...1MB
 - you can have that amount available, but in scattered 1K chunks
   - so, you have to go ask the OS for more memory :-(
   - or, you move things around to compact memory (this is basically garbage
     collection)

 - the best strategies to avoid memory fragmentation make assumptions about
   patterns of allocation
    - thus, if you know how your application allocates memory, then
      you can probably develop a way to allocate memory that minimizes
      fragmentation

Cache-friendly allocation
 - more to do with how you organize data structures wrt access patterns
 - should organize them so your "working set" at any time fits into the caches

To get best performance, you want small data structures
 - so data structures can all be packed into cache
but small data structures means more allocations/deallocations
 - which hurt performance

Core data type in Godot is Variant
 - can be used to represent almost anything
 - note, it allows for standard type checking to be completely
   bypassed (but Godot has its own mechanisms)

By having a small data structure that is uniform in size but can represent
all kinds of data, it makes the memory allocation problem easier
 - just managing uniform-sized variant's!
 - different kinds of data structures will get their own pools in general

Note, not the most efficient in terms of space
 - some Variant types are smaller than 20 bytes
 - but still can improve performance

Always trade-offs between time and space

Variant is interesting for reasons beyond allocator efficiency
 - why implement your own type system?!

Also see Godot's documentation on Variant.