logo
Published on

Memory Allocation of Fruits

🍉 Memory Allocation of Fruits 🍌

Introduction: The Fruit Basket Problem 🍎

Imagine you’re managing a magical fruit basket. This basket can store different types of fruits (data), like bananas (strings), apples (numbers), and even fruit smoothies (arrays). But there’s a problem: each new fruit takes up too much space, making access slow and inefficient! 🚀💨

To solve this, we need to optimize our basket (memory layout) to avoid waste and ensure fast access. Let’s embark on an adventure to make our fruit basket the best in town! 🏆

Step 1: The Naïve Approach 🍍

A basic way to store fruits might look like this:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Different types of fruit data
typedef enum { BOOL, FLOAT, STRING, ARRAY } DataType;

typedef struct {
    DataType type;
    union {
        int b;
        float f;
        char *s;
        float *array;
    } value;
} FruitData;

At first glance, this seems fine. We can store bananas (strings), apples (floats), or even a bunch of grapes (arrays). However, every time we add a fruit, it requires a separate memory allocation, leading to inefficiencies. 🍑😵

Step 2: Hashing Fruit Names for Faster Lookups 🍓

Instead of storing full fruit names, we can use a hashed fruit ID. This way, instead of storing "Strawberry," we store its numerical equivalent:

#include <stdint.h>

unsigned hash_fruit(const char *fruit_name) {
    unsigned hash = 0;
    while (*fruit_name) {
        hash = hash * 31 + *(fruit_name++);
    }
    return hash;
}

Now, instead of storing "Banana", we store 54321. This speeds up lookups and reduces memory waste. 🍌⚡

Step 3: Flattening the Fruit Basket 🍊

Instead of using a hierarchical structure where fruits are nested under categories (citrus, berries, tropical), we flatten everything. This means storing:

fruit.sweetness = 10
fruit.size = 5
fruit.color = 'yellow'

instead of:

fruit = {
  sweetness: 10,
  size: 5,
  color: 'yellow',
}

🚀 Why Flattening Improves Performance?

  1. Faster Lookups – No need to traverse a tree structure; properties are accessed instantly.
  2. Less Complexity – No deep nesting, making data handling easier.
  3. Database Efficiency – NoSQL databases prefer flat structures for better indexing.
  4. Reduced Memory Overhead – Nested structures require extra memory for object references.

Step 4: Optimizing with Structure of Arrays (SoA) 🍏

Instead of storing fruit data as an Array of Structures (AoS), we switch to a Structure of Arrays (SoA) for better cache efficiency.

typedef enum { BOOL, FLOAT, STRING, OBJECT, ARRAY } DataType;

typedef struct {
    unsigned *keys;
    DataType *types;
    void **values;
    size_t count;
    size_t capacity;
} FruitBasket;

FruitBasket* createFruitBasket(size_t capacity) {
    FruitBasket *basket = malloc(sizeof(FruitBasket));
    if (!basket) return NULL;

    void *data = malloc(capacity * (sizeof(unsigned) + sizeof(DataType) + sizeof(void *)));
    if (!data) {
        free(basket);
        return NULL;
    }

    basket->keys = (unsigned *)data;
    basket->types = (DataType *)(basket->keys + capacity);
    basket->values = (void **)(basket->types + capacity);
    basket->count = 0;
    basket->capacity = capacity;
    return basket;
}

void freeFruitBasket(FruitBasket *basket) {
    if (basket) {
        free(basket->keys); // Free all arrays at once
        free(basket);
    }
}

This stores keys, types, and values in separate arrays for better memory locality, making access much faster! 🏎️💨

📌 When is SoA Better?

  • When accessing all attributes of a single object (e.g., one fruit at a time), AoS is better.
  • When accessing one attribute across multiple objects (e.g., colors of all fruits), SoA is better.

| AoS (Original) | SoA (Optimized) | | -------------- | --------------- | ------ | -------- | ------- | -------- | | key | type | value | key_0 | key_1 | key_2 | | key | type | value | type_0 | type_1 | type_2 | | key | type | value | value_0 | value_1 | value_2 |

Step 5: Efficient Memory Allocation with Pre-Allocated Buffers 🍉

Instead of calling malloc() for every fruit, we pre-allocate a memory buffer:

typedef struct {
    char *buffer;
    size_t capacity;
    size_t used;
} FruitMemory;

void *allocate_memory(FruitMemory *fm, size_t size) {
    if (fm->used + size > fm->capacity) return NULL;
    void *ptr = fm->buffer + fm->used;
    fm->used += size;
    return ptr;
}

📌 Why is This Better?

  1. Reduces malloc overhead – Calling malloc() repeatedly can cause fragmentation and slow performance.
  2. Better Cache Utilization – Pre-allocating ensures that memory is contiguous, improving cache hits.
  3. Simplified Deallocation – Instead of freeing multiple small allocations, we free the entire buffer at once.

Example usage:

