C++ valarray vs. vector

Question

I like vectors a lot. They're nifty and fast. But I know this thing called a valarray exists. Why would I use a valarray instead of a vector? I know valarrays have some syntactic sugar, but other than that, when are they useful?

Sofko

Just was pondering this the other day, too. As far as I know, it's really just as specialized math vector. – Karolynkaron

Doesn't valarray do expression templates? – Pectoralis

Physicist Ulrich Mutze provides a use-case for valarray here and here – Kobayashi

Answer 1

Valarrays (value arrays) are intended to bring some of the speed of Fortran to C++. You wouldn't make a valarray of pointers so the compiler can make assumptions about the code and optimise it better. (The main reason that Fortran is so fast is that there is no pointer type so there can be no pointer aliasing.)

Valarrays also have classes which allow you to slice them up in a reasonably easy way although that part of the standard could use a bit more work. Resizing them is destructive and they lack iterators they have iterators since C++11.

So, if it's numbers you are working with and convenience isn't all that important use valarrays. Otherwise, vectors are just a lot more convenient.

Gurias

They are not designed to avoid pointers. C++11 defines begin() and end() in valarray that return iterators to them – Danford

@user2023370: that's why so many Fortran users prefer Fortran 77. :) – Argilliferous

Answer 2

valarray is kind of an orphan that was born in the wrong place at the wrong time. It's an attempt at optimization, fairly specifically for the machines that were used for heavy-duty math when it was written -- specifically, vector processors like the Crays.

For a vector processor, what you generally wanted to do was apply a single operation to an entire array, then apply the next operation to the entire array, and so on until you'd done everything you needed to do.

Unless you're dealing with fairly small arrays, however, that tends to work poorly with caching. On most modern machines, what you'd generally prefer (to the extent possible) would be to load part of the array, do all the operations on it you're going to, then move on to the next part of the array.

valarray is also supposed to eliminate any possibility of aliasing, which (at least theoretically) lets the compiler improve speed because it's more free to store values in registers. In reality, however, I'm not at all sure that any real implementation takes advantage of this to any significant degree. I suspect it's rather a chicken-and-egg sort of problem -- without compiler support it didn't become popular, and as long as it's not popular, nobody's going to go to the trouble of working on their compiler to support it.

There's also a bewildering (literally) array of ancillary classes to use with valarray. You get slice, slice_array, gslice and gslice_array to play with pieces of a valarray, and make it act like a multi-dimensional array. You also get mask_array to "mask" an operation (e.g. add items in x to y, but only at the positions where z is non-zero). To make more than trivial use of valarray, you have to learn a lot about these ancillary classes, some of which are pretty complex and none of which seems (at least to me) very well documented.

Bottom line: while it has moments of brilliance, and can do some things pretty neatly, there are also some very good reasons that it is (and will almost certainly remain) obscure.

Edit (eight years later, in 2017): Some of the preceding has become obsolete to at least some degree. For one example, Intel has implemented an optimized version of valarray for their compiler. It uses the Intel Integrated Performance Primitives (Intel IPP) to improve performance. Although the exact performance improvement undoubtedly varies, a quick test with simple code shows around a 2:1 improvement in speed, compared to identical code compiled with the "standard" implementation of valarray.

So, while I'm not entirely convinced that C++ programmers will be starting to use valarray in huge numbers, there are least some circumstances in which it can provide a speed improvement.

Taste

Is it specifically disallowed to store arbitrary object types inside valarray? – Jaundiced

@Mehrdad: Yes -- there's a (rather long) list of restrictions at [Numeric.Requirements]. For just a couple examples, all abstract classes and exceptions are prohibited. It also requires equivalence between (for example) copy construction and a sequence of default construction followed by assignment. – Taste

@JerryCoffin sheesh that's scary. we promise that we wont use it. – Charged

I wouldn't decide that based on fear. I'd decide it based on whether you need to store elements that use features it prohibits. – Taste

Truly is amazing how many upvotes you got here. Most of the information is vague and just incorrect. – Tapp

@annoying_squid: If you have more specific and (you believe) accurate information to add, please feel free to add an answer showing it. As it stands right now, your comment doesn't seem to add any useful information though. – Taste

I read similar things, e.g.lacking expression templates and perhaps sbo or fixed size valarray. I hope that the standard committee fixes this thing since in itself there is room for such a specialized container. another wish would be that Visual Studio adds some SSE optimizations for arithmetic operations on valarrays. – Hackle

@gast128: I'd guess most compilers can vectorize (at least some) operations on valarrays. The "problem" is that they can probably do the same vectorizing for similar operations on something like a std::vector just about as well, so there's rarely much efficiency gain from using a valarray. To gain much, somebody's almost certainly going to have to go beyond generic optimizations that apply equally to other code. – Taste

