<p>You want to read</p>

<ul>
<li>Wilson et al., <em><a href="https://scholar.google.co.uk/scholar?hl=en&amp;q=Dynamic%20Storage%20Allocation%3A%20A%20Survey%20and%20Critical%20Review" rel="nofollow noreferrer">Dynamic Storage Allocation: A Survey and Critical Review</a></em>, 1995</li>
</ul>

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

<blockquote>
  <p>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$.</p>
</blockquote>

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

<p>(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.)</p>

<p>PS: I was searching for a link to Robson's article and I found this related CSTheory question: <a href="https://cstheory.stackexchange.com/questions/30791/data-structure-for-dynamic-memory-allocation">Data structure for dynamic memory allocation</a></p>

CC BY-SA 3.0
2015-04-10T20:02:01.713Z
2015-04-10T20:02:01.713Z
2017-04-13T12:32:28.117Z
Radu GRIGore
<p>Just allocating memory without touching it is very cheap. The cost should be negligible in any kind of theoretical algorithm analysis.</p>

<p>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.</p>

<p>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.</p>

<hr>

<p>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:</p>

<ol>
<li><p>Write to $x[0], x[b], x[2b], \dotsc, x[n-b]$.</p></li>
<li><p>Write to $x[0], x[1], \dotsc, x[n-1]$ and read from $x[0], x[1], \dotsc, x[n-1]$.</p></li>
</ol>

<p>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.</p>

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

CC BY-SA 3.0
2015-04-11T01:32:51.733Z
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.
CC BY-SA 3.0
2015-04-10T13:31:58.243Z
2015-04-10T13:55:06.103Z
2015-04-10T13:55:06.103Z
Jukka Suomela
<p>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?</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-04-10T15:28:23.913Z
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
CC BY-SA 3.0
2015-04-11T01:00:34.610Z
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
CC BY-SA 3.0
2015-04-12T21:49:29.223Z
It looks to me that this question might be more suitable for [cs.se].
Kaveh
<analysis-of-algorithms>
How to treat dynamic memory allocation in algorithm analysis?
user931392
# How to treat dynamic memory allocation in algorithm analysis?

(Asked by: username_0 on 2015-04-10)

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.

**Tags:** analysis-of-algorithms

> **Comments:**
> **username_1**: 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, ...?  
> **username_2**: 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.  
> **username_3**: It looks to me that this question might be more suitable for [cs.se].  

---

## 2 answers

### Answer by username_4 on 2015-04-10. Score: 3

You want to read

* Wilson et al., *[Dynamic Storage Allocation: A Survey and Critical Review](https://scholar.google.co.uk/scholar?hl=en&q=Dynamic%20Storage%20Allocation%3A%20A%20Survey%20and%20Critical%20Review)*, 1995

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](https://cstheory.stackexchange.com/questions/30791/data-structure-for-dynamic-memory-allocation)


---

### Answer by username_5 on 2015-04-10. Score: 2

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[0], x[b], x[2b], \dotsc, x[n-b]$.
2. Write to $x[0], x[1], \dotsc, x[n-1]$ and read from $x[0], x[1], \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.

> **Comments:**
> **username_6**: 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.)  

---

