Quick Index
Overview


In this section we'll look at memory usage for a dynamic array.

Note that we are not talking about Big-O algorithm space complexity analysis, but rather memory usage by the structure.

Wasted Space


Definition


When we say "wasted space" will mean space in computer memory that is part of the structure and not the data.

Data Pointers


We will assume array position has one pointer (to the data).

Assuming each pointer is 8 bytes (64 bits), then there are 8 bytes (1*8) wasted per element.

Unused Capacity


Also remember that our dynamic array will "grow" when needed.

Let us assume the growth factor is 2.

Then, after a "grow" operation (which conservatively assumes worst case), we will have 50% pointers to actual data, and 50% unused pointers.

Thus, assuming worst we now waste one additional pointer per actual element or 8 bytes (1*8).

Total Wasted Space


Summing up the wasted space from the previous two sections gives us:

8 + 8 = 16 bytes of wasted space per data element in a dynamic array.

When to Analyze Wasted Space


The problem and the target hardware will dictate if wasted space need be considered. Here are a couple reasons that would drive us to analyze wasted space:


Data (Element) Size


Let us assume for both of the cases below that we know that memory usage is something that needs to be considered.

Large Data Elements


It is common that data size is much larger than "wasted space".

If our structure contains "customers", and for example purposes, we estimate "Customer" objects average 2500 bytes each, then the wasted space (24/2500) is less than 1% of the data memory use, and thus becomes a minor factor.

In this case, we would generally not perform a "wasted space" analysis. (naturally there are always exceptions if later in the project we are desperate to find ways to save even small amounts of memory usage -- then we may undertake the analysis)

Small Data Elements


However, if we have a specific case where each data elements are relatively small, then may want to consider wasted space.

If our structure contains "lines", and for example purposes, we estimate "Line" objects average 48 bytes each, then the wasted space (24/48) is almost 50% of the data memory use.

In this case, we would want to do a memory space analysis.





























Data Structures And Algorithms (DSA) (Chapter 304 - Dynamic Array)










Chapter 304 - Dynamic Array Memory Usage

Contents Intro Design Add Grow Insert Remove Access Design-2 Memory

Chapter Top Search TOC