Publish @IronPeter: Allocator for “search”

IronPeter: @All
Мы тут как-то с Zeux обсуждали С++ аллокатор для “поиска”. Т.е. для stateless программы, в которой просто запускаются jobs. Я собрался с силами и написал вот какую поебень. Память выделяется в чанках, как чанк заполняется, то заполняем новый, malloc делает ref на чанк, free unref. Целиком пустые чанки выкидываем. Вот работает просто заебись. С учетом того, что программа не совсем stateless, в ней есть синглтоны, так что какая-то часть памяти зависает до конца программы. Ну и часть памяти между потоками херачится, обработкой одного запроса несколько тредов занимаются, так что нельзя просто сказать “вот тут начал, вот тут кончил, очисти память”.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
А у тебя у ‘job’ есть ассоциированный с ней чанк? Для всякого локального говна, которое по завершению job можно чистить вообще не задумываясь?

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
не-не. Чанк ассоциирован с тредом. обычная dropin замена malloc/free malloc – определяет, достаточно ли места в старом чанке, выделяет новый и забывает старый; ref++ free – ref–, удалить чанк, если ref==0. так делают аллокаторы для GC с аренами, только с GC еще обычно йобля с компактификацией долгоживущих арен. а тут хуй чего закомпактифицируешь, зато чанк 8K заебись работает. а не мегабайты, как для арен.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
А из треда в тред память не передается никогда? И второй вопрос – если хочется аллоцировать гигабайт-другой, то как это делать с 8к чанком? Собственно, я вот даже проще спрошу. Вот в Apache были (и, наверное, есть) memory pools. С разным временем жизни (всегда, запрос). И было удобно – завершился запрос, все что связано с ним – освободил не думая и куку. В чем отличие у тебя? Казалось бы “для поиска” – вот ровно та же модель, есть короткоживущие аллокации, есть долгоживущие, в момент аллокации – известно, сколько она будет жить. Ну и зачем тогда free() вообще?

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
передается конечно. Все что больше 8K – в отдельных аллокациях страничного размера. В момент аллокации не известно точно, сколько она будет жить.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Тогда я вообще не понял в чем фишка. Кроме борьбы с фрагментацией.

Simon Kozlov: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
Очень быстрая аллокация

Simon Kozlov: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
Петя пишет про то, что передавать всюду эту отдельную арену сложно, когда над запросом работает много тредов/job’ов, которые друг друга зовут, сходятся и расходятся Всюду передавать арену – типа, тяжело

aka.rider: reply @IronPeter
А gperftools не пробовал? Там per-thread arena и общий пул арен. Т.е. аллокация сначала из локальной арены, потом попытка достать арену из общего пула, потом malloc. При удалении арены переползают в общий пул, потом уже удаляются полностью, а вот как удаление в пределах одной арены происходит я не в курсе.

IronPeter: reply @aka.rider
пробовали, как-то не айс.

Andrew Aksyonoff: reply @IronPeter
насколько вырос qps?

IronPeter: reply @Andrew Aksyonoff
2%. При том что аллокатор в профайлере стал занимать 0.4% вместо 0.6%.

Simon Kozlov: reply @IronPeter
А альтернатива – арены передавать?

IronPeter: reply @Simon Kozlov
да если бы работало, там этот контекст очень размазан. ну и синглтоны и всякая поебень. например, есть очередь для статистики, в которую всякая С++ поебень за последнюю минуту складывается. с аренами поебался бы, короче. а так очень влобно и красиво, вся функциональность живет в своем слое.

aruslan: reply @IronPeter
У нас было ровно такое, но ебучий код слишком часто оставлял что-то долгоживущее висеть, и хинтовать показалось слишком нестабильно.
У тебя я так понимаю внезапно долгоживущее не часто блокирует выделенную страницу?
Кстати, ты привязываешь аллокатор к треду чтобы уменьшить перемешивание выделений из других тредов?

Simon Kozlov: reply @aruslan
У вас – это где?

aruslan: reply @Simon Kozlov
В лукасе.

Simon Kozlov: reply @aruslan
Хм, и тоже был паттерн “stateless запроса”?

aruslan: reply @Simon Kozlov
скорее job’а.

Simon Kozlov: reply @aruslan
Насколько я понимаю, Петино добро хорошо работает только если постоянно случается stateless shit Которое поаллоцирует, поаллоцирует, да умрет со всем аллоцированным И таких миллионы

