arrays - valor - ¿Los vectores de indexación en MATLAB son ineficaces?

posicion de un valor en un vector matlab

Question

Fondo

Mi pregunta está motivada por observaciones simples, que de alguna manera socavan las creencias / suposiciones que a menudo tienen los usuarios experimentados de MATLAB:

• MATLAB está muy bien optimizado en lo que respecta a las funciones incorporadas y las características fundamentales del lenguaje, como los vectores de indexación y las matrices.
• Los bucles en MATLAB son lentos (a pesar del JIT) y, en general, deben evitarse si el algoritmo se puede expresar de forma nativa y "vectorizada".

La conclusión: la funcionalidad central de MATLAB es eficiente y tratar de superarla usando el código MATLAB es difícil, si no imposible.

Investigar el rendimiento de la indexación vectorial

Los códigos de ejemplo que se muestran a continuación son tan fundamentales como es posible: asigno un valor escalar a todas las entradas de vectores. Primero, asigno un vector vacío x :

tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.

Tener x me gustaría establecer todas sus entradas al mismo valor. En la práctica, lo haría de manera diferente, por ejemplo, x = value*ones(1e8,1) , pero el punto aquí es investigar el rendimiento de la indexación vectorial. La forma más simple es escribir:

tic; x(:) = 1; toc
Elapsed time is 0.094316 seconds.

Vamos a llamarlo método 1 (del valor asignado a x ). Parece ser muy rápido (más rápido al menos que la asignación de memoria). Como lo único que hago aquí es operar en la memoria, puedo estimar la eficiencia de este código calculando el ancho de banda efectivo de memoria obtenido y comparándolo con el ancho de banda de la memoria de hardware de mi computadora:

eff_bandwidth = numel(x) * 8 bytes per double * 2 / time

En lo anterior, multiplico por 2 porque a menos que se use la transmisión SSE, establecer valores en la memoria requiere que el vector se lea y se escriba en la memoria. En el ejemplo anterior:

eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s

El ancho de banda de memoria de STREAM-benchmarked de mi computadora es de alrededor de 17.9 Gb / s, así que de hecho, ¡MATLAB ofrece un rendimiento cercano al máximo en este caso! Hasta aquí todo bien.

El Método 1 es adecuado si desea establecer todos los elementos vector a algún valor. Pero si desea acceder a los elementos en cada step entradas, debe sustituir el : por ejemplo, 1:step:end . A continuación se muestra una comparación de velocidad directa con el método 1:

tic; x(1:end) = 2; toc
Elapsed time is 0.496476 seconds.

Si bien no esperarías que funcionara de manera diferente, el método 2 es claramente un gran problema: la ralentización del factor 5 no tiene ninguna razón. Mi sospecha es que en este caso MATLAB asigna explícitamente el vector de índice ( 1:end ). Esto se confirma de alguna manera mediante el uso de un tamaño de vector explícito en lugar de un end :

tic; x(1:1e8) = 3; toc
Elapsed time is 0.482083 seconds.

Los métodos 2 y 3 funcionan igual de mal.

Otra posibilidad es crear explícitamente una id índice vectorial y usarla para indexar x . Esto le brinda las capacidades de indexación más flexibles. En nuestro caso:

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
Elapsed time is 1.208419 seconds.

Ahora eso es realmente algo: ¡12 veces más lento que el método 1! Entiendo que debería funcionar peor que el método 1 debido a la memoria adicional utilizada para la id , pero ¿por qué es mucho peor que los métodos 2 y 3?

Tratemos de probar los bucles, por desesperado que parezca.

tic;
for i=1:numel(x)
    x(i) = 5;
end
toc
Elapsed time is 0.788944 seconds.

Una gran sorpresa: un ciclo supera un método vectorized 4, pero aún es más lento que los métodos 1, 2 y 3. Resulta que en este caso particular puedes hacerlo mejor:

tic;
for i=1:1e8
    x(i) = 6;
end
toc
Elapsed time is 0.321246 seconds.

Y ese es probablemente el resultado más extraño de este estudio: un ciclo escrito por MATLAB significativamente supera el índice de vectores nativos . Eso ciertamente no debería ser así. Tenga en cuenta que el ciclo JIT sigue siendo 3 veces más lento que el pico teórico casi obtenido por el método 1. Por lo tanto, todavía hay mucho margen de mejora. Es simplemente sorprendente (una palabra más fuerte sería más adecuada) que la indexación "vectorizada" habitual ( 1:end ) es aún más lenta.

Preguntas

