C: Realloc in Array (again)

It's possible that you just need to develop a more complicated data structure supporting semantic of an "array list". Say, you have too many elements to justify the use of a linked list with a separate element (with one or two pointers in each one), and the speed of addressing of an element is more critical factor then the cost of element insertion, which rarely or never happens. This is a very usual situation. Then you can develop one of the know hybrid model. For example, you can have a linked list of element each representing a fairly big chunk of your array. In your array structure, you will also need to support two different lengths: allocated and actually used. In general case, your last chunk sill be only partially used. You can create some initialization for your structure which accept custom chunk size, which you can vary in actual object depending on the usage criteria.

Say, in typical use, you may have the number of linked list elements not exceeding, say, 30-100 elements, which is not a big burden the your algorithm of the indexing: you will have the time complexity of O(N) for reaching required chunk, but inside chuck it will be direct pointer calculation, with time complexity of O(1). When your data grows, you just add another linked list element and put data in fully filled last chunk element, and then in new chunk element. Overall, can will give you some reasonable trade off between flexibility of the growing size of data and performance of element addressing.

This is only one of possible solution. I wanted to give you just the idea of some hybrid data structure. In all cases, I would avoid realloc. The problem is not just it's performance, but the fact that its code is external to your application, so the consequence are hard to predict; it includes unpredictable performance and unpredictable level of process memory fragmentation. When you go with fixed-size chunks, it's much more likely that runtime system will avoid memory considerable memory fragmentation.

The problem of heap optimization is a separate big problem, but here is just some food for thought: a number of software development technologies manage memory based on some runtime library with internal sub-allocator. That is, the implementation does not allocate heap directly through the OS API allocation/deallocaton function, but do it in larger chunks, leaving allocation to smaller objects to that sub-allocator.

—SA