https://www.opennet.me/openforum/vsluhforumID3/52314.html "BerkeleyDB btree vs hash table benchmark (http://www.ioremap.net/node/213)" - результаты измерения производительности реализаци btree структур и хэшей в BerkeleyDB, в сравнении с организацией хранения данных в файлах в ФС ext3 (ключ к хэшу = имя файла). Интересно, что хэш в BerkeleyDB оказался быстрее btree, который в свою очередь обогнал метод хранения в файлах.<br><br><br>Результаты тестов заставляют задуматься о целесообразности замены файлового хранилища, системой подобной memcacheDB (http://memcachedb.org/) (хранение данных в BerkeleyDB базе с использование совместимого с memcached протокола).<br><br><br>URL: http://www.ioremap.net/node/213<br>Новость: http://www.opennet.ru/opennews/art.shtml?num=21234<br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#37 Wed, 15 Apr 2009 10:52:51 GMT &gt;&gt;только надеятся, что для случайного ключа в среднем скорость будет вести <br>&gt;&gt;себя как в идеальном случае,<br>&gt;<br>&gt;Все это конечно замечательно, но для дерева то время поиска (включая и <br>&gt;среднее) будет логарифмически расти с ростом числа записей в бд.А у <br>&gt;хеша это время в среднем не растет.На бд с большим числом <br>&gt;записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то <br>&gt;что на конкретном ключе может быть и несколько медленнее чем в <br>&gt;среднем обычно мало кого волнует. <br><br>Ну, дык я и не спорю. Хэш рано или поздно на больших объемах победит деревья, но пока до этого дойдет - замотаешься пыль глотать.<br><br>Хотя практика сравнения среднего времени в смысле статистики с гарантированным worst case - кажется мне несколько порочной ...<br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#35 Wed, 15 Apr 2009 07:18:05 GMT &gt; Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).<br><br>скорость доступа всегда O(1), даже если при возникновении коллизии мы проведем повторную операцию хеширования получим O(2) = O(1). есть методы заполнения позволяющие иметь кпд хеша 95% при максимум 3х вычеслениях хеша на операцию записи/чтения, что O(3) = O(1).<br><br>тот метод, который возможно, вы имеете в виду (перебор в цикле всех последующих ячеек до нахождения свободной) описывается для облегчения понимания в начале каждого учебника, но никак не может быть использован в качестве рабочего варианта, т.к. сводит быстрый доступ по индексу к банальнобу перебору всех значений.<br><br>&gt; Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше.<br><br>Читайте выше и дальше - это тоже самое начало любого учебника, есть методы быстрого заполнения хеша на 95%.<br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#34 Wed, 15 Apr 2009 07:02:43 GMT &gt;Таки теперь выясняется, что блокировать всё уже не надо? <br><br>опять непонятно из какого пальца ты такое умозаключение высосал: выше я описал что постраничная блокировка - это бессмысленное действие на очень больших бд и так или иначе глобальная блокировка будет присутствовать всегда - от этого не уйдешь.<br><br>&gt;Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно <br>&gt;только надеятся, что для случайного ключа в среднем скорость будет вести <br>&gt;себя как в идеальном случае, когда хэширующая функция подобрана под заранее <br>&gt;известный набор ключей.<br><br>тут вообще тяжело догодаться что ты хочешь сказать. функция хеширования не занимается подгонкой под определенный набор, она вычесляет число(хеш), на основе которого высчитывается индекс. например, если в пямяти умещяется массив из 1млн экземпляров, а хеш-число - 64битное, то расчет индекса будет: i = 1млн * ( hashfunc( data ) / max( uint_64 )), где max( uint_64 ) = 0xffffffffffff, а i - индекс массива mas[i] куда/откуда мы должны положить/извлеч данн https://www.opennet.me/openforum/vsluhforumID3/52314.html#33 Wed, 15 Apr 2009 06:59:02 GMT &gt;&gt;только надеятся, что для случайного ключа в среднем скорость будет вести <br>&gt;&gt;себя как в идеальном случае,<br>&gt;<br>&gt;Все это конечно замечательно, но для дерева то время поиска (включая и <br>&gt;среднее) будет логарифмически расти с ростом числа записей в бд.А у <br>&gt;хеша это время в среднем не растет.На бд с большим числом <br>&gt;записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то <br>&gt;что на конкретном ключе может быть и несколько медленнее чем в <br>&gt;среднем обычно мало кого волнует. <br><br>Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n).<br><br>Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше.<br><br>Как устроена таблица (в частности, есть ли в ней автоматическое изменение размера) в BDB, не известно.<br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#32 Wed, 15 Apr 2009 06:40:55 GMT &gt;только надеятся, что для случайного ключа в среднем скорость будет вести <br>&gt;себя как в идеальном случае,<br><br>Все это конечно замечательно, но для дерева то время поиска (включая и среднее) будет логарифмически расти с ростом числа записей в бд.А у хеша это время в среднем не растет.На бд с большим числом записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то что на конкретном ключе может быть и несколько медленнее чем в среднем обычно мало кого волнует. <br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#31 Wed, 15 Apr 2009 05:06:33 GMT &gt; перестать перефразировать мои слова. + мозг подключять <br>&gt;при чтении документации. <br><br>"в случае с хешем, надо блокировать весь хеш"(svn)<br>"В случае с деревом - таже история. Нужно заблокировать все."(parad)<br>Таки теперь выясняется, что блокировать всё уже не надо?<br><br>&gt;Хеш будет сливать только при малом размере БД (очень малом). <br>&gt;При всех остальных, даже если он целиком будет храниться на диске <br>&gt;- он будет впереди. <br><br>Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно только надеятся, что для случайного ключа в среднем скорость будет вести себя как в идеальном случае, когда хэширующая функция подобрана под заранее известный набор ключей.<br> https://www.opennet.me/openforum/vsluhforumID3/52314.html#29 Wed, 15 Apr 2009 00:35:05 GMT &gt;не хочется даже ничего спрашивать, боюсь услышать ответ<br><br>Не сомневаюсь. А я имел в виду всего навсего lock cmpxchg (для x86). Не думал что это настолько неочевидно.<br><br>&gt;ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру <br><br>Нет, я взял размер регистра. От реализации тредов тут вообще ничего не зависит, спинлоки всегда будут эффективней ядерных мьютексов (разумеется речь идет про SMP).<br><br>&gt;- эт раз. слово - это 2байта, указатель - минимум 4байта <br><br>Слово это размер регистра общего назначния. Когда пишешь под что-то кроме x86, от ереси типа слово=2байта быстро отвыкаешь.<br><br>&gt;- это какбы два. три - не придумывай херню про байт,<br>&gt;потомучто как минимум у тебя будет 256 мьютексов + это нужно <br>&gt;сильно обидется чтобы так начать фантазировать.<br><br>Я имел в виду cmpxchg XXX, _byte ptr_ [YYY]<br>Просто не уверен насчет ее производителньости и сайдэффектов, к тому же такие мьютексы придется хранить сбоку из-за выравнивания.<br><br>&gt;четыре - хеш не хранит смещение, хеш может не хранить и само https://www.opennet.me/openforum/vsluhforumID3/52314.html#28 Tue, 14 Apr 2009 20:51:21 GMT &gt;угу, а мьютекс реализовываается сам на себе, надо думать? я про железные <br>&gt;атомарные операции. <br><br>не хочется даже ничего спрашивать, боюсь услышать ответ.<br><br>&gt;совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (&gt; 50% заполнение) - &lt;1.5 раза. Не уверен, но можно под мьютексы и байты использовать.<br><br>ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру - эт раз. слово - это 2байта, указатель - минимум 4байта - это какбы два. три - не придумывай херню про байт, потомучто как минимум у тебя будет 256 мьютексов + это нужно сильно обидется чтобы так начать фантазировать. (извини если где-то, возможно, резко высказался, - давай будем объективными). четыре - хеш не хранит смещение, хеш может не хранить и само вычесленное хеш-число - это массив данных, занесенных в ячейку на основе вычесленного хеш-числа, указавшего номер ячейки для размещения + несколько методов борьбы с коллизиями, поэтому размер ячейки хеша может быть https://www.opennet.me/openforum/vsluhforumID3/52314.html#27 Tue, 14 Apr 2009 19:07:00 GMT &gt; на смп за атомарностью следит ядро<br><br>угу, а мьютекс реализовываается сам на себе, надо думать? я про железные атомарные операции.<br><br>&gt; после второго этапа может возникнуть черти-что без блокировки ячейки<br><br>для не-unique значений второй этап не нужен. я той реализации не видел, возможно это и был multimap.<br><br>&gt; а мьютекс на каждую ячейку - это слишком дорого<br><br>совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (&gt; 50% заполнение) - &lt;1.5 раза. Не уверен, но можно под мьютексы и байты использовать.<br>