ChatGPT解决这个技术问题 Extra ChatGPT

C++ valarray vs. vector

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?

Just was pondering this the other day, too. As far as I know, it's really just as specialized math vector.
Doesn't valarray do expression templates?
Physicist Ulrich Mutze provides a use-case for valarray here and here

J
Jerry Coffin

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.


Is it specifically disallowed to store arbitrary object types inside valarray?
@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.
@JerryCoffin sheesh that's scary. we promise that we wont use it.
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.
@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.
Z
ZachB

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.


They are not designed to avoid pointers. C++11 defines begin() and end() in valarray that return iterators to them
@user2023370: that's why so many Fortran users prefer Fortran 77. :)
a
admo

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.


expression templates can be equally credited to Vandevoorde too, right ?
@Nikos: Not that I know of. I could be wrong, though. What do you have in favor of that reading?
it's mentioned in the book "C++ Templates - The complete guide", I think it's generally accepted that they both invented them independently.
M
Max Lybbert

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.


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.
@musiphil My response got too long for a comment, so I've updated the answer.
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).)
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.
@musiphil You're right; that change brought the sample code to almost identical performance.
t
timday

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.


Z
Zeta

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);

https://i.stack.imgur.com/Q799S.png

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()

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.
L
Lingxi

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.


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?
P
Paul Jurczak

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.


m
mrpivello

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.