LINUX.ORG.RU

libc хэш таблицы

 , hashtable,


1

2

Glibc 2.17, открываю search.h и вижу такой апи

int  hsearch_r  (item, action, **return, *htable)
int  hcreate_r  (nel, *htable)
void hdestroy_r (*htable)
и все?

Гуглю альтернативы:

  1. uthash макро ад!
  2. khash макро ад!
  3. glib hash тащить целый glib ради хэш таблиц не хочется
  4. strmap хранит char *, а не void *
  5. judy «if you have random access and sparse keys, Judy lookups and deletes could be twice as slow as an optimized hash table». не нужно
  6. hashit GPL v2 без Lesser

Итого выбрал CCAN.

Но тут внезапно гугл выкатывает u-boot где вижу апи

int     hcreate_r  (nel, *htable)
void    hdestroy_r (*htable)
int     hsearch_r  (item, action, **return, *htable, flag)
int     hmatch_r   (*match, last_idx, **return, *htable)
int     hstrstr_r  (*match, last_idx, **return, *htable)
int     hdelete_r  (*key, *htable, flag)
ssize_t hexport_r  (*htable, separator, flag, **responce, size, argc, *argv[])
int     himport_r  (*htable, *env, size, separator, flag, argc, *vars[])
int     hwalk_r    (*htable, *callback);
Етить колотить! Так это же апи моей мечты.

Вопрос почти риторический: почему этот форк уже минимум 2.5 года не видят разработчики glibc?

★★

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

uthash макро ад!
khash макро ад!

Либо макросы либо потеря производительности на непрямых вызовах. Выбирай. Макросы это вполне по сишному и по производительности будет близко к stl.

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

оверхед от одного вызова много меньше оверхеда от твоей плюсовой обертки. пожертвовать одним вызовом на каждый макрос чтобы не гемороится с макросами - я готов

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

Осведомленность от тебя так и прет. Впрочем, как всегда. Во-первых, stl не является оберткой. Во-вторых, оверхед действительно существенный, напиши сам тест и проверь.

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

Уверен, что если взять современный gcc, взять одинаковые хеш-функции и сравнить сейчас, то разница с реализацией на макросах будет в пределах погрешности, а glib и похожие реализации всё равно сольют :)

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

Сам неси с исходниками, а мы на них посмотрим. В прошлом сраче я уже делал тесты для сравнения std::map и rb_tree из бздишного tree.h. Тогда разницы не было. Повторно что-то писать, да еще и в воскресенье я не собираюсь.

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

с tr1, и повторяюсь, я не агитирую конкретно за unordered_map

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

о, нужно будет восполнить знания.

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

не хочешь - так чего свою точку зрения толкаешь. и зачем мне бинарные деревья усрались твои. меня интересует выборка за O(1) а не O(log n)

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

не хочешь - так чего свою точку зрения толкаешь.

Это не точка зрения, а объективная истина. Не хочешь проверять сам — не проверяй, так и останешься дураком.

и зачем мне бинарные деревья усрались твои. меня интересует выборка за O(1) а не O(log n)

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

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

сам пишешь

Либо макросы либо потеря производительности на непрямых вызовах

чем тебе здесь поможет шаблон?

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

Внезапно, отсутствием непрямых вызовов. Все адреса и типы уже известны на этапе компиляции, и, более того, в 99.99% пользовательские компараторы будут инлайниться и вызовов вообще не будет.

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

khash быстрее stl

было бы удивительно ожидать другого от сравнения от автора knash :) вот тут:

http://www.ultimatepp.org/www$uppweb$vsstd$en-us.html

автор меряет, что u++ быстрее STL почти в 4 раза, тут:

http://tommyds.sourceforge.net/doc/benchmark.html

у автора его реализация быстрее всех ( в том числе и khash ), тут:

http://preshing.com/20110603/hash-table-performance-tests

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

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

При использовании макросов будут. В твоем примере использующий и используемый код компилируются одновременно. В случае с glib и аналогами это не так и inline невозможен.

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

все ясно. ну если использовать хедер-онли библиотеки внутри которых будут инлайн функции, а не макросы, то с gcc все будет хорошо инлайнится.

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

Лол, только сравнивать хеш таблицу с Rb деревом (std::map) не совсем корректно. Вот если бы с unordered_map сравнили, то да.

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

сударь, там в первом предложении сказано что используется hash_set (в c++11 его переименовали в unordered_set). это не rb-дерево, а обычная хэш таблица

punya ★★
() автор топика
Последнее исправление: punya (всего исправлений: 1)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.