Есть ли способ сделать этот хэш-поиск быстрее?

Ответ 1

Здесь самая маленькая последовательность, которую я смог найти для EBCDIC-US:

Он содержит 24 элемента в ведре и использует только 2 операции для вычисления индекса:

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 ])];
}

Во-вторых, 25 предметов с 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 ])];
}

(На самом деле, вкладка [] должна быть здесь 32 записи, потому что 0x1f может генерировать переполнение для неправильных входов).

Обновление от Pax: для чего это стоит, первый вариант отлично работал для кода EBCDIC на стр. 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

Ответ 2

Я согласен с остальными, что возможностей для улучшения нет. Все, что я могу предложить, - это небольшая таблица поиска, которая работает с тем же количеством операций, которые могут задержать ее дольше в кэше CPU. Кроме того, он не полагается на заполняющие пробелы пробелы в конце, и он работает с любой смесью символов верхнего и нижнего регистра. Я обнаружил, что добавление некоторой разумной устойчивости к вероятным изменениям требований часто окупается в будущем, особенно когда реализация оптимизирована до точки, где небольшие изменения не так уж и легки.

#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 ) ];
}

Это похоже на вашу оригинальную идею, но с меньшим количеством пробелов:

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

Ответ 3

Это проверено для EBDIC (CCSID 500), таблица 32 байт (меньше вашего, того же размера, что и 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];
}

Ответ 4

Я бы начал с подробного профиля вашего более крупного процесса, чтобы убедиться, что вы не занимаетесь преждевременной оптимизацией.

Это выглядит довольно быстро на первый взгляд, но если память действительно дешевая, может быть лучше просто использовать еще более разреженный массив и позволить вашему кешу выполнять некоторую работу. Например (и придумывая здесь манжету), что, если вы просто добавите short, найденный в первых двух байтах, к short в следующих двух. Это включает в себя как первый, так и четвертый символы, поэтому при угадывании он должен генерировать ваши 12 различных значений, и он не включает экстракции битового поля, которые могут не оптимизироваться хорошо. Затем сделайте сопоставление массива bucket[] с 64 КБ, только 12 из которых когда-либо попадаются. Если это правильно, те 12 записей в конечном итоге занимают часть вашего кеша D, и вы обменяли несколько арифметических операций для индекса в кешированный более крупный массив.

Но делайте профили как до, так и после каких-либо ошибок, пытаясь сделать арифметику быстрее, и не беспокойтесь, оптимизируя, где это фактически не сэкономит время. (Я знаю, что Pax знает это, но его обязательное предупреждение придается любому обсуждению оптимизации.)

Ответ 5

Хорошо, так как все в SO, я все в нем для rep..; *) Как я уже писал в комментариях выше, нижний конец ваших целевых архитектур имеет размер кеша в 256 байт, поэтому вы можете в конечном итоге с помощью кэширования в ваших табличных поисках (ваша таблица более 256 байтов). Попытка сложить таблицу, используя какой-то дешевый бит-трюк, может на самом деле получить некоторую производительность.

Я играл с вашими данными. У вас также есть опция для столбцов 2 и 3. Не удалось выяснить, что до 8 бит, хотя.

... и, как всегда, профиль, убедитесь, что это лучшая точка для приложения усилий, и профиль снова после этого, убедитесь, что он быстрее.

... и вы читаете несколько строк за раз, верно? Фиксированные размеры записей хороши таким образом, что вам не нужно искать разделители (новые строки), и вы можете читать их большой объем за раз.

Вы можете уменьшить размер массива, используя:

#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)];
}

который меняет его с 16 на 26 на 16 на 13.

ИЗМЕНИТЬ

Если, как было предложено другими сообщениями, ваши строки ARE выровнены, так что вы можете использовать их как шорты, вы можете добавить первый и второй короткие, xor два байта вместе, и у вас будет уникальный 8-битный ключ (ну, семь, фактически). Возможно, стоит и ваше время. Это ASCII, хотя, возможно, не работает в EBCDIC. В ASCII ключи оказываются:

6e Jan
7f Feb
7b Mar
6a Apr
47 May
62 Jun
58 Jul
42 Aug
1a Sep
11 Oct
10 Nov
6d Dec

Ответ 6

Выглядит неплохо для меня. Вопрос в том, достаточно ли самой хэш-функции узкого места, чтобы оправдать продолжающиеся усилия по устранению одной или двух более простых двоичных операций. Учитывая, что доступ к файлам, похоже, задействован, я сомневаюсь, конечно, не зная подробностей об общей обработке.

EDIT:

Возможно, вы могли увидеть, если вы найдете пару символов, которые при добавлении будут иметь уникальные младшие биты (4, 5 или 6):

(str[1] + str[2]) & 0x1f

Если сложение не будет выполнено, возможно, одна из других операций & | ^. Если это не поможет, возможно, используя три символа.

Ответ 7

В ASCII, если вы берете month[0] ^ month[2] ^ month[3], тогда вы получаете уникальный хеш с максимальным значением 95 (июль), что должно позволить вам уменьшить размер таблицы справедливым битом (и минимальным значением 20 (май), поэтому вычитание уменьшает его снова).

То же самое может быть неверно в EBCDIC, но что-то подобное может быть.

Ответ 8

Вам действительно нужно сопоставление между хэшем и индексом месяца, чтобы сделать подсчет? Вы можете устранить поиск, если вместо возвращения месяца вы вернули хэш и используете его для подсчета голосов. В x4u answer последняя строка хеш-функции может выглядеть как

return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )

и вы все равно сможете делать суммы, сортируя результаты только в конце, а не внутри цикла.