UPD: Дададада strcmp в общих случаях быстреее, не пишите мне про это, всё есть в треде, спаааасииибо ))
У кого есть список коллизий хеш алгоритма djb2? Выбрал его как замену strcmp() ибо не смотря на все оптимизации с SSE2 strcmp() проигрывает почти в 4 раза.
[DEBUG] (src/engine.c:timer_start:112) Timer 0 'strcompare' Start: 0.000000
[DEBUG] (src/engine.c:timer_stop:133) Timer 0 'end' End: 0.189000
[DEBUG] (src/engine.c:timer_start:112) Timer 0 'strhash-compare' Start: 0.000000
[DEBUG] (src/engine.c:timer_stop:133) Timer 0 'end' End: 0.053000
Ну и опционально, приведу код может кто ещё подскажет как ускорить
Сейчас поиск элемента в материале такой
1000000 интераций поиска 0.189000 секунд cpu MHz: 3501.001
material_item material_entry_item(material_entry* me, char* name) {
for(int i = 0; i < me->num_items; i++){
if(me->names[i][0] == name[0]){
if (strcmp(me->names[i], name) == 0){
return me->items[i];
}}
}
material_item empty;
memset(&empty, 0, sizeof(empty));
return empty;
}
Оно же с хешем djb2 1000000 интераций поиска 0.053000 секунды cpu MHz: 3501.009
long
hash(char *str)/*djb2*/
{
register long hash = 5381;
register int c;
while ((c = *str++))
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
material_item material_entry_item2(material_entry* me, char* name) {
for(int i = 0; i < me->num_items; i++){
if(me->names[i][0] == name[0]){
if(hash(me->names[i]) == hash(name)){
return me->items[i];
}}
}
material_item empty;
memset(&empty, 0, sizeof(empty));
return empty;
}
Сам файл материала выглядит так он загружается в в стуктуру material_entry каждая строка вносится в union material_item именно поиск item мы и выполняем по имени
float sadfsdf = 0
int sadfsadf = 0
bool dfgdfgdf = 0
float asdfaksdfhaskdjf = 0
bool sdfasdjfioasdjf = 0
int fsdfaefasdfasdfas = 0
float sadfasdfaefsf = 0
float aasdfasdfsadf = 0
float asiodufhaoiuefhw = 0
bool 654654sadfasdf = 0
int fq34tgsergwtysdfgg = 0
float asdfasdfsdfasfwe = 0
bool sdfggesrdf = 0
int asdfgrstghrth = 0
int atyehdfdfhdfgh = 0
float adtghrt6htrh = 0
int test_value = 333
Ну первое что приходит на ум это добавить в material_entry поле hash куда делать предрасчёт хеша так мы сократим время поиска ещё в ~двое. Ну может у кого иди какае ещё будет как сделать ещё быстрее (без openmp и прочего параллелизма) Но основной вопрос про коллизии djb2, хочется их знать и проверять на этапе загрузки материалов.
Оригинальный код тут https://github.com/orangeduck/Corange/blob/master/src/assets/material.c https://github.com/orangeduck/Corange/blob/master/include/assets/material.h
Короче ладно, пока остановлюсь на djb2 вместо strcmp проверка коллизий будет осуществляться через функцию которая будет аккумулировать в себе все уникальные строки имён материалов (их у меня десятка два, а будет может ещё десяток так что норм) и при загрузке каждого нового материала будет проверять есть ли коллизия хеша между всеми теми что есть и новыми, вот сам код если кому надо будет.
чекер коллизий (без проверок аллокации, так что ну вы поняли) акоммулирует в себе всё уникальное чекает входящее и сохраняет в себе для последующих сравнений
void hash_cheker(char * str)
{
static char ** hash_cheker_storage = NULL;
static long hash_cheker_storage_num = 0;
if(hash_cheker_storage == NULL)
{
hash_cheker_storage_num++;
hash_cheker_storage = malloc(sizeof(char**) * hash_cheker_storage_num+1);
hash_cheker_storage[hash_cheker_storage_num-1] = malloc(sizeof(char)* strlen(str));
memset(hash_cheker_storage[hash_cheker_storage_num-1],'\0',strlen(str));
strcat(hash_cheker_storage[hash_cheker_storage_num-1],str);
debug("HASH CHECK OK: %s ",str);
return;
}
bool new_elem = false;
for (int i = 0; i < hash_cheker_storage_num; i++)
{
if(strcmp(hash_cheker_storage[i],str) == 0)
{
return;
};
};
for (int i = 0; i < hash_cheker_storage_num; i++)
{
if(hash(hash_cheker_storage[i]) == hash(str))
{
error("Сollision Hash between '%s' (%ld) and '%s' (%ld) choose another name for '%s'",
hash_cheker_storage[i],hash(hash_cheker_storage[i]),
str,hash(str),
str);
return;
};
};
hash_cheker_storage_num++;
hash_cheker_storage = realloc(hash_cheker_storage,sizeof(char**) * hash_cheker_storage_num+1);
hash_cheker_storage[hash_cheker_storage_num-1] = malloc(sizeof(char)* strlen(str));
memset(hash_cheker_storage[hash_cheker_storage_num-1],'\0',strlen(str));
strcat(hash_cheker_storage[hash_cheker_storage_num-1],str);
debug("HASH CHECK OK: %s ",str);
for (int i = 0; i < hash_cheker_storage_num; ++i)
{
debug("HASH: %-10s = [%ld]",hash_cheker_storage[i],hash(hash_cheker_storage[i]));
}
}
А вот вся суть
[DEBUG] (main.c:hash_cheker:78) HASH CHECK OK: asdfgrstghrth
[DEBUG] (main.c:hash_cheker:81) HASH: sadfsdf = [229482278995104]
[DEBUG] (main.c:hash_cheker:81) HASH: sadfsadf = [7572915206835201]
[DEBUG] (main.c:hash_cheker:81) HASH: dfgdfgdf = [7572282502104081]
[DEBUG] (main.c:hash_cheker:81) HASH: asdfaksdfhaskdjf = [1788434361038682215]
[DEBUG] (main.c:hash_cheker:81) HASH: sdfasdjfioasdjf = [-531356999790002134]
[DEBUG] (main.c:hash_cheker:81) HASH: fsdfaefasdfasdfas = [2674916009048082468]
[DEBUG] (main.c:hash_cheker:81) HASH: sadfasdfaefsf = [3622462406116730534]
[DEBUG] (main.c:hash_cheker:81) HASH: aasdfasdfsadf = [-7929917643305991168]
[DEBUG] (main.c:hash_cheker:81) HASH: asiodufhaoiuefhw = [-2980351034500385520]
[DEBUG] (main.c:hash_cheker:81) HASH: 654654sadfasdf = [6604793431210835103]
[DEBUG] (main.c:hash_cheker:81) HASH: fq34tgsergwtysdfgg = [7202372098568309662]
[DEBUG] (main.c:hash_cheker:81) HASH: asdfasdfsdfasfwe = [1799994182520512308]
[DEBUG] (main.c:hash_cheker:81) HASH: sdfggesrdf = [8246908965533417028]
[DEBUG] (main.c:hash_cheker:81) HASH: asdfgrstghrth = [-7043038456319946496]
[DEBUG] (main.c:hash_cheker:78) HASH CHECK OK: atyehdfdfhdfgh
Сам материал же выглядит так
material_item material_entry_item2(material_entry* me, char* name) {
register long hash_name = hash(name);
for(register int i = 0; i < me->num_items; i++){
if(me->hash[i] == hash_name){ //me->hash[i] предрасчитан заранее на этапе инициализации material_entry
return me->items[i];
}
}
material_item empty;
memset(&empty, 0, sizeof(empty));
return empty;
}
UDP:
Правда я лоханулся ибо доступ к аллоцируемой памяти дольше и для предрасчёта надо брать статичный массив, а в нём уже ссылаться на позицию item. Ай да и ладно, пока что химичу, основной вопрос с колизиями решён, тему закрою. Но в целом, если использовать #pragma omp parallel for для поиска по strcmp() то эта комбина рвёт как тузик грелку поиск по хешу.
