C ++ valarray vs. vector

Me gustan mucho los vectores. Son ingeniosos y rápidos. Pero sé que existe esta cosa llamada valarray. ¿Por qué usaría un valarray en lugar de un vector? Sé que los valarrays tienen algo de azúcar sintáctica, pero aparte de eso, ¿cuándo son útiles?

Los Valarrays (matrices de valores) están destinados a llevar algo de la velocidad de Fortran a C ++. No haría una gran variedad de punteros para que el compilador pueda hacer suposiciones sobre el código y optimizarlo mejor. (La razón principal por la que Fortran es tan rápido es que no hay ningún tipo de puntero, por lo que no puede haber alias de puntero).

Los Valarrays también tienen clases que le permiten dividirlos de una manera razonablemente fácil, aunque esa parte del estándar podría necesitar un poco más de trabajo. Cambiar su tamaño es destructivo y carecen de iteradores.

Entonces, si se trata de números con los que está trabajando y la conveniencia no es tan importante, use valarrays. De lo contrario, los vectores son mucho más convenientes.

valarrayes una especie de huérfano que nació en el lugar equivocado en el momento equivocado. Es un intento de optimización, bastante específico para las máquinas que se utilizaron para las matemáticas pesadas cuando se escribió, específicamente, los procesadores vectoriales como los Crays.

Para un procesador vectorial, lo que generalmente quería hacer era aplicar una sola operación a una matriz completa, luego aplicar la siguiente operación a toda la matriz, y así sucesivamente hasta que haya hecho todo lo que tenía que hacer.

Sin embargo, a menos que se trate de matrices bastante pequeñas, eso tiende a funcionar mal con el almacenamiento en caché. En la mayoría de las máquinas modernas, lo que generalmente preferiría (en la medida de lo posible) sería cargar parte de la matriz, realizar todas las operaciones que vaya a realizar y luego pasar a la siguiente parte de la matriz.

valarraytambién se supone que elimina cualquier posibilidad de alias, lo que (al menos en teoría) permite que el compilador mejore la velocidad porque es más libre de almacenar valores en los registros. En realidad, sin embargo, no estoy del todo seguro de que una implementación real aproveche esto en un grado significativo. Sospecho que es más bien un problema de huevo y gallina: sin el soporte del compilador no se hizo popular, y mientras no sea popular, nadie se tomará la molestia de trabajar en su compilador para soportarlo.

También hay una desconcertante (literalmente) variedad de clases auxiliares para usar con valarray. Se obtiene slice, slice_array, gslicey gslice_arrayjugar con las piezas de un valarray, y hacerlo actuar como una matriz multidimensional. También puede mask_array"enmascarar" una operación (por ejemplo, agregar elementos en xay, pero solo en las posiciones donde z no es cero). Para hacer un uso más que trivial valarray, debe aprender mucho sobre estas clases auxiliares, algunas de las cuales son bastante complejas y ninguna de las cuales parece (al menos para mí) muy bien documentada.

En pocas palabras: si bien tiene momentos de brillantez y puede hacer algunas cosas de manera bastante ordenada, también hay algunas muy buenas razones por las que es (y seguramente seguirá siendo) oscuro.

Editar (ocho años después, en 2017): algunas de las anteriores se han vuelto obsoletas al menos en algún grado. Por ejemplo, Intel ha implementado una versión optimizada de valarray para su compilador. Utiliza las primitivas de rendimiento integrado de Intel (Intel IPP) para mejorar el rendimiento. Aunque la mejora exacta del rendimiento varía indudablemente, una prueba rápida con código simple muestra una mejora de velocidad de 2: 1, en comparación con el código idéntico compilado con la implementación "estándar" de valarray.

Entonces, aunque no estoy completamente convencido de que los programadores de C ++ comenzarán a usar valarrayen grandes cantidades, existen al menos algunas circunstancias en las que puede proporcionar una mejora de la velocidad.

Durante la estandarización de C ++ 98, valarray fue diseñado para permitir algún tipo de cálculos matemáticos rápidos. Sin embargo, por esa época, Todd Veldhuizen inventó plantillas de expresión y creó blitz ++ , y se inventaron técnicas similares de meta-plantillas, que hicieron que los valarrays fueran bastante obsoletos incluso antes de que se lanzara el estándar. IIRC, los proponentes originales de valarray lo abandonaron a mitad de camino de la estandarización, lo que (si es cierto) tampoco lo ayudó.

ISTR dice que la razón principal por la que no se eliminó del estándar es que nadie se tomó el tiempo para evaluar el problema a fondo y escribir una propuesta para eliminarlo.

