¿Cuándo no vectorizar matlab?

Question

Estoy trabajando en algún código de matlab que está procesando conjuntos de datos grandes (pero no enormes): 10.000 784 vectores de elementos (no dispersos) y calculando información sobre lo que está almacenado en una matriz dispersa de 10.000x10. Para que el código funcione, hice algunas de las partes más complicadas de forma iterativa, haciendo bucles sobre los 10k elementos para procesarlos, y algunos sobre los 10 elementos en la matriz dispersa para la limpieza.

Mi proceso inicialmente tomó 73 iteraciones (por lo tanto, en el orden de 730k bucles) para procesar, y se ejecutó en aproximadamente 120 segundos. No está mal, pero esto es matlab, así que me puse a vectorizarlo para acelerarlo.

Al final tengo una solución totalmente vectorizada que obtiene la misma respuesta (por lo que es correcta, o al menos tan correcta como mi solución inicial), pero tarda 274 segundos en ejecutarse, ¡es casi la mitad de rápida!

Esta es la primera vez que me encuentro con el código de matlab, que se ejecuta con una vectorización más lenta que iterativamente. ¿Existen reglas generales o mejores prácticas para identificar cuándo es probable/posible?

Me encantaría compartir el código para obtener algunos comentarios, pero es para una tarea escolar actualmente abierta, así que realmente no puedo en este momento. Si termina siendo uno de esos "Wow, eso es raro, probablemente hiciste algo mal" probablemente revise esto en una semana o dos para ver si mi vectorización está apagada.

Answer 1

Vectorización en Matlab a menudo significa la asignación de una memoria mucho más (haciendo una gama mucho más grande para evitar el bucle por ejemplo, por tony's trick). Con la mejora de la compilación JIT de bucles en las versiones recientes, es posible que la asignación de memoria necesaria para su solución vectorizada significa que no hay ninguna ventaja, pero sin ver el código es difícil de decir. Matlab tiene un excelente perfilador línea por línea que debería ayudarlo a ver qué partes particulares de la versión vectorizada están tomando el tiempo.

Answer 2

¿Ha intentado trazar el tiempo de ejecución como una función del tamaño del problema (ya sea el número de elementos por vector [actualmente 784], o el número de vectores [actualmente 10,000])? Me encontré con una anomalía similar al vectorizar un algoritmo de ortogonalización de Gram-Schmidt; resultó que la versión vectorizada fue más rápido hasta que el problema creció a un cierto tamaño, y en ese momento la versión iterativa realidad corría más rápido, como se ve en esta trama:

Éstos son los dos implementaciones y el guión evaluación comparativa:

clgs.m

function [Q,R] = clgs(A) 
% QR factorization by unvectorized classical Gram-Schmidt orthogonalization 

[m,n] = size(A); 

R = zeros(n,n);  % pre-allocate upper-triangular matrix 

% iterate over columns 
for j = 1:n 
    v = A(:,j); 

    % iterate over remaining columns 
    for i = 1:j-1 
     R(i,j) = A(:,i)' * A(:,j); 
     v = v - R(i,j) * A(:,i); 
    end 

    R(j,j) = norm(v); 
    A(:,j) = v/norm(v); % normalize 
end 
Q = A; 

clgs2.m

function [Q,R] = clgs2(A) 
% QR factorization by classical Gram-Schmidt orthogonalization with a 
% vectorized inner loop 

[m,n] = size(A); 
R = zeros(n,n);  % pre-allocate upper-triangular matrix 

for k=1:n 
    R(1:k-1,k) = A(:,1:k-1)' * A(:,k); 
    A(:,k) = A(:,k) - A(:,1:k-1) * R(1:k-1,k); 
    R(k,k) = norm(A(:,k)); 
    A(:,k) = A(:,k)/R(k,k); 
end 

Q = A; 

benchgs.m

n = [300,350,400,450,500]; 

clgs_time=zeros(length(n),1); 
clgs2_time=clgs_time; 

for i = 1:length(n) 
    A = rand(n(i)); 
    tic; 
    [Q,R] = clgs(A); 
    clgs_time(i) = toc; 

    tic; 
    [Q,R] = clgs2(A); 
    clgs2_time(i) = toc; 
end 

semilogy(n,clgs_time,'b',n,clgs2_time,'r') 
xlabel 'n', ylabel 'Time [seconds]' 
legend('unvectorized CGS','vectorized CGS') 

Answer 3

Para responder a la pregunta "¿Cuándo no vectorizar código de MATLAB" en términos más generales:

No Vectorize código si la vectorización no es sencillo y hace que el código muy difícil de leer. Esto es bajo la suposición de que

1. Es posible que otras personas deban leerlo y comprenderlo.
2. El código no revelado es lo suficientemente rápido para lo que necesita.

Answer 4

Esta no será una respuesta muy específica, pero trato con conjuntos de datos extremadamente grandes (datasets 4D cardiacos).

Hay ocasiones en las que necesito realizar una operación que involucra varios conjuntos 4D. Puedo crear un bucle o una operación vectorizada que esencialmente funciona en un objeto 5D concatenado. (por ejemplo, como un ejemplo trivial, digamos que desea obtener el objeto 4D promedio, puede crear un bucle que recoja un promedio móvil o concatenar en la quinta dimensión y usar la función media sobre él).

En mi experiencia, dejando de lado el tiempo que tomará crear el objeto 5D en primer lugar, presumiblemente debido a los enormes saltos de acceso de memoria y tamaño involucrados al realizar los cálculos, generalmente es mucho más rápido recurrir a un bucle de los objetos 4D aún grandes, pero mucho más manejables.

El otro truco de "microoptimización" que señalaré es que el matlab es "pedido mayor de columna". Es decir, para mi ejemplo trivial, creo que sería más rápido promediar a lo largo de la 1ª dimensión, en lugar de la 5ª, ya que la primera implica ubicaciones contiguas en la memoria, mientras que la segunda implica saltos enormes, por así decirlo. Por lo tanto, puede valer la pena almacenar su megaarray en un orden de dimensión que tenga los datos en los que estará operando como la primera dimensión, si tiene sentido.

ejemplo trivial para mostrar la diferencia entre poner en filas vs columnas:

>> A = randn(10000,10000); 
>> tic; for n = 1 : 100; sum(A,1); end; toc 
Elapsed time is 12.354861 seconds. 
>> tic; for n = 1 : 100; sum(A,2); end; toc 
Elapsed time is 22.298909 seconds.