Implementing a Memory Pool in Python

Memory pools are a technique used to optimize memory allocation, particularly when dealing with frequent allocation and deallocation of small, fixed-size objects. This challenge asks you to implement a basic memory pool in Python to improve performance in scenarios where standard Python memory allocation overhead becomes a bottleneck. A well-implemented memory pool can significantly reduce fragmentation and allocation latency.

Problem Description

You are tasked with creating a MemoryPool class in Python. This class should manage a pool of pre-allocated objects of a specific size. The pool should support the following operations:

• __init__(self, size, block_size): Initializes the memory pool. size represents the total memory (in bytes) to allocate for the pool. block_size is the size (in bytes) of each object that will be stored in the pool.
• allocate(self): Allocates a free block from the pool. If there are free blocks, it returns a pointer (represented as an integer index) to the allocated block. If the pool is full (no free blocks), it returns None.
• deallocate(self, ptr): Deallocates a block pointed to by ptr (an integer index). This block is then marked as free and can be reused by allocate().
• is_valid(self, ptr): Checks if the given pointer ptr is a valid pointer within the memory pool. Returns True if valid, False otherwise.

The memory pool should be implemented using a simple list to represent the memory blocks. Each element in the list represents a block. A boolean flag associated with each block indicates whether it is free or allocated. You can use a separate list to track the free blocks.

Examples

Example 1:

Input: size = 1024, block_size = 64
pool = MemoryPool(size, block_size)
ptr1 = pool.allocate()  # Returns 0
ptr2 = pool.allocate()  # Returns 1
pool.deallocate(ptr1)
ptr3 = pool.allocate()  # Returns 0
print(pool.is_valid(ptr1)) # True
print(pool.is_valid(100)) # False

Explanation: The pool is initialized with 1024 bytes, divided into blocks of 64 bytes each (16 blocks total). The first two blocks are allocated, then the first is deallocated, and it's reallocated later. is_valid checks if the pointer is within the bounds of the pool.

Example 2:

Input: size = 256, block_size = 32
pool = MemoryPool(size, block_size)
for _ in range(8):
    ptr = pool.allocate()
    if ptr is None:
        break
    pool.deallocate(ptr)
print(pool.allocate()) # Returns 0

Explanation: The pool is initialized with 256 bytes, divided into 8 blocks. All blocks are allocated and deallocated repeatedly. Finally, a new block is allocated, which should be the first available block (index 0).

Example 3: (Edge Case - Pool Full)

Input: size = 64, block_size = 16
pool = MemoryPool(size, block_size)
for _ in range(4):
    ptr = pool.allocate()
    if ptr is None:
        break
    pool.deallocate(ptr)
ptr1 = pool.allocate()
ptr2 = pool.allocate()
ptr3 = pool.allocate()
ptr4 = pool.allocate()
ptr5 = pool.allocate() # Returns None
print(ptr5)

Explanation: The pool is initialized with 64 bytes, divided into 4 blocks. All blocks are allocated and deallocated. Attempting to allocate more blocks than available results in None being returned.

Constraints

• size will be a positive integer between 64 and 10240 (inclusive).
• block_size will be a positive integer between 8 and 256 (inclusive).
• size must be divisible by block_size.
• ptr will be an integer between 0 and size // block_size - 1 (inclusive) if it's a valid pointer.
• The implementation should be reasonably efficient, avoiding unnecessary iterations or complex data structures. While a perfect solution isn't required, avoid O(n) operations within allocate and deallocate where possible.

Notes

• You can represent the memory blocks as a list of booleans, where True indicates a free block and False indicates an allocated block.
• Consider using a separate list to keep track of the indices of free blocks for faster allocation.
• Error handling (e.g., raising exceptions for invalid ptr values) is not required for this challenge, but is_valid should handle these cases.
• The "pointer" ptr is simply an index into the list of blocks. It doesn't represent a memory address in the traditional sense.
• Focus on the core logic of the memory pool – allocation and deallocation. Don't worry about complex features like block merging or compaction.