# How to treat dynamic memory allocation in algorithm analysis?

I have an algorithm in which I want to dynamically allocate some memory. Let's say that I have N numbers and that I want to describe some binary relation over them. To do so I want to create a N*N matrix. But how fast is the memory allocation itself regarding N?

I do not want to zero out the new memory. In fact I do not want to touch it at all in this moment - I just want to allocate it and be sure that all of it is there.

I understand that the answer is: how is the memory allocation implemented? Bit I hope that you can give me some upper bounds that are common for most of the popular memory management strategies.

• What is the goal of your analysis? Do you want to find out if the algorithm is good in practice, do you want to prove that it's good in theory, ...? – usul Apr 10 '15 at 15:28
• Also ask yourself why you are allocating so much memory. If you never intend to touch it all, you may be better off using a hash table. – Pat Morin Apr 11 '15 at 1:00
• It looks to me that this question might be more suitable for Computer Science. – Kaveh Apr 12 '15 at 21:49

and references therein, especially those to papers by Robson. Here is a quote that answers your question:

Robson put [in 1974] a fairly tight upper and lower bounds on the worst-case performance of the best possible allocation algorithm. He showed that a worst-case-optimal strategy's worst-case memory usage was somewhere between $0.5M\log_2 n$ and about $0.84 M\log_2 n$.

Here, $M$ is the live memory, and $n$ is the ratio of the largest to the smallest block.

(So, if your algorithm allocates blocks of wildly different sizes, then you may want to think more carefully about how memory allocation works. This doesn't seem to be the case for the example given in the question.)

PS: I was searching for a link to Robson's article and I found this related CSTheory question: Data structure for dynamic memory allocation

Just allocating memory without touching it is very cheap. The cost should be negligible in any kind of theoretical algorithm analysis.

You pay the serious penalty the first time you touch each page. The CPU will generate page faults and the operating system will have to do the one-time setup for each memory page. This is a non-trivial cost. Large constant per memory page.

In general, you should make sure that your algorithm touches each memory page a large number of times; otherwise the memory management cost will dominate.

Let $x$ be a newly allocated array with $n$ words, and let $b$ be the size of the memory page (in words). Very roughly, the following operations (executed in this order) are equally expensive:

1. Write to $x, x[b], x[2b], \dotsc, x[n-b]$.

2. Write to $x, x, \dotsc, x[n-1]$ and read from $x, x, \dotsc, x[n-1]$.

In the first step, you only perform $n/b$ write operations, but each of them hits a new memory page and you pay the penalty. In the second step, you perform $n$ write and read operations, but they are now cheap, as we do not have any page faults or memory management overhead.

A typical page size is 4 kilobytes, so if you estimate $b \approx 1000$, you should get reasonable ballpark figures.

• This is a good rule of thumb that I expect may be helpful as a guide for many platforms, but a small note of caution: the cost of allocating memory without touching it may depend upon the details of the memory allocator and underlying OS's policy for assigning virtual memory. (If you're unlucky, the OS might assign you physical pages immediately, and the OS policy will probably require that all of those pages have been zeroed out, so there could be a non-trivial cost.) – D.W. Apr 11 '15 at 1:32