Forma más rápida de inicializar matrices en Delphi

Question

Estoy tratando de exprimir hasta el último detalle en mi aplicación Delphi y ahora llegué a un procedimiento que funciona con matrices dinámicas. La línea más lenta es

SetLength (Resultado, Len);

que se utiliza para inicializar la matriz dinámica. Cuando miro el código para el procedimiento SetLength, veo que está lejos de ser óptimo. La secuencia de llamada es el siguiente:

_DynArraySetLength -> DynArraySetLength

DynArraySetLength consigue la longitud de la matriz (que es cero para inicialización) y luego utiliza ReallocMem que también es innecesario para initilization.

Estaba haciendo SetLength para inicializar la matriz dinámica todo el tiempo. Tal vez me estoy perdiendo algo? ¿Hay una manera más rápida de hacer esto?

EDIT: Describir el algoritmo principal tomaría mucho espacio y realmente es innecesario porque estoy tratando de optimizar una pequeña parte de él. En términos generales, es un verificador del problema de enrutamiento de vehículos (http://en.wikipedia.org/wiki/Vehicle_routing_problem). Necesito tropecientos de asignaciones, porque tengo que mantener todos los datos y mantenerlos por separado. Probalby ayudaría si pudiera pensar en alguna estructura de datos inteligente aquí, pero cualquier cosa que pueda pensar aumentaría en gran medida la complejidad del código. Básicamente he hecho todo lo que pude en el nivel algorítmico, así que ahora estoy tratando de obtener todo lo que pueda de las cosas de bajo nivel. Entonces, esta es una pregunta bastante limitada: ¿hay alguna posibilidad de aumentar esta llamada en particular? Y creo que para hacer esto necesito escribir mi propia función de inicialización basada en el código SetLength. Y hazlo en línea.

Answer 1

Max escribió:

Tengo un trillón llama a una función el que hace una SetLength tiempo (Resultado, Len).

Compruebe cómo utiliza su función: ¿realmente necesita un trillón de llamadas distintas a esta función de asignación? ¿puedes, como sugirió Francois, rediseñar tu código para disminuir el número de llamadas?

Si realmente necesita un trillón de llamadas distintas a su función, y necesita acelerar las cosas, creo que tendrá que dejar matrices dinámicas y usar una estructura diferente.

Pero antes de hacer eso, y entrar en un infierno de depuración completo, me uniría fuertemente a la sugerencia de Francois, y trataré de rediseñar el código.

Tal vez nos puede decir un poco más acerca de su algoritmo? ¿Se trata de manejar estructuras 3D gráficas?

[EDITAR] Ok, si se trata de resolver problemas NP-completos, trataría de evitar asignar tanto como sea posible.

mayoría de las veces, se puede dar un límite superior al tamaño de las matrices de bloques/los/las estructuras - por ejemplo: #cities, #vehicles + #drivers, #roads * #cities ...

Para esas partes, sugiero asignar una vez la matriz más grande posible, y manejar manualmente el hecho de que use solo las primeras n filas o tal.

Dado el tiempo de cálculo que puede guardar después, incluso la asignación de estructuras en n^2 o n^3 puede ser aceptable.

Optimizing SetLength: lo que sugiere tiene sentido.

Sin embargo, si las matrices dinámicas están bien adaptadas para escribir código Delphi, principalmente por su semántica de "constructor automático", no están bien adaptadas a cálculos de alto rendimiento, depende en gran medida de RTTI, el recuento de referencias puede dar usted sorprende de vez en cuando ...
Lo que está sugiriendo es un cambio en la semántica de matrices dinámicas. Intente ver si la solución "cambiar su tipo de datos" es realmente tan imposible de escribir & depurar.

Answer 2

Esto es más que un comentario, pero como publicar grandes bloques de código en los comentarios no es bonito, lo publico aquí.

A veces, si usted no sabe cuántos elementos que va a terminar con al final, puede ser tentador para escribir código como este:

var 
    Arr: array of cardinal; 

procedure AddElement(const NewElement: cardinal); 
begin 
    SetLength(Arr, length(Arr) + 1); 
    Arr[high(Arr)] := NewElement; 
end; 

Esto es muy malo, porque entonces las necesidades de memoria para ser reasignado cada vez que agregue un nuevo elemento. Un enfoque mucho mejor (si es posible) es encontrar un límite superior para la cantidad de elementos, como MAX_ELEMENTS = 100000; y luego ajustar la duración inicialmente:

SetLength(Arr, MAX_ELEMENTS); 

a continuación, crear una variable como

var 
    ActualNumberOfElements: cardinal = 0; 

y escribir

procedure AddElement(const NewElement: cardinal); 
begin 
    Arr[ActualNumberOfElements] := NewElement; 
    inc(ActualNumberOfElements); 
end; 

Cuando haya terminado de llenar la matriz, simplemente trunca:

SetLength(Arr, ActualNumberOfElements); 

Answer 3

Si usted es o Si lo llama una sola vez y tarda mucho tiempo, solicita más RAM de la disponible, lo que hace que el sistema operativo intercambie otras cosas en un intento de hacerle espacio. Solución: agregue más RAM, use matrices más pequeñas.

Si lo está llamando en un bucle, entonces el "realloc" es el problema. Cada vez que lo llamas, aumentando poco a poco la longitud de la matriz, Delphi reasigna su matriz completa, y luego copia todo, desde la matriz anterior a la nueva matriz. No es exactamente eficiente.

Answer 4

"optimización prematura es la raíz de todo mal."
dudo que tendría que preocuparse por una vez en la vida ... inicialización
Eso es menos que usted lo llama un millón de veces, y luego Te sugiero que rediseñes tu código.

Answer 5

La parte más lenta de SetLength no son "llamadas no sinceras" o algo así: asignación de memoria, que realiza el administrador de memoria (y ReallocMem en su caso será simple GetMem, ya que el puntero fuente es nulo).

Entonces, ¿qué administrador de memoria usa? ¿Estás, por casualidad, en D7 sin FastMM?

Intente instalar FastMM y vea si ayuda un poco.

Answer 6

En lugar de llamar a una función que contiene SetLength un trillón de veces, en lugar de preasignar el almacenamiento, y pasar las matrices preasignadas a la función.Una forma de hacerlo es algo como esto:

const 
    NUM_ARRAYS = 1000; 
    ARRAY_SIZE = 1000; 
type 
    TMyArray = array [0..ARRAY_SIZE] of Integer; 
var 
    MyStorage: array[0..NUM_ARRAYS] of TMyArray; 

procedure DoWork(var AArray: TMyArray); 
begin 
    Blah; 
end; 

procedure MainLoop; 
var 
    i: Integer; 
begin 
    for i := 0 to High(MyStorage) do 
    begin 
    DoWork(MyStorage[i]); 
    end; 
end; 

Ésta será significativamente más rápido que llamar SetLength dentro de un bucle interno. Lo principal a tener en cuenta es usar demasiada memoria para el hardware.