Answer 3

During the standardization of C++98, valarray was designed to allow some sort of fast mathematical computations. However, around that time Todd Veldhuizen invented expression templates and created blitz++, and similar template-meta techniques were invented, which made valarrays pretty much obsolete before the standard was even released. IIRC, the original proposer(s) of valarray abandoned it halfway into the standardization, which (if true) didn't help it either.

ISTR that the main reason it wasn't removed from the standard is that nobody took the time to evaluate the issue thoroughly and write a proposal to remove it.

Please keep in mind, however, that all this is vaguely remembered hearsay. Take this with a grain of salt and hope someone corrects or confirms this.

Chow

expression templates can be equally credited to Vandevoorde too, right ? – Rilda

@Nikos: Not that I know of. I could be wrong, though. What do you have in favor of that reading? – Chow

it's mentioned in the book "C++ Templates - The complete guide", I think it's generally accepted that they both invented them independently. – Rilda

Answer 4

I know valarrays have some syntactic sugar

I have to say that I don't think std::valarrays have much in way of syntactic sugar. The syntax is different, but I wouldn't call the difference "sugar." The API is weird. The section on std::valarrays in The C++ Programming Language mentions this unusual API and the fact that, since std::valarrays are expected to be highly optimized, any error messages you get while using them will probably be non-intuitive.

