Memory Management

This blog post dives into a crucial aspect of real-time data handling: Memory Management. Despite its significance in architectural system design, this topic is not extensively covered in the official KX documentation. A profound comprehension of Memory Management in KDB/Q is crucial for understanding the workings of Garbage Collection in the same environment. In this blog post, I aim to provide a comprehensive overview of Memory Management in KDB/Q, shedding light on essential considerations for designing an efficient system.

Buddy Memory Allocation

In the background, KDB/Q employs the Buddy Memory Allocation Algorithm for memory allocation to objects. This method partitions memory into sizes that are powers of two, aiming to fulfill memory requests in the most efficient manner. The approach involves dividing memory into halves and attempting to provide the best fit for a given request. According to the renowned computer scientist and mathematician Donald Knuth, the buddy system was invented in 1963 by Harry Markowitz. Markowitz is widely recognized for his groundbreaking contributions to Modern Portfolio Theory (MPT) and the development of the Efficient Portfolio Frontier.

Various forms of the buddy system exist, and the most common variant involves subdividing each block into two smaller blocks. Each memory block in this system is assigned an order, represented by an integer ranging from 0 to a specified upper limit. The size of a block with order n is proportional to 2^n, ensuring that blocks are precisely twice the size of those one order lower. This power-of-two sizing simplifies address computation as all buddies are aligned on memory address boundaries that are powers of two. When a larger block is split, it divides into two smaller blocks, with each smaller block serving as a unique buddy to the other. Importantly, a split block can only be merged with its unique buddy block (the block adjacent to it), effectively reconstituting the larger block from which they were initially split.

The following example should illustrate the concept of Buddy Memory Allocation. Suppose the smallest block size in this system is 64 kilobytes, and the upper limit for the order is 4, yielding the largest possible allocatable block at 2^4 times 64K = 1024K in size. The system's state after several memory requests might appear as follows:

Source: Wikipedia Buddy memory allocation

In the above scenario the Buddy Memory Allocation Algorithm functions in the following sequence:

1. The initial state of the memory of our system
2. Program A requests memory 34 K, order 0.
   1. No order 0 blocks are available, so an order 4 block is split, creating two order 3 blocks.
   2. Still no order 0 blocks available, so the first order 3 block is split, creating two order 2 blocks.
   3. Still no order 0 blocks available, so the first order 2 block is split, creating two order 1 blocks.
   4. Still no order 0 blocks available, so the first order 1 block is split, creating two order 0 blocks.
   5. Now an order 0 block is available, so it is allocated to A.
3. Program B requests memory 66 K, order 1. An order 1 block is available, so it is allocated to B.
4. Program C requests memory 35 K, order 0. An order 0 block is available, so it is allocated to C.
5. Program D requests memory 67 K, order 1.
   1. No order 1 blocks are available, so an order 2 block is split, creating two order 1 blocks.
   2. Now an order 1 block is available, so it is allocated to D.
6. Program B releases its memory, freeing one order 1 block.
7. Program D releases its memory.
   1. One order 1 block is freed.
   2. Since the buddy block of the newly freed block is also free, the two are merged into one order 2 block.
8. Program A releases its memory, freeing one order 0 block.
9. Program C releases its memory.
   1. One order 0 block is freed.
   2. Since the buddy block of the newly freed block is also free, the two are merged into one order 1 block.
   3. Since the buddy block of the newly formed order 1 block is also free, the two are merged into one order 2 block.
   4. Since the buddy block of the newly formed order 2 block is also free, the two are merged into one order 3 block.
   5. Since the buddy block of the newly formed order 3 block is also free, the two are merged into one order 4 block.

As you can see, what happens when a memory request is made is as follows:

• If memory is to be allocated

1. Look for a memory slot of a suitable size (the minimal 2k block that is larger or equal to that of the requested memory)
   1. If it is found, it is allocated to the program
   2. If not, it tries to make a suitable memory slot. The system does so by trying the following:
      1. Split a free memory slot larger than the requested memory size into half
      2. If the lower limit is reached, then allocate that amount of memory
      3. Go back to step 1 (look for a memory slot of a suitable size)
      4. Repeat this process until a suitable memory slot is found

• If memory is to be freed

1. Free the block of memory
2. Look at the neighboring block – is it free too?
3. If it is, combine the two, and go back to step 2 and repeat this process until either the upper limit is reached (all memory is freed), or until a non-free neighbour block is encountered

Why Memory Management Matters

You might wonder why you should pay this much attention to the inner working of KDB/Q's Memory Management. When building a KDB/Q system, you are bound by hardware restrictions and the amount of memory available. This means that the volume of data you can store in memory is finite and this limitation needs to be considered when designing your system. However, the required space can easily be underestimated due to the fact that the Buddy Memory allocation algorithm allocates memory to objects in blocks of power-of-two, rounding the size of an object to the next larger power-of-two.

This can easily be seen by inspecting the memory allocated to a simple list. An atom of datatype long (the default datatype in KDB/Q) has a size of 8 bytes. A simple list of 4000 long atoms should therefore occupy 4000 * 8 = 32000 bytes, and a list with 5000 long atoms should occupy 5000*8=40000 bytes. However, as evident from the code snippet below, the list with 5000 long atoms consumes approximately 1.5 times more space than our initial estimation. We can delve deeper to determine the number of elements required for the Buddy Memory Allocation to allocate the next power-of-two block size.

tip

You can use the system command \ts to evaluate the execution time an expression takes to run in milliseconds and the space used in bytes.

q)4000*8
32000
q)5000*8
40000
q)\ts til 4000
48 32944
q)\ts til 5000
0 65712
q)\ts til 4094
0 32944
q)\ts til 4095
0 65712

As you can observe, once our list of long atoms grows beyond 4094 elements, the Buddy Memory Algorithm allocates the next larger block of memory to accommodate the list. Calculating the various memory blocks is straightforward:

q)2 xexp til 20
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288f

I hope this post has been beneficial in explaining the concept of Memory Management in KBD/Q. It is essential to grasp this concept as it forms the foundation for our upcoming discussion on Garbage Collection. Stay tuned!

Resources

1. Memory Management in KDB, TimeStored by Ryan Hamilton
2. KDB+ Database Setup Utilities by Data Intellect
3. Adventure in Retrieving Memory Size of KDB+ Object by Data Intellect