Sin embargo, tenga en cuenta que todo esto se recuerda vagamente por rumores. Tome esto con un grano de sal y espere que alguien corrija o confirme esto.

Sé que los valarrays tienen algo de azúcar sintáctica

Tengo que decir que no creo que std::valarraystenga mucho azúcar sintáctico. La sintaxis es diferente, pero no llamaría a la diferencia "azúcar". La API es rara. La sección sobre std::valarrays en The C ++ Programming Language menciona esta API inusual y el hecho de que, dado que std::valarrayse espera que los s estén altamente optimizados, cualquier mensaje de error que reciba mientras los usa probablemente no sea intuitivo.

Por curiosidad, hace aproximadamente un año Entré en boxes std::valarrayen contra std::vector. Ya no tengo el código o los resultados precisos (aunque no debería ser difícil escribir el tuyo). El uso de GCC Me hice un poco beneficio en el rendimiento cuando se utilizan std::valarraypara operaciones matemáticas sencillas, pero no para mis implementaciones para calcular la desviación estándar (y, por supuesto, la desviación estándar no es tan compleja, en lo que va de matemáticas). Sospecho que las operaciones en cada elemento en un std::vectorjuego grande funcionan mejor con cachés que las operaciones en std::valarrays. ( NOTA , siguiendo los consejos de musiphil , he logrado obtener un rendimiento casi idéntico de vectory valarray).

Al final, decidí usarlo std::vectormientras prestaba mucha atención a cosas como la asignación de memoria y la creación de objetos temporales.

Ambos std::vectory std::valarrayalmacenan los datos en un bloque contiguo. Sin embargo, acceden a esos datos utilizando diferentes patrones y, lo que es más importante, la API std::valarrayfomenta diferentes patrones de acceso que la API std::vector.

Para el ejemplo de la desviación estándar, en un paso particular necesitaba encontrar la media de la colección y la diferencia entre el valor de cada elemento y la media.

Para el std::valarray, hice algo como:

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;

Puede que haya sido más inteligente con std::sliceo std::gslice. Han pasado más de cinco años.

Para std::vector, hice algo en la línea de:

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

Hoy ciertamente escribiría eso de manera diferente. Si nada más, aprovecharía C ++ 11 lambdas.

Es obvio que estos dos fragmentos de código hacen cosas diferentes. Por un lado, el std::vectorejemplo no hace una colección intermedia como lo hace el std::valarrayejemplo. Sin embargo, creo que es justo compararlos porque las diferencias están vinculadas a las diferencias entre std::vectory std::valarray.

Cuando escribí esta respuesta, sospeché que restar el valor de los elementos de dos std::valarrays (última línea en el std::valarrayejemplo) sería menos amigable con el caché que la línea correspondiente en el std::vectorejemplo (que también es la última línea).

Resulta, sin embargo, que

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;

Hace lo mismo que el std::vectorejemplo y tiene un rendimiento casi idéntico. Al final, la pregunta es qué API prefieres.

Se suponía que valarray debía dejar que algo de la calidad del procesamiento de vectores FORTRAN se contagiara en C ++. De alguna manera, el soporte necesario del compilador nunca sucedió realmente.

Los libros de Josuttis contienen algunos comentarios interesantes (algo despectivos) sobre valarray ( aquí y aquí ).

Sin embargo, Intel ahora parece estar revisando valarray en sus recientes versiones del compilador (por ejemplo, vea la diapositiva 9 ); este es un desarrollo interesante dado que su conjunto de instrucciones SIMD SSE de 4 vías está a punto de unirse con instrucciones AVX de 8 vías y Larrabee de 16 vías y en aras de la portabilidad, probablemente sea mucho mejor codificar con una abstracción como valarray que (digamos) intrínsecos.

Encontré un buen uso para valarray. Es usar valarray al igual que matrices 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);

Podemos implementar lo anterior con 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;
}

Además, necesitamos un script de 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()

El estándar C ++ 11 dice:

Las clases de matriz valarray se definen libres de ciertas formas de alias, lo que permite optimizar las operaciones en estas clases.

Ver C ++ 11 26.6.1-2.

Con std::valarrayusted puede usar la notación matemática estándar como lista para usar v1 = a*v2 + v3. Esto no es posible con vectores a menos que defina sus propios operadores.

std :: valarray está destinado a tareas numéricas pesadas, como la dinámica de fluidos computacional o la dinámica de estructura computacional, en las que tiene matrices con millones, a veces decenas de millones de elementos, y las itera en un bucle con millones de pasos. Tal vez hoy std :: vector tenga un rendimiento comparable, pero, hace unos 15 años, valarray era casi obligatorio si deseaba escribir un solucionador numérico eficiente.