C ++ valarray против вектора - PullRequest
       95

C ++ valarray против вектора

148 голосов
/ 21 октября 2009

Мне очень нравятся векторы. Они изящны и быстры. Но я знаю, что существует то, что называется valarray. Зачем мне использовать valarray вместо вектора? Я знаю, что у valarrays есть некоторый синтаксический сахар, но кроме этого, когда они полезны?

Ответы [ 7 ]

141 голосов
/ 21 октября 2009

valarray - это вид сироты, которая родилась не в то время и не в том месте. Это попытка оптимизации, особенно для машин, которые использовались для тяжелой математики, когда она была написана, в частности, для векторных процессоров, таких как Crays.

Для векторного процессора вы обычно хотели применить одну операцию ко всему массиву, затем применить следующую операцию ко всему массиву и так далее, пока вы не сделаете все, что вам нужно сделать.

Однако, если вы не имеете дело с довольно маленькими массивами, это плохо работает с кэшированием. На большинстве современных машин вы, как правило, предпочитаете (насколько это возможно) загружать часть массива, выполнять на нем все необходимые операции, а затем переходить к следующей части массива.

valarray также должен исключить любую возможность наложения псевдонимов, что (по крайней мере, теоретически) позволяет компилятору повысить скорость, поскольку он более свободен для хранения значений в регистрах. В действительности, однако, я совсем не уверен, что любая реальная реализация в значительной степени использует это в своих интересах. Я подозреваю, что это скорее проблема типа «курица и яйцо» - без поддержки компилятора она не стала бы популярной, и пока она не популярна, никто не собирается работать над своим компилятором, чтобы поддержать ее.

Существует также изумительный (буквально) массив вспомогательных классов, которые можно использовать с valarray. Вы получаете slice, slice_array, gslice и gslice_array, чтобы играть с частями valarray, и заставить его действовать как многомерный массив. Вы также получаете mask_array для «маскировки» операции (например, добавьте элементы от x до y, но только в тех местах, где z не равен нулю). Для более чем тривиального использования valarray вы должны многое узнать об этих вспомогательных классах, некоторые из которых довольно сложны, и ни один из них не кажется (по крайней мере мне) очень хорошо задокументированным.

Итог: хотя в нем есть моменты блеска, и он может делать некоторые вещи довольно аккуратно, есть также несколько очень веских причин, по которым он (и почти наверняка останется) неясным.

Редактировать (восемь лет спустя, в 2017 году): Некоторые из предыдущих устарели, по крайней мере, до некоторой степени. Например, Intel внедрила оптимизированную версию valarray для своего компилятора. Он использует Intel Integrated Performance Primitives (Intel IPP) для повышения производительности. Хотя точное улучшение производительности, несомненно, варьируется, быстрый тест с простым кодом показывает увеличение скорости примерно в 2: 1 по сравнению с идентичным кодом, скомпилированным со «стандартной» реализацией valarray.

Итак, хотя я не совсем убежден, что программисты на C ++ начнут использовать valarray в огромных количествах, есть, по крайней мере, некоторые обстоятельства, в которых это может обеспечить повышение скорости.

65 голосов
/ 21 октября 2009

Valarrays (массивы значений) предназначены для переноса части скорости Fortran в C ++. Вы не сделаете множество указателей, чтобы компилятор мог делать предположения о коде и лучше его оптимизировать. (Основная причина того, что Fortran такой быстрый, заключается в том, что нет типа указателя, поэтому не может быть псевдонима для указателя.)

В Valarrays также есть классы, которые позволяют достаточно легко их нарезать, хотя в этой части стандарта может потребоваться немного больше работы. Изменение их размера разрушительно, и им не хватает итераторов.

Итак, если вы работаете с числами, а удобство не так уж важно, используйте значения. В противном случае векторы намного удобнее.

38 голосов
/ 21 октября 2009

Во время стандартизации C ++ 98, valarray был разработан, чтобы позволить некоторые виды быстрых математических вычислений. Однако примерно в то же время Тодд Вельдхуйзен изобрел шаблоны выражений и создал blitz ++ , и были изобретены аналогичные методы метаданных шаблонов, что сделало valarra-ы практически устаревшими еще до выпуска стандарта. IIRC, первоначальный разработчик (и) valarray, оставил его на полпути к стандартизации, что (если верно) также не помогло.