FruitMemory fm = {malloc(1024), 1024, 0};
char *buffer = allocate_memory(&fm, capacity * (sizeof(char*) + sizeof(int) + sizeof(float)));
char **names = (char **)buffer;
int *types = (int *)(names + capacity);
float *prices = (float *)(types + capacity);

Now, adding a new fruit simply takes a slice from the buffer instead of requesting memory dynamically. 🍉✨

🍏 The Fruit Basket (Memory Buffer)

Imagine you have a basket 🧺 with a fixed size (e.g., 10 slots).
This basket represents our memory buffer.

We will store fruit names (headers) on the left side and actual fruits (values) on the right side.

🍎🍌 Adding Fruits and Labels

  1. We first place labels (fruit names) on the left side.
  2. We then place the actual fruits on the right side.
  3. The free space in the middle shrinks as we keep adding.

🍏 Example Scenario (Adding Fruits)

Header (Names) →🍎 Apple🍌 Banana🟩 Free Space 🟩🍊 Orange🍉 Watermelon← Value (Fruits)
  • Apple label is stored on the left.
  • The actual Apple fruit is stored on the right.
  • Banana label is added next to Apple on the left.
  • The actual Banana fruit is stored on the right, next to Apple.

🍏 If Space Runs Out?

If we keep adding more fruit without enough space, the two sides will collide in the middle, meaning:

  1. The basket is full 🧺.
  2. We must get a bigger basket (reallocate memory).
  3. The fruits are rearranged into the new larger basket.

🍏 Code Representation

Here’s how this works in C code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// The basket (memory buffer)
typedef struct {
    char *basket;        // Single buffer for fruit names & fruits
    unsigned capacity;   // Total space
    unsigned label_size; // Space used by fruit names
    unsigned fruit_size; // Space used by actual fruits
} FruitBasket;

// Initialize the basket
FruitBasket *init_fruit_basket(unsigned capacity) {
    FruitBasket *fb = malloc(sizeof(FruitBasket));
    if (!fb) return NULL;
    fb->basket = malloc(capacity);
    if (!fb->basket) {
        free(fb);
        return NULL;
    }
    fb->capacity = capacity;
    fb->label_size = 0;
    fb->fruit_size = 0;
    return fb;
}

// Store a fruit name (growing left to right)
void *store_label(FruitBasket *fb, const char *name) {
    unsigned size = strlen(name) + 1;
    if (fb->label_size + fb->fruit_size + size > fb->capacity)
        return NULL; // No space left
    char *res = fb->basket + fb->label_size;
    strcpy(res, name);
    fb->label_size += size;
    return res;
}

// Store an actual fruit (growing right to left)
void *store_fruit(FruitBasket *fb, const char *fruit) {
    unsigned size = strlen(fruit) + 1;
    if (fb->label_size + fb->fruit_size + size > fb->capacity)
        return NULL; // No space left
    fb->fruit_size += size;
    char *res = fb->basket + fb->capacity - fb->fruit_size;
    strcpy(res, fruit);
    return res;
}

// Print basket contents
void print_basket(FruitBasket *fb) {
    printf("Total Capacity: %u\n", fb->capacity);
    printf("Label Space Used: %u\n", fb->label_size);
    printf("Fruit Space Used: %u\n", fb->fruit_size);
    printf("Free Space: %u\n", fb->capacity - (fb->label_size + fb->fruit_size));
}

// Free memory
void free_basket(FruitBasket *fb) {
    if (fb) {
        free(fb->basket);
        free(fb);
    }
}

// Example Usage
int main() {
    FruitBasket *fb = init_fruit_basket(100); // 100-byte basket

    char *apple_label = store_label(fb, "Apple");
    char *apple_fruit = store_fruit(fb, "🍎");

    char *banana_label = store_label(fb, "Banana");
    char *banana_fruit = store_fruit(fb, "🍌");

    print_basket(fb);

    printf("Fruit Label 1: %s -> %s\n", apple_label, apple_fruit);
    printf("Fruit Label 2: %s -> %s\n", banana_label, banana_fruit);

    free_basket(fb);
    return 0;
}

🍏 Output Example

Total Capacity: 100
Label Space Used: 13
Fruit Space Used: 10
Free Space: 77
Fruit Label 1: Apple -> 🍎
Fruit Label 2: Banana -> 🍌

🍏 Summary

  • The fruit basket (buffer) stores both labels and fruits.
  • Labels grow left to right 🏷️.
  • Fruits grow right to left 🍎.
  • If they meet in the middle, we need a bigger basket 🧺.

This is an efficient memory management technique that minimizes fragmentation! 🚀

Conclusion: A Super-Efficient Fruit Basket! 🏆

By applying these optimizations, we’ve transformed our messy fruit basket into a cache-friendly, memory-efficient system:

✅ Hashing reduces lookup times.
✅ Flattening simplifies data access.
✅ Structure of Arrays enhances performance.
✅ Pre-allocated Buffers minimize allocation overhead.

So, next time you’re designing data structures, think of memory allocation as a fruit basket—and make sure your bananas, apples, and grapes are stored efficiently! 🍌🍏🍇