performance - traza - matriz transpuesta matlab

¿Forma más rápida de inicializar matrices mediante la multiplicación de matrices vacías?(Matlab) (5)

Después de investigar un poco, encontré este artículo en "Matlab indocumentado" , en el cual el Sr. Yair Altman ya había llegado a la conclusión de que la forma de MathWork de preasignar matrices utilizando zeros(M, N) no es la forma más eficiente.

Él cronometró x = zeros(M,N) vs. clear x, x(M,N) = 0 y encontró que el último es ~ 500 veces más rápido. Según su explicación, el segundo método simplemente crea una matriz M-by-N, cuyos elementos se inicializan automáticamente a 0. Sin embargo, el primer método crea x (con x tener cero elementos automáticos) y luego asigna un cero a cada elemento en x otra vez, y esa es una operación redundante que lleva más tiempo.

En el caso de la multiplicación de matriz vacía, como lo que ha mostrado en su pregunta, MATLAB espera que el producto sea una matriz M × N y, por lo tanto, asigna una matriz M × N. En consecuencia, la matriz de salida se inicializa automáticamente a ceros. Dado que las matrices originales están vacías, no se realizan más cálculos y, por lo tanto, los elementos en la matriz de salida permanecen sin cambios e iguales a cero.

Me he tropezado con la forma extraña (en mi opinión) de que Matlab está lidiando con matrices vacías . Por ejemplo, si se multiplican dos matrices vacías, el resultado es:

zeros(3,0)*zeros(0,3) ans = 0 0 0 0 0 0 0 0 0

Ahora, esto ya me tomó por sorpresa, sin embargo, una búsqueda rápida me llevó al enlace de arriba, y obtuve una explicación de la lógica algo retorcida de por qué esto está sucediendo.

Sin embargo , nada me preparó para la siguiente observación. Me pregunté, ¿qué tan eficiente es este tipo de multiplicación frente a la simple utilización de la función de zeros(n) , por ejemplo con el propósito de la inicialización? He usado timeit para responder esto:

f=@() zeros(1000) timeit(f) ans = 0.0033

vs:

g=@() zeros(1000,0)*zeros(0,1000) timeit(g) ans = 9.2048e-06

Ambos tienen el mismo resultado que la matriz de 1000x1000 de ceros de clase double , pero la multiplicación de matriz vacía es ~ 350 veces más rápida. (un resultado similar ocurre usando tic y toc y un bucle)

¿Cómo puede ser esto? son timeit o tic,toc farol o he encontrado una forma más rápida de inicializar matrices? (Esto fue hecho con Matlab 2012a, en una máquina win7-64, intel-i5 650 3.2Ghz ...)

EDITAR:

Después de leer sus comentarios, he estudiado con más detenimiento esta peculiaridad y probado en 2 computadoras diferentes (el mismo matlab ver aunque 2012a) un código que examina el tiempo de ejecución frente al tamaño de la matriz n. Esto es lo que obtengo:

El código para generar este timeit usado como antes, pero un loop con tic y toc tendrá el mismo aspecto. Entonces, para tamaños pequeños, zeros(n) es comparable. Sin embargo, alrededor de n=400 hay un salto en el rendimiento para la multiplicación de la matriz vacía. El código que he usado para generar ese diagrama fue:

n=unique(round(logspace(0,4,200))); for k=1:length(n) f=@() zeros(n(k)); t1(k)=timeit(f); g=@() zeros(n(k),0)*zeros(0,n(k)); t2(k)=timeit(g); end loglog(n,t1,''b'',n,t2,''r''); legend(''zeros(n)'',''zeros(n,0)*zeros(0,n)'',2); xlabel(''matrix size (n)''); ylabel(''time [sec]'');

¿Alguno de ustedes experimenta esto también?

EDIT # 2:

A propósito, la multiplicación de matriz vacía no es necesaria para obtener este efecto. Uno puede simplemente hacer:

z(n,n)=0;

donde n> algún tamaño de matriz de umbral visto en el gráfico anterior, y obtener el perfil de eficiencia exacto como con la multiplicación de matrices vacías (otra vez usando timeit).

Aquí hay un ejemplo donde mejora la eficiencia de un código:

n = 1e4; clear z1 tic z1 = zeros( n ); for cc = 1 : n z1(:,cc)=cc; end toc % Elapsed time is 0.445780 seconds. %% clear z0 tic z0 = zeros(n,0)*zeros(0,n); for cc = 1 : n z0(:,cc)=cc; end toc % Elapsed time is 0.297953 seconds.

