Комментарии 34
Спасибо за интересную информацию. Однако, думается мне, что графику не хватает нормальной шкалы времени, ибо уменьшение потребления самой структурой данных количества памяти — это конечно хорошо, хотя и мизерно по сравнению с самим данными, которые ей предстоит хранить и обрабатывать. А вот повышение эффективности работы — совсем другое дело. Хоть бери, и сам замеряй и сравнивай скорость работы…
мизерно по сравнению с самим данными
Судя по таблице, экономия в некоторых случаях на порядок. Или я не так понял?
Есть мета-информация, которая позволяет структурировать данные. Экономия на 50-80% как раз лишь в хранении мета-информации. В большинстве случаев размер самих данных, которые мы храним в какой-то структуре изначально на порядки превосходит размеры мета-информации. Но не всегда так. Если вы собираетесь хранить там маленькие поля, то структура однозначно для Вас! Если у вас уже есть написанный код, и элементы большие, то врятли стоит переходить на эту либу.
Кроме того здесь показано среднее амортизированное время вставки. У красно-черных деревьев плюс в том что они имеют гарантированное максимальное время вставки-удаления O(lnN). У B-Tree я так понимаю худший случай O(N) тобишь линейное время.
На графике показано среднее время выполнения вставки, в зависимости от размеров контейнера.А по оси Y, надо полагать, попугаи отложены? Вроде серьёзные люди, не маркетологи какие-нибудь а туда же.
Всё равно параметры тестирующей машины неизвестны. Ну, увидите вы где-то на шкале отметку 1 нс. И что она даст, если не знать, 1 там гигагерц или 5.
Так плохо, что неизвестны. Добавить надо параметры. Странная логика «я не буду подписывать ось, потому что я всё равно не указал параметры машины».
Странная логика. «Нельзя сделать вывод, какой алгоритм и во сколько раз лучше, пока на шкале не подписано время». По хорошему, пришлось бы указать и время, и параметры машины, и компилятор (со всеми ключами компиляции), и ОС, и способ генерации входных данных (чтобы можно было оценить расходы времени на их генерацию)… в конечном итоге, весь тестирующий код — ведь любой из этих параметров повлияет на результат, а значит, и на его обратную интерпретацию. Но зачем это делать? А если незачем, то зачем подписывать шкалу времени? Какая разница, в какой точке на шкале строгости и серьёзности остановиться?
Я где-то написал, что нельзя сделать вывод? Я к тому, что подписывать ось графика — это всё равно что писать без орфографических ошибок. Люди, которые пишут с ошибками, примерно так и рассуждают: «зачем писать правильно, если и так всё понятно?»
Ну знаете, неподписанная ось может начинается не с нуля (в последнее время это очень любят). Или быть в логарифмическом масштабе. Так что без подписей даже «какой алгоритм и во сколько раз лучше» не всегда можно правильно оценить
не, хотя бы палочки с какими-нибудь попугаями лучше бы нарисовали всё-таки. Пиксели-то неудобно измерять ;-)
Кстати говоря, автор jemalloc предлагает красно-черные деревья, в которых используется всего лишь два указателя на узел: отсутствует указатель на родительский элемент, а цвет кодируется младшим битом указателя на правый дочерний элемент.
Josh MacDonald10:46 AM — Public
[Responding to the comments section.]
My Russian friends, the Y-axis of the C++ B-tree graphs are irrelevant; the Red-Black tree and B-tree results are plotted on the same scale with a proper zero origin. The benchmark code is included in the release.
I didn't label the Y-axis because the results are hardware dependent, but since you're curious, the graph was computed using an Intel Xeon CPU E5-1650 @ 3.20GHz with L1=32K, L2=256K, L3=12M and for the far right of the graph (10 million elements per container), it's approximately 1.6 microseconds vs. 400 nanoseconds.
[Responding to the comments section.]
My Russian friends, the Y-axis of the C++ B-tree graphs are irrelevant; the Red-Black tree and B-tree results are plotted on the same scale with a proper zero origin. The benchmark code is included in the release.
I didn't label the Y-axis because the results are hardware dependent, but since you're curious, the graph was computed using an Intel Xeon CPU E5-1650 @ 3.20GHz with L1=32K, L2=256K, L3=12M and for the far right of the graph (10 million elements per container), it's approximately 1.6 microseconds vs. 400 nanoseconds.
Спасибо, что спросили у автора. Но от конкретного оборудования (в частности, от размеров кэшей) будут зависеть не только метки осей, но и сама форма графика. Фаза резкого роста начинается, когда не хватает кэшей. Сейчас видно, что до 1K записей обе реализации влезают в L1, поэтому результаты сходные.
По мне так, сравнивать производительность только со стандартным STL не совсем корректно. Интересно было бы сравнить с Boost.
Довели человека — зато теперь совершенно ясно, что на данной конкретной железяке на конкретной задаче прирост в 4 раза! =)
p.s.: тут есть и длугие френды, например ukrainian friends… ;)
p.s.: тут есть и длугие френды, например ukrainian friends… ;)
Довольно много лет существует stx-btree panthema.net/2007/stx-btree/
Бенчмарки panthema.net/2007/stx-btree/stx-btree-0.8.6/doxygen-html/a00001.html
Бенчмарки panthema.net/2007/stx-btree/stx-btree-0.8.6/doxygen-html/a00001.html
Стандартная реализация красно-черных деревьев в STL кривая (GNU, HP, Microsoft и смотрел много других, правильной не встречал, может правда уже и есть). Поскольку не далекие программисты практически в лоб программировали описание алгоритма из книги Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ = Introduction to algorithms. А там дополнительно определяется, как черный узел nil, что все нарушает. В частности резко увеличивает память + есть понимание, что надо использовать NULL, что еще сильнее увеличивает хаос в головах. В результате разбора их реализаций можно узнать тайный ход масти (мысли) программера, который путем проб и ошибок в собственный лоб решает проблему лишь бы работало.
Насчет B-Tree согласен при правильных реализациях будет лучше красно-коричневых деревьев, но не так значительно как у авторов из Google. Ясно, что красно-коричневые имитируют в каком-то смысле B-деревья и B-деревья первичны, но у обоих свои ±. Для библиотеки игра может и стоит того, но за счет сложности реализации (а значит и поддержки) я бы лично не стал возится, слишком много рисков.
Если кому интересна реализация на C++ могу выложить ее + краткое описание, но только на freehabr.ru/
Насчет B-Tree согласен при правильных реализациях будет лучше красно-коричневых деревьев, но не так значительно как у авторов из Google. Ясно, что красно-коричневые имитируют в каком-то смысле B-деревья и B-деревья первичны, но у обоих свои ±. Для библиотеки игра может и стоит того, но за счет сложности реализации (а значит и поддержки) я бы лично не стал возится, слишком много рисков.
Если кому интересна реализация на C++ могу выложить ее + краткое описание, но только на freehabr.ru/
> Стандартная реализация красно-черных деревьев в STL кривая (GNU, HP, Microsoft и смотрел много других, правильной не встречал, может правда уже и есть).
Все !@#$^%, один я д’Артаньян. Я сомневаюсь что сотни не самых глупых инженеров так и не смогли написать хоть одно нормальное RB дерево.
Все !@#$^%, один я д’Артаньян. Я сомневаюсь что сотни не самых глупых инженеров так и не смогли написать хоть одно нормальное RB дерево.
Повтор. Если кому интересна реализация на C++ могу выложить ее + краткое описание…
Если Вам неинтересно (Вы возможно из сотни не самых глупых инженеров), то я тогда Вам советую глянуть на хорошие реализации (GNU, HP, Microsoft и много других, не правильных пока я не встречал, может правда уже они и есть).
Если Вам неинтересно (Вы возможно из сотни не самых глупых инженеров), то я тогда Вам советую глянуть на хорошие реализации (GNU, HP, Microsoft и много других, не правильных пока я не встречал, может правда уже они и есть).
Если бы вы действительно были заинтересованы в улучшении ситуации, вы бы взяли и написали патч. А рассказывать как там всё плохо где-либо кроме списка рассылки разработчиков — д'Артаньянство. Кроме того, ваша «реализация» с нуля да ещё и неопубликованная — типичный синдром NIH. Если бы вы хоть немного ценили своё время, вы опять таки бы написали патч, а не писали с нуля, и кроме того — опубликовали бы сразу.
1. STL не использую, хотя признаю ее чисто «образовательную пользу».
2.… дополнительно определяется, как черный узел nil, что все нарушает...+ссылка на книгу откуда руки растут
3.… + есть понимание, что надо использовать NULL…
4. Если кому интересна реализация на C++ могу выложить ее + краткое описание, но только на freehabr.ru/
5. Сотне не самых глупых инженеров предлагаю на основании моих замечаний написать патч, чтобы не быть сотней д'Артаньянов.
Шарль-Сеза́р де Рошфо́р
2.… дополнительно определяется, как черный узел nil, что все нарушает...+ссылка на книгу откуда руки растут
3.… + есть понимание, что надо использовать NULL…
4. Если кому интересна реализация на C++ могу выложить ее + краткое описание, но только на freehabr.ru/
5. Сотне не самых глупых инженеров предлагаю на основании моих замечаний написать патч, чтобы не быть сотней д'Артаньянов.
Шарль-Сеза́р де Рошфо́р
Не лишним было бы добавить ещё в статью просто определения B- и красно-черных деревьев (или хотя бы ссылочки на википедию).
А ещё интересно, с какой скоростью работал бы map, реализованный на хэш-таблицах, по сравнению с B/red-black деревьями.
А чем отличается от реализации stx::btree?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
С++ библиотека от Google с контейнерами map и set на B-деревьях