aruslan: reply @Simon Kozlov
да, я понимаю. наши jobы были в меру stateless as in “stateless сами по себе, не считая world object”.
но они каскадно передавали память, и прибивать всё когда конкретный job “по-настоящему” закончился было слишком поздно и геморрно.
очевидное решение было сделать спец максимально lightweight аллокатор и не трогать код сильно — и первая проба была как раз натурально как у Пети.
это дало возможность прибивать существенно раньше, но потом тупо посмотрели lifetime, кто что делает, упростили и переписали чтобы там нахуй это всё не нужно было еяпп. “долгоживущее” – оно в смысле или совсем долго (кэши всякие, это решаемо) или “дольше чем хотелось бы” — память не резиновая.

Simon Kozlov: reply @aruslan
Ну, понятно что с таким аллокатором чем более ты не stateless, тем большим memory overhead’ом за это платишь Теми самыми висящими кусками

IronPeter: reply @aruslan
Ага, не часто блокирует. Все так, как ты говоришь. А perthread оно натурально для скорости и локальности. Не просто многопоточность, еще же NUMA, даже чанки беру со своей нума-ноды. Там вообще забавно. Даже тупой atomic люто тормозит. Например тот самый каунтер нельзя делать атомиком. Нельзя но надо! Че же делать!

Simon Kozlov: reply @IronPeter
На винде кстати были функции, которые делают memory barrier на read, а не на write В смысле, что мол пишешь как придется, а как надо прочитать из другого треда – вызываешь страшную функцию, которая флашит все

IronPeter: reply @Simon Kozlov
нене. Смотри, вот чанк. допустим, он не per thread. как держать у него текущий указатель – атомиком? атомик – сразу жопа-кеды. особенно если он между numa-нодами. но и внутри тоже говно.

Simon Kozlov: reply @IronPeter
Дык а зачем держать текущий указатель, для освобождения?

IronPeter: reply @Simon Kozlov
для добавления malloc’ом. если не per-thread

Simon Kozlov: reply @IronPeter
А, понимаю. Да, per-thread хорошо А когда ты освобождаешь в другом треде – то как?

IronPeter: reply @Simon Kozlov
во, смотри! освобождение – это atomic_decrement. и так оно работает. Но делать атомарным не хочется. Поэтому! Каждый тред держит указатель на “текущий” блок для декремента. И накопленный декремент. и уже atomic’ом его сбрасывает в честный рефкаунтер блока. когда меняется “текущий” блок для декремента.

Simon Kozlov: reply @IronPeter
Т.е. отдаляет деаллокацию, пока не сменится текущий блок?

IronPeter: reply @Simon Kozlov
ага. но это трюки, чтобы почти не было atomics.

Simon Kozlov: reply @IronPeter
Но свой – таки деаллоцирует? Т.е. родной для треда Или тоже ждет переключения? А, он не может То есть всегда ждет переключения

IronPeter: reply @Simon Kozlov
куда денется.

IronPeter: reply @Simon Kozlov
типа, да. очень забавные трюки. Оказывается, что можно thread-специфично аккумулировать не какие-то сложные операции типа добавления в очередь. а тупые atomic сложения, превращая их в обычные сложения, но thread-специфичные.

Simon Kozlov: reply @IronPeter
Ща, момент А типа atomic decrement не вызывает проблем, если одновременно его не-атомарно инкрементируют?

IronPeter: reply @Simon Kozlov
инкрементируют из того треда, где идет аллокация.

Simon Kozlov: reply @IronPeter
Я понимаю. И типа если из другого в этот момент сделали atomic decrement, то с точки зрения треда где аллокация – ничего плохого случиться не может?

IronPeter: reply @Simon Kozlov
может! по этой причине инкременты на malloc идут в другой счетчик :) который atomic’ом же сбрасывается в основной счетчик, когда блок переполнится.

Simon Kozlov: reply @IronPeter
А пока не переполнился – вычитается каждый раз?

IronPeter: reply @Simon Kozlov
как-то так, да.

Simon Kozlov: reply @IronPeter
Надо референс-код выложить!

IronPeter: reply @Simon Kozlov
выложу, он забавный. оказалось, что аккуратно такое написать – это не просто. там самая жопа например с порядком удаления thread local объектов. аллокатор – это обычный thread local объект. В pthreadах. и он вполне может йобнуцца раньше, чем другие объекты, которые зовут free.

Simon Kozlov: reply @IronPeter
Давай. И в бложек лог хуйнем Мне тоже всегда были интересны идеи про аккуратное жонглирование этих ограничений