Out of curiosity, about a year ago I pitted std::valarray against std::vector. I no longer have the code or the precise results (although it shouldn't be hard to write your own). Using GCC I did get a little performance benefit when using std::valarray for simple math, but not for my implementations to calculate standard deviation (and, of course, standard deviation isn't that complex, as far as math goes). I suspect that operations on each item in a large std::vector play better with caches than operations on std::valarrays. (NOTE, following advice from musiphil, I've managed to get almost identical performance from vector and valarray).

In the end, I decided to use std::vector while paying close attention to things like memory allocation and temporary object creation.

---

Both std::vector and std::valarray store the data in a contiguous block. However, they access that data using different patterns, and more importantly, the API for std::valarray encourages different access patterns than the API for std::vector.

For the standard deviation example, at a particular step I needed to find the collection's mean and the difference between each element's value and the mean.

For the std::valarray, I did something like:

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> temp(mean, original_values.size());
std::valarray<double> differences_from_mean = original_values - temp;

I may have been more clever with std::slice or std::gslice. It's been over five years now.

For std::vector, I did something along the lines of:

std::vector<double> original_values = ... // obviously, I put something here
double mean = std::accumulate(original_values.begin(), original_values.end(), 0.0) / original_values.size();

std::vector<double> differences_from_mean;
differences_from_mean.reserve(original_values.size());
std::transform(original_values.begin(), original_values.end(), std::back_inserter(differences_from_mean), std::bind1st(std::minus<double>(), mean));

Today I would certainly write that differently. If nothing else, I would take advantage of C++11 lambdas.

It's obvious that these two snippets of code do different things. For one, the std::vector example doesn't make an intermediate collection like the std::valarray example does. However, I think it's fair to compare them because the differences are tied to the differences between std::vector and std::valarray.

When I wrote this answer, I suspected that subtracting the value of elements from two std::valarrays (last line in the std::valarray example) would be less cache-friendly than the corresponding line in the std::vector example (which happens to also be the last line).

It turns out, however, that

std::valarray<double> original_values = ... // obviously I put something here
double mean = original_values.sum() / original_values.size();
std::valarray<double> differences_from_mean = original_values - mean;

Does the same thing as the std::vector example, and has almost identical performance. In the end, the question is which API you prefer.

Heflin

I cannot think of any reason why a std::vector would play better with caches than a std::valarray; they both allocate a single contiguous block of memory for their elements. – Mccreary

@Mccreary My response got too long for a comment, so I've updated the answer. – Heflin

For your valarray example above, you didn't have to construct a temp valarray object, but you could have just done std::valarray<double> differences_from_mean = original_values - mean;, and then the cache behavior should be similar to that of the vector example. (By the way, if mean is really int, not double, you may need static_cast<double>(mean).) – Mccreary

Thanks for the suggestion to clean up the valarray. I'll need to see if that improves the performance. As for mean being int: that was a mistake. I originally wrote the example up using ints, and then realized that the mean would then be very far from the real mean because of truncation. But I missed a few needed changes on my first round of edits. – Heflin

@Mccreary You're right; that change brought the sample code to almost identical performance. – Heflin

Not sure how this answer got so many upvotes as it essentially conveys no new and important information. The example is overly simplistic and doesn't play to valarrays strength, so drawing conclusions from it is a mistake. – Tapp

Answer 5

valarray was supposed to let some FORTRAN vector-processing goodness rub off on C++. Somehow the necessary compiler support never really happened.

The Josuttis books contains some interesting (somewhat disparaging) commentary on valarray (here and here).

However, Intel now seem to be revisiting valarray in their recent compiler releases (e.g see slide 9); this is an interesting development given that their 4-way SIMD SSE instruction set is about to be joined by 8-way AVX and 16-way Larrabee instructions and in the interests of portability it'll likely be much better to code with an abstraction like valarray than (say) intrinsics.

Stoat

Answer 6

I found one good usage for valarray. It's to use valarray just like numpy arrays.

auto x = linspace(0, 2 * 3.14, 100);
plot(x, sin(x) + sin(3.f * x) / 3.f + sin(5.f * x) / 5.f);

We can implement above with valarray.

valarray<float> linspace(float start, float stop, int size)
{
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + i * (stop-start)/size;
    return v;
}

std::valarray<float> arange(float start, float step, float stop)
{
    int size = (stop - start) / step;
    valarray<float> v(size);
    for(int i=0; i<size; i++) v[i] = start + step * i;
    return v;
}

string psstm(string command)
{//return system call output as string
    string s;
    char tmp[1000];
    FILE* f = popen(command.c_str(), "r");
    while(fgets(tmp, sizeof(tmp), f)) s += tmp;
    pclose(f);
    return s;
}

string plot(const valarray<float>& x, const valarray<float>& y)
{
    int sz = x.size();
    assert(sz == y.size());
    int bytes = sz * sizeof(float) * 2;
    const char* name = "plot1";
    int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    ftruncate(shm_fd, bytes);
    float* ptr = (float*)mmap(0, bytes, PROT_WRITE, MAP_SHARED, shm_fd, 0);
    for(int i=0; i<sz; i++) {
        *ptr++ = x[i];
        *ptr++ = y[i];
    }

    string command = "python plot.py ";
    string s = psstm(command + to_string(sz));
    shm_unlink(name);
    return s;
}

Also, we need python script.

import sys, posix_ipc, os, struct
import matplotlib.pyplot as plt

sz = int(sys.argv[1])
f = posix_ipc.SharedMemory("plot1")
x = [0] * sz
y = [0] * sz
for i in range(sz):
    x[i], y[i] = struct.unpack('ff', os.read(f.fd, 8))
os.close(f.fd)
plt.plot(x, y)
plt.show()

Gustave

I had literally the exact same thoughts as you did when I found out about valarray today at work. I think from now on for math processing problems in c++ I will be using valarray since the code looks way simpler to under stand from a math perspective. – Lying

Answer 7

The C++11 standard says:

The valarray array classes are defined to be free of certain forms of aliasing, thus allowing operations on these classes to be optimized.

See C++11 26.6.1-2.

Instigate

Since I assume the Standard does define which forms, can you quote them? Also, are these implemented using coding tricks, or are they compiler-based exceptions to aliasing rules elsewhere in the language? – Castellated

Answer 8

With std::valarray you can use the standard mathematical notation like v1 = a*v2 + v3 out of the box. This is not possible with vectors unless you define your own operators.

Hoopes

Answer 9

std::valarray is intended for heavy numeric tasks, such as Computational Fluid Dynamics or Computational Structure Dynamics, in which you have arrays with millions, sometimes tens of millions of items, and you iterate over them in a loop with also millions of timesteps. Maybe today std::vector has a comparable performance but, some 15 years ago, valarray was almost mandatory if you wanted to write an efficient numeric solver.

Cucullate

Answer 10

Basically std::valarray are vectors in a more mathematical sense that allow well defined mathematical operations like c = a + b, while std::vector are dynamic arrays. The names are just misleading.

In a vector the dimension is fixed and all its elements are restricted to variables that allow arithmetic operations and if you create one with apples, the compiler will immediately complains that apples are not variables that support arithmetic operations.

Also, mathematical functions like sqrt(), log(), sin(), etc. accept vectors as input and perform the operation to each element, which is great for architectures Single Instruction Multiple Data with a very large number of cores. For example, GPUs are very good working with vectors.

This is why a vector can have a much more complex memory structure. Its elements can be distributed along several nodes, while std::vector is basically a container with a pointer to a continuous memory.

And I still see people trying to use std::vector with CUDA. No sorry, despite the misleading name, you can't use std::vector because it is not a vector. I know, they recognize it was a historical error, but they haven't even tried to correct that mistake.

Lubin