XD blog

stack

2013-12-06 Extend the exception stack in Python

Most of the time, message given by exception are not enough precise to quickly understand the error. To add more information, I used to catch it and throw a new one:

try :
    # something
except Exception as e :
    message = "my message with more information \n" + str(e)
    raise Exception(message)

However, it is possible to do this:

try :
    # something
except Exception as e :
    message = "my message with more information"
    raise Exception(message) from e

It does not break the exception stack as before. The new exception is just added to it.

more...

2013-02-07 How to extend a stack?

A common way to create a sizeable but continuous array is to use a stack mechanism. We start by allocating a buffer and when we need more space to store new elements, we often multiply the size of this buffer by 2. We copy the existing elements into the new space, we add the new one and we free the old buffer. If we follow that strategy for a long time, we end up by allocation memory blocks of size N, 2N, 4N, 8N, ... The major drawback of this approach is we cannot reuse the space we used for the first allocation. The reason is simple:

$N + 2N + 4N + ... + 2^k N = N (2^{k+1} - 1 ) < 2^{k+1} N$

As a consequence, the new buffer is always larger than the sum of all previously allocated block. And we because, we need to keep the last one alive to copy the existing elements to the new block, this way of growing a stack cannot reuse the same memory space. This side effect could increase the memory fragmentation.

What does happen if we multiply the size of a block by a coefficient c smaller than 2:

$N + cN + c^2 N + ... + c^k N = N \frac{c^{k+1} - 1 }{c-1}$