LINUX.ORG.RU

Все извесные djb2 коллизии

 , , , ,


2

2

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() то эта комбина рвёт как тузик грелку поиск по хешу.

Deleted

Ответ на: комментарий от anonymous

Да понятное дело, материалы не рандомные сомволы содержат, а чёткий набор только того что поддерживается вот дефолтный материал в движке, любой объект в игре имеет их все


bool    surfaces_numbers = false
bool    envcube_dynamic  = false

shader  vertex           = $ASSETS/shaders/basic.vs
shader  fragment         = $ASSETS/shaders/basic.fs
texture diffuse_map      = $ASSETS/textures/orange_peel.dds
texture normal_map       = $ASSETS/textures/orange_peel_nm.dds
texture specular_map     = $ASSETS/textures/orange_peel_s.dds
texture parallax_map     = $ASSETS/textures/orange_peel_s.dds 
texture reflecting_map   = $ASSETS/textures/reflecting.tga
texture refracting_map   = $ASSETS/textures/refracting.tga
texture envcube_map      = $ASSETS/water/cube_sea.dds

float transparency_level = 0

float reflecting_level  = 0
int   reflecting_chanel = 1
float refracting_level  = 0
int   refracting_chanel = 1
int   specular_chanel   = 1
int   repeat_level      = 0
float glossiness_level  = 10
float bumpiness_level   = 3
float specular_level    = 1
float parallax_level    = 0
int   parallax_layers   = 22
int   parallax_type     = 3
int   parallax_chanel   = 1
bool  parallax_offlim   = true
bool  parallax_filter   = false 
float alpha_filter      = 0
int   material          = 2

Тоесть ведётся поиск только по ним, я конечно их проверю, но потом я буду добавлять ещё опции и хотелось бы не парится и имена где то проверять на колизии заранее, ну а в предварительную проверку сунуть пару сотен общих слов поторые подвержены коллизиям. Прям всё всё мне не надо проверять.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Harald

Чёт я сомневаюсь, но сейчас налабаю и проверю

Deleted ()
Ответ на: комментарий от Deleted

Оно у тебя в игровом цикле каждый раз выполняется? Если нет, то смысл оптимизировать? А если оптимизировать, то логичнее на какую-то более компактную структуру данных перейти, с логарифмическим временем поиска вместо линейного

Harald ★★★★★ ()
Ответ на: комментарий от Harald

Да, отсортировать по ключу при вставке в список (добавить в структурку элементов списка prev и next указатели на пред и след элементы). Тогда можно не цикл, а войти в центр списка и по первому символу определить вверх или вниз идти дальше, за каждый шаг сокращая диапазон поиска вдвое. Если символ совпал, то сравнивать по второму и т.д.

deep-purple ★★★★★ ()
Ответ на: комментарий от Harald

Там где было можно я сделал 1 раз и оптимизировать там не надо, а вот рендер да каждый фрейм для каждого объекта сцены ищет элемент материала по имени.

Первое что важно, убрать строки нельзя, ибо есть «динамический рендер» я могу написать полностью свой материал со своими именами и шейдерами и скормить его движку, он его распарсит и сожрёт обработав. Это я к тому да, можно отдельно рендер просто на статичные структуры перевести где поиска вообще не будет, нужно уже заранее будет лежать в нужных индексах, но придётся отказаться от рендера который строится на основе пользовательского материала, ну как бы проще сказать, я хочу свечение объекта я пишу шейдер и описываю его параметры в материале кормлю движку он хавает и после основного рендера объекта к нему применяется ещё эффект свечения, так как имена материалов могут быть любыми поиск по ним убрать нельзя и индексы им заранее проставить нельзя

Deleted ()
Ответ на: комментарий от Deleted

рендер да каждый фрейм для каждого объекта сцены ищет элемент материала по имени

В объекте должен быть уже указатель на материал, а не его имя.

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

добавить в структурку элементов списка prev и next указатели на пред и след элементы

Нет, оптимальнее разместить структурки в одну сосиску и получать доступ к нужным по смещению указателя.

deep-purple ★★★★★ ()
Ответ на: комментарий от deep-purple

Там и есть указатель, имена у элементов материала выглядит так

static_object * so; //передаётся рендеру

so->renderable //меш
so->material   //материал

renderable и material это хандлеры ассетов в них указатель на структуры

so->material->ptr; // хранит материал, тоесть доступ к структуре material прямой.

Далее так, у каждого renderable есть renderable_surface тоесть 
модель одна человек а честей у него много, голова, рука, нога, у каждого renderable_surface есть свой material_entry