Sin embargo, usando z(n,n)=0; en su lugar produce resultados similares al caso de zeros(n) .

Esto es extraño, estoy viendo que f es más rápido mientras que g es más lento de lo que estás viendo. Pero ambos son idénticos para mí. ¿Quizás una versión diferente de MATLAB?

>> g = @() zeros(1000, 0) * zeros(0, 1000); >> f = @() zeros(1000) f = @()zeros(1000) >> timeit(f) ans = 8.5019e-04 >> timeit(f) ans = 8.4627e-04 >> timeit(g) ans = 8.4627e-04

EDITAR puede agregar +1 para el final de fyg, y ver qué horas está recibiendo.

EDITAR Ene 6, 2013 7:42 EST

Estoy usando una máquina de forma remota, lo siento por los gráficos de baja calidad (tuve que generarlos a ciegas).

Configuración de la máquina:

i7 920. 2,665 GHz. Linux. 12 GB de RAM 8 MB de caché

Parece que incluso la máquina a la que tengo acceso muestra este comportamiento, excepto en un tamaño más grande (en algún lugar entre 1979 y 2073). No hay ninguna razón por la que pueda pensar en este momento para que la multiplicación de la matriz vacía sea más rápida en tamaños más grandes.

Investigaré un poco más antes de volver.

EDITAR 11 de enero de 2013

Después de la publicación de @EitanT, quería hacer un poco más de investigación. Escribí un código C para ver cómo Matlab puede estar creando una matriz de ceros. Aquí está el código de C ++ que utilicé.

int main(int argc, char **argv) { for (int i = 1975; i <= 2100; i+=25) { timer::start(); double *foo = (double *)malloc(i * i * sizeof(double)); for (int k = 0; k < i * i; k++) foo[k] = 0; double mftime = timer::stop(); free(foo); timer::start(); double *bar = (double *)malloc(i * i * sizeof(double)); memset(bar, 0, i * i * sizeof(double)); double mmtime = timer::stop(); free(bar); timer::start(); double *baz = (double *)calloc(i * i, sizeof(double)); double catime = timer::stop(); free(baz); printf("%d, %lf, %lf, %lf/n", i, mftime, mmtime, catime); } }

Aquí están los resultados.

$ ./test 1975, 0.013812, 0.013578, 0.003321 2000, 0.014144, 0.013879, 0.003408 2025, 0.014396, 0.014219, 0.003490 2050, 0.014732, 0.013784, 0.000043 2075, 0.015022, 0.014122, 0.000045 2100, 0.014606, 0.014480, 0.000045

Como puede ver, el calloc (cuarta columna) parece ser el método más rápido. También se está volviendo significativamente más rápido entre 2025 y 2050 (supongo que sería alrededor de 2048?).

Ahora volví a Matlab para comprobar lo mismo. Aquí están los resultados.

>> test 1975, 0.003296, 0.003297 2000, 0.003377, 0.003385 2025, 0.003465, 0.003464 2050, 0.015987, 0.000019 2075, 0.016373, 0.000019 2100, 0.016762, 0.000020

Parece que tanto f () como g () usan calloc en tamaños más pequeños (<2048?). Pero en tamaños más grandes f () (ceros (m, n)) comienza a usar malloc + memset , mientras que g () (ceros (m, 0) * ceros (0, n)) sigue usando calloc .

Entonces la divergencia se explica por el siguiente

ceros (..) comienza a usar un esquema diferente (¿más lento?) en tamaños más grandes.
calloc también se comporta de forma algo inesperada, lo que lleva a una mejora en el rendimiento.

Este es el comportamiento en Linux. ¿Puede alguien hacer el mismo experimento en una máquina diferente (y tal vez en un sistema operativo diferente) y ver si el experimento es válido?

Interesante pregunta, aparentemente hay varias formas de ''vencer'' la función de zeros integrada. Mi única conjetura sobre por qué sucede esto sería que podría ser más eficiente en la memoria (después de todo, los zeros(LargeNumer) harán que Matlab llegue al límite de la memoria antes que formar un cuello de botella de velocidad en la mayoría de los códigos), o más robustos de alguna manera .

Aquí hay otro método de asignación rápida que usa una matriz dispersa. He añadido la función de ceros regulares como punto de referencia:

tic; x=zeros(1000,1000); toc Elapsed time is 0.002863 seconds. tic; clear x; x(1000,1000)=0; toc Elapsed time is 0.000282 seconds. tic; x=full(spalloc(1000,1000,0)); toc Elapsed time is 0.000273 seconds. tic; x=spalloc(1000,1000,1000000); toc %Is this the same for practical purposes? Elapsed time is 0.000281 seconds.

