Есть ли способ сделать этот поиск быстрее?
У меня есть требование (очень) быстро обрабатывать строки ограниченного диапазона, подсчитывая их значения. Входной файл имеет форму:
January 7
March 22
September 87
March 36
и так далее. Поскольку ширина линий одинакова, я могу просто прочитать в строке fread достаточно быстро, и я разработал идеальную функцию хеширования, которая работает, но я хотел посмотреть, может ли кто-нибудь дать какой-нибудь совет, как сделать это еще быстрее. Я буду профилировать каждое предложение, чтобы увидеть, как оно идет.
Функция хеширования основана на названии месяца, чтобы обеспечить быстрое распределение значения в сегменте. Потерпи меня здесь. Сначала я выяснил минимальное количество символов для идеального хэша:
January
February
March
April
May
June
July
August
September
October
November
December
Имейте в виду, что все месяцы состоят из девяти символов, потому что у меня есть вся строка ввода.
К сожалению, нет ни одного столбца, чтобы пометить месяц как уникальный. Колонка 1 дубликатов J столбец 2 дубликаты a столбец 3 дубликаты r столбец 4 дубликаты u и столбцы 5 и далее дублируют <space> (есть другие дубликаты, но одного достаточно, чтобы предотвратить хеш-ключ с одним столбцом).
Однако, используя первый и четвертый столбец, я получаю значения Ju, Fr, Mc, Ai, M<space>, Je, Jy, Au, St, Oo, Ne а также De, которые являются уникальными. В этом файле не будет недопустимых значений, поэтому мне не нужно беспокоиться о неправильных сегментах для входных данных.
Просматривая шестнадцатеричные коды для символов, я обнаружил, что могу получить низкие уникальные значения, просто используя AND со стратегическими значениями:
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
и это позволило мне настроить статический массив для создания (надеюсь) слепо-быстрой хэш-функции:
#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)];
}
Тестирование с помощью кода:
#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;
}
показывает, что это функционально правильно:
January -> 0
February -> 1
March -> 2
April -> 3
May -> 4
June -> 5
July -> 6
August -> 7
September -> 8
October -> 9
November -> 10
December -> 11
но я хочу знать, можно ли сделать это быстрее.
Есть предложения? Я открыт для любых простых оптимизаций или даже полного переписывания, если с моей функцией хеширования есть что-то плохое.
Я не думаю, что это так важно, но окончательная версия будет использовать EBCDIC. Теория все еще остается в силе, но операция И может немного измениться, поскольку символы имеют разные кодовые точки. Я буду рад любой помощи только на фронте ASCII, так как я уверен, что любой совет, который будет предложен, будет хорошо переведен в EBCDIC.
8 ответов
Вот самая маленькая последовательность, которую я мог найти для 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
Я согласен с другими, что не так много возможностей для улучшения. Все, что я могу предложить, - это меньшая справочная таблица, которая работает с тем же числом операций, что может сделать ее дольше сохраняющейся в кэше ЦП. Кроме того, он не полагается на символы заполнения пробела в конце и работает с любой смесью прописных и строчных букв. Я обнаружил, что добавление некоторой разумной устойчивости к возможным изменениям требований часто окупается в будущем, особенно когда реализация оптимизирована до такой степени, что небольшие изменения уже не так просты.
#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
Это проверено для 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];
}
Я бы начал с подробного описания вашего более крупного процесса, чтобы убедиться, что вы не участвуете в преждевременной оптимизации.
На первый взгляд это выглядит довольно быстро, но если память действительно дешевая, может быть лучше просто использовать еще более редкий массив и позволить вашему кешу выполнять часть работы. Например (и размышляя здесь), что если вы просто добавите short найдено в первых двух байтах short в следующие два. Это включает в себя как первый, так и четвертый символы, так что, по-видимому, он должен генерировать ваши 12 различных значений, и он не требует извлечения битовых полей, которые могут плохо оптимизироваться. Затем сделайте соответствие bucket[] В массиве имеется 64 тыс. записей, из которых только 12 попаданий. Если все работает правильно, эти 12 записей в итоге занимают часть вашего D-кэша, и вы обменяли несколько арифметических операций на индекс в кэшированном массиве большего размера.
Но ведите профиль как до, так и после любого взлома, пытаясь сделать арифметику быстрее, и не пытайтесь оптимизировать, где это не сэкономит время. (Я знаю, что Пакс знает об этом, но это обязательное предупреждение при любом обсуждении оптимизации.)
Хорошо, как и все на 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
В ASCII, если вы берете month[0] ^ month[2] ^ month[3] затем вы получите уникальный хеш с максимальным значением 95 (июль), который должен позволить вам значительно уменьшить размер таблицы (и минимальное значение 20 (май), поэтому вычитание снова уменьшит его).
То же самое не может быть правдой в EBCDIC, но может быть что-то похожее.
Выглядит достаточно хорошо для меня. Вопрос в том, является ли сама хеш-функция достаточно узким местом, чтобы оправдать продолжающиеся усилия по устранению одной или двух более простых двоичных операций из нее. Учитывая, что доступ к файлам, по-видимому, связан, я сомневаюсь в этом, конечно, не зная никаких подробностей об общей обработке.
РЕДАКТИРОВАТЬ:
Может быть, вы могли бы увидеть, если вы найдете любую пару символов, которые приводят к уникальным младшим битам (4, 5 или 6) при добавлении:
(str[1] + str[2]) & 0x1f
Если дополнение не будет, возможно, одна из других операций & | ^, Если это не поможет, возможно, с использованием трех символов.
Вы действительно нуждаетесь в сопоставлении между хешем и индексом месяца, чтобы сделать подсчет? Вы можете исключить поиск, если вместо того, чтобы возвращать месяц, вы вернули хеш и использовать его для подсчета. В ответе x4u последняя строка хэш-функции может выглядеть так:
return ( ( str[ 1 ] >> 4 ) & 1 ) + ( str[ 2 ] & 0x1f )
и вы все равно сможете делать суммы, сортируя результаты только в конце, а не внутри цикла.