Существует ли способ сделать этот поиск хеша немного быстрее?

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

#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

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

Это может быть не так в EBCDIC, но может быть что-то подобное.

Это проверено для 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];
}

Хорошо, как и все в SO, я готов к представлению ..; *) Как я писал в комментариях выше, нижняя часть ваших целевых архитектур имеет размер строки кэша 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.

РЕДАКТИРОВАТЬ

Если, как предлагается в других сообщениях, ваши строки ВЫРАВНИВАЮТСЯ, чтобы вы могли использовать их как короткие, вы можете добавить первый и второй короткие, 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

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

EDIT:

Может быть, вы можете посмотреть, не найдется ли какая-нибудь пара символов, при сложении которых получаются уникальные младшие биты (4, 5 или 6):

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

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

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

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

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

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

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

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