Simon Kozlov: reply @IronPeter
Ну это значит просто не надо делать free :) Раз мы уже почти мертвые

IronPeter: reply @Simon Kozlov
как не надо! вот кто-то сказал pthread_setspecific с деструктором. создал per-thread int[10] скажем. и хочет его йобнуть.

Simon Kozlov: reply @IronPeter
Что такое pthread_setspecific?

IronPeter: reply @Simon Kozlov
ну смотри, какая семантиках posix tls. можно создать абстрактный ключ. и в каждом треде говорить ему “установись в этот per thread объект”. соответственно этот объект надо родить с помощью malloc. а убиться он должен при смерти треда, так что мы коллбеком присовываем деструктор. деструктор – free или там delete. фишка, что наш аллокатор ровно так же рождается. точнее, его per-thread инстанс.

Simon Kozlov: reply @IronPeter
А можно узнать, что этот malloc для такого объекта и его не оптимизировать? :)

IronPeter: reply @Simon Kozlov
malloc не страшный, страшный delete.

Simon Kozlov: reply @IronPeter
Да понятно. Но может его можно отдать стандартному аллокатору, чтобы он разбирался с delete

IronPeter: reply @Simon Kozlov
в общем такого рода веселые проблемы, да. если в семантике pthreads, то надо сказать pthread_setspecific(0) на tls аллокатор после его удаления. и сделать так, чтобы delete работал если указатель на тред-специфичную часть аллокатора равен 0.

IronPeter: reply @Simon Kozlov
В общем вот: https://github.com/IronPeter/block-alloc там posix-совместимый tls. Тормознее, чем _thread, зато портабельно и наглядно. И в принципе шустро.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Ага, теперь понятно. Спасибо, интересно. А какой средний размер аллокации среди тех, что в 8к влезают? В смысле, по вашей статистике, чтобы совсем понимать ради чего борьба была

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
50 аллокаций на чанк примерно. На 20 потоков использование мелких блоков до 40 мегабайт в прыжке доходит. С аллокациями конечно боролись и бОльшая часть живет в аренах, но мелочь все равно остается, и мелочи дофига в общем.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Ну то есть ~160 байт на аллокацию и 2 мегабайта всего т.е. ~10k аллокаций. Знакомая картина для C++, я ее розгами старался лечить. “Тут будет zero copy и не ебет” Но, наверное, если кода очень много – розги не спасут. На эти 10к аллокаций – будет же и 10к инициализаций

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
как-то так.

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
не, и код относительно разумный, какая-то там сериализация дерева.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Ну так сделать prealloc, чтобы примерно хватило? Но вообще – боль понятная, а C++ – зло

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
ну вот я условно говорю – дерево запроса. В узлах С++ объектиками всякие свойства, Stroka, прости Б-же. оно в других модулях живет, колбасицца, в поиск приходит в сериализованном виде и он дерево восстанавливает.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Свойства же, поди, документов, а не запроса?

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
не, даже запроса, там 1000+ нод. и не спрашивай меня, почему 1000+! т.е. оно так на самом деле, но это отнюдь не единственное место.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Да и не буду. Те, кто увлекаются машинным обучением, первые падут от бунта машин! Ты в понедельник будешь на вашей конференции? Ну вот я бы, в такой ситуации, выебал бы всех – и получал бы дерево as is, нахера его сериализовать, а потом обратно. Но охотно допускаю, что у вас это невозможно не по организационным, а по настоящим причинам. Свечку вашему поиску не держал

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
неа, мне работать надо!

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
А я пока не понял. Если не долечу ангину, то тоже забью. Хотя программа местами интересная

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
проще не выебать, а костылик вставить.

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Зависит от. Эти C++-программисты любят всякие ужасы программировать, вроде пополнения вектора по элементику. Убилбынах То есть розги нужны обязательно, а костылик – уже по месту.

IronPeter: reply @Alex Tutubalin (lexa.ru, alextutubalin@lj)
“розги, выебать, а потом костылик по месту вставить” – это фу. Любить людей надо!

Alex Tutubalin (lexa.ru, alextutubalin@lj): reply @IronPeter
Так розги – любя же! Лучше я, чем какой-нибудь мерзавец

Zeux: reply @IronPeter
Ага. pugixml так работает (только без атомиков). Классно что поиску тоже радостно!

Simon Kozlov: reply @Zeux
В смысле, у тебя тоже нет атомиков?

Zeux: reply @Simon Kozlov
В смысле у меня нет проблемы атомиков, потому что пулы per document, и thread safety тоже per document.

Это произошло на #programming