Comments 51
Ну вообще да. Если мы говорим о системах способных запускать Линукс, то там уже не надо париться об эфективности управления памятью. Всё уже украдено сделано до нас.
Другое дело — всякие OSless системы, где аллокатор вроде бы и есть, но чаще всего сделан довольно топорно. В основном из-за ограничений самой архитектуры (например — нету MMU).
Иными словами — если у вас не жёсткий embedded и вы не пишете числодробилку/БД/высоконагруженный сервис — не думайте о сложности, делайте как вам удобнее. Всё равно, когда дело дойдет до узких мест — они будут совершенно не там, где вы ожидаете.
Другое дело — всякие OSless системы, где аллокатор вроде бы и есть, но чаще всего сделан довольно топорно. В основном из-за ограничений самой архитектуры (например — нету MMU).
Иными словами — если у вас не жёсткий embedded и вы не пишете числодробилку/БД/высоконагруженный сервис — не думайте о сложности, делайте как вам удобнее. Всё равно, когда дело дойдет до узких мест — они будут совершенно не там, где вы ожидаете.
А в системах, в которых можем упереться в фрагментацию памяти — виртуальное адресное пространство IMO первое, что надо сделать. А дальше можно realloc-ать направо и налево.
А в жёстком embedded'е всё тем более не имеет смысла заниматься оптимизациями не имея данных о том, что тормозит. Ибо в «больших» системах у вас есть хотя бы путеводитель в лице «O большого», а в системах, которые по своей природе ограничены проблемы могут быть совсем-совсем не там где вы их ждёте и на тех объёмах, на которых вы собрались работать O(N³) легко может оказаться быстрее, чем O(N²), а иногда может быть и быстрее, чем O(N).
tcmalloc & jemalloc нам в помощь
за статьи спасибо, а так же за книгу
думаю знания пригодятся в жизни
за статьи спасибо, а так же за книгу
думаю знания пригодятся в жизни
Отличная статья, спасибо!
Интересно, как это реализовано в Win32…
Интересно, как это реализовано в Win32…
Вызова VirtualRealloc нет — поэтому оно работает хуже линуксовой версии. Хотя это ограничение и можно обойти через явное отображение файла подкачки на память — сильно сомневаюсь, что стандартная библиотека C использует этот механизм.
Я покопался в коде ReactOS, смотрел, как ReallocHeap реализован. Тоже через копирование.
Можно подробнее, что вы имеете в виду, что это даст?
через явное отображение файла подкачки на память
Можно подробнее, что вы имеете в виду, что это даст?
buffer = realloc(buffer, capa);Так может утекать память. Если realloc не смог выделить память, теряется предыдущий адрес, на который указывал buffer.
В остальном разбор неплохой, спасибо.
Там же в следующей строке assert торчит.
Всё равно мало какая программа умеет корректно обрабатывать недостачу памяти.
Всё равно мало какая программа умеет корректно обрабатывать недостачу памяти.
Хм, действительно. Конечно да, упасть при нехватке памяти — решение. Но для embedded, к примеру, не подойдёт.
Для драйверов тоже не пойдет.
Мне почему-то кажется, что не только меня бесит, когда при работе на грани доступной памяти система в произвольный момент времени может умереть.
Для прояснения контекста: работаю без SWAP, т.к. если Java начинает вытесняться в SWAP все становится ну очень печально — проще все закрыть и открыть заново.
P.S. В Windows 7 по сравнению с предыдущими версиями получить эту ошибку на уровне драйвера намного труднее.
Мне почему-то кажется, что не только меня бесит, когда при работе на грани доступной памяти система в произвольный момент времени может умереть.
Для прояснения контекста: работаю без SWAP, т.к. если Java начинает вытесняться в SWAP все становится ну очень печально — проще все закрыть и открыть заново.
P.S. В Windows 7 по сравнению с предыдущими версиями получить эту ошибку на уровне драйвера намного труднее.
Только лучше всё-таки не x2 а x1.5 делать, чтобы не получилось так, что памяти еще вагон, а адресное пространство уже закончилось.
В чем суть стратегии «увеличивать вдвое»? Почему именно вдвое? Если неизвестно, какие данные записываются и с какой скоростью, непонятно, какой необходим прирост. Есть ли какие-то изыскания по этой теме?
Если мне не изменяет память, то у Кнута (по моему в первом томе в конце) есть пример аллокатора, подбирающего свободный блок за O(1) время. Особенность этого аллокатора была в том, что пространство выделяется размером равным степени двойки. Возможно поэтому повелось удваивать пространство при реаллокации.
Кроме того не вижу ни одного повода не удваивать его, ибо если мы удваиваем куски, то теоретически его можно эффективнее менеджить, т.к. любой свободный кусок может быть представлен как 2^n+2^(n-1)+2^(n-2)+...+2^1+2^0 (часть членов может остутсвовать)
Кроме того не вижу ни одного повода не удваивать его, ибо если мы удваиваем куски, то теоретически его можно эффективнее менеджить, т.к. любой свободный кусок может быть представлен как 2^n+2^(n-1)+2^(n-2)+...+2^1+2^0 (часть членов может остутсвовать)
Особенность этого аллокатора была в том, что пространство выделяется размером равным степени двойки. Возможно поэтому повелось удваивать пространство при реаллокации.
Я наивно думал, что любой аллокатор стремится оперировать блоками размера степени двойки. Более того, точно знаю, что с некоторыми аллокаторами (например, FastMM для Delphi) затребование блоков именно такого размера уменьшает фрагментацию.
Кроме того не вижу ни одного повода не удваивать его
Размер растет слишком быстро, в итоге получается, что после определенного момента мы для записи лишнего байта будем выделять мегабайты памяти, это неоптимально.
Мне кажется, логичным был бы множитель вроде логарифма от какого-то параметра, т.е. крутой рост в самом начале, когда будет много вызовов и более пологий рост в конце.
Размер растет слишком быстро, в итоге получается, что после определенного момента мы для записи лишнего байта будем выделять мегабайты памяти, это неоптимально.А вы уверены, что менджер памяти не выделяет на самом деле степень двойки, при запросе блока произвольного размера? Я считаю что прежде чем вот так свободно оперировать множителем (мол 1.5х лучше чем 2х) — нужно изучить конкретный аллокатор памяти. Ну и опять же 2x нам обеспечивает значительно меньшую фрагментацию памяти (но за это мы платим оверхедом используемой памяти до 50% в худшем случае).
Мне кажется, логичным был бы множитель вроде логарифма от какого-то параметра, т.е. крутой рост в самом начале, когда будет много вызовов и более пологий рост в конце.Не забываем, что при реаллокации может производится копирование, а чаще ёрзать блоком в кучу мегабайт — не самый оптимальный вариант, имхо.
А вы уверены, что менджер памяти не выделяет на самом деле степень двойки, при запросе блока произвольного размера?
Зависит от конкретного менеджера памяти.
Я считаю что прежде чем вот так свободно оперировать множителем (мол 1.5х лучше чем 2х) — нужно изучить конкретный аллокатор памяти.
И я тоже. Странно, что вы мне это пишете.
Ну и опять же 2x нам обеспечивает значительно меньшую фрагментацию памяти (но за это мы платим оверхедом используемой памяти до 50% в худшем случае).
Значительно меньшую чем при каком выделении?
Не забываем, что при реаллокации может производится копирование, а чаще ёрзать блоком в кучу мегабайт — не самый оптимальный вариант, имхо.
Все как всегда — нельзя выиграть одновременно в силе и перемещении.
ну вот совсем недавно писали, что
можно математически доказать, что константа 2 — строго худшее из всех возможных значений
Там же были комменты, наполненные куда меньшей категоричностью по данному вопросу. Этот, например.
UFO just landed and posted this here
Если у вас в 32-х битном приложении массив одним куском размером в 1.5Гб — то у вас явно проблема с архитектурой. Выделять такой кусок памяти — явно не здоровая идея.
Необходимо выделить, как минимум, 2 буфера под изображение 24576*6000 px. Посоветуете, как мне улучшить архитектуру приложения? </ирония>
Очевидно: пользуйтесь изображениями 245*60
Тайлы? Вы бы всю задачу описали. А то выглядит в духе:
> А мне надо пол гига одним куском </конец иронии>
> А мне надо пол гига одним куском </конец иронии>
Могу ответить за автора. Если у вас какая-нибудь числодробилка или обработка изображений (например, сделать euclidean distance transform с картинкой—да или просто инвертировать биты в изображении), то часто перфоманс будет ограничен скоростью доступа к памяти. Если выделить память под картинку одним куском, то перфоманс вполне может быть в полтора раз больше, чем, к примеру, если выделять массив массивов (потому что у вас в два раза меньше прыжков по памяти) или выделять тайлы (те быстрые алгоритмы EDT, что я знаю, не могут обрабатывать тайл за тайлом). А если это не одна картинка, а тысяча штук таких картинок (реконструкция человеческой почки какая-нибудь для исследований), то обработка в 1,5 раза быстрее очень даже желательна. Так или иначе, выделять одним куском—самая лучшая стратегия с точки зрения производительности (в первом приближении).
В euclidean distance transform перфоманс будет ограничен кеш линией процессора. Тайлы будут эффективнее одного куска. А еще эффективнее тайлы + кривая мортона, ибо в изображении шириной 24576 пикселей кешмиссы будут лететь направо и налево.
Если инвентировать биты — то между тайлами и цельным куском вы без микроскопа не разберете. О полутора раз тут не может быть и речи.
> Так или иначе, выделять одним куском—самая лучшая стратегия с точки зрения производительности
Выделять — может быть да. Работать с одним куском — скорее всего нет.
Если инвентировать биты — то между тайлами и цельным куском вы без микроскопа не разберете. О полутора раз тут не может быть и речи.
> Так или иначе, выделять одним куском—самая лучшая стратегия с точки зрения производительности
Выделять — может быть да. Работать с одним куском — скорее всего нет.
Выделять — может быть да. Работать с одним куском — скорее всего нет.
Вот Вам палочки в колесо Ваших рассуждений.
— что копируется быстрее из одного участка памяти, в другой?
1) данные лежащие последовательно.
2) данные лежащие разрозненно.
— поиск в каком бинарном дереве будет производиться быстрее?
1) в том, в котором узлы лежат в памяти последовательно (дочерние узлы лежат в памяти сразу за родительским).
2) в том, в котором узлы разбросаны по памяти как попало.
Я могу еще много примеров как придумать, так и привести из личного опыта. Это раз.
Теперь два.
ибо в изображении шириной 24576 пикселей кешмиссы будут лететь направо и налево.
То есть, если данные у нас в памяти лежат последовательно, то будет больше промахов кэша? Вы серьезно?:)
То есть, если данные у нас в памяти лежат последовательно, то будет больше промахов кэша? Вы серьезно?:)Именно так, только надо был всю мою фразу цитировать. Там был разговор о euclidean distance transform, а эти преобразования предполагают обращение строками выше и строками ниже.
Да и вообще я предлагаю заканчивать ваш троллинг. Почитайте вот тут сначала:
en.wikipedia.org/wiki/Z-order_curve
а еще вот тут хорошее, но тяжелое чтиво:
etd.uwaterloo.ca/etd/wmyee2004.pdf
1) Вы, я так понимаю, не в курсе, что в L2 кэш даже старичка Pentium III свободно помещаются от 7 до 21 (в зависимости от битности) строки изображения шириной 24576 px. Что уж говорить о современных процессорах, где появился L3 кэш >= 3Mb. Если данные разбросаны в памяти, вот тогда и имеет смысл говорить о кэш промахах. А когда они лежат друг за другом, то программист сделал все правильно и свел явление Cache Miss к минимуму.
2) Если у Вас заканчиваются контраргументы, это не значит, что Вас троллят.
3) Читал. Не понимаю как эти ссылки доказывают Ваши утверждения или опровергают мои.
4) Привет от SSE/AVX инструкций.
2) Если у Вас заканчиваются контраргументы, это не значит, что Вас троллят.
3) Читал. Не понимаю как эти ссылки доказывают Ваши утверждения или опровергают мои.
4) Привет от SSE/AVX инструкций.
1. Интересно, вы слышали про виртуальное адресное пространство? В одной 24576px строке аж 6 страниц памяти. Вы я так понимаю наивно полагаете, что если вы выделили кусок памяти, то он так и лежит в памяти, одним куском. В общем даже не смотря на то, что помещается аж 7 строк — кешмиссы будут значительно чаще. Почему — оставлю вам в качестве домашнего задания. Мне надоело объяснять. Я на современном процессоре получал прирост до 3-4 раз в рендере частиц на CPU используя того же мортона.
2. У меня нет контраргументов к вам, только потому что вы никогда не занимались подобными оптимизациями. Иначе вы бы не говорили такую чушь.
3. Плохо читали. То что я вам дал — показывает как можно оптимизировать данные под кеш, и там нет требований в «одном куске»
4. Да да, кунгфу и еще много страшных слов.
2. У меня нет контраргументов к вам, только потому что вы никогда не занимались подобными оптимизациями. Иначе вы бы не говорили такую чушь.
3. Плохо читали. То что я вам дал — показывает как можно оптимизировать данные под кеш, и там нет требований в «одном куске»
4. Да да, кунгфу и еще много страшных слов.
1) Более того, я даже про TLB и про блок предсказаний ничего не слышал. Да что там, аппаратный Prefetch для меня пустой звук:)
По сравнению с чем? Я так и не дождался ответа.
Нет уж, Ваши домашние задания за Вас я не выполню.
2) Вам видней. Но есть одно НО! Зачем нужен большой кусок памяти и почему архитектура тут не причем, я обосновал, пример привел. Почему работа с последовательно расположенными в памяти данными идет быстрей, выше привел 2 тривиальных примера, которые отвечают на этот вопрос. От Вас в свой адрес я пока слышу только слова о моей не компетентности. Делаем выводы.
3) Под чей кэш? Мы может про разные устройства говорим. Я вот про CPU.
UPD: Даже, специально для Вас нашел перевод. Обратите внимание на «Однопоточный последовательный доступ» и на «Измерение однопоточного доступа, осуществляемого в произвольном порядке».
4) То есть, все таки не поняли намека, и как он связан со всем, что я говорил про выравнивание и последовательность в памяти.
В общем даже не смотря на то, что помещается аж 7 строк — кешмиссы будут значительно чаще.
По сравнению с чем? Я так и не дождался ответа.
Почему — оставлю вам в качестве домашнего задания.
Нет уж, Ваши домашние задания за Вас я не выполню.
2) Вам видней. Но есть одно НО! Зачем нужен большой кусок памяти и почему архитектура тут не причем, я обосновал, пример привел. Почему работа с последовательно расположенными в памяти данными идет быстрей, выше привел 2 тривиальных примера, которые отвечают на этот вопрос. От Вас в свой адрес я пока слышу только слова о моей не компетентности. Делаем выводы.
3) Под чей кэш? Мы может про разные устройства говорим. Я вот про CPU.
UPD: Даже, специально для Вас нашел перевод. Обратите внимание на «Однопоточный последовательный доступ» и на «Измерение однопоточного доступа, осуществляемого в произвольном порядке».
4) То есть, все таки не поняли намека, и как он связан со всем, что я говорил про выравнивание и последовательность в памяти.
Почему работа с последовательно расположенными в памяти данными идет быстрей
Последовательно расположенными в физической памяти?
А Вы умеете выделять физически непрерывную память в user mode? Расскажете как?
Об этом и речь. Понятно, что TLB. Насколько быстрее работа с последовательными данными именно в виртуальной памяти? Что именно кешируется в L2? Я спрашиваю, без подколок. Интересно же.
Лучше один раз увидеть, чем сто раз услышать.
Я переписал Ваш код на C и что меня удивило. Если компилировать без оптимизации — то результат: небольшое отставание когерентного массива.
Но при оптимизации (Bang!) Random выхватывает по полной.
И это ещё не самое главное. При ещё большем ускорении ситуация для Random только хуже (Тарарах-тах-тах!):
Прикол в том, что, чем сильнее оптимизация тем сильнее замедляется Random и сильнее ускоряется Coherent. Ну и ну. Хотел бы я знать про эти подводные камни.
Вот код.
sh-4.3$ gcc -o main *.c
sh-4.3$ main
Coherent array avg search - 5187.44 μs
1048575
Random array avg search - -4005.54 μs
1048575
Но при оптимизации (Bang!) Random выхватывает по полной.
sh-4.3$ gcc -O3 -pipe -fomit-frame-pointer -Wall -Werror -o main *.c
sh-4.3$ main
Coherent array avg search - 2837.95 μs
1048575
Random array avg search - 4514.26 μs
1048575
И это ещё не самое главное. При ещё большем ускорении ситуация для Random только хуже (Тарарах-тах-тах!):
sh-4.3$ gcc -march=native -O3 -pipe -fomit-frame-pointer -Wall -Werror -o main *.c
sh-4.3$ main
Coherent array avg search - 2686.56 μs
1048575
Random array avg search - 4637.16 μs
1048575
Прикол в том, что, чем сильнее оптимизация тем сильнее замедляется Random и сильнее ускоряется Coherent. Ну и ну. Хотел бы я знать про эти подводные камни.
Вот код.
Такие требования — данность. И не важно какая архитектура всего приложения. Необходимо просто выделять буферы большого размера для хранения и обработки изображений в режиме реального времени(двойная буферизация: один обрабатывается, другой заполняется). Как и сказал Bas1l, такой буфер выделять лучше в непрерывной памяти, а также необходимо, чтобы адрес был выровнен (2 профита — данные в кэше + скорость выполнения машинных инструкций на кратных адресах).
Я это все к тому, что не всегда верно утверждать —
Я это все к тому, что не всегда верно утверждать —
Если у вас в 32-х битном приложении массив одним куском размером в 1.5Гб — то у вас явно проблема с архитектурой.
Такие требования — данность. И не важно какая архитектура всего приложения. Необходимо просто выделять буферы большого размераВы задачу можете привести в пример? Задачу которая требует одним куском такой буфер. А то пока только аргумент «а мне нужно». Двойная буферизация — не аргумент. Храните оба буфера как тайлы 512*512, какие проблемы?
Есть куча возможностей работать с огромными данными. Винда вон например маппит адресное пространство. Так что я не верю в такую данность.
То есть, фраза
для Вас не пример?:) Хорошо, распишу подробней.
Необходимо в режиме реального времени обработать изображение, которое приходит с N камер. Конечное изображение получается «склеиванием» кадров со всех камер. В зависимости от количества камер и их разрешения, может получится изображение 24576*6000, а может и больше. Время на обработку данного изображения ~200мс. Какого рода обработка? Буду краток — сложные алгоритмы и их много.
Вангую, сейчас будет вопрос, почему эти 2 буфера должны быть в непрерывном куске памяти:)
<ирония>Так Вы что-то говорили про тайлы и маппинг?</ирония>
буферы большого размера для хранения и обработки изображений в режиме реального времени
для Вас не пример?:) Хорошо, распишу подробней.
Необходимо в режиме реального времени обработать изображение, которое приходит с N камер. Конечное изображение получается «склеиванием» кадров со всех камер. В зависимости от количества камер и их разрешения, может получится изображение 24576*6000, а может и больше. Время на обработку данного изображения ~200мс. Какого рода обработка? Буду краток — сложные алгоритмы и их много.
Вангую, сейчас будет вопрос, почему эти 2 буфера должны быть в непрерывном куске памяти:)
<ирония>Так Вы что-то говорили про тайлы и маппинг?</ирония>
В худшем случае все стратегии, кроме экспоненциальных, дают квадратичную сложность, к сожалению.
Лень!
Отсталость только подумать как код с realloc() будет работать в случае OMP_NUM_THREADS>1 на современном 12-корнике например.
Sign up to leave a comment.
История про realloc (и лень)