Virtual Arrays

A virtual array (source) is a data structure that behaves similarly to an array, but its elements are accessed through virtual methods. This improves the decoupling of a function from its callers, because it does not have to know exactly how the data is laid out in memory, or if it is stored in memory at all. It could just as well be computed on the fly.

Taking a virtual array as parameter instead of a more specific non-virtual type has some tradeoffs. Access to individual elements is slower due to function call overhead. On the other hand, potential callers don't have to convert the data into the specific format required for the function. That can be a costly conversion if only few of the elements are accessed in the end.

Functions taking a virtual array as input can still optimize for different data layouts. For example, they can check if the array references contiguous memory internally or if it is the same value for all indices. Whether it is worth optimizing for different data layouts in a function has to be decided on a case by case basis. One should always do some benchmarking to see if the increased compile time and binary size is worth it.

/* Create an empty virtual array. */
VArray<int> values;

/* Create a virtual array that has the same value at every index. */
VArray<int> values = VArray<int>::ForSingle(value, num_values);

/* Create a virtual array that references a span. */
VArray<int> values = VArray<int>::ForSpan(int_span);

/* Create a virtual array where the value at each index is twice the index. */
VArray<int> values = VArray<int>::ForFunc(
    num_values, [](const int64_t i) { return i * 2; });

/* Get the value at a specific index. */
int value = values[5];

/* Optimize for the case when the virtual array contains a single value. */
if (const std::optional<int> value = values.get_if_single()) {
  /* Handle the case when all values are the same. */
}
else {
  /* Handle the general case whenvalues may be all different. */
}

/* Automatically generate a function multiple times for different data layouts. */
devirtualize_varray(values, [&](auto values) {
  /* The code in this lambda is optimized for three possible variants. */
  /* `values` can be a Span, a SingleAsSpan or a VArrayRef. */
});