ISTR, что главная причина, по которой он не был удален из стандарта, заключается в том, что никто не нашел время тщательно оценить проблему и написать предложение по ее устранению.

Имейте в виду, однако, что все это смутно запоминается слухами. Возьмите это с крошкой соли и надейтесь, что кто-то исправит или подтвердит это.

26 голосов
/ 21 октября 2009

Я знаю, у valarrays есть синтаксический сахар

Я должен сказать, что не думаю, что std::valarrays имеет много синтаксического сахара. Синтаксис другой, но я бы не назвал разницу "сахар". API странный. В разделе std::valarray s на языке программирования C ++ упоминается этот необычный API и тот факт, что, поскольку ожидается, что std::valarray s будет высоко оптимизирован, любые сообщения об ошибках, которые вы получите при их использовании, вероятно, будут не-интуитивный.

Из любопытства около года назад я противопоставил std::valarray против std::vector. У меня больше нет кода или точных результатов (хотя это не должно быть трудно написать свой собственный). Использование GCC I принесло небольшой выигрыш в производительности при использовании std::valarray для простой математики, но не для моих реализаций для расчета стандартного отклонения (и, конечно, стандартное отклонение не так сложно, насколько математика идет) Я подозреваю, что операции с каждым элементом в большом std::vector лучше работают с кэшами, чем операции с std::valarray с. ( NOTE , следуя советам musiphil Мне удалось получить почти одинаковую производительность от vector и valarray).

В конце концов, я решил использовать std::vector, уделяя пристальное внимание таким вещам, как выделение памяти и создание временных объектов.


И std::vector, и std::valarray хранят данные в непрерывном блоке. Однако они получают доступ к этим данным, используя разные шаблоны, и, что более важно, API для std::valarray поддерживает другие шаблоны доступа, чем API для std::vector.

Для примера стандартного отклонения на конкретном этапе мне нужно было найти среднее значение для коллекции и разницу между значением каждого элемента и средним значением.

Для std::valarray я сделал что-то вроде:

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;

Возможно, я был умнее с std::slice или std::gslice. Прошло уже более пяти лет.

Для std::vector я сделал что-то вроде:

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

Сегодня я бы, конечно, написал это по-другому. Если бы не что иное, я бы воспользовался лямбдами C ++ 11.

Очевидно, что эти два фрагмента кода делают разные вещи. Например, пример std::vector не создает промежуточную коллекцию, как пример std::valarray. Тем не менее, я думаю, что было бы справедливо сравнивать их, потому что различия связаны с различиями между std::vector и std::valarray.

Когда я писал этот ответ, я подозревал, что вычитание значений элементов из двух std::valarray s (последняя строка в примере std::valarray) будет менее дружественным к кэшу, чем соответствующая строка в примере std::vector ( что также является последней строкой).

Оказывается, однако, что

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;

Делает то же самое, что и пример std::vector, и имеет почти идентичную производительность. В конце концов, вопрос в том, какой API вы предпочитаете.

23 голосов
/ 21 октября 2009

valarray должен был позволить чему-то хорошему в векторной обработке FORTRAN на C ++. Каким-то образом необходимой поддержки компилятора никогда не было.

Книги Josuttis содержат несколько интересных (несколько уничижительных) комментариев о valarray ( здесь и здесь ).

Однако теперь Intel, похоже, пересматривает valarray в своих последних выпусках компилятора (например, см. slide 9 ); это интересная разработка, учитывая, что их набор инструкций SIMD SSE с 4 путями собирается соединиться с инструкциями AVX с 8 путями и инструкциями Larrabee с 16 путями, и в интересах переносимости, вероятно, будет намного лучше кодировать с такой абстракцией, как valarray чем (скажем) свойственные.

13 голосов
/ 11 июня 2017

Я нашел одно хорошее применение для valarray. Это использовать valarray, как массивы numpy.

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

enter image description here

Мы можем реализовать выше с 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;
}

Также нам нужен скрипт на python.

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()
7 голосов
/ 17 мая 2012

Стандарт C ++ 11 гласит:

Классы массивов valarray определены как свободные от определенных форм алиасинг, что позволяет оптимизировать операции над этими классами.

См. C ++ 11 26.6.1-2.

...