C ++ valarray vs. vector

Question

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

Answer 1

Valarrays (arrays de valores) tienen la intención de llevar algo de la velocidad de Fortran a C ++. No haría un conjunto 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 un tipo de puntero, por lo que no puede haber alias de punteros).

Valarrays también tiene clases que le permiten dividirlos de una manera bastante fácil, aunque esa parte de la norma podría requerir un poco más de trabajo. Cambiar su tamaño es destructivo y carecen de iteradores.

Por lo tanto, si se trata de números con los que está trabajando y la conveniencia, no es tan importante utilizar vallas de seguridad. De lo contrario, los vectores son mucho más convenientes.

Answer 2

valarray es una especie de huérfano que nació en el lugar equivocado en el momento equivocado. Es un intento de optimización, bastante específicamente para las máquinas que se utilizaron para las matemáticas de uso pesado cuando se escribió, específicamente, 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 arreglos bastante pequeños, esto 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 a las que va a ir, y luego pasar a la siguiente parte de la matriz. / p>

valarray también se supone que elimina cualquier posibilidad de alias, lo que (al menos en teoría) le permite al compilador mejorar la velocidad porque es más libre para almacenar valores en los registros. En realidad, sin embargo, no estoy seguro de que ninguna implementación real aproveche esto en un grado significativo. Sospecho que es más bien una especie de problema de la gallina y el huevo: 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 variedad desconcertante (literalmente) de clases auxiliares para usar con valarray. Obtiene slice , slice_array , gslice y gslice_array para jugar con piezas de un valarray , y hacer que actúe como una matriz multidimensional. También obtiene mask_array para " mask " una operación (por ejemplo, agregar elementos en x a y, pero solo en las posiciones donde z no es cero). Para hacer más que un uso trivial de valarray , tienes que 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.

Conclusión: si bien tiene momentos de brillantez y puede hacer algunas cosas bastante bien, también hay algunas buenas razones por las que es (y casi seguro que seguirá siendo) oscuro.

Editar (ocho años después, en 2017): parte de lo anterior se ha vuelto obsoleto hasta cierto punto. Por ejemplo, Intel ha implementado una versión optimizada de valarray para su compilador. Utiliza Intel Integrated Performance Primitives (Intel IPP) para mejorar el rendimiento. Aunque la mejora exacta del rendimiento sin duda varía, una prueba rápida con código simple muestra una mejora en la velocidad de 2: 1, en comparación con el código idéntico compilado con el " estándar " implementación de valarray .

Entonces, aunque no estoy completamente convencido de que los programadores de C ++ comenzarán a utilizar valarray en grandes cantidades, hay algunas circunstancias en las que puede proporcionar una mejora de la velocidad.

Answer 3

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, alrededor de ese tiempo, Todd Veldhuizen inventó plantillas de expresión y creó blitz ++ , y se inventaron técnicas similares de plantilla-meta. , lo que hizo que los valarrays fueran bastante obsoletos incluso antes de que el estándar fuera lanzado. IIRC, el (los) proponente (s) original (es) de valarray lo abandonó a la mitad de la estandarización, lo cual (si es cierto) tampoco lo ayudó.

ISTR que la razón principal por la que no se eliminó de la norma es que nadie se tomó el tiempo de evaluar el problema a fondo y escribir una propuesta para eliminarlo.

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

Answer 4

  

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

Tengo que decir que no creo que std :: valarrays tenga mucho azúcar sintáctico. La sintaxis es diferente, pero yo no llamaría la diferencia "azúcar". La API es rara. La sección sobre std :: valarray s en The C ++ Programming Language menciona esta API inusual y el hecho de que, desde std :: valarray s son Se espera que esté altamente optimizado, cualquier mensaje de error que recibas al usarlos probablemente no sea intuitivo.

Por curiosidad, hace aproximadamente un año enfrenté a std :: valarray contra std :: vector . Ya no tengo el código ni los resultados precisos (aunque no debería ser difícil escribir el tuyo). Al usar GCC, obtuve un pequeño beneficio de rendimiento al usar std :: valarray para matemáticas simples, pero no para mis implementaciones para calcular la desviación estándar (y, por supuesto, la desviación estándar no es tan complejo, en lo que se refiere a las matemáticas). Sospecho que las operaciones en cada elemento en un gran std :: vector se juegan mejor con cachés que las operaciones en std :: valarray s. (< strong> NOTA , siguiendo los consejos de musiphil , he logrado obtener un rendimiento casi idéntico de vector y valarray ).

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

---

Tanto std :: vector como std :: valarray almacenan los datos en un bloque contiguo. Sin embargo, acceden a esos datos utilizando diferentes patrones y, lo que es más importante, la API para std :: valarray fomenta diferentes patrones de acceso que la API para std :: vector .

Para el ejemplo de desviación estándar, en un paso en 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 :: slice o std :: gslice . Han pasado más de cinco años.

Para std :: vector , hice algo como:

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, me gustaría aprovechar las lambdas C ++ 11.

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

Cuando escribí esta respuesta, sospeché que restar el valor de los elementos de dos std :: valarray s (última línea en el ejemplo de std :: valarray ) sea ??menos amigable con la memoria caché que la línea correspondiente en el ejemplo de std :: vector (que también es la última línea).

Sin embargo, resulta 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 ejemplo std :: vector , y tiene un rendimiento casi idéntico. Al final, la pregunta es qué API prefieres.

Answer 5

se suponía que valarray permitía que algo de bondad de procesamiento de vectores de FORTRAN se borrara de C ++. De alguna manera, el soporte necesario del compilador nunca sucedió realmente.

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

Sin embargo, parece que Intel ahora está revisando valarray en sus recientes versiones del compilador (por ejemplo, vea diapositiva 9 ); este es un desarrollo interesante dado que su conjunto de instrucciones SIMD SSE de 4 vías está a punto de unirse a las 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.

Answer 6

Encontré un buen uso para valarray. Es para usar valarray como 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;
}

También necesitamos scripts 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()

Answer 7

El estándar C ++ 11 dice:

  

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

Ver C ++ 11 26.6.1-2.

Answer 8

std :: valarray está diseñado para tareas numéricas pesadas, como Dinámica de fluidos computacional o Dinámica de estructuras computacionales, en las que tiene arreglos con millones, a veces decenas de millones de elementos, y los itera en un circuito con millones también. de pasos de tiempo. Quizás hoy std :: vector tenga un rendimiento comparable pero, hace unos 15 años, valarray era casi obligatorio si quería escribir un solucionador numérico eficiente.