so->rendetable->renderable_surface[i]
so->material->ptr->material_entry[i] 

И уже в material_enry лежит массив c union`нами в которых лежат параметры

/*тут не реальный вид, а просто более наглядный*/
so->material->ptr->material_entry[i]->material_item->names[j];
so->material->ptr->material_entry[i]->material_item->types[j];
so->material->ptr->material_entry[i]->material_item->items[j];

Поиск ведётся по names возвращается это


typedef union {
  int  as_int;
  bool as_bool;
  float as_float;
  vec2 as_vec2;
  vec3 as_vec3;
  vec4 as_vec4;
  asset_hndl as_asset;
} material_item;

Нужный элемент извлекается и передаётся шейдеру, важно ещё то что шейдеру нужно отдавать имена в виде строк что бы получить локацию данных в слинкованом шейдере и уже потом отдать по этому адресу значение.
Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Harald

Блин, спасибо и сорян за путаницу :D

Deleted ()
Ответ на: комментарий от Harald

Линейный поиск сасает, если я для имён в материале захочу префиксы использовать типа mat_elemname и он будет проходить по всем mat_ что уже 4 сравния, а хардкорить смещение по ним не могу, это уже прибивание параметров гвоздями, а фича в том что всё гибко на данный момент ))

Пока что сасает всё кроме хеша ибо там я 1 раз вычисляю хеш строки, а далее у меня константное время сравнения с хешами material_item, сравнивать инты в разы быстрее чем перебирать элементы строк (а если перебирать тут быстрее strcmp() ибо он юзает SSE2 ускорялку и сравнивает все символы сразу вроде). Ну не знаю может как в датабазах из строк построить граф на указателях и спускаться по нему.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 4)

Тебе надо почитать про проектирование баз данных. Как там строят отношения 1:1, 1:N, M:N.
По сути. Заведи таблицу «ИменаСвойствМатериала», куда будешь добавлять новые имена при загрузке материалов в движок. В материале будешь ссылаться на индекс имени в таблице. Сравнивать будешь индексы(целые числа). Прикинь, это тоже хеширование, да еще правильное и однозначное. Будет чуть более долгая загрузука материалов в движок, но получишь независимое он длины имени сравнение во время работы.

anonymous ()
Ответ на: комментарий от beastie

Интересно, спасибо. Ну он там прав конечно, надо не слепо брать что-то и полностью не понимая как это работает использовать. С djb2 я экспериментировал. Пробовал другие. Но мне важна скорость, коллизии я буду проверять заранее у меня лишь пару десятков наборов строк и нет труда проверить все коллизии на этапе загрузки. А вот для хеширования большого количества разнообразных данных я бы побоялся, коллизии не проверить, а словить трудноуловимую ошибку легко. Так что в моём случае, норм. Хотя сейчас если в локальных тестах поиск по хешу быстрее то при переносе функцй в библиотеку и вызове их от туда всё медленней, даже если она статическая -O3 меня запутало.

Deleted ()
Ответ на: комментарий от anonymous

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

Deleted ()
Ответ на: комментарий от Deleted

Я специально показал узкоспециализированное решение. Ты можешь вместо таблицы «имен свойств» сделать таблицу «свойство материала» (расширить до такой таблицы), содержащая записи/структуры с именем, типом, парсером значения/валидатором, обработчиком-генератором значений для 3D-движка по значению свойства.

anonymous ()

Владимир

А вот так:

// ----------------
//
int __cdecl strcmpnew (
 unsigned char  *src,
 unsigned char  *dst
) {

 INT  i = 0;

 while ( src[ i ]  &&
         dst[ i ]
       ) {

  if  ( src[ i ] - dst[ i ] )
   return  1;

  i++;

 }

 return 0;

}                                                          // int __cdecl strcmpnew (    

anonymous ()
Ответ на: комментарий от anonymous

1000000 сравнений по 17 полям gcc -O3

strcmp - 0.043000 секунды strcmpnew - 0.054000 секунды

Deleted ()
Ответ на: комментарий от Harald

Сразу впиливать не надо, надо взять файлик который я указал в шапке, вбить всё в таблицу и вызвать 1000000 итераций получения значения ключа test_value по имени "test_value" и уже посмотрев на результат призадуматься )) Хотя будет странно совать DB в 3D рендерер ))))))))))) Но как минимум ради прикола можно затестить.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 2)
Ответ на: комментарий от Deleted

Блин пусть увеличат время редактирвания!

Сразу впиливать не надо, надо взять файлик который я указал в шапке, вбить всё в таблицу и вызвать 1000000 итераций получения значения ключа test_value по имени "test_value" и уже посмотрев на результат призадуматься )) Хотя будет странно совать DB в 3D рендерер ))))))))))) Но как минимум ради прикола можно затестить. Но мне чёт лень вот прямо сейчас, потому что я только что поменял возврат не по значению, а указателю в функции поиска и эммм мой вариант с хешем сасает :D И вообще, я знатно лоханулся когда я тестил я функции хеша и поиска хранил в том же исходном файле что и сам тест с и поиск в миллион итераций выполнялся за 0.016000 секунды с возвратом по значению когда же я перенёс всё в библиотеку собрал её и слинковал статически с тестом и вызвал от туда я получил 0.116000 секунды с возвратом по значению O_o и 0.063000 секунды с возвратом по указателю и при этом старый поиск через strcmp возвратом по указателю выдаёт уже 0.054000 секунды на миллион итераций что ставит на нет все потуги с хешами. Но! мне интересно сфигали если имплементация и вызов в 1 объектном файле у меня 0.016000 а если в другом 0.116000 это с -O3 короче хеш мне пригодится, но вот прямо сейчас, всё не имеет смысла strcmp выходит быстрее, а узкое место было в возврате то жирный union а то указатель на него. Короче не знаю. Может я где косячу надо перепроверять

Deleted ()

Re: Блин пусть увеличат время редактирвания!

Владимир

Хеш и должен был быть дольше.
Для вычисления хэш, используются все символы каждой из строк.
Если строки не равны, то strcmp выполняет меньше итераций /да и арифметики меньше/.

Пожалуй сравнение можно было бы ускорить, если бы были известны заранее
длины строк /то бишь на входе, что-то типа CString/.
Но согласно решаемой задачи это не ваш случай.

anonymous ()

В точку, я выше написал что сильно налажал с тестами. Но! Если имплементить всё в одной цели компиляции то выигрывает хеш, gcc при -O3 очень хорошо всё разруливает когда весь код вместе, а вот при вызове из вне приходится исполнять как есть, даже инлайн не спасёт ибо дело не в том. Так что если полагаться на оптимизацию компилятора и весь код в одном компилируемом файле, то будет почти 4х кратный прирост, если из вне всё ломается и либо разницы нет (особенно если намеренно снизить частоту CPU до констанных тактов например 800Mz) и всё идёт вровень почти ибо да и тут strcmp чуть выигрывает. Но и тут не всё так гладко, если я отрубаю из своих 6 ядер 5. Оставляя 1 ядро на с принудительной частотой в 800Mz то выигрывает снова хеш при условии что при условии что весь код хеша и функция сравнения находятся в том же компилируемом файле что и рабочий код, но это при условии обязательного -O3 и ручки к нему в молитве что бы оптимизация таки была. Хотя даже тут не всё гладко если при использовании возврата значения по указателю из функции которая в библиотеке то всё быстрее по понятным причинам, если же всё в одном файле то время двойного доступа к памяти из за использования указателя накладывает расходы и получается медлене, то есть для локального вызова лучше использовать возврат по значению даже для жирного union, видать gcc видит что я использую его только как int и приводит к int запихивая его вообще в регистр. Короче, нечего выёживатся strcmp вполне себе норм (жёстко оптимизирован (спасибо разрабам) и переплюнуть его сложно для общего случая), поверху ещё openmp и всё, так или иначе вот прямо сейчас я не упираюсь в редере с скорость получения данных материала, поэтому что-то ещё делать смысла нет, разве что завесить openmp что бы был дополнительный бюджет миллисекунд.

Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)

Выбрал его как замену strcmp() ибо не смотря на все оптимизации с SSE2 strcmp() проигрывает почти в 4 раза.

Полная и нелепая чушь. Ты явно измерял что угодно, только не то, что нужно.

anonymous ()
Ответ на: комментарий от anonymous

Читай выше, я описал что налажал с тестами, но в определённых ситуациях хеш идёт в ровень, но в большинстве случаев да strcmp быстрее. 1000000 итераций поиска.

[DEBUG] (Corange/src/casset.c:file_load:282) Loading: '/home/dron/material.mat'
[DEBUG] (speedtest.c:main:37) ================================================
[DEBUG] (Corange/src/cengine.c:timer_start:112) Timer 0 'STRCMP FIND ITEM' Start: 0.000000
[DEBUG] (Corange/src/cengine.c:timer_stop:133) Timer 0 '===>' End: 0.301000
[DEBUG] (speedtest.c:main:49) =================================================
[DEBUG] (Corange/src/cengine.c:timer_start:112) Timer 0 'HASHCMP FIND ITEM' Start: 0.000000
[DEBUG] (Corange/src/cengine.c:timer_stop:133) Timer 0 '===>' End: 0.374000
[DEBUG] (speedtest.c:main:61) 333 333
[DEBUG] (Corange/src/casset.c:delete_bucket_list:215) Unloading: '/home/dron/material.mat'

Оригинального кода теста уже нет, всё стёр, также нет предрасчёта хеша так что в этом тесте он молотится не 1 раз, а на каждое имя так что если убрать лишние расчёты хеша то они будут идти нос в нос

#include "corange.h"

unsigned long material_hash(char *str)
{
    unsigned long hash = 5381;
    int c;
    while ((c = *str++))
    hash = ((hash << 5) + hash) + c;
    return hash;
}

material_item   material_entry_item_hash(material_entry * me, char* name)
{
  long hash = material_hash(name);
  for(int i = 0; i < me->num_items; i++){
    if(material_hash(me->names[i]) == hash){
       return me->items[i];
    };
  };

  static material_item empty = {0};
  memset(&empty, 0, sizeof(empty));
  return  empty;
}


int main(int argc, char *argv[])
{
    corange_init("/home/$USER/Corange/assets_core");
    file_load(P("./material.mat"));
    material * m = asset_get(P("./material.mat"));
    material_entry * me = material_get_entry(m,0);



    long  str_cmp_return = 0;
    debug("================================================");
    timer str_cmp = timer_start(0,"STRCMP FIND ITEM");
    for (int i = 0; i < 1000000; i++)
    {
       if(material_entry_item(me,"test_value").as_int == 333)
       {
        str_cmp_return = 333;
       }
    }
    timer_stop(str_cmp,"===>");

    long  hash_cmp_return = 0;
    debug("=================================================");
    timer hash_cmp = timer_start(0,"HASHCMP FIND ITEM");
    for (int i = 0; i < 1000000; i++)
    {
       if(material_entry_item_hash(me,"test_value").as_int == 333)
       {
        hash_cmp_return = 333;
       }
    }
    timer_stop(hash_cmp,"===>");


    debug("%ld %ld",str_cmp_return,hash_cmp_return);
    corange_finish();
    return 0;
}

материал


float  sadfsdf = 0
int  sadfsadf = 0
float sfgdfgdf = 0
float ssdfaksdfhaskdjf = 0 
float  sdfasdjfioasdjf = 0
int  sdfaefasdfasdfas = 0
float  sadfasdfaefsf = 0
int sasdfasdfsadf = 0
float siodufhaoiuefhw = 0
int   s54654sadfasdf = 0
float  sq34tgsergwtysdfgg = 0
float ssdfasdfsdfasfwe = 0
int sdfggesrdf = 0
int ssdfgrstghrth = 0
int styehdfdfhdfgh = 0
float sdtghrt6htrh = 0
int test_value = 333

git clone https://github.com/orangeduck/Corange.git
touch material.mat
touch speedtest.c
#скопируй данные в них из этого сообщения
gcc speedtest.c Corange/src/*.c Corange/src/*/*.c -O3 -ICorange/include  -lSDL2 -lSDL2_net -lSDL2_mixer -lGL -lm
./a.out

Deleted ()
Ответ на: комментарий от anonymous

Так или иначе тема закрыта, но если кому интересно такой вариант самый быстрый в общих случаях

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

  static material_item empty = {0};
  memset(&empty, 0, sizeof(empty));
  return ∅
}

При компиляции в одном фале и возврату по указателю и с предрасчётом хеша! то есть так как ниже, хеш быстрее в ~3 раза, только за счёт оптимизаций gcc. Если сунуть это в отдельную компилируемую единицу или вызывать из библиотеки то всё медленее раза в два. Так что если в системе нет SSE2 (ну а вдруг) и strcmp не имеет SIMD ускорялок то можно использовать хеш

material_item *  material_entry_item_hash(material_entry* me, char* name)  {
  unsigned long hash = material_hash(name);
  for(int i = 0; i < me->num_items; i++){
    if(me->hashes[i] == hash){
       return &me->items[i];
    }
  }

  static material_item empty = {0};
  memset(&empty, 0, sizeof(empty));
  return  ∅
}
Deleted ()
Последнее исправление: Deleted (всего исправлений: 1)
Ответ на: комментарий от Deleted

Так что если в системе нет SSE2 (ну а вдруг) и strcmp не имеет SIMD ускорялок то можно использовать хеш

Тоже глупость. Хэш никак не может быть быстрее strcmp, т.к. это по-сути и есть strcmp с дополнительной логикой. Как максимум он может быть ИДЕНТИЧНЫМ. Но ты просто засрёшь ядро дерьмом, т.е. замедлишь соседний гипертред.

anonymous ()
Ответ на: комментарий от Deleted

но в определённых ситуациях хеш идёт в ровень

Я тебе даже объясню почему. У strcmp из glibc достаточно большая летенси, т.е. на этих же тестах колхозный strcmp через while будет быстрее, чем strcmp из glibc.

В каких случаях летенси функции влияет - в тех, где у тебя строки короткие. Хотя, скорее всего, в glibc-strcmp есть специальная ветка для этого случая, но мб именно в твоей версии strcmp её нет.

anonymous ()
Ответ на: комментарий от anonymous

Возми код, добавь предрасчёт хеша, запусти и всё сам увидишь, я не о цифрах с потолка говорю. Я говорю о полученных цифрах на моём 3500Mz Phenom 2 X6 если это важно. Теоретизировать и я могу)) И ты наверное пропустил момент важный, при вызове из вне, и сборке в 1 компилируемой единице разница на порядки, суть в gcc конкретной оптимизации. Явно же если поведение настолько разное и хеш отрабатывает быстрее только если собран всместе с тестом то вывозит только за счёт оптимизаций gcc я уже про это четвёртый раз говорю наверное. Именно это я и не учёл в начале поста и именно поэтому я лоханулся, но факт есть факт, перечитывай тред короче

Deleted ()
Ответ на: комментарий от anonymous

Спасиб за уточнения, пожалуй может и так и есть в профайлере на каком то материале не помню уже количество __strcmp_sse было с какой то странной задержкой где было много вызовов __strchr_sse2 (могу путать пост/пре суффиксы) тоесть в некоторых строках много вызовов поиска вхождения в строку символа, а строки до 4 например символов выполняются в чуть ли не такт без вызова чего либо кроме __strcmp_sse

Deleted ()
Ответ на: комментарий от Deleted

Посмотрел я на код. Ну во-первых, очевидно, что это:

material_item   material_entry_item_hash(material_entry * me, char * name) {
  long hash = material_hash(name);

  for(int i = 0; i < me->num_items; i++) {
    if(material_hash(me->names[i]) == hash) {
      return me->items[i];
    };
  };

  static material_item empty = {0};

  memset(&empty, 0, sizeof(empty));

  return  empty;
}

Будет работать быстрее, но уже не сравнение строк. Это поиск строки. К тому же - у тебя неправильно написан код и ты не понимаешь что такое хеш. Хеш тебе позволяет получить «не равно», но никак не «равно». Поэтому ты должен сравнить строки strcmp и только тогда, когда они равны - ты можешь возвращать результат.

Выкинь тот треш, что у тебя написан и замени на return (material_item){}; Статик-дристня нужна только тогда, когда ты возвращаешь указатель. К тому же, каждый раз её занулять ненужно, если только «для надёжности».

Да и сам код - треш. Зачем ты оптимизируешь поиск перебором? Бахни хешмап, раз взялся за хеш. Либо бревно.

if(me->names[0] == name[0]) {

Это херню тоже можно засунуть в твой код с хешом.

anonymous ()
Ответ на: комментарий от Deleted

Возми код, добавь предрасчёт хеша, запусти и всё сам увидишь, я не о цифрах с потолка говорю.

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

И ты наверное пропустил момент важный, при вызове из вне, и сборке в 1 компилируемой единице разница на порядки

Это полная херня. Добавь туда __attribute__((noinline)) - будет тоже самое.

суть в gcc конкретной оптимизации.

Там нечего оптимизировать, вообще. Ты опять что-то перепутал. Осиль lto.

А лучше - выпили нахрен эту мусорное разделение на *.c-файлы, переведи на header-only и юзай -fwhole-program.

anonymous ()
Ответ на: комментарий от anonymous

Этот код я написал по быстрому что бы построить тест и дать ответ анону (ты не ты там был не знаю), и показывал как и в чём я совершал ошибки

Сейчас рабочий код такой, всё вернулось к strcmp

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

  static material_item empty = {0};
  warning("Undefined material item '%s' FIXIT!",name);
  return &empty;
}
Deleted ()
Ответ на: комментарий от anonymous

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

Всё уже давно уехало от того что в шапке

А лучше - выпили нахрен эту мусорное разделение на *.c-файлы, переведи на header-only и юзай -fwhole-program.

Спасибо, попробую. Если снова упрусь в это. Ну или для интереса как минимум попозже.

Это полная херня. Добавь туда attribute((noinline)) - будет тоже самое.

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

Deleted ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.