ser - ¿Hay alguna manera de hacer que esta búsqueda de hash sea más rápida?
la leche es buena para la alergia en la piel (8)
Tengo el requisito de (muy) procesar rápidamente cadenas de un rango limitado, contando sus valores. El archivo de entrada es de la forma:
January 7
March 22
September 87
March 36
Etcétera. Debido a que los anchos de línea son idénticos, simplemente puedo leer en línea con un ritmo razonablemente rápido, y he desarrollado una función de hashing perfecta que funciona, pero quería ver si alguien podía ofrecer algún consejo sobre cómo hacerlo aún más rápido. Voy a hacer un perfil de cada sugerencia para ver cómo va.
La función de hashing se basa en el nombre del mes para permitir una rápida asignación del valor a un grupo. Ten paciencia conmigo aquí. La primera vez que calculé el número mínimo de caracteres para un hash perfecto:
January
February
March
April
May
June
July
August
September
October
November
December
Tenga en cuenta que los meses son los nueve caracteres, ya que tengo toda la línea de entrada.
Desafortunadamente, no hay una sola columna para marcar un mes como único. La columna 1 duplica J , la columna 2 duplica a , la columna 3 duplica r , la columna 4 duplica u y las columnas 5 en adelante duplican <space> (hay otros duplicados, pero uno es suficiente para evitar una clave hash de una sola columna).
Sin embargo, al usar la primera y la cuarta columnas, obtengo los valores Ju , Fr , Mc , Ai , M<space> , Je , Jy , Au , St , Oo , Ne y De , que son únicos. No habrá valores no válidos en este archivo, por lo que no tengo que preocuparme por los depósitos incorrectos para los datos de entrada.
Al ver los códigos hexadecimales de los caracteres, descubrí que podía obtener valores únicos bajos con solo AND con valores estratégicos:
FirstChar Hex Binary &0x0f
--------- --- --------- -----
A x41 0100 0001 1
D x44 0100 0100 4
F x46 0100 0110 6
J x4a 0100 1010 10
M x4d 0100 1101 13
N x4e 0100 1110 14
O x4f 0100 1111 15
S x53 0101 0011 3
SecondChar Hex Binary &0x1f
---------- --- --------- -----
<space> x20 0010 0000 0
c x63 0110 0011 3
e x65 0110 0101 5
i x69 0110 1001 9
o x6f 0110 1111 15
r x72 0111 0010 18
t x74 0111 0100 20
u x75 0111 0101 21
y x79 0111 1001 25
y esto me permitió configurar una matriz estática para crear una función de hash increíblemente rápida (con suerte):
#define __ -1
static unsigned int hash (const char *str) {
static unsigned char bucket[] = {
// A S D F J M N O
__, __, __, __, __, __, __, __, __, __, __, __, __, 4, __, __, // space
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, 2, __, __, // c
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, 11, __, __, __, __, __, 5, __, __, __, 10, __, // e
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, 3, __, __, __, __, __, __, __, __, __, __, __, __, __, __, // i
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 9, // o
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, 1, __, __, __, __, __, __, __, __, __, // r
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, 8, __, __, __, __, __, __, __, __, __, __, __, __, // t
__, 7, __, __, __, __, __, __, __, __, 0, __, __, __, __, __, // u
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, 6, __, __, __, __, __ // y
};
return bucket[((unsigned int)(str[3]&0x1f)<<4)|(str[0]&0xf)];
}
Probando eso con el código:
#include <stdio.h>
#include <string.h>
// Hash function here.
static char *months[] = {
"January ", "February ", "March ", "April ", "May ", "June ",
"July ", "August ", "September", "October ", "November ", "December "
};
int main (void) {
int i;
for (i = 0; i < sizeof(months)/sizeof(*months); i++)
printf ("%-10s -> %2d/n", months[i], hash(months[i]));
return 0;
}
muestra que es funcionalmente correcto:
January -> 0
February -> 1
March -> 2
April -> 3
May -> 4
June -> 5
July -> 6
August -> 7
September -> 8
October -> 9
November -> 10
December -> 11
Pero quiero saber si se puede hacer más rápido.
¿Alguna sugerencia por ahí? Estoy abierto a cualquier optimización simple o incluso a una reescritura total si hay algo inherentemente malo con mi función de hashing.
No creo que esto sea tan importante, pero la versión final usará EBCDIC. La teoría seguirá vigente pero la operación AND puede cambiar ligeramente ya que los caracteres tienen diferentes puntos de código. Estaré contento con cualquier asistencia solo en el frente de ASCII, ya que estoy seguro de que cualquier consejo que se ofrezca se traducirá en correcto para EBCDIC.
¿Realmente necesita la asignación entre el hash y el índice del mes para hacer el recuento? Podría eliminar una búsqueda si, en lugar de devolver el mes en que devolvió el hash y utilizarlo para realizar el recuento. En la respuesta de x4u, la última línea de la función hash podría verse como
return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )
y aún sería capaz de hacer las sumas, clasificando los resultados solo al final, no dentro del bucle.
Aquí está la secuencia más pequeña que pude encontrar para EBCDIC-US :
Tiene 24 elementos en el depósito y utiliza solo 2 operaciones para calcular el índice:
static unsigned int hash (const char *str)
{
static unsigned char tab[] = {
11, 4,__, 7,__,__, 9, 1,
__,__,__,__,__,__,__,__,
3, 5, 2,10, 8,__, 0, 6
};
return tab[0x17 & (str[ 1 ] + str[ 2 ])];
}
Segundo mejor, 25 artículos con xor:
static unsigned int hash(const char *str)
{
static unsigned char tab[] = {
9,__,__, 7,__,__,11, 1,
__, 4,__,__,__,__, 3,__,
__, 5, 8,10, 0,__,__, 6, 2
};
return tab[0x1f & (str[ 1 ] ^ str[ 2 ])];
}
(En realidad, la pestaña [] debe tener 32 entradas de largo aquí, porque 0x1f puede generar un desbordamiento de entradas incorrectas).
Actualización de Pax: para lo que vale, la primera opción funcionó perfectamente para el código EBCDIC página 500:
## Month str[1] str[2] Lookup
-- --------- ------ ------ ------
0 January a (81) n (95) 0
1 February e (85) b (82) 1
2 March a (81) r (99) 2
3 April p (97) r (99) 3
4 May a (81) y (a8) 4
5 June u (a4) n (95) 5
6 July u (a4) l (93) 6
7 August u (a4) g (87) 7
8 September e (85) p (97) 8
9 October c (83) t (a3) 9
10 November o (96) v (a5) 10
11 December e (85) c (83) 11
Comenzaría con un perfil detallado de su proceso más amplio para asegurarme de que no esté participando en una optimización prematura.
Esto se ve bastante rápido a primera vista, pero si la memoria es realmente barata, podría ser mejor usar una matriz aún más dispersa y dejar que tu caché haga algo del trabajo. Por ejemplo (y pensando en el brazalete aquí), qué pasa si simplemente agrega el short encontrado en los primeros dos bytes al short en los dos siguientes. Eso incluye tanto el primer como el cuarto carácter, por lo que, en una suposición, debería producir sus 12 valores distintos, y no implica extracciones de campo de bits que pueden no optimizarse bien. Luego, haga que la matriz del bucket[] coincidente tenga entradas de 64K, de las cuales solo 12 son alcanzadas. Si funciona bien, esas 12 entradas terminan ocupando parte de tu caché D y has intercambiado un puñado de operaciones aritméticas por un índice en una matriz más grande en caché.
Pero haga un perfil tanto antes como después de cualquier desorden acerca de tratar de hacer la aritmética más rápido, y no se moleste en optimizar dónde no ahorrará tiempo. (Sé que Pax lo sabe, pero es la advertencia obligatoria que se adjunta a cualquier discusión sobre optimización).
En ASCII, si toma el month[0] ^ month[2] ^ month[3] , obtendrá un hash único con un valor máximo de 95 (julio), que le permitirá reducir el tamaño de su tabla un poco (y un valor mínimo de 20 (mayo), por lo que una resta la vuelve a hacer más pequeña).
Lo mismo podría no ser cierto en EBCDIC, pero algo similar podría serlo.
Esto se prueba para EBDIC (CCSID 500), la tabla de 32 bytes (más pequeña que la suya, del mismo tamaño que la de x4u):
#define __ -1
static unsigned int hash(const char *str)
{
static unsigned char bucket[] = {
__, __, __, __, __, __, 1, 8,
__, 7, __, __, __, 3, __, __,
11, 6, __, __, 4, __, 2, __,
__, 0, __, 5, 9, __, __, 10,
}
return bucket[(unsigned int)(str[0]|str[3]<<1)&0x1f];
}
Estoy de acuerdo con los demás en que no hay mucho margen de mejora. Todo lo que puedo sugerir es una tabla de búsqueda más pequeña que funciona con el mismo número de operaciones que podrían hacer que permanezca más tiempo en la memoria caché de la CPU. Además, no se basa en los caracteres que llenan el espacio al final y funciona con cualquier mezcla de mayúsculas y minúsculas. Descubrí que agregar cierta solidez razonable contra los posibles cambios en los requisitos a menudo se amortiza en el futuro, especialmente cuando la implementación está optimizada hasta un punto en el que los pequeños cambios ya no son tan fáciles.
#define __ -1
static unsigned int hash (const char *str)
{
static unsigned char tab[] = {
__, __, 1, 11, __, __, __, __, 7, __, __, __, __, 6, 0, 5,
8, __, 2, 3, 9, __, 10, __, __, 4, __, __, __, __, __, __
};
return tab[ ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f ) ];
}
Esto funciona de manera similar a su idea original pero con menos espacio en blanco:
Month s[1] s[2] s[1].4 s[2].4-0 sum lookup
----- ------------ ------------ ------ -------- --- ------
Jan 61:0110 0001 6e:0110 1110 0 14 14 0
Feb 65:0110 0101 62:0110 0010 0 2 2 1
Mar 61:0110 0001 72:0111 0010 0 18 18 2
Apr 70:0111 0000 72:0111 0010 1 18 19 3
May 61:0110 0001 79:0111 1001 0 25 25 4
Jun 75:0111 0101 6e:0110 1110 1 14 15 5
Jul 75:0111 0101 6c:0110 1100 1 12 13 6
Aug 75:0111 0101 67:0110 0111 1 7 8 7
Sep 65:0110 0101 70:0111 0000 0 16 16 8
Oct 63:0110 0011 74:0111 0100 0 20 20 9
Nov 6f:0110 1111 76:0111 0110 0 22 22 10
Dec 65:0110 0101 63:0110 0111 0 3 3 11
^ ^ ^^^^
bits: 4 4 3210
Ok, como todos en SO, estoy en el mismo para el representante ...; *) Como escribí en los comentarios anteriores, el extremo inferior de sus arquitecturas de destino tiene un tamaño de línea de caché de 256 bytes, por lo que podría terminar con alguna basura de caché en sus búsquedas de tablas (su tabla tiene más de 256 bytes). Un intento de plegar la tabla con un poco de truco de bits barato podría obtener algún rendimiento.
He estado jugando con tus datos. También tiene la opción de las columnas 2 y 3. Sin embargo, todavía no he encontrado una manera de obtener eso por debajo de 8 bits.
... y, como siempre, perfil, asegúrese de que sea el mejor punto para aplicar esfuerzo, y vuelva a hacer el perfil después, asegúrese de que sea más rápido.
... y estás leyendo más de una línea a la vez, ¿verdad? Los tamaños de registros fijos son buenos de esa manera, ya que no tiene que buscar separadores (nuevas líneas), y puede leer una gran parte de ellos a la vez.
Puedes reducir el tamaño de la matriz usando:
#define __ -1
static unsigned int hash (const char *str) {
static unsigned char alloc_to[] = {
// A S D F J M N O
__, __, __, __, __, __, __, __, __, __, __, __, __, 4, __, __, // space
__, __, __, __, __, __, __, __, __, __, __, __, __, 2, __, __, // c
__, __, __, __, 11, __, __, __, __, __, 5, __, __, __, 10, __, // e
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, 3, __, __, __, __, __, __, __, __, __, __, __, __, __, __, // i
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, 9, // o
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, 1, __, __, __, __, __, __, __, __, __, // r
__, 7, __, 8, __, __, __, __, __, __, 0, __, __, __, __, __, // t/u
__, __, __, __, __, __, __, __, __, __, __, __, __, __, __, __, //
__, __, __, __, __, __, __, __, __, __, 6, __, __, __, __, __ // y
};
return alloc_to[((unsigned int)(str[3]&0x1e)<<3)|(str[0]&0xf)];
}
que lo cambia de 16 por 26 a 16 por 13.
EDITAR
Si, como lo sugieren otras publicaciones, sus cadenas ESTÁN alineadas, de modo que pueda usarlas como cortos, puede agregar el primer y segundo cortocircuito, xo los dos bytes juntos y tendrá una clave única de 8 bits (bueno, siete, en realidad). Podría valer la pena su tiempo también. Sin embargo, esto es ASCII, por lo que podría no funcionar en EBCDIC. En ASCII, las teclas resultan ser:
6e Jan
7f Feb
7b Mar
6a Apr
47 May
62 Jun
58 Jul
42 Aug
1a Sep
11 Oct
10 Nov
6d Dec
Parece lo suficientemente agradable para mí. La pregunta es si la función hash en sí misma es un cuello de botella suficiente para justificar los esfuerzos en curso de eliminar de ella una o dos operaciones binarias más simples. Dado que el acceso a los archivos parece estar involucrado, lo dudo, sin conocer ningún detalle sobre el procesamiento general, por supuesto.
EDITAR:
Tal vez podría ver si encuentra algún par de caracteres que resulten en bits inferiores únicos (4, 5 o 6) cuando se agreguen:
(str[1] + str[2]) & 0x1f
Si la adición no funciona, quizás una de las otras operaciones & | ^ & | ^ . Si esto no ayuda, tal vez usando tres caracteres.