1

If I have an array and all I have is an upper limit on how big the array can get, and if the number of elements that get added can be considerably smaller than this limit, is it always the right choice to declare a pointer and just reallocate extra memory whenever the array grows?

For instance, instead of declaring int a[max] I can declare a pointer int *a and than just realloc when I add elements. This would save memory. Is there any drawback to doing this?

Mars
  • 4,677
  • 8
  • 43
  • 65
  • 1
    What if realloc fails? You should profile the performance on target with actual application before making your mind. – Mohit Jain Oct 15 '14 at 06:43
  • @MohitJain. Oh I see, I did not think of failure. – Mars Oct 15 '14 at 06:46
  • "This would save memory. Is there any drawback to doing this?" -- Of course; there's a time/space tradeoff. – Jim Balter Oct 15 '14 at 07:02
  • possible duplicate of [Unknown size of int array](http://stackoverflow.com/questions/26375137/unknown-size-of-int-array) – n0p Oct 15 '14 at 07:41

3 Answers3

2

Calling realloc on every append to your array is probably too expensive. You should keep the allocated size of your memory zone, and increase it once in a while. If oldsize is the old size, you might compute something like newsize = (5*oldsize/4+10)|0xf; since for small sizes this would grow by at least 10 elements, and for large sizes you won't lose more than about 25% of memory.

If speed is a concern, you might special-case the common small sizes, e.g. by declaring a local array int loc[8]; and use loc instead of a malloc-ed or calloc-ed pointer for small arrays of size <=8. You could also consider alloca(3) to allocate some small array on the stack (don't use alloca on more than a few dozens of kilobytes on current desktops), or use VLAs. You might also consider flexible array members.

Of course you should always test against failure of calls to malloc, calloc, realloc etc.... (and in general of every library function you are using). Read carefully the documentation of malloc(3)

Basile Starynkevitch
  • 223,805
  • 18
  • 296
  • 547
1

Some drawbacks:

  • increased code complexity
  • additional failure cases (realloc might fail)
  • possible performance loss (realloc can be slow if the array has to be moved)

You have to check and decide if the drawbacks outweigh the benefit of using less resources in most cases. Another advantage is that you don't have to know a maximum array size in advance.

undur_gongor
  • 15,657
  • 5
  • 63
  • 75
  • I was aware of the possible performance loss but just always took for granted that the call will succeed. – Mars Oct 15 '14 at 06:47
  • 1
    @Zaphod Unless you're working in a highly memory constrained environment or your max size is huge, it's reasonable to assume that the realloc will succeed (and to exit the program if it doesn't) ... after all, you assume that the static array allocation will succeed, but that can fail just as well (in which case your program won't load). – Jim Balter Oct 15 '14 at 07:08
1

You might save memory but you will certainly affect the performances.

If you want to store elements but you does not know a priori how much, why don't you use linked list ?

n0p
  • 3,399
  • 2
  • 29
  • 50
  • This might be more efficient for adding (+ realloc), but access to the list is typically much slower. Depends on the usage, of course. – undur_gongor Oct 15 '14 at 07:00
  • It depends on how you intend to handle it (and we have no clue here). But from a memory management POV at least it is simpler. – n0p Oct 15 '14 at 07:03
  • The OP wrote "I have an array". A linked list is not an array, and there aren't very many use cases where they are interchangeable. – Jim Balter Oct 15 '14 at 07:03
  • 1
    reallocing an array to a new size is simpler than adding a node to a linked list and is far more memory-efficient. – Jim Balter Oct 15 '14 at 07:05
  • Maybe OP has an array because he didn't thought about alternatives, that is why I suggested linked list. Since we don't know how OP would use it, it is hard to make any assumption about the interchangeability and the efficiency of adding/removing/moving elements in the data structure without being opinion-based. – n0p Oct 15 '14 at 07:16