Los resultados pueden ser un poco engañosos. Cuando multiplicas dos matrices vacías, la matriz resultante no se "asigna" e "inicializa" inmediatamente, sino que se pospone hasta que la utilices por primera vez (algo así como una evaluación perezosa).

Lo mismo se aplica cuando se indexing fuera de límites para hacer grow una variable, que en el caso de las matrices numéricas rellena las entradas faltantes con ceros (analizo después el caso no numérico). Por supuesto, crecer la matriz de esta manera no sobrescribe los elementos existentes.

Entonces, si bien puede parecer más rápido, solo está demorando el tiempo de asignación hasta que realmente usa la matriz por primera vez. Al final, tendrá tiempos similares a los de la asignación desde el principio.

Ejemplo para mostrar este comportamiento, en comparación con algunas otras alternativas :

N = 1000; clear z tic, z = zeros(N,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = zeros(N,0)*zeros(0,N); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(N,N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = full(spalloc(N,N,0)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z(1:N,1:N) = 0; toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z val = 0; tic, z = val(ones(N)); toc tic, z = z + 1; toc assert(isequal(z,ones(N))) clear z tic, z = repmat(0, [N N]); toc tic, z = z + 1; toc assert(isequal(z,ones(N)))

El resultado muestra que si suma el tiempo transcurrido para ambas instrucciones en cada caso, termina con tiempos totales similares:

// zeros(N,N) Elapsed time is 0.004525 seconds. Elapsed time is 0.000792 seconds. // zeros(N,0)*zeros(0,N) Elapsed time is 0.000052 seconds. Elapsed time is 0.004365 seconds. // z(N,N) = 0 Elapsed time is 0.000053 seconds. Elapsed time is 0.004119 seconds.

Los otros tiempos fueron:

// full(spalloc(N,N,0)) Elapsed time is 0.001463 seconds. Elapsed time is 0.003751 seconds. // z(1:N,1:N) = 0 Elapsed time is 0.006820 seconds. Elapsed time is 0.000647 seconds. // val(ones(N)) Elapsed time is 0.034880 seconds. Elapsed time is 0.000911 seconds. // repmat(0, [N N]) Elapsed time is 0.001320 seconds. Elapsed time is 0.003749 seconds.

Estas medidas son demasiado pequeñas en milisegundos y pueden no ser muy precisas, por lo que es posible que desee ejecutar estos comandos en un bucle de miles de veces y tomar el promedio. También a veces ejecutar funciones M guardadas es más rápido que ejecutar scripts o en el símbolo del sistema, ya que ciertas optimizaciones solo suceden de esa manera ...

De cualquier forma, la asignación se realiza generalmente una vez, entonces, ¿a quién le importa si se necesitan 30ms adicionales? :)

Un comportamiento similar se puede ver con matrices de celdas o matrices de estructuras. Considere el siguiente ejemplo:

N = 1000; tic, a = cell(N,N); toc tic, b = repmat({[]}, [N,N]); toc tic, c{N,N} = []; toc

lo que da:

Elapsed time is 0.001245 seconds. Elapsed time is 0.040698 seconds. Elapsed time is 0.004846 seconds.

Tenga en cuenta que incluso si son todos iguales, ocupan diferente cantidad de memoria:

>> assert(isequal(a,b,c)) >> whos a b c Name Size Bytes Class Attributes a 1000x1000 8000000 cell b 1000x1000 112000000 cell c 1000x1000 8000104 cell

De hecho, la situación es un poco más complicada aquí, ya que MATLAB probablemente está sharing la misma matriz vacía para todas las celdas, en lugar de crear copias múltiples.

La matriz de celdas a es, de hecho, una matriz de celdas no inicializadas (una matriz de punteros NULL), mientras que b es una matriz de celdas donde cada celda es una matriz vacía [] (internamente y debido al intercambio de datos, solo la primera celda b{1} apunta a [] mientras que el resto tiene una referencia a la primera celda). La matriz final c es similar a a (celdas no inicializadas), pero la última contiene una matriz numérica vacía [] .

Miré alrededor de la lista de funciones C exportadas de libmx.dll (usando la herramienta Dependency Walker ), y encontré algunas cosas interesantes.

hay funciones no documentadas para crear matrices no inicializadas: mxCreateUninitDoubleMatrix , mxCreateUninitNumericArray y mxCreateUninitNumericMatrix . De hecho, hay una presentación en el intercambio de archivos que hace uso de estas funciones para proporcionar una alternativa más rápida a la función de zeros .
existe una función no documentada llamada mxFastZeros . Haciendo búsquedas en línea, puedo ver que has publicado esta pregunta en MATLAB Answers también, con algunas respuestas excelentes. James Tursa (el mismo autor de UNINIT de antes) dio un example sobre cómo usar esta función no documentada.
libmx.dll está vinculado contra la biblioteca compartida tbbmalloc.dll . Este es el asignador de memoria escalable Intel TBB . Esta biblioteca proporciona funciones de asignación de memoria equivalentes ( malloc , calloc , free ) optimizadas para aplicaciones paralelas. Recuerde que muchas funciones de MATLAB son multiproceso automático , por lo que no me sorprendería si zeros(..) tiene múltiples subprocesos y está utilizando el asignador de memoria de Intel una vez que el tamaño de la matriz es lo suficientemente grande (este es un comentario reciente de Loren Shure que confirma este hecho) .

Con respecto al último punto sobre el asignador de memoria, podría escribir un punto de referencia similar en C / C ++ similar a lo que hizo @PavanYalamanchili , y comparar los diversos asignadores disponibles. Algo como this Recuerde que los archivos MEX tienen una sobrecarga de administración de memoria ligeramente mayor, ya que MATLAB libera automáticamente cualquier memoria asignada en archivos MEX utilizando las mxCalloc , mxMalloc o mxRealloc . Por lo que vale, solía ser posible cambiar el administrador de memoria interna en versiones anteriores.

EDITAR:

Aquí hay un punto de referencia más completo para comparar las alternativas discutidas. Muestra específicamente que una vez que enfatiza el uso de toda la matriz asignada, los tres métodos están en igualdad de condiciones, y la diferencia es insignificante.

function compare_zeros_init() iter = 100; for N = 512.*(1:8) % ZEROS(N,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf(''N = %4d, ZEROS = %.9f/n'', N, mean(sum(t,2))) % z(N,N)=0 t = zeros(iter,3); for i=1:iter clear z tic, z(N,N) = 0; t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf(''N = %4d, GROW = %.9f/n'', N, mean(sum(t,2))) % ZEROS(N,0)*ZEROS(0,N) t = zeros(iter,3); for i=1:iter clear z tic, z = zeros(N,0)*zeros(0,N); t(i,1) = toc; tic, z(:) = 9; t(i,2) = toc; tic, z = z + 1; t(i,3) = toc; end fprintf(''N = %4d, MULT = %.9f/n/n'', N, mean(sum(t,2))) end end

A continuación se muestran los tiempos promediados sobre 100 iteraciones en términos de aumentar el tamaño de la matriz. Realicé las pruebas en R2013a.

>> compare_zeros_init N = 512, ZEROS = 0.001560168 N = 512, GROW = 0.001479991 N = 512, MULT = 0.001457031 N = 1024, ZEROS = 0.005744873 N = 1024, GROW = 0.005352638 N = 1024, MULT = 0.005359236 N = 1536, ZEROS = 0.011950846 N = 1536, GROW = 0.009051589 N = 1536, MULT = 0.008418878 N = 2048, ZEROS = 0.012154002 N = 2048, GROW = 0.010996315 N = 2048, MULT = 0.011002169 N = 2560, ZEROS = 0.017940950 N = 2560, GROW = 0.017641046 N = 2560, MULT = 0.017640323 N = 3072, ZEROS = 0.025657999 N = 3072, GROW = 0.025836506 N = 3072, MULT = 0.051533432 N = 3584, ZEROS = 0.074739924 N = 3584, GROW = 0.070486857 N = 3584, MULT = 0.072822335 N = 4096, ZEROS = 0.098791732 N = 4096, GROW = 0.095849788 N = 4096, MULT = 0.102148452

Parece que matlab decide usar matrices dispersas cuando recibió un comando como z(n,n)=0; cuando n es lo suficientemente grande La implementación interna puede estar en forma de una condición como: (si newsize> THRESHOLD + oldsize luego usa sparse ...) donde THRESHOLD es su "tamaño de umbral".

Sin embargo, esto es a pesar de que Mathworks afirma: "Matlab nunca crea matrices dispersas automáticamente" ( link )

No tengo Matlab para probar esto. Sin embargo, usar matrices dispersas (internamente) es una explicación más corta (la navaja de Occam), por lo tanto, es mejor hasta que se falsifique.