Get into GameDev:
cheat-codes for defeating the coding interview
|
This book will cover: how to get an interview, pass the interview, and ultimately break into the video game development industry!
TODO: need to talk about all my internships in the opening sentence This book is a WORK IN PROGRESS it is presently being ported from a word document. View the full document here: tinyurl.com/gamedevStudySheet |
Half-Life enthusiast breaking into the video game industry
|
Introduction
Table of Contents
|
Vertical Divider
|
About The Guide / Author
|
This guide is fool-proof! I would know, because it worked for me and I am often-times foolish. I wrote this guide over many years of many job interviews for Gameplay Engineer positions. After each interview, whether it went well or not-so-well, I amended this guide to include everything that I needed to know to pass that interview. It’s still a work-in-progress, and probably will be forever, as I continue to learn! Please let me know where I can improve it.
Note: This was not originally imagined as a beginner’s guide. It was written as a reference sheet to have during a workday or interview for folks who already knew the content. So if you come across something you don’t understand, you may need to Google the topic. I am presently expanding it to be more instructive. Thank you for your patience. This book was inspired by Cracking the Coding Interview, an excellent book for general computer science interview questions. I highly recommend reading that book prior to this one if you are new to coding. |
WIP book-cover design
|
Bitwise Operators
It seemed to me that the best place to start this guide would be with the very building blocks of all data: bits. Bits are our smallest unit of data and are used to compose all of the larger data types we will discuss later on. A bit is a single number: 0 or 1 aka "off" or "on". Usually when we need a two-state variable we will use a bool (more about those later) but they are 8 bits! So to save space, it is common to instead discretize our bits so that each bit in an 8-bit structure can represent a different parameter's on/off state. When we treat each bit in a data type as its own value, that's called a Bit Field. Now, instead of only two states, we can represent 8*2 states within the same 8-bit structure! And if we consider several bits within a bit field instead of just one at a time ( a process called Bit-Masking ) we can represent many more combinations!
To manipulate a single bit within a bit field, we can use the following operators:
To manipulate a single bit within a bit field, we can use the following operators:
|
|
Bitwise Operations
Let's crack straight into it by putting these bitwise operators into practice! Below are the most common operations which we may need to perform upon a bitfield.
|
Several bits socializing together
|
Practice Question: What's the fastest way to tell if 2 signed floats are the same polarity?
Compare the sign bit of both numbers to see if they are equal, an AND or XOR would work.
Binary / Hexadecimal Numbers
The bits we discussed above have two states ( 0 or 1 ) a number described in bits is called binary ( "bi" meaning two, as in two states ). But you (assuming you are also human) are probably used to numbers in decimal format ( 10 states ). Binary numbers are simply another way of representing decimal numbers and they're specifically an easier format for the computer (composed of binary switches). Another common format is Hexadecimal ( 16 states ), its compactness makes it easier for humans to read. As a video game programmer you will be expected to translate numbers between these formats. You should be very familiar with the following powers of two.
As a pneumonic, I have memorized that "2 to the 6 is 64", which helps me jump to adjacent powers such as 2^5 with a simple 64/2. The most important one is 2^8 which you should have memorized as 256. This is an incredibly important number because it is the total number of possible numbers which we can represent with an 8-bit value. This is why an unsigned int-8's maximum value is 255 (it would be 256 if we did not also need to represent 0). Using this understanding we can easily calculate the maximum value of an arbitrarily sized integer, let's give it a try!
20 = 1 | 21 = 2 | 22 = 4 | 23 = 8 | 24 = 16 | 25 = 32 | 26 = 64 | 27 = 128 | 28 = 256
Practice Question: What is the maximum value of a signed int-32?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
You may have noticed that I tried to trick you by asking for the signed max instead of the unsigned max. Since we are representing a signed number, we need to divide all possible permutations of our 32 bits into three categories: positives, negatives, and zero. With three categories we cannot evenly divide the permutations. The result is that the absolute value of Int32.MinValue is not equal to the absolute value of Int32.MaxValue. Hopefully this provides a small a hint to address the next practice question.
Practice Question: What is the minimum value of a signed int-32?
We learned that the maximum value of a signed int-32 is 2^31-1, because of the 32 bits one needs to be used for the sign (hence the 31) and because one combination of bits is used to represent 0 (hence the -1). Because we accounted for 0 by lowering the maximum value by 1, we do not need to constrain the minimum value. Therefore the minimum value of a signed int-32 is simply -2^31.
Additional reading:
https://stackoverflow.com/questions/11243014/why-the-absolute-value-of-the-max-negative-integer-2147483648-is-still-2147483
Additional reading:
https://stackoverflow.com/questions/11243014/why-the-absolute-value-of-the-max-negative-integer-2147483648-is-still-2147483
We are about to jump into Two's Complement which is the way fixed-point numbers (such as ints and longs) are represented. We will cover binary and hexadecimal approaches but before we do, I want to provide you with this useful list to remind you of how two digit numbers are represented in Hex (this will come in handy very soon!).
Decimal: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15
Hex: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F
Positive numbers in binary:
Representing numbers in binary or hex is a simple process of first understanding what exponent each column of the number represents and then calculating the total value in each column. I explain this in detail within the following video.
Two's Complement:
On an interview, it is more likely you will be asked to represent a negative number because that process requires you to understand the positive representation in addition to two more steps. In total, the three steps to writing a negative number in binary or hex are:
- Write the number
- Take the 1's complement
- Add 1
Here are two simple examples that break down the process into those simple steps.
On an interview, it is more likely you will be asked to represent a negative number because that process requires you to understand the positive representation in addition to two more steps. In total, the three steps to writing a negative number in binary or hex are:
- Write the number
- Take the 1's complement
- Add 1
Here are two simple examples that break down the process into those simple steps.
|
“Please write -5 in binary”
Step 1: write 5 (as an int8) 0000 0101 Step 2: take 1’s complement (invert bits) If binary just swap 1’s with 0’s and vice-versa 1111 1010 Step 3: Add 1 (so it’s 2’s complement) 1111 1011 |
“Please write -2 in hex”
Step 1: write 2 (as an int8) 02 Step 2: take 1’s complement For hex, just do |# - 15| or (# + 15)%16 ( ex. the 0’s become F’s) FD (or 1111 1101 in binary) Step 3: Add 1 (so it’s 2’s complement) FE |
Step 2 for hex numbers is normally the hardest part for students because they learn it in the binary example as "simply swap the 1's and 0's" and suddenly that simplification does not apply for hex examples. It may be easier to think of the 1's complement as |#-Max| where # is the current digit and Max is the largest value that digit can hold. This approach works in both cases.
- For example, in binary the Max is 1, so this applied to a 0 will yield: |0-1| --> |-1| --> 1
- And in hex, the max is 15 or "F" (shown in our list above), so this applied to 0 will yield: |0-15| --> |-15| --> 15 or "F"
This approach will always work, whether it's binary, hex, or maybe even octal that we need to convert.
Additional Binary & Hex Notes:
- If asked for HEX_1 - HEX_2, instead do... HEX_1 + ( 2’s complement of HEX_2)
- 0b10000 will declare 16 in binary, the b means binary
- 0x00000010 will declare 16 in hex, the x means hex
- Each hex number is represented using 4 binary bits, hex notation is simple an abbreviation
Misc Numbers Info:
You should be familiar with the ASCII table. Know that it has 127 entries, and know that A is 065
Endianness: this term refers to the order in which a number's bits are stored.
----- Big-Endian = stored starting with most-significant-bytes
---- Little-Endian = stored starting with least-significant-bytes.
---- Note: Little-Endian is the widespread default.
For storage, you should prefer data types that express the exact size such as int_8 instead of the generic int.
In the next section we will discuss an alternative way to represent numbers that will allow for decimal values.
- For example, in binary the Max is 1, so this applied to a 0 will yield: |0-1| --> |-1| --> 1
- And in hex, the max is 15 or "F" (shown in our list above), so this applied to 0 will yield: |0-15| --> |-15| --> 15 or "F"
This approach will always work, whether it's binary, hex, or maybe even octal that we need to convert.
Additional Binary & Hex Notes:
- If asked for HEX_1 - HEX_2, instead do... HEX_1 + ( 2’s complement of HEX_2)
- 0b10000 will declare 16 in binary, the b means binary
- 0x00000010 will declare 16 in hex, the x means hex
- Each hex number is represented using 4 binary bits, hex notation is simple an abbreviation
Misc Numbers Info:
You should be familiar with the ASCII table. Know that it has 127 entries, and know that A is 065
Endianness: this term refers to the order in which a number's bits are stored.
----- Big-Endian = stored starting with most-significant-bytes
---- Little-Endian = stored starting with least-significant-bytes.
---- Note: Little-Endian is the widespread default.
For storage, you should prefer data types that express the exact size such as int_8 instead of the generic int.
In the next section we will discuss an alternative way to represent numbers that will allow for decimal values.
Practice Question: How would you write -42 in hex?
Step 1: Write 42 in hex.
I know that my answer will be a number with several columns. I start by writing out labels for my columns from right to left to assess how many columns I will need. First, 16^0 = 0, then 16^1 = 16. These two columns are respectively the 0's column and the 16's column. I know I will not need more than these 2 columns because the highest value I can place into the 16's column is 15 (F). And 15 * 16 is a value far beyond 42, which means I will not need additional columns to reach the number 42.
To determine which number to put in the 16's column, I divide 42 by 16. The result is 2, with 10 remaining. So I place a 2 in the 16's column and bring the remaining 10 into the 0's column. The 0's column is our final column and we place the entire remainder of 10 inside by using the letter A. Remember that each column can only have one digit, so when we need to represent a two digit number, they become letters (in this case 10-->A).
Our final answer for this step is therefore 2A.
Step 2: take 1's compliment.
In this case we are working in hex, so the 1's compliment is |#-15|. Let's apply this to both column values, 2 and A.
2 : |2-15| = |-13| = 13 = D
A : |A-15| = |10-15| = |-5| = 5
Our final answer for this step is therefore D5.
Step 3: add 1
In this step we add 1 to the entire number (not each column). Our 0's column is currently 5, 5+1=6. 6 does not exceed 15 (the maximum value we can hold in any particular column) so we don't need to worry about carrying over any values to the 16's column.
Our final answer for this step is therefore D6.
I should note that this D6 is represented by 8-bits. If it were instead a 16-bit representation, then we would have 00D5 as our answer to Step 1, and FFD6 as our answer to Step 3.
I know that my answer will be a number with several columns. I start by writing out labels for my columns from right to left to assess how many columns I will need. First, 16^0 = 0, then 16^1 = 16. These two columns are respectively the 0's column and the 16's column. I know I will not need more than these 2 columns because the highest value I can place into the 16's column is 15 (F). And 15 * 16 is a value far beyond 42, which means I will not need additional columns to reach the number 42.
To determine which number to put in the 16's column, I divide 42 by 16. The result is 2, with 10 remaining. So I place a 2 in the 16's column and bring the remaining 10 into the 0's column. The 0's column is our final column and we place the entire remainder of 10 inside by using the letter A. Remember that each column can only have one digit, so when we need to represent a two digit number, they become letters (in this case 10-->A).
Our final answer for this step is therefore 2A.
Step 2: take 1's compliment.
In this case we are working in hex, so the 1's compliment is |#-15|. Let's apply this to both column values, 2 and A.
2 : |2-15| = |-13| = 13 = D
A : |A-15| = |10-15| = |-5| = 5
Our final answer for this step is therefore D5.
Step 3: add 1
In this step we add 1 to the entire number (not each column). Our 0's column is currently 5, 5+1=6. 6 does not exceed 15 (the maximum value we can hold in any particular column) so we don't need to worry about carrying over any values to the 16's column.
Our final answer for this step is therefore D6.
I should note that this D6 is represented by 8-bits. If it were instead a 16-bit representation, then we would have 00D5 as our answer to Step 1, and FFD6 as our answer to Step 3.
Floating-Point Numbers
We just explored how Fixed-Point numbers are represented at the bit level. Fixed-Point is great for whole numbers, but when we need to express decimal numbers we use Floating-Point numbers. Floating point numbers have an interesting tradeoff, they can express very large numbers (both negative and positive) but as the magnitude of the numbers increases, it decreases its precision. Here is how a float is laid out in memory:
1 09876543 21098765432109876543210
+-+--------------+---------------------------------------------+
| | +-- 23 significand / mantissa (normal binary #)
| +----------------------------- 8 exponent (128 - value of the exponent)
+-------------------------------------- 1 sign bit (if 1 then it's negative)
An interesting decision was made here. The float's designers chose for the exponent bits to represent a number that would be subtracted from 128 instead of representing the exponent itself. That allows for fractions because a large number subtracted from 128 will yield a negative exponent.
TODO: because floats are an approximation, they can be lossy. Discuss how adding big numbers with small numbers can lead to loss of data and how to approach fixes to this phenomenon. Include mention of IsNearlyEqual and IsNearlyZero. Include a practice question to code a method such as IsNearlyEqual.
A float's lack of precision at large magnitude's is its general downside. This was a big problem for Minecraft, dubbed the Far Lands. In God of War, the team resolved this issue by introducing intermediary transforms for the level sections so that at any given time you only need to make calculations relative to a somewhat-nearby origin (so the numbers never got too big). In Star Citizen, the team used double precision floating point values (these "double's" act like floats but they're double the size). I think the latter approach is extraordinarily rare, developers usually avoid doubles because they take up so much space. In the next sections we will explore the relative sizes of these objects and the consequences they have on memory layout.
1 09876543 21098765432109876543210
+-+--------------+---------------------------------------------+
| | +-- 23 significand / mantissa (normal binary #)
| +----------------------------- 8 exponent (128 - value of the exponent)
+-------------------------------------- 1 sign bit (if 1 then it's negative)
An interesting decision was made here. The float's designers chose for the exponent bits to represent a number that would be subtracted from 128 instead of representing the exponent itself. That allows for fractions because a large number subtracted from 128 will yield a negative exponent.
TODO: because floats are an approximation, they can be lossy. Discuss how adding big numbers with small numbers can lead to loss of data and how to approach fixes to this phenomenon. Include mention of IsNearlyEqual and IsNearlyZero. Include a practice question to code a method such as IsNearlyEqual.
A float's lack of precision at large magnitude's is its general downside. This was a big problem for Minecraft, dubbed the Far Lands. In God of War, the team resolved this issue by introducing intermediary transforms for the level sections so that at any given time you only need to make calculations relative to a somewhat-nearby origin (so the numbers never got too big). In Star Citizen, the team used double precision floating point values (these "double's" act like floats but they're double the size). I think the latter approach is extraordinarily rare, developers usually avoid doubles because they take up so much space. In the next sections we will explore the relative sizes of these objects and the consequences they have on memory layout.
Data Type Sizes
Let's begin by covering the memory footprints of several common data types. In an interview, candidates will be expected to recite these values from memory. Note that 1 byte = 8 bits. Also note that the size of several of these types varies depending on if the processor size (32-bit vs 64-bit). However, since the first PlayStation, pretty much all development has been focused on 64-bit processors. More historical context here.
Data Type |
32-bit Size |
64-bit Size (if different) |
Representation |
Bool |
1 byte ( 8 bits ) |
- |
- |
Char |
1 byte ( 8 bits ) |
- |
- |
Short |
2 bytes ( 16 bits ) |
- |
- |
Int |
4 bytes ( 32 bits ) |
- |
Two's Complement |
Long |
4 bytes ( 32 bits ) |
8 bytes ( 64 bits ) |
Two's Complement |
Float |
4 bytes ( 32 bits ) |
- |
Floating Point |
Double |
8 bytes ( 64 bits ) |
- |
Floating Point |
Pointer |
4 bytes ( 32 bits ) |
8 bytes ( 64 bits ) |
- |
While an Int is 32 bits by default, we often need to represent a number with a much smaller range. For these cases we can save memory by using a Int type of explicit size such as int8_t which only uses 8 bits. More details here.
Since pointers are used to represent memory addresses, the pointer's size (and therefore it's maximum value) implicitly defines how much memory we can use. A 32-bit pointer can only access values up to about 3.5 GB of RAM (this is a serious limitation), whereas a 64-bit pointer could theoretically access values up to 17 Million GB of RAM.
Below are some game file sizes for perspective. Halo 1 (Combat Evolved) was released on the original Xbox (which was 32-bit) the later entries were released on 64-bit hardware.
Halo 1 (2001) - 1.2 GB
Halo 2 (2004) - 20 GB
Halo 3 (2007) - 55 GB
Halo 4 (2012) - 55 GB
Halo 5 (2015) - 95 GB
Since pointers are used to represent memory addresses, the pointer's size (and therefore it's maximum value) implicitly defines how much memory we can use. A 32-bit pointer can only access values up to about 3.5 GB of RAM (this is a serious limitation), whereas a 64-bit pointer could theoretically access values up to 17 Million GB of RAM.
Below are some game file sizes for perspective. Halo 1 (Combat Evolved) was released on the original Xbox (which was 32-bit) the later entries were released on 64-bit hardware.
Halo 1 (2001) - 1.2 GB
Halo 2 (2004) - 20 GB
Halo 3 (2007) - 55 GB
Halo 4 (2012) - 55 GB
Halo 5 (2015) - 95 GB
Practice Question: How large is an int* on a 64-bit system? What about a float* on a 64-bit system?
Both int* and float* are pointers so they will both be the size of a pointer (we can disregard the int vs float distinction regarding the type of data we are pointing to). A pointer is 8 bytes ( 64 bits ) on a 64-bit system. So both of these will be 8 bytes.
Alignment
With some rare exceptions, the size of a data type also determines an attribute called its "alignment". For example, an Int is 4 bytes large and therefore 4-byte aligned. When data types are stored into memory they are stored at the next available alignment boundary of appropriate size. Let's break that process down with an example. In the diagram below, I marked the 4-byte alignment boundaries with X1, X2, and X3. If we wanted to store an Int at Y1 (position 2) we might instead add bytes of padding at position Y1 and Y2, then we could place the Int at position X2 so that it is aligned. In simple terms, we find the next 4-byte aligned address by determining the next address that is a multiple of 4.
Data: X1 Y1 Y2 X2 X3
Address: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Aligning data can drastically decrease the time it takes to access it, and some processors actually cannot perform reads on unaligned addresses. In C++, the compiler will automatically align data which can lead to some interesting behavior. For example, take the following struct on the left:
Data: X1 Y1 Y2 X2 X3
Address: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
Aligning data can drastically decrease the time it takes to access it, and some processors actually cannot perform reads on unaligned addresses. In C++, the compiler will automatically align data which can lead to some interesting behavior. For example, take the following struct on the left:
|
struct MixedData{
char Data1; short Data2; int Data3; char Data4; }; |
This struct (on the left) is 8 bytes large prior to compilation:
1byte (char) + 2byte (short) + 4byte (int) + 1byte (char) = 8 bytes However, after compilation, the compiler will add padding to align the data as shown on the right. These additional 4 bytes of padding mean that this struct will actually use 12 bytes of memory. The trailing 3 bytes of padding are due to the struct assuming more MixedData's will be declared after it (as in an array). |
struct MixedData{
char Data1; char Padding1[1]; short Data2; int Data3; char Data4; char Padding2[3]; }; |
TODO: Why would it need to 4-byte align the next MixedData if MixedData starts with a char? Aren't char's 1-byte aligned?
To reduce the amount of padding a struct will need, structs should always be laid out with data members in order of descending size. Note that you can explicitly tell a compiler to not add padding by wrapping a struct in: “#pragma pack(push,1)” and “#pragma pack(pop)”.
TODO: discuss denormal numbers and isNearlyEqual
To reduce the amount of padding a struct will need, structs should always be laid out with data members in order of descending size. Note that you can explicitly tell a compiler to not add padding by wrapping a struct in: “#pragma pack(push,1)” and “#pragma pack(pop)”.
TODO: discuss denormal numbers and isNearlyEqual
Practice Question: What is the size of the following struct before and after compilation?
struct MixedData{
short Data2;
float Data1;
};
struct MixedData{
short Data2;
float Data1;
};
Prior to compilation the size would be 2bytes (short) + 4bytes (float) = 6bytes.
After compilation, two bytes of padding would be added after the short so that the float will be 4-byte aligned. The resulting size is then 8 bytes.
Additional reading:
https://www.youtube.com/watch?v=c0g3S_2QxWM&list=PLW3Zl3wyJwWPmA00yqu9wiCREj4Of_1F8&index=15&ab_channel=JorgeRodriguez
After compilation, two bytes of padding would be added after the short so that the float will be 4-byte aligned. The resulting size is then 8 bytes.
Additional reading:
https://www.youtube.com/watch?v=c0g3S_2QxWM&list=PLW3Zl3wyJwWPmA00yqu9wiCREj4Of_1F8&index=15&ab_channel=JorgeRodriguez
Caching
Caching is a process of optimizing memory usage to minimize how frequently we search main memory. Whenever your program asks the processor to bring it a section of memory, the processor brings a chunk of memory to a temporary storage location called a cache and then from that cache it returns the part you want. You can imagine it scooping up memory with imprecise mittens. The amount it moves at any given time is called a cache-line which is typically 64 bytes. When you ask it for memory again it will check if your newly requested data is within the recently scooped cache and if so it can bring you memory from there. If the processor can't find your data in the cache then it is considered a "cache miss" and it instead falls back to a very slow main memory load to find your data. It is extremely worth our time to design our programs that reuse the same sections of memory again and again rather than requiring frequent slow heap searches. That'e because re-using data that is nearby each other in main memory increases the chance that it will all be scooped up together and stored in the cache.
Checkout this interactive demo which can help visualize the speed of obtaining cached data versus calling into main memory: http://www.overbyte.com.au/misc/Lesson3/CacheFun.html
Because reusing cached memory can leave to such amazing time savings, most computers are designed with multiple caches. If you played the demo linked above then you saw an L2 cache in addition to the smallest and speediest cache named L1. The basic idea here is the same, if we can't find data in the L1 cache, then check the L2 cache, and only after that do we fallback to a main memory look-up. Below is a diagram from Jason Gregory's excellent talk Dogged Determination. In the diagram you can see the PS4 is designed with two groups of four CPU cores sharing an L2 and L1 cache each. The PS5 has an L3 cache as well, and some computers even have L4 caches.
Checkout this interactive demo which can help visualize the speed of obtaining cached data versus calling into main memory: http://www.overbyte.com.au/misc/Lesson3/CacheFun.html
Because reusing cached memory can leave to such amazing time savings, most computers are designed with multiple caches. If you played the demo linked above then you saw an L2 cache in addition to the smallest and speediest cache named L1. The basic idea here is the same, if we can't find data in the L1 cache, then check the L2 cache, and only after that do we fallback to a main memory look-up. Below is a diagram from Jason Gregory's excellent talk Dogged Determination. In the diagram you can see the PS4 is designed with two groups of four CPU cores sharing an L2 and L1 cache each. The PS5 has an L3 cache as well, and some computers even have L4 caches.
I would recommend being aware of the approximate size of the different caches you are dealing with on your target platform. Typically you will see L1, L2, L3 then main memory. Each level is about 3 times slower. So main memory 27x slower than L1.
Practice Question: Let's consider the role of data locality in practice, below is a simple nested for-loop that traverses every element of a 2d matrix, we could choose option A or B to preform the desired ++ operation. Which is the faster option and why?
for (X = 0; X < MAX; X++) {
for (Y = 0; Y < MAX; Y++) {
Option A: arr[ X ][ Y ]++;
Option B: arr[ Y ][ X ]++;
}
}
for (X = 0; X < MAX; X++) {
for (Y = 0; Y < MAX; Y++) {
Option A: arr[ X ][ Y ]++;
Option B: arr[ Y ][ X ]++;
}
}
In this case A is the faster option. It's faster because it is referencing consecutive values within the matrix. C and C++ store matrix values in row major order (https://www.codee.com/knowledge/glossary-row-major-and-column-major-order/ ) so that means when we grab a matrix index from memory it is going to come with a cacheline comprised of the other values in its row in addition to adjacent rows. We reduce the frequency of cache misses by primarily iterating through the rows of data recently cached rather than by primarily iterating through the columns which would have the processor jumping around memory and missing the cache more frequently.
Basically whenever you see a question like this (and I've seen them frequently in interviews) you want to look at the inner loop and make sure that variable is the one in the second part of the array index. For example if the loops were re-ordered (with Y as the outer loop and X as in inner) then Option B would be correct.
The question comes from the opening of Scott Meyer's "Cpu Caches and Why You Care" (you should definitely watch this lecture): https://youtu.be/WDIkqP4JbkE
Basically whenever you see a question like this (and I've seen them frequently in interviews) you want to look at the inner loop and make sure that variable is the one in the second part of the array index. For example if the loops were re-ordered (with Y as the outer loop and X as in inner) then Option B would be correct.
The question comes from the opening of Scott Meyer's "Cpu Caches and Why You Care" (you should definitely watch this lecture): https://youtu.be/WDIkqP4JbkE
In the above practice question we explored editing data in memory. However we are actually editing a copy of the main memory that has been cached (aka copied) into the L1 cache. The processor usually maintains a list of flags to track if cachelines within the caches have been changed and therefore determine if it needs to update main memory. The main memory update typically is handled when a cache's data is updated which only further extends the time cost of a cache-miss.
In a multi-processor environment, multiple cores can share the same cache; but if they affect its data, then they need to mark it as dirty which can lead to some nasty concurrency problems. To better support multi-processing, designs may include several caches of the same level. For example in the PS4 designs above, there are two L2 and L1 caches shared by four cores each. Likewise, processors can benefit from decoupling instruction storage into a separate cache so you might see those instruction-specific caches referred to by the term "i-caches" versus "d-caches" which are for data. Caches that are designed for data and instructions are called unified caches.
In addition to reducing cache misses, applying cache locality principles to our program design can allow us to use powerful hardware operations called SIMD instructions. SIMD or "single-instruction-multiple-data" instructions allow us to to perform multiple computations at once. The exact capabilities of SIMD instructions are going to vary based on the hardware architecture, but getting down to the metal is what game programming is all about! Here is an example using SIMD for vector addition.
Additional terms to know:
In a multi-processor environment, multiple cores can share the same cache; but if they affect its data, then they need to mark it as dirty which can lead to some nasty concurrency problems. To better support multi-processing, designs may include several caches of the same level. For example in the PS4 designs above, there are two L2 and L1 caches shared by four cores each. Likewise, processors can benefit from decoupling instruction storage into a separate cache so you might see those instruction-specific caches referred to by the term "i-caches" versus "d-caches" which are for data. Caches that are designed for data and instructions are called unified caches.
In addition to reducing cache misses, applying cache locality principles to our program design can allow us to use powerful hardware operations called SIMD instructions. SIMD or "single-instruction-multiple-data" instructions allow us to to perform multiple computations at once. The exact capabilities of SIMD instructions are going to vary based on the hardware architecture, but getting down to the metal is what game programming is all about! Here is an example using SIMD for vector addition.
Additional terms to know:
- Cache-Thrash - when frequent cache misses require frequent loads from main memory.
- False-Sharing - when multiple cores are editing the same cache line and are frequently setting the dirty flag due to constant cache misses.
Practice Question: Let's imagine you are optimizing a game that manages thousands of player's where a player struct contains information described in the struct below. The game is currently designed with a huge array containing a struct instance for every player. In the game, we frequently need to cycle through that huge array to access all of the players' health and all of their positions to check things like who is dead or who is close enough to an exploding grenade to be affected. How could you apply the principles of data locality to this design to increase the speed of these operations?
struct Player {
int health;
Vector3 position;
string otherStringData;
}
struct Player {
int health;
Vector3 position;
string otherStringData;
}
This classic problem is often called an Array of Structs (AOS) versus a Struct of Arrays (SOA). In the answer they are looking for you to identify that iterating through the structs requires jumping over the other data which will result in far more cache misses than if the health floats were arranged beside each other. This problem will become worse if the player struct grows in size.This is just like the earlier problem where a column-major matrix traversal cost us to unnecessarily jump over rows of data.
The solution is to replace the array of structs with a struct of arrays like this:
Now we can iterate straight through all of health's values, performing the desired operations with far less cache misses. Additionally if we are performing the same operation on multiple values (such as decreasing all player's health by five points) then we now have the added affordance of using SIMD instructions because the data is contiguous.
The solution is to replace the array of structs with a struct of arrays like this:
struct Players{
int [] healths;
Vector3 [] positions;
string [] otherStringDatas;
}
Now we can iterate straight through all of health's values, performing the desired operations with far less cache misses. Additionally if we are performing the same operation on multiple values (such as decreasing all player's health by five points) then we now have the added affordance of using SIMD instructions because the data is contiguous.
The TLB (translation lookaside buffer) is an additional type of cache that maps addresses to virtual memory pages. When a computer runs out of RAM pages it can create virtual memory pages to simulate a larger memory capacity. However even though it can pretend to have a larger capacity, the RAM still has the same maximum storage capacity; so when it swaps out real pages with virtual pages it puts the real data into main memory and uses the TLB to remember where it put them. Here's a nice video demo of the process. Pages on a x64 system are all the same size of 4KB, but you can alternatively setup a TLB to segment virtual memory into non-uniformly sized allocations called segments; these two approaches are called paging and segmentation respectively.
Allocation
An allocator is an algorithm for partitioning memory for usage. Good allocators have high speed and low fragmentation. Fragmentation refers to inefficiencies in memory usage. There are two kinds of fragmentation:
Here are some common allocator designs; on an interview you will be expected to explain the designs of various allocators in addition to the benefits of each approach with respect to speed and fragmentation. Watch the lecture, Dogged Determination, from Jason Gregory for a brief primer on some of these designs. Keep in mind that for most allocators we are not cleaning the memory once it is freed, that takes too long. Instead we just record it as free and we write over it when the client requests the memory.
- Internal means giving a client more memory than they need, leading to wasted unused space within the allocations. It's like giving a very skinny man a super long bench all to himself, there is extra room on that bench that is wasted since the occupant is so skinny. (think: wasted space within allocated memory)
- External means you have memory available, but you can't allocate it because the free memory is interspersed between used memory causing it to be too small for the client to use. It's like telling a skinny person to sit in the center seat of a row of three seats; and then a fat 2-seat wide person wants a seat but even though you have two free seats, they are not contiguous so you can't fit the fat guy anywhere.
- There are many allocation strategies that you should be aware of below are some of the common approaches. As we learn about each approach we want to consider their limitations with respect to fragmentation. (think: wasted space between allocated memory).
Here are some common allocator designs; on an interview you will be expected to explain the designs of various allocators in addition to the benefits of each approach with respect to speed and fragmentation. Watch the lecture, Dogged Determination, from Jason Gregory for a brief primer on some of these designs. Keep in mind that for most allocators we are not cleaning the memory once it is freed, that takes too long. Instead we just record it as free and we write over it when the client requests the memory.
- Slab allocator: Gives out "slabs" of memory but the size(s) of the slabs it provides are restricted. Usually slabs are all just one size but sometimes a slab allocator supports a very small range of sizes. Because the allocations have known sizes, they have known bounds which makes the allocator very fast to swap slabs in and out. However because we are rounded the requested memory amount up to the closest slab size, we are basically guaranteeing internal fragmentation for the benefit of having zero external fragmentation.
- Buddy allocator: first divides memory into big blocks that are then broken into smaller blocks that will be re-absorbed when they are freed. The sizes of allocation are somewhat arbitrary so external fragmentation chances are high. But there is less internal fragmentation than a traditional slab allocator.
- Stack AKA “LIFO” allocator: Used for situations that have predictable build-up and tear-down sequences. There is zero internal or external fragmentation since we know exactly what sizes are needed and that the memory allocation order will mirror the memory free order. mind that we can grow the stack from two directions.
- Relocatable Heap: can move allocated blocks after deallocations, but it has to manually update any external pointers that were tracking addresses in the allocated blocks. This is useful if we want to extend an allocated object beyond the size we originally allocated for it.
- Pooled Allocator: gives small allocations but does not free until the pooled allocator is destroyed. Used for very many, very small, allocations but with short lifetimes. Similar to the stack allocator, we have very low internal fragmentation but this design allows us to reuse the allocated memory at the cost of some external fragmentation.
Practice Question: What are some examples of when each of these allocators would be useful?
TODO
The Virtual Keyword
The virtual keyword is very overloaded in C++ which means it has many different definitions depending on the context.
Virtual Pages
We already discussed the role of the TLB simulating additional memory capacity using "virtual" pages. See the previous TLB section for more information.
Virtual Methods (and vtables)
Methods can be marked as virtual so that subclasses can override their functionality.
TODO: talk about vtables
Every virtual class has a vTable which contains a map from all of its virtual functions to their definitions
Virtual class memory overhead includes: 1 vTable per class, 1 vPointer per object
What is a polymorphic type?
Any class that has at least one virtual method or virtual destructor or virtual base class is polymorphic. Only those types have a virtual method table (VMT) in their data layout.
Explain when parts of code happen,including when the VTable for virtual classes is constructed. Also, what part of code does the VTable live in? Explain the Stack vs Heap vs Globals VS Codevs Code sections
Virtual Classes
TODO
Other notes:
Will virtual function calls be inlined?
Inlining is a compiler optimization wherein the compiler adds the code of a method directly into the code where the method is called. Whenever a virtual function is called using a base class reference or pointer, it cannot be inlined (because the call is resolved at runtime). But whenever a virtual function is called using the object of that class, it can be inlined because compiler knows the exact class of the object at compile time.
Virtual Pages
We already discussed the role of the TLB simulating additional memory capacity using "virtual" pages. See the previous TLB section for more information.
Virtual Methods (and vtables)
Methods can be marked as virtual so that subclasses can override their functionality.
TODO: talk about vtables
Every virtual class has a vTable which contains a map from all of its virtual functions to their definitions
Virtual class memory overhead includes: 1 vTable per class, 1 vPointer per object
What is a polymorphic type?
Any class that has at least one virtual method or virtual destructor or virtual base class is polymorphic. Only those types have a virtual method table (VMT) in their data layout.
Explain when parts of code happen,including when the VTable for virtual classes is constructed. Also, what part of code does the VTable live in? Explain the Stack vs Heap vs Globals VS Codevs Code sections
Virtual Classes
TODO
Other notes:
- in case of virtual inheritance,inheritance it is the most derived class that calls the virtual base class' constructor LINK
- The purpose of inheritance in C++ is NOT code reuse, but instead to express interface compliance (subtyping) LINK
Will virtual function calls be inlined?
Inlining is a compiler optimization wherein the compiler adds the code of a method directly into the code where the method is called. Whenever a virtual function is called using a base class reference or pointer, it cannot be inlined (because the call is resolved at runtime). But whenever a virtual function is called using the object of that class, it can be inlined because compiler knows the exact class of the object at compile time.
Practice Question: Imagine you have a class named A which implements a method, and A has two derived "sub-classes" B1 and B2which both override the A's implementation of the method. Additionally, let's imagine that a fourth class exists called C which is both a subclass of B1 and B2. When C calls the method, will it use B1's definition of the method or B2's? How can this design be improved?
This is a classic problem called the Diamond Inheritance problem, so called because the class hierarchy can be drawn as a diamond with A at the top, B1 and B2 in the middle, and C at the bottom. The result of this situation is that A's data members are inherited twice into C (once from B1 and once from B2).
C++ requires you to specify in the call to C's method whether the implementation of B1 or B2 should be used. The invocation looks something like this: B1::C.Method() which indicates that we should call B1's override of the method. This resolves the ambiguity but it does not resolve the data duplication.
To prevent duplicating A's data, you need to define subclass B with virtual inheritance which looks like this: class B1 : virtual public A{ }. This will prevent data member duplication as long as both B1 and B2 are defined with virtual inheritance. In general, it's a good practice to use virtual inheritance whenever you are using a derived class as a bass class.
Some studios choose to outright ban multiple inheritance to simply prevent these sorts of scenarios.
C++ requires you to specify in the call to C's method whether the implementation of B1 or B2 should be used. The invocation looks something like this: B1::C.Method() which indicates that we should call B1's override of the method. This resolves the ambiguity but it does not resolve the data duplication.
To prevent duplicating A's data, you need to define subclass B with virtual inheritance which looks like this: class B1 : virtual public A{ }. This will prevent data member duplication as long as both B1 and B2 are defined with virtual inheritance. In general, it's a good practice to use virtual inheritance whenever you are using a derived class as a bass class.
Some studios choose to outright ban multiple inheritance to simply prevent these sorts of scenarios.
Pure Virtual Methods
Pure virtual functions aka "abstract" functions are just virtual functions that do not declare an implementation. Pure virtual functions must be implemented by subclasses. Below is an example pure virtual definition. Interviews often ask you to write out a pure virtual function definition like this example.
class Base
{
public:
virtual void function() = 0;
};
Virtual functions add an overheadadd an additional overhead because they are stored in the vTable. Their benefit is sharing the signature from a class to its subclasses. And if virtual, ensuring they implement it.
A virtual method makes a class abstract and forces its children to implement it or they’re also abstract. The method is not abstract itself, itself as pure virtual methods can define bodies. Derived classes that implement a pure virtual function may call its implementation somewhere in their code. Advice: If part of the code of two different derived classes is similar,similar then it makes sense to move it up in the hierarchy, even if the function should be pure virtual.
Understand dynamic dispatching. You will never dynamically dispatch to a pure virtual function. If defined at all, they are only invoked manually.
Pure virtual functions aka "abstract" functions are just virtual functions that do not declare an implementation. Pure virtual functions must be implemented by subclasses. Below is an example pure virtual definition. Interviews often ask you to write out a pure virtual function definition like this example.
class Base
{
public:
virtual void function() = 0;
};
Virtual functions add an overheadadd an additional overhead because they are stored in the vTable. Their benefit is sharing the signature from a class to its subclasses. And if virtual, ensuring they implement it.
A virtual method makes a class abstract and forces its children to implement it or they’re also abstract. The method is not abstract itself, itself as pure virtual methods can define bodies. Derived classes that implement a pure virtual function may call its implementation somewhere in their code. Advice: If part of the code of two different derived classes is similar,similar then it makes sense to move it up in the hierarchy, even if the function should be pure virtual.
Understand dynamic dispatching. You will never dynamically dispatch to a pure virtual function. If defined at all, they are only invoked manually.
Practice Question: What is the difference between the vtable for a class with virtual functions and a class with pure virtual functions?
TODO: https://stackoverflow.com/questions/7636230/c-interview-vtable-for-a-class-with-a-pure-virtual-function
Virtual Destructors
You need to mark a class' destructor as virtual if you will destruct a derived object of that class using a pointer with the type of its base class. Without a virtual destructor memory will leak, here's an example:
If Pet p = Dog, and I delete the p (which has no virtual destructor), it will destruct the Pet data but not propagate the call down to Dog's destructor. Dog may have memory that is now leaked!
This is an extremely common interview topic; you should memorize that...
*Technically* your method does not need a virtual destructor if:
In the words of Scott Meyers: "if a class has any virtual function, it should have a virtual destructor unless it’s not designed to be a base class or not designed to be used polymorphically."
You need to mark a class' destructor as virtual if you will destruct a derived object of that class using a pointer with the type of its base class. Without a virtual destructor memory will leak, here's an example:
If Pet p = Dog, and I delete the p (which has no virtual destructor), it will destruct the Pet data but not propagate the call down to Dog's destructor. Dog may have memory that is now leaked!
This is an extremely common interview topic; you should memorize that...
*Technically* your method does not need a virtual destructor if:
- Your class is never instantiated on the heap
- You have no intention to derive classes from the class
- You never refer to an instance of a derived class using a pointer of type baseClass
In the words of Scott Meyers: "if a class has any virtual function, it should have a virtual destructor unless it’s not designed to be a base class or not designed to be used polymorphically."
Static Keyword
Static Variables
Static: TODO
In the below example, “zeroinit” will be zero initialized while, "undef" will be undefined
static int zeroInit1;
int zeroInit2;
int main(){
int undef;
static int zeroInit3;
}
^only for primitive static types, no zero-initialization for user-defined types
Static Classes
A static class cannot be instantiated, and can contain only static members. Stored in static area (not on stack).
Static Functions
A static function is blah blach. It's unique properties are that...
Static: TODO
In the below example, “zeroinit” will be zero initialized while, "undef" will be undefined
static int zeroInit1;
int zeroInit2;
int main(){
int undef;
static int zeroInit3;
}
^only for primitive static types, no zero-initialization for user-defined types
Static Classes
A static class cannot be instantiated, and can contain only static members. Stored in static area (not on stack).
Static Functions
A static function is blah blach. It's unique properties are that...
- It can’t directly access the non-static members of its class
- It can’t be declared const, volatile or virtual.
- It doesn’t need to be invoked through an object of its class, although for convenience, it may. Usually,Usually static member functions are called using the class name: class_name::function(( )
Practice Question: Example Question?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Miscellaneous C++ Keywords
A portion of most gamedev coding interviews will judge your familiarity with C++, these question will often ask for the definition and use of the following keywords. Review each and ensure you are familiar with its proper usage.
Volatile: “Omit from optimization”
Friend: the friend keyword is used to declare one class to be a friend of another. Classes can access the private and protected members of any of their friend classes.
Const: const is an extremely common keyword that determines if a variable will change its value. Usually the const keyword precedes a type in an initialization statement. For example:
const int x;
The above line means x cannot change the value of its integer. However, in the case of pointers, the const keyword can be placed in several different positions, such as in the below example the const keyword can be place in either the A1 or A2 position and it can also be placed in the B position:
A1 int A2 * B myPtr
Let's break down what the const value would mean in each of these positions:
Explicit: forces object creation to use the constructor. Prevents implicit conversions that would be caused (for example, putting an int when it expects a customNum where customNum has an int constructor defined).
Extern: prevents compiler name mangling
Inline: suggests to compiler that a function should be inlined. See the virtual section for a discussion on inlining virtual functions.
Union: a user-defined datatype that groups values so that they can all share one value. Useful for shared storage of conditionally necessary variables. Usually used with a variable to indicate which type is in use.
Placement New Operator (In-Place New)
type * myPtr = new(addr)(type)(init)
Example: int x;
int* myPtr= new(&x) int (10);
“creates a pointer to a new int that is written where x was stored, initializes the new int with value 10”
std::move() explainer
--------------------------------
Reflection is runtime compiling, and could be useful for compiling a code class based on art data, or perhaps a property field display in a component editor. Unity uses reflection to inspect classes for an Update method.
Linked: 1, 2,
Include Guards
Include vs Using:
'include' basically does a copy-paste the value of a file to the location of the "include" line. This is used to make your source code (usually .c file) aware of a declaration of other source code (usually sits in .h file).
'using' basically tells the compiler that in the next code you are using something (usually a namespace) so you won't have to do it explicitly each time:
Big-O complexities: n! > 2n > n2 >> n log n >> n > log n > 1
int32.MAX is 2,147,483,647….why? This doesn’t appear to be 2^32 -1, that’s because we have a sign bit!
Streams vs Branches, LINK
Streams have privileged branches that “merge-down and copy-up”. Stream branches automatically receive changes from the mainline (OOO approach).
Q: What are the differences between a C++ struct and C++ class?
The only differences are that a struct defaults to public member access and public base-class inheritance, and a class defaults to the private access specifier and private base-class inheritance. Structs can have inheritance.
Forward Declaration
Useful if we just need to know an object exists, but we don’t need to use its properties. Note, you still need the A.h include in your B.cpp file.
//File A.h
class A
{
};
// File B.h
class A; //forward declaration
class B
{
B* m_pTest; // no error
B m_Test; //COMPILER ERROR
};
Volatile: “Omit from optimization”
Friend: the friend keyword is used to declare one class to be a friend of another. Classes can access the private and protected members of any of their friend classes.
- Friendship is not transitive (friends of friends are not friends).
- Friendship is not necessarily bi-directional (just because A is a friend of B, B is not automatically a friend of A).
- Friendship is not inherited (subclasses of friends do not become friends automatically).
Const: const is an extremely common keyword that determines if a variable will change its value. Usually the const keyword precedes a type in an initialization statement. For example:
const int x;
The above line means x cannot change the value of its integer. However, in the case of pointers, the const keyword can be placed in several different positions, such as in the below example the const keyword can be place in either the A1 or A2 position and it can also be placed in the B position:
A1 int A2 * B myPtr
Let's break down what the const value would mean in each of these positions:
- If const is place at location B then the pointer is constant. That means we cannot change which memory address the pointer is pointing to, but it does not restrict us from changing the value located at that address. If const is placed on B then reassigning myPtr's value such as in the following example will produce an error:
- myPtr = newPtr
- If const is place at location A1 or A2 then the value is constant. That means we cannot change the value pointed to by the pointer, but it does not restrict us from changing the which address the pointer is pointing to. Const cannot be placed on both A1 and A2, one position must be chosen and most game studios choose either the A1 or A2 position to be the definitive position to use for all of their values. If const is placed on A1 or A2 then reassigning the value myPtr is pointing at such as in the following example will produce an error:
- *myPtr = newValue
Explicit: forces object creation to use the constructor. Prevents implicit conversions that would be caused (for example, putting an int when it expects a customNum where customNum has an int constructor defined).
Extern: prevents compiler name mangling
- extern "C" { void foo(); }
Inline: suggests to compiler that a function should be inlined. See the virtual section for a discussion on inlining virtual functions.
Union: a user-defined datatype that groups values so that they can all share one value. Useful for shared storage of conditionally necessary variables. Usually used with a variable to indicate which type is in use.
Placement New Operator (In-Place New)
type * myPtr = new(addr)(type)(init)
Example: int x;
int* myPtr= new(&x) int (10);
“creates a pointer to a new int that is written where x was stored, initializes the new int with value 10”
std::move() explainer
--------------------------------
Reflection is runtime compiling, and could be useful for compiling a code class based on art data, or perhaps a property field display in a component editor. Unity uses reflection to inspect classes for an Update method.
Linked: 1, 2,
Include Guards
Include vs Using:
'include' basically does a copy-paste the value of a file to the location of the "include" line. This is used to make your source code (usually .c file) aware of a declaration of other source code (usually sits in .h file).
'using' basically tells the compiler that in the next code you are using something (usually a namespace) so you won't have to do it explicitly each time:
Big-O complexities: n! > 2n > n2 >> n log n >> n > log n > 1
int32.MAX is 2,147,483,647….why? This doesn’t appear to be 2^32 -1, that’s because we have a sign bit!
Streams vs Branches, LINK
Streams have privileged branches that “merge-down and copy-up”. Stream branches automatically receive changes from the mainline (OOO approach).
Q: What are the differences between a C++ struct and C++ class?
The only differences are that a struct defaults to public member access and public base-class inheritance, and a class defaults to the private access specifier and private base-class inheritance. Structs can have inheritance.
Forward Declaration
Useful if we just need to know an object exists, but we don’t need to use its properties. Note, you still need the A.h include in your B.cpp file.
//File A.h
class A
{
};
// File B.h
class A; //forward declaration
class B
{
B* m_pTest; // no error
B m_Test; //COMPILER ERROR
};
Practice Question: Example Question?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Example
X
Practice Question: Example Question?
An unsigned int-32 would have all 32 bits to represent its value, but we need to remember to subtract one because one combination of bits is used to represent 0. Therefore the max value of a uint-32 is 2^32-1.
But I asked for a signed int-32 which requires the first bit to represent the sign. Therefore the max value of a uint-32 is 2^31-1.
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
Additional reading:
https://stackoverflow.com/questions/94591/what-is-the-maximum-value-for-an-int32
More sections coming soon as I continue to port them from my Google Sheet:
tinyurl.com/gamedevStudySheet <<< You can view additional topics there!
tinyurl.com/gamedevStudySheet <<< You can view additional topics there!