DOD - Index instead of Pointers in ArrayList
Introduction
Learn DOD now!!
Essence of Data Oriented Design (DOD)
In software design, DOD (Data-Oriented Design) focuses on efficient data structures to optimize performance, especially in critical scenarios like game development, real-time systems, and high-performance computing. A key principle is to minimize cache misses by organizing data for maximum locality, keeping related data close in memory.
I will be showing you what is being discussed in Andrew Kelley's video.
TLDR:
Using Array Indices only took 16 bytes vs 48 bytes in Array Pointers.
Use Index in ArrayList instead of Pointers
Memory Usage
As shown in the image, Array Pointers uses 48 bytes while Array Indices only uses 16 bytes. This is because the Array2D_Pointers struct requires additional memory to store the pointers to the elements, while the Array2D_Indices struct stores the elements directly in the struct.
Memory Allocation
When we use pointers to store the elements of an array, we have to allocate memory for each element separately. This can lead to memory fragmentation, as the memory blocks are scattered throughout the heap.
On the other hand, when we use indices to store the elements of an array, we can allocate a single block of memory to store all the elements. This reduces memory fragmentation and improves memory efficiency.
The code
Struct creation
#include <stdio.h>
#include <stdlib.h>
#define NUM_ELEMENTS 4
// Define the structure for the 2D array using pointers
typedef struct Array2D_Pointers {
int *a;
int *b;
int *c;
int *d;
} Array2D_Pointers;
// Define the structure for the 2D array using indices
typedef struct Array2D_Indices {
int a;
int b;
int c;
int d;
} Array2D_Indices;
Defines 2 structures: one using pointers to integers, the other one directly store the integer value. The choice between these structures determines how you access the elements within the array.
Allocate memory
// Create a new 2D array using pointers
Array2D_Pointers* Array2D_Pointers_create()
{
Array2D_Pointers *array = malloc(sizeof(Array2D_Pointers));
array->a = malloc(sizeof(int));
array->b = malloc(sizeof(int));
array->c = malloc(sizeof(int));
array->d = malloc(sizeof(int));
return array;
}
// Create a new 2D array using indices
Array2D_Indices* Array2D_Indices_create()
{
Array2D_Indices *array = malloc(sizeof(Array2D_Indices));
return array;
}
Dynamically allocate memory for their respective structures. Note how much easier it is to allocate the index-based struct, another +1 point to use it instead of pointer-based struct..
Setting values in 2D arrays
// Set values in the 2D array using pointers
void Array2D_Pointers_set(Array2D_Pointers *array, int a, int b, int c, int d)
{
*array->a = a;
*array->b = b;
*array->c = c;
*array->d = d;
}
// Set values in the 2D array using indices
void Array2D_Indices_set(Array2D_Indices *array, int a, int b, int c, int d)
{
array->a = a;
array->b = b;
array->c = c;
array->d = d;
}
These functions allow for setting values in their respective 2D array representations, either through pointers or direct member access.
Print the size and capacity along with the array's contents.
// Print size and capacity of the arrays
void print_sizeCap_array(Array2D_Pointers *array_pointers, Array2D_Indices *array_indices)
{
// Calculate the size of array pointer
size_t size_pointers = sizeof(Array2D_Pointers) + NUM_ELEMENTS * sizeof(int);
// Calculate the size of array indices
size_t size_indices = sizeof(Array2D_Indices);
// Calculate the capacity of array pointer
size_t capacity_pointers = NUM_ELEMENTS * sizeof(int);
// Calculate the capacity of array indices
size_t capacity_indices = NUM_ELEMENTS * sizeof(int);
printf("\nSize and Capacity of Arrays: \n");
printf("Array2D_Pointers: Size = %zu bytes, Capacity = %zu bytes\n",
size_pointers, capacity_pointers);
printf("Array2D_Indices: Size = %zu bytes, Capacity = %zu bytes\n",
size_indices, capacity_indices);
printf("\nArray2D_Pointers: \n");
printf("%d %d %d %d\n",
*array_pointers->a,
*array_pointers->b,
*array_pointers->c,
*array_pointers->d);
printf("\nArray2D_Indices: \n");
printf("%d %d %d %d\n",
array_indices->a,
array_indices->b,
array_indices->c,
array_indices->d);
}
Display the size, capacity, and contents of two different 2D array representations.
Main function
int main()
{
// ---POINTERS---
// Create 2D array using pointers
Array2D_Pointers *array_pointers = Array2D_Pointers_create();
// Set values using pointers
Array2D_Pointers_set(array_pointers, 10, 20, 30, 40);
// ---INDICES---
// Create 2D array using indices
Array2D_Indices *array_indices = Array2D_Indices_create();
// Set values using indices
Array2D_Indices_set(array_indices, 10, 20, 30, 40);
// Print the size, capacity and contents of the arrays
print_sizeCap_array(array_pointers, array_indices);
// Clean up
free(array_pointers->a);
free(array_pointers->b);
free(array_pointers->c);
free(array_pointers->d);
free(array_pointers);
free(array_indices);
return 0;
}
Demonstrates the creation, initialization, and printing of two 2D arrays, using both pointer-based and index-based structures. Note how much easier to free the memory in array_indices compared to array_pointers, for me this is another +1 point to index-based struct.
Result
If done correctly you should get this outcome:
Conclusion
As mentioned in the Andrew Kelley's video, using index indeed resulted in efficient memory usage. I want to dig deeper on how's the performance differences between the two array structs but this article has gotten too lengthy, I will discuss it in a follow-up article. Cheers!