• ¿Es la indexación simple en MATLAB muy ineficiente (los métodos 2, 3 y 4 son más lentos que el método 1) o me perdí algo?
• ¿Por qué el método 4 (mucho) es más lento que los métodos 2 y 3?
• ¿Por qué el uso de 1e8 lugar de numel(x) como un lazo enlazado acelera el código por el factor 2?

Editar Después de leer el comentario de Jonas, aquí hay otra forma de hacerlo usando índices lógicos:

tic;
id = logical(ones(1, 1e8));
x(id) = 7;
toc
Elapsed time is 0.613363 seconds.

Mucho mejor que el método 4.

Por conveniencia:

function test

tic; x = zeros(1,1e8); toc

tic; x(:) = 1; toc
tic; x(1:end) = 2; toc
tic; x(1:1e8) = 3; toc

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc

tic;
for i=1:numel(x)
    x(i) = 5;
end
toc

tic;
for i=1:1e8
    x(i) = 6;
end
toc

end

Answer 1

No tengo una respuesta para todos los problemas, pero tengo algunas especulaciones refinadas sobre los métodos 2, 3 y 4.

En cuanto a los métodos 2 y 3. Parece que MATLAB asigna memoria para los índices de vectores y la llena con valores de 1 a 1e8 . Para entenderlo, veamos qué está pasando. Por defecto, MATLAB usa el double como su tipo de datos. La asignación de la matriz de índice lleva el mismo tiempo que la asignación de x

tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.

Por ahora, la matriz de índice contiene solo ceros. La asignación de valores al vector x de una manera óptima, como en el método 1, toma 0.094316 segundos. Ahora, el vector de índice debe leerse en la memoria para que pueda usarse en la indexación. Eso es 0.094316/2 segundos adicionales. Recuerde que en x(:)=1 vector x tiene que leerse y escribirse en la memoria. Entonces solo leerlo toma la mitad del tiempo. Suponiendo que esto es todo lo que se hace en x(1:end)=value , el tiempo total de los métodos 2 y 3 debe ser

t = 0.260525+0.094316+0.094316/2 = 0.402

Es casi correcto, pero no del todo. Solo puedo especular, pero llenar el vector de índice con valores probablemente se hace como un paso adicional y toma 0.094316 segundos adicionales. Por lo tanto, t=0.4963 , que más o menos se ajusta al tiempo de los métodos 2 y 3.

Estas son solo especulaciones, pero parecen confirmar que MATLAB crea explícitamente vectores de índice al hacer indexación vectorial nativa. Personalmente, considero que esto es un error de rendimiento. El compilador JIT de MATLAB debe ser lo suficientemente inteligente como para entender esta construcción trivial y convertirla en una llamada a una función interna correcta. Tal como está ahora, en la memoria de hoy la indexación de las arquitecturas limitadas de ancho de banda realiza alrededor del 20% de pico teórico.

Entonces, si le importa el rendimiento, tendrá que implementar x(1:step:end) como una función MEX, algo así como

set_value(x, 1, step, 1e8, value);

Ahora esto es claramente ilegal en MATLAB, ya que NO ESTÁ PERMITIDO modificar las matrices en los archivos MEX en el lugar.

Editar Con respecto al método 4, se puede tratar de analizar el rendimiento de los pasos individuales de la siguiente manera:

tic;
id = 1:1e8; % colon(1,1e8);
toc
tic
x(id) = 4;
toc

Elapsed time is 0.475243 seconds.
Elapsed time is 0.763450 seconds.

El primer paso, la asignación y el llenado de los valores del vector de índice toma el mismo tiempo que los métodos 2 y 3 solos. Parece que es demasiado, debería tomar como máximo el tiempo necesario para asignar la memoria y establecer los valores ( 0.260525s+0.094316s = 0.3548s ), por lo que hay una sobrecarga adicional de 0.12 segundos en algún lugar, lo que no entiendo. La segunda parte ( x(id) = 4 ) también parece muy ineficiente: debería tomarse el tiempo necesario para establecer los valores de x , y para leer el vector de id ( 0.094316s+0.094316/2s = 0.1415s ) más algunas comprobaciones de error en los valores de id . Programado en C, los dos pasos toman:

create id                              0.214259
x(id) = 4                              0.219768

El código utilizado comprueba que, de hecho, un índice double representa un número entero y que se ajusta al tamaño de x :

tic();
id  = malloc(sizeof(double)*n);
for(i=0; i<n; i++) id[i] = i;
toc("create id");

