What is a Shadow Array

Question

What is a shadow array and how is it implemented? I came through the term while reading about compiler optimizations but I couldn't find any substantial reference about it.

Answer 1

When using arrays to implement dynamically resizable abstract data types, such as a List, Queue or Stack, the obvious problem that one encounters is that arrays are not themselves freely resized. At some point, then, if one adds enough items to an array, one will eventually run out of space.

The naive solution to this problem is to wait until the array being used runs out of space and then create a new larger array, copy all of the items from the old array into the new array, and the start using the new array.

A shadow array using implementation of an abstract data type is an alternative to this. Instead of waiting until the old array is full, a second, larger array is created after some threshold of fullness is passed on the array that's being used. Thereafter, as items are added to the old array, multiple items are copied from the old array to the shadow array, such that when the old array is full, all of it's items have already been copied to the new array.

The advantage of using a shadow array implementation instead of the naive "copy everything at the end" approach is that the time required by each add operation is much more consistent.

Answer 2

I think of it as a form of dynamic array.

The term shadow would referr to the underlying algorithms that try to resize it with good performance but are hidden behind an easy interface. (For example ArrayList in Java)