Вариант для распечатки		Пред. тема | След. тема
Форум Разговоры, обсуждение новостей
Режим отображения отдельной подветви беседы		[ Отслеживать ]

Результаты измерения производительности BerkeleyDB, opennews (ok), 13-Апр-09, (0) [смотреть все] Метод поиска по хешу априори быстрей метода поиска, основанного на бинарных дере, parad (ok), 13:17 , 13-Апр-09, (1) // Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо м, Аноним (-), 13:56 , 13-Апр-09, (2) // Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или а, sky (??), 14:51 , 13-Апр-09, (3)   // Кроме поиска есть ещё и редактирование И в случае с хешем, надо блокировать вес, svn (??), 19:35 , 13-Апр-09, (13)   Кто же редактирует хеш В хешу пишуть и из него читають , pavlinux (ok), 22:34 , 13-Апр-09, (16)   Ложь, никто не мешает блокировать как отдельный bucket, так и вообще отдельный э, Guest (??), 00:36 , 14-Апр-09, (18)   атомарными операциями не прокатит - на смп за атомарностью следит ядро, а доступ, parad (ok), 10:47 , 14-Апр-09, (21)   Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать Для btree и , geekkoo (ok), 11:05 , 14-Апр-09, (23)   В памяти хранится только кэш - все транзакции обязаны быть на диске в базе или л, Аноним (-), 12:41 , 14-Апр-09, (24)   Постраничная блокировка - это не атомарная операция и в больших БД страница може, parad (ok), 17:25 , 14-Апр-09, (25)   в случае с хешем, надо блокировать весь хеш svn В случае с деревом - таже ист, geekkoo (ok), 09:06 , 15-Апр-09, (31)   Все это конечно замечательно, но для дерева то время поиска включая и среднее , User294 (??), 10:40 , 15-Апр-09, (32)   Если хеш автоматически не меняет свой размер, то с ростом количества записей ско, Аноним (-), 10:59 , 15-Апр-09, (33)   скорость доступа всегда O 1 , даже если при возникновении коллизии мы проведем п, parad (ok), 11:18 , 15-Апр-09, (35)   Ну, дык я и не спорю Хэш рано или поздно на больших объемах победит деревья, но, geekkoo (ok), 14:52 , 15-Апр-09, (37)   опять непонятно из какого пальца ты такое умозаключение высосал выше я описал ч, parad (ok), 11:02 , 15-Апр-09, (34)   угу, а мьютекс реализовываается сам на себе, надо думать я про железные атомарн, Guest (??), 23:07 , 14-Апр-09, (27)   не хочется даже ничего спрашивать, боюсь услышать ответ ты взял sizeof phtrad_mu, parad (??), 00:51 , 15-Апр-09, (28)   Не сомневаюсь А я имел в виду всего навсего lock cmpxchg для x86 Не думал чт, Guest (??), 04:35 , 15-Апр-09, (29)   В случае с деревом - таже история Нужно заблокировать все , parad (??), 01:09 , 14-Апр-09, (19)   Что-то слабо верится во все эти бенчмарки, да и результат зависит от слишком мно, Аноним (-), 15:17 , 13-Апр-09, (4) О Капитан Очевидность А если просто ПОЧИТАТЬ ОПИСАНИЕ технологий hash и btree , User294 (??), 16:05 , 13-Апр-09, (6) // А ещё хеш не может искать по частичному совпадению , svn (??), 19:38 , 13-Апр-09, (15) http www ioremap net gallery elliptics_bdb_hash_btree_file pngГрафик несколько, XoRe (ok), 16:10 , 13-Апр-09, (7) // Может просто тесты останавливались в разное время По графику файловая реализация, Аноним (-), 17:06 , 13-Апр-09, (8) Если в тексте блога сходить по ссылочке yesterday , то там можно наткнуться на , geekkoo (ok), 17:13 , 13-Апр-09, (10) // Этот хояин блога zbr - автор POHMELFS оказывается, а elliptics - сервер для хран, geekkoo (ok), 17:38 , 13-Апр-09, (11) Можете не брать Евгений порою несколько импульсивен в своих высказаваниях и выв, alexr (??), 19:37 , 13-Апр-09, (14) // Сложно сказать, в чем там косяк, не видя кода, но настораживает такой момент Нас, geekkoo (ok), 10:33 , 14-Апр-09, (20) // Код можно посмотреть в git http www ioremap net cgi-bin gitweb cgi p elliptic, Аноним (-), 10:59 , 14-Апр-09, (22) 1,4,6,7,10,14

Сообщения