tic();
for(i=0; i<n; i++) {
  long iid = (long)id[i];
  if(iid>=0 && iid<n && (double)iid==id[i]){
    x[iid] = 4;
  } else break;
}
toc("x(id) = 4");

El segundo paso lleva más tiempo que los 0.1415s esperados, esto se debe a la necesidad de verificar errores en los valores de id . La sobrecarga me parece demasiado grande, tal vez podría escribirse mejor. Aún así, el tiempo requerido es 0.4340s , no 1.208419s . Lo que MATLAB hace bajo el capó, no tengo ni idea. Tal vez es necesario hacerlo, simplemente no lo veo.

Por supuesto, usar doubles como índices introduce dos niveles adicionales de sobrecarga:

• tamaño del double del double del tamaño de uint32 . Recuerde que el ancho de banda de la memoria es el factor limitante aquí.
• los dobles se deben convertir a números enteros para indexar

El Método 4 se puede escribir en MATLAB usando índices enteros:

tic;
id = uint32(1):1e8;
toc
tic
x(id) = 8;
toc

Elapsed time is 0.327704 seconds.
Elapsed time is 0.561121 seconds.

Lo cual claramente mejoró el rendimiento en un 30% y prueba que uno debería usar números enteros como índices de vectores. Sin embargo, la sobrecarga todavía está allí.

Tal como lo veo ahora, no podemos hacer nada para mejorar la situación trabajando en el marco de MATLAB, y tenemos que esperar hasta que Mathworks corrija estos problemas.

Answer 2

Puedo, por supuesto, solo especular. Sin embargo, cuando ejecuto la prueba con el compilador JIT habilitado o deshabilitado, obtengo los siguientes resultados:

 % with JIT   no JIT
    0.1677    0.0011 %# init
    0.0974    0.0936 %# #1 I added an assigment before this line to avoid issues with deferring
    0.4005    0.4028 %# #2
    0.4047    0.4005 %# #3
    1.1160    1.1180 %# #4
    0.8221   48.3239 %# #5 This is where "don''t use loops in Matlab" comes from 
    0.3232   48.2197 %# #6
    0.5464   %# logical indexing

Dividir nos muestra dónde hay un aumento de velocidad:

% withoutJit./withJit
    0.0067 %# w/o JIT, the memory allocation is deferred
    0.9614 %# no JIT
    1.0057 %# no JIT
    0.9897 %# no JIT
    1.0018 %# no JIT
   58.7792 %# numel
  149.2010 %# no numel

La aparente aceleración en la inicialización ocurre, porque con JIT desactivado, parece que MATLAB retrasa la asignación de memoria hasta que se usa, por lo que x = ceros (...) no hace nada realmente. (gracias, @angainor).

Los métodos del 1 al 4 no parecen beneficiarse del JIT. Supongo que # 4 podría ser lento debido a las pruebas de entrada adicionales en subsref para asegurarse de que la entrada sea de la forma correcta.

El resultado numel podría tener algo que ver con que sea más difícil para el compilador lidiar con un número incierto de iteraciones, o con algunos gastos indirectos debido a que se verifica si el límite del bucle está bien (las pruebas no JIT sugieren que solo ~ 0.1s para ese)

Sorprendentemente, en R2012b en mi máquina, la indexación lógica parece ser más lenta que la # 4.

Creo que esto demuestra, una vez más, que MathWorks ha hecho un gran trabajo para acelerar el código, y que "no usar bucles" no siempre es mejor si estás tratando de obtener el tiempo de ejecución más rápido (al menos En el momento). Sin embargo, considero que la vectorización es en general un buen enfoque, ya que (a) el JIT falla en bucles más complejos, y (b) aprender a vectorizar te hace entender Matlab mucho mejor.

Conclusión: si quieres velocidad, utiliza el generador de perfiles y vuelve a crear un perfil si cambias las versiones de Matlab.

Como referencia, utilicé la siguiente función de prueba ligeramente modificada

function tt = speedTest

tt = zeros(8,1);

tic; x = zeros(1,1e8); tt(1)=toc;

x(:) = 2;

tic; x(:) = 1; tt(2)=toc;
tic; x(1:end) = 2; tt(3)=toc;
tic; x(1:1e8) = 3; tt(4)=toc;

tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
tt(5)=toc;

tic;
for i=1:numel(x)
    x(i) = 5;
end
tt(6)=toc;

tic;
for i=1:1e8
    x(i) = 6;
end
tt(7)=toc;

%# logical indexing
tic;
id = true(1e8,1));
x(id)=7;
tt(8)=toc;