0

I am interested in at least an approximate answer to:

int n;
...
std::vector<void*> vectorOfPointers;
vectorOfPointers.reserve(n);

For up to which number n does the above mentioned program run in O(1) ?

Let us suppose that for a laptop running 32 bit Ubuntu with 3 gigabytes of memory, not running any other programs. Is it tens, thousands, millions? What information does one need to know to be able to asses such a question? Is there a way to find out without running any experiments?

I have never studied anything about operating systems but in my imagination, the operating system allocates memory in just 2 steps. It determines the pointer to start the chunk and the pointer of the end of the chunk. The situation can be more complicated because the system may have to tidy up in order to get a big enough chunk of memory. But if we suppose that the system runs just this one program, how can we estimate the time needed? Are there some other aspects to be considered, besides the fragmentation of memory?

EDIT:

sorry, I didn't make my question clear. It is important to consider, that the vector is empty before calling reserve, so no copying of data is required.

Martin Drozdik
  • 12,742
  • 22
  • 81
  • 146

3 Answers3

2

You can't rely on a O(1) complexity when using reserve().

Complexity

linear in the size of the container

(cf cppreference)

Basically, the allocation of the new memory is in constant time, but you will also need to copy the old elements from the previous memory into the new one (hence the linear complexity).

So on an empty vector, reserve will probably have a constant time, but I'm not sure that the standard explicitely states it. So it probably depends on the underlying implementation (even if I don't see any reason to not do it).

Maël Nison
  • 7,055
  • 7
  • 46
  • 77
2

From the C++ point of view, the code takes O(1) time (it's linear in the current size of the container, which in your case is always zero).

Now, it seems that your question is really about the complexity of allocating m bytes of memory. That, I am afraid, is unspecified.

For further discussion, see Time complexity of memory allocation

To add to what's already been said in the other question, there are several layers of complexity:

  • Firstly, malloc() needs to maintain its internal data structures. The complexity of doing that is not specified, but one would hope that malloc(m) would not take Θ(m) time. However, the complexity could well depend on other factors, such as memory fragmentation.
  • Secondly, malloc() may need to request additional memory from the OS. Here, it is not unreasonable to expect the OS to do something with every memory page it allocates (e.g. wipe it so you don't see someone else's confidential data). If this were to happen, the operation would indeed be Θ(m).
Community
  • 1
  • 1
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • Thank you, the question you refer to is what I am looking for. And it seems more complicated than I thought. But is there some "rule of the thumb" approximate answer? – Martin Drozdik Jan 19 '13 at 08:26
  • @MartinDrozdik: The rule of thumb is to profile your code on realistic inputs, and see where the bottleneck is. It is highly unlikely that memory allocation will be the bottleneck, rendering the question moot. – NPE Jan 19 '13 at 08:27
  • Actually I am not concerned about bottlenecks at all. I am developing an algorithm for which I try to estimate the complexity by experiments. I just want to know to what degree can my measurements be biased by things such as memory allocation – Martin Drozdik Jan 19 '13 at 08:30
  • 1
    @MartinDrozdik: If that's a concern, you might want to pre-allocate the memory. – NPE Jan 19 '13 at 08:41
  • Do you mean at compile time? Using a simple array instead of a vector? – Martin Drozdik Jan 19 '13 at 08:42
  • 1
    @MartinDrozdik: Either that, or just move the allocation outside the code that you're measuring. – NPE Jan 19 '13 at 08:44
1

The only O(1) I can think of std::vector::reserve() is when n <= capacity() which means reserve() does nothing.

billz
  • 44,644
  • 9
  • 83
  • 100