[Сортировка по времени | RSS]

	3. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от sky (??), 13-Апр-09, 14:51
	> >Например, индексы на основе хешей в PostgreSQL работали пару лет назад ощутимо >медленее btree. Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования. В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n).
	Ответить | Правка | Наверх | Cообщить модератору

	13. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от svn (??), 13-Апр-09, 19:35
	>Это всего лишь означает, что постгресовцы неправильно выбрали размер ключа или алгоритм хэширования. >В любом учебнике написано, что у нормального хэша время поиска не зависит от числа элементов, т.е. растет как O(1). У бинарных деревьев в лучшем случае O(ln n). Кроме поиска есть ещё и редактирование. И в случае с хешем, надо блокировать весь хеш. И пусть весь мир подождёт :)
	Ответить | Правка | Наверх | Cообщить модератору

	16. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от pavlinux (ok), 13-Апр-09, 22:34
	Кто же редактирует хеш??? В хешу пишуть и из него читають.
	Ответить | Правка | Наверх | Cообщить модератору

	18. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от Guest (??), 14-Апр-09, 00:36
	Ложь, никто не мешает блокировать как отдельный bucket, так и вообще отдельный элемент. А вообще, мне рассказывали про реализацию thread-safe хэша вообще без блокировок, чисто на атомарных операциях. Да, с изменением размера, как положено.
	Ответить | Правка | К родителю #13 | Наверх | Cообщить модератору

	21. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (ok), 14-Апр-09, 10:47
	атомарными операциями не прокатит - на смп за атомарностью следит ядро, а доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры. заполнение хеша происходит в 3этапа - вычесление хеша, проверка на коллизии вычеленного значения, вставка в массив. после второго этапа может возникнуть черти-что без блокировки ячейки. а мьютекс на каждую ячейку - это слишком дорого, поэтому и остается блокировать все, хоть даже и рв-локами.
	Ответить | Правка | Наверх | Cообщить модератору

	23. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от geekkoo (ok), 14-Апр-09, 11:05
	>атомарными операциями не прокатит - на смп за атомарностью следит ядро, а >доступ к этим блокировкам только через тред-мьютексы или ипц-семафоры. > >заполнение хеша происходит в 3этапа - вычесление хеша, проверка на коллизии вычеленного >значения, вставка в массив. после второго этапа может возникнуть черти-что без >блокировки ячейки. а мьютекс на каждую ячейку - это слишком дорого, >поэтому и остается блокировать все, хоть даже и рв-локами. Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать? Для btree и hash там используется постраничная блокировка. Ни о каком блокировании всей базы речи нет. Кстати, там же речь идет о сравнении производительности hash и btree. Резюме такое, что в зависимости от размера базы это немонотонная функция. Вначале (пока база влезает в оперативную память) - без разницы, потом узким местом становится IO и hash сливает, а потом начинает сказываться размер метаданных, который больше у btree, и в итоге на самых больших базах выигрывает hash. Разумеется, если locality не важна, а нужен только точный поиск по ключу и важна производительность.
	Ответить | Правка | Наверх | Cообщить модератору

	24. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от Аноним (-), 14-Апр-09, 12:41
	>Кстати, там же речь идет о сравнении производительности hash и btree. Резюме >такое, что в зависимости от размера базы это немонотонная функция. Вначале >(пока база влезает в оперативную память) - без разницы, потом узким >местом становится IO и hash сливает, а потом начинает сказываться размер >метаданных, который больше у btree, и в итоге на самых больших >базах выигрывает hash. Разумеется, если locality не важна, а нужен только >точный поиск по ключу и важна производительность. В памяти хранится только кэш - все транзакции обязаны быть на диске в базе или логе во время коммита (хотя это можно несколько ослабить). Дисковый ввод.вывод всегда является узким местом базы данных.
	Ответить | Правка | Наверх | Cообщить модератору

	25. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (ok), 14-Апр-09, 17:25
	>Что мешает прочитать мануал по BerkeleyDB и перестать фантазировать? > >Для btree и hash там используется постраничная блокировка. Ни о каком блокировании >всей базы речи нет. Постраничная блокировка - это не атомарная операция и в больших БД страница может стать о(sizeof(DB)) - 'о'-малое от размера бд, те фактические своим количеством сэмитировать блокировку ячейки. Если даже поставить лимит кол-ва страниц, то на тех-же больших бд возникнет эффект схожий с блокировкой все БД. Предлагаю не выпендриваться и перестать перефразировать мои слова. + мозг подключять при чтении документации. >Кстати, там же речь идет о сравнении производительности hash и btree. Резюме >такое, что в зависимости от размера базы это немонотонная функция. Вначале >(пока база влезает в оперативную память) - без разницы, потом узким >местом становится IO и hash сливает, а потом начинает сказываться размер >метаданных, который больше у btree, и в итоге на самых больших >базах выигрывает hash. Разумеется, если locality не важна, а нужен только >точный поиск по ключу и важна производительность. Твою ###########! Хеш будет сливать только при малом размере БД (очень малом). При всех остальных, даже если он целиком будет храниться на диске - он будет впереди. Другое дело реализация - можно обосраться и сделать даже самый быстрый алгоритм медленее банального перебора. Если берклидб в документации пишет, то, что ты выше рассказал - то это явно у них проблемы с реализацией.
	Ответить | Правка | К родителю #23 | Наверх | Cообщить модератору

	31. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от geekkoo (ok), 15-Апр-09, 09:06
	> перестать перефразировать мои слова. + мозг подключять >при чтении документации. "в случае с хешем, надо блокировать весь хеш"(svn) "В случае с деревом - таже история. Нужно заблокировать все."(parad) Таки теперь выясняется, что блокировать всё уже не надо? >Хеш будет сливать только при малом размере БД (очень малом). >При всех остальных, даже если он целиком будет храниться на диске >- он будет впереди. Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно только надеятся, что для случайного ключа в среднем скорость будет вести себя как в идеальном случае, когда хэширующая функция подобрана под заранее известный набор ключей.
	Ответить | Правка | Наверх | Cообщить модератору

	32. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от User294 (??), 15-Апр-09, 10:40
	>только надеятся, что для случайного ключа в среднем скорость будет вести >себя как в идеальном случае, Все это конечно замечательно, но для дерева то время поиска (включая и среднее) будет логарифмически расти с ростом числа записей в бд.А у хеша это время в среднем не растет.На бд с большим числом записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то что на конкретном ключе может быть и несколько медленнее чем в среднем обычно мало кого волнует.
	Ответить | Правка | Наверх | Cообщить модератору

	33. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от Аноним (-), 15-Апр-09, 10:59
	>>только надеятся, что для случайного ключа в среднем скорость будет вести >>себя как в идеальном случае, > >Все это конечно замечательно, но для дерева то время поиска (включая и >среднее) будет логарифмически расти с ростом числа записей в бд.А у >хеша это время в среднем не растет.На бд с большим числом >записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то >что на конкретном ключе может быть и несколько медленнее чем в >среднем обычно мало кого волнует. Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n). Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше. Как устроена таблица (в частности, есть ли в ней автоматическое изменение размера) в BDB, не известно.
	Ответить | Правка | Наверх | Cообщить модератору

	35. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (ok), 15-Апр-09, 11:18
	> Если хеш автоматически не меняет свой размер, то с ростом количества записей скорость доступа будет уменьшаться как O(количества ключей / количество ячеек в хеш-таблице), что по сути есть O(n). скорость доступа всегда O(1), даже если при возникновении коллизии мы проведем повторную операцию хеширования получим O(2) = O(1). есть методы заполнения позволяющие иметь кпд хеша 95% при максимум 3х вычеслениях хеша на операцию записи/чтения, что O(3) = O(1). тот метод, который возможно, вы имеете в виду (перебор в цикле всех последующих ячеек до нахождения свободной) описывается для облегчения понимания в начале каждого учебника, но никак не может быть использован в качестве рабочего варианта, т.к. сводит быстрый доступ по индексу к банальнобу перебору всех значений. > Хеш-таблица подходит для случаев, когда количество ключей сравнимо с размером таблицы, т.е. максимум в несколько раз больше. Читайте выше и дальше - это тоже самое начало любого учебника, есть методы быстрого заполнения хеша на 95%.
	Ответить | Правка | Наверх | Cообщить модератору

	37. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от geekkoo (ok), 15-Апр-09, 14:52
	>>только надеятся, что для случайного ключа в среднем скорость будет вести >>себя как в идеальном случае, > >Все это конечно замечательно, но для дерева то время поиска (включая и >среднее) будет логарифмически расти с ростом числа записей в бд.А у >хеша это время в среднем не растет.На бд с большим числом >записей хэш должен выиграть.Как минимум при вытаскивании пар ключ-значение.При том то >что на конкретном ключе может быть и несколько медленнее чем в >среднем обычно мало кого волнует. Ну, дык я и не спорю. Хэш рано или поздно на больших объемах победит деревья, но пока до этого дойдет - замотаешься пыль глотать. Хотя практика сравнения среднего времени в смысле статистики с гарантированным worst case - кажется мне несколько порочной ...
	Ответить | Правка | К родителю #32 | Наверх | Cообщить модератору

	34. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (ok), 15-Апр-09, 11:02
	>Таки теперь выясняется, что блокировать всё уже не надо? опять непонятно из какого пальца ты такое умозаключение высосал: выше я описал что постраничная блокировка - это бессмысленное действие на очень больших бд и так или иначе глобальная блокировка будет присутствовать всегда - от этого не уйдешь. >Забавная уверенность, учитывая, что хэш не дает гарантий по времени, и можно >только надеятся, что для случайного ключа в среднем скорость будет вести >себя как в идеальном случае, когда хэширующая функция подобрана под заранее >известный набор ключей. тут вообще тяжело догодаться что ты хочешь сказать. функция хеширования не занимается подгонкой под определенный набор, она вычесляет число(хеш), на основе которого высчитывается индекс. например, если в пямяти умещяется массив из 1млн экземпляров, а хеш-число - 64битное, то расчет индекса будет: i = 1млн * ( hashfunc( data ) / max( uint_64 )), где max( uint_64 ) = 0xffffffffffff, а i - индекс массива mas[i] куда/откуда мы должны положить/извлеч данные. + конечно обработка коллизий.
	Ответить | Правка | К родителю #31 | Наверх | Cообщить модератору

	27. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от Guest (??), 14-Апр-09, 23:07
	> на смп за атомарностью следит ядро угу, а мьютекс реализовываается сам на себе, надо думать? я про железные атомарные операции. > после второго этапа может возникнуть черти-что без блокировки ячейки для не-unique значений второй этап не нужен. я той реализации не видел, возможно это и был multimap. > а мьютекс на каждую ячейку - это слишком дорого совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (> 50% заполнение) - <1.5 раза. Не уверен, но можно под мьютексы и байты использовать.
	Ответить | Правка | К родителю #21 | Наверх | Cообщить модератору

	28. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (??), 15-Апр-09, 00:51
	>угу, а мьютекс реализовываается сам на себе, надо думать? я про железные >атомарные операции. не хочется даже ничего спрашивать, боюсь услышать ответ. >совсем нет. теоретический потолок - в 2 раза больше памяти (пустой хэш, смещение=слово, мьютекс=слово). На практике (> 50% заполнение) - <1.5 раза. Не уверен, но можно под мьютексы и байты использовать. ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру - эт раз. слово - это 2байта, указатель - минимум 4байта - это какбы два. три - не придумывай херню про байт, потомучто как минимум у тебя будет 256 мьютексов + это нужно сильно обидется чтобы так начать фантазировать. (извини если где-то, возможно, резко высказался, - давай будем объективными). четыре - хеш не хранит смещение, хеш может не хранить и само вычесленное хеш-число - это массив данных, занесенных в ячейку на основе вычесленного хеш-числа, указавшего номер ячейки для размещения + несколько методов борьбы с коллизиями, поэтому размер ячейки хеша может быть скольугоднобольшим. можешь просто спросить если есть вопрос - придумывать незачем. для этого форум и создан. а бред, извини, в таких количествах раздражает.
	Ответить | Правка | Наверх | Cообщить модератору

	29. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от Guest (??), 15-Апр-09, 04:35
	>не хочется даже ничего спрашивать, боюсь услышать ответ Не сомневаюсь. А я имел в виду всего навсего lock cmpxchg (для x86). Не думал что это настолько неочевидно. >ты взял sizeof(phtrad_mutex_t)? флаг в руки. этот тип дефайнет указатель на структуру Нет, я взял размер регистра. От реализации тредов тут вообще ничего не зависит, спинлоки всегда будут эффективней ядерных мьютексов (разумеется речь идет про SMP). >- эт раз. слово - это 2байта, указатель - минимум 4байта Слово это размер регистра общего назначния. Когда пишешь под что-то кроме x86, от ереси типа слово=2байта быстро отвыкаешь. >- это какбы два. три - не придумывай херню про байт, >потомучто как минимум у тебя будет 256 мьютексов + это нужно >сильно обидется чтобы так начать фантазировать. Я имел в виду cmpxchg XXX, _byte ptr_ [YYY] Просто не уверен насчет ее производителньости и сайдэффектов, к тому же такие мьютексы придется хранить сбоку из-за выравнивания. >четыре - хеш не хранит смещение, хеш может не хранить и само >вычесленное хеш-число - это массив данных, занесенных в ячейку >на основе вычесленного хеш-числа, указавшего номер ячейки >для размещения + несколько методов борьбы с коллизиями, >поэтому размер ячейки хеша может быть скольугоднобольшим. Боже мой. Вы бы для начала все-таки читали, что читаете, а не изображали преподавателя инфорамтики. Хэш никогда не хранит вычисленное хэш число, потому что это и есть индекс бакета. А по этому индексу надо хранить ни что иное как адрес(=смещение) массива/первого элемента списка элементов данных, имеющих этот хэш. В любом случае, если вы предлагаете напихать в бакет скольугодномного всякого мусора, я думаю не то что int, но и pthread_mutex_t со всеми его прелестями вас там не смутит. >а бред, извини, в таких количествах раздражает. Полностью согласен
	Ответить | Правка | Наверх | Cообщить модератору

	19. "Результаты измерения производительности BerkeleyDB"	+/–
	Сообщение от parad (??), 14-Апр-09, 01:09
	В случае с деревом - таже история. Нужно заблокировать все.
	Ответить | Правка | К родителю #13 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема