¿Cuándo tiene sentido preseleccionar un hash?

Question

De perldata:

You can preallocate space for a hash by assigning to the keys() function. 
This rounds up the allocated buckets to the next power of two: 

    keys(%users) = 1000;  # allocate 1024 buckets 

¿Existe una regla de oro para cuando presizing un hash mejorará el rendimiento?

Answer 1

La regla de oro es que cuanto más grande sea el Hash, mayor será la probabilidad de que obtenga un valor al dimensionarlo previamente. Considere si su hash tiene 10 ranuras, y comienza a agregar una después de la otra, el número de expansiones a) serán pocas (si es que las tiene), yb) pequeñas (dado que hay pocos datos).

Pero si usted SABE que va a necesitar al menos 1M de artículos, entonces no hay razón para expandirse y copiar las estructuras de datos subyacentes y en constante expansión una y otra vez mientras la tabla crece.

¿AVISO esta expansión? Eh, tal vez Las máquinas modernas son bastante rápidas, es posible que no aparezcan. Pero es una gran oportunidad para la expansión del montón, lo que provoca un GC y una cascada de todo tipo de cosas. Entonces, si sabes que vas a usarlo, es una solución "barata" para modificar algunos miles de milisegundos de rendimiento.

Answer 2

Básicamente es la puerta para optimizar el rendimiento hash. El rendimiento del hash depende en gran medida del algoritmo de hashing utilizado y de los datos que maneja, por lo que es casi imposible establecer una regla de oro. De todos modos, algo se puede decir.

Sabe que cada estructura de datos ofrece un equilibrio entre la eficiencia del espacio y el tiempo. Las tablas hash son especialmente buenas en cuanto a la eficiencia del tiempo, ofreciendo un atractivo acceso constante (0 (1)).

Esto es válido a menos que haya una colisión. Cuando ocurre una colisión, el tiempo de acceso es lineal con el tamaño del cubo correspondiente al valor de colisión. (Eche un vistazo a this para más detalles). Las colisiones, además de ser "más lentas", son principalmente una interrupción de la garantía de tiempo de acceso, que es el aspecto más importante que a menudo lleva a elegir una tabla hash en primer lugar.

Idealmente, las tablas hash podrían apuntar a lo que se conoce como "hashing perfecto" (que solo es factible cuando se puede ajustar el algoritmo al tipo de datos que manejará), pero esto no es tan fácil de alcanzar en el caso general (esto es un eufemismo, en realidad). De todos modos, es una cuestión de hecho que las tablas hash más grandes (junto con un buen algoritmo hash) pueden reducir la frecuencia de las colisiones, y así mejorar el rendimiento, a expensas de la memoria. Las tablas hash más pequeñas verán más colisiones (por lo tanto, tendrán un menor rendimiento y una menor garantía de tiempo de acceso de calidad) pero ocuparán menos memoria.

Por lo tanto, si perfila su programa y ve que el acceso a la tabla hash es un cuello de botella (por algún motivo) tiene la posibilidad de resolver esto reservando más memoria para el espacio hash (si tiene memoria para dar).

En cualquier caso, no aumentaría este valor al azar, sino solo después de un perfil completo, ya que también es cierto que el algoritmo perl usa está compilado en (AFAIK) y esto también tiene un gran efecto en el rendimiento hash (en otras palabras, podrías tener muchas colisiones incluso si haces que el espacio de hash sea más grande).

Como de costumbre con las cosas relacionadas con el rendimiento, podría ser útil o no, depende de su caso concreto.

Answer 3

Me trataron de costos de expansión de referencia en el cultivo de hash:

use Benchmark qw(cmpthese); 

# few values 
cmpthese(-4, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 17576; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaa' .. 'zzz'; 
    }, 
}); 

# more values 
cmpthese(-8, { 
    prealloc => sub { 
     my %hash; 
     keys(%hash) = 456976; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
    normal => sub { 
     my %hash; 
     $hash{$_} = $_ for 'aaaa' .. 'zzzz'; 
    }, 
}); 

Resultados no suena como gran optimización, sin embargo, la reducción de la fragmentación del montón mencionado por Will Hartung podría ser de beneficio. Ejecutando Perl 5.12 en la máquina WinXP.

 Rate normal prealloc 
normal 48.3/s  --  -2% 
prealloc 49.4/s  2%  -- 
     (warning: too few iterations for a reliable count) 
    s/iter normal prealloc 
normal  3.62  --  -1% 
prealloc 3.57  1%  --