Комментарии 50
Стоит, наверное, добавить, что множитель 2 — не самый оптимальный.
Допустим, у нас был выделен блок 4 МБ. Потом он вырос вдвое, до 8 МБ.
И пусть так сложилось, что между этими двумя выделениями не было других обращений за памятью. Т.е. эти 4 МБ и 8 МБ, скорее всего, расположены друг за другом.
И теперь, когда будем увеличивать блок до 16 МБ, никак не получится использовать эти освободившиеся блоки.
Хотя, если бы, например, фактор роста был равен 1.5, то блоки были бы 4 МБ и 6 МБ.
И грамотный аллокатор смог бы выделить 9 МБ блок (6 * 1.5) прямо поверх этих 4+6 = 10 МБ.
Решив квадратное уравнение, получим, что оптимальное значение коэффициента равно… золотому сечению — 1.618
Допустим, у нас был выделен блок 4 МБ. Потом он вырос вдвое, до 8 МБ.
И пусть так сложилось, что между этими двумя выделениями не было других обращений за памятью. Т.е. эти 4 МБ и 8 МБ, скорее всего, расположены друг за другом.
И теперь, когда будем увеличивать блок до 16 МБ, никак не получится использовать эти освободившиеся блоки.
Хотя, если бы, например, фактор роста был равен 1.5, то блоки были бы 4 МБ и 6 МБ.
И грамотный аллокатор смог бы выделить 9 МБ блок (6 * 1.5) прямо поверх этих 4+6 = 10 МБ.
Решив квадратное уравнение, получим, что оптимальное значение коэффициента равно… золотому сечению — 1.618
Золотое сечение не годится — чтобы сработал realloc, нам могут потребоваться одновременно два буфера — старый и новый. Разве что, у нас очень умный аллокатор, который умеет для realloc удлиннять буфер «с головы», если там свободно.
НЛО прилетело и опубликовало эту надпись здесь
Мне кажется, тут речь была не о простом realloc'е, а о ситуации, когда мы сначала malloc'ом выделяем буфер нового размера, потом каким-то нетривиальный образом перемещаем в него данные, а затем вызываем для старого участка free (так, например, делает vector в С++ для нетривиально копируемых типов, так как он обязан вызвать для каждого элемента конструктор перемещения). Потому что в случае realloc'a описанной ситуации:
Т.е. эти 4 МБ и 8 МБ, скорее всего, расположены друг за другом.быть не может, на предыдущем шаге наш участок памяти просто расширился бы с 4 мб до 8ми.
НЛО прилетело и опубликовало эту надпись здесь
Не очень понял, что вы хотели сказать. Смотрите, пусть мы действуем вышеописанным способом: делаем malloc для буфера нового размера, потом free для старого. Кроме того, больше никто аллокатором не пользуется. Тогда при malloc'e аллокатор каждый раз будет выдавать нам кусок памяти, непосредственно следующий за текущим куском, то есть наша память будет выглядеть следующим образом:
| ранее использовавшаяся память | старый буфер | новый буфер |
И так будет продолжаться до тех пор, пока кусок ранее использовавшейся памяти не станет достаточно велик, чтобы вместить буфер нового размера. Математически можно показать, что для того, чтобы это хоть когда-нибудь произошло, требуется, чтобы наша константа была меньше золотого сечения.
| ранее использовавшаяся память | старый буфер | новый буфер |
И так будет продолжаться до тех пор, пока кусок ранее использовавшейся памяти не станет достаточно велик, чтобы вместить буфер нового размера. Математически можно показать, что для того, чтобы это хоть когда-нибудь произошло, требуется, чтобы наша константа была меньше золотого сечения.
НЛО прилетело и опубликовало эту надпись здесь
Я об этом выше писал, все эти рассуждения (вида: пусть никто не больше не пользуется аллокатором памяти, тогда ...) имеют смысл только если мы делаем не realloc, а malloc нового блока, а затем free старого.
Есть мнение, что множитель должен быть x=1.3. Для него выполняется условие x^3<x+1, поэтому после захвата буферов длиной 1,x,x^2 (и освобождения первых двух) буфер длиной x^3 захватится снова в начале памяти — на участке, который занимали 1 и x. Кроме того, объём неиспользуемой захваченной памяти будет меньше.
Мне кажется, что этот вопрос должен решаться теми, кто проектирует систему выделения памяти в стандартной библиотеке. Вдруг там блоки каждого фиксированного размера (допустим, степени двойки) выделяются из своего пула.
Ну 1.5 не сильно хуже в данном плане, нужно просто «отложить» побольше места.
Для любого x < φ найдётся такое k, что
xk < xk-2 + … + 1
Это следует из тех соображений, что
xk < xk-2 + … + 1
эквивалентно
xk (x-1) < xk-1 — 1
xk+1 — xk — xk-1 + 1 < 0
xk-1(x2 — x — 1) + 1 < 0
Очевидно, что если мы подствим x = φ, то получим 1 < 0, что неверно для любого k. Но если x = φ — ɛ, то первое слагаемое отрицательно, а для достаточно большого k ещё и очень велико по модулю за счёт экспоненциального роста xk-1
Так, для x = 1.5 нужно взять k=5. Подступаться к φ, конечно, не стоит ибо для x=1.61803398 мы получим k=38.
Для любого x < φ найдётся такое k, что
xk < xk-2 + … + 1
Это следует из тех соображений, что
xk < xk-2 + … + 1
эквивалентно
xk (x-1) < xk-1 — 1
xk+1 — xk — xk-1 + 1 < 0
xk-1(x2 — x — 1) + 1 < 0
Очевидно, что если мы подствим x = φ, то получим 1 < 0, что неверно для любого k. Но если x = φ — ɛ, то первое слагаемое отрицательно, а для достаточно большого k ещё и очень велико по модулю за счёт экспоненциального роста xk-1
Так, для x = 1.5 нужно взять k=5. Подступаться к φ, конечно, не стоит ибо для x=1.61803398 мы получим k=38.
Это очень сильно зависит от того, как работает аллокатор. У современных «быстрых» аллокаторов (tcmalloc от гугла или jemalloc от Facebook и Mozilla), блоки разного размера (до некоторых пределов) выделяются из разных пулов и перееиспользовать освобожденную память не получится. Более того, эти аллокаторы особенно эффективны для размеров равных степени двойки.
В частности, реализация вектора от Facebook использует удвоение до определённого размера, а дальше — увеличение в полтора раза.
В частности, реализация вектора от Facebook использует удвоение до определённого размера, а дальше — увеличение в полтора раза.
Более того, эти аллокаторы особенно эффективны для размеров равных степени двойки.
А степени двойки должен быть равен размер, выделяемый пользователю, или физический размер буфера (включая поля, нужные аллокатору)?
Размер, выделяемый пользователю. Все запросы разделяются на классы по из размеру, и для каждого класса используется пул объектов. Данные самого аллокатора хранятся отдельно.
http://www.canonware.com/download/jemalloc/jemalloc-latest/doc/jemalloc.html
http://www.canonware.com/download/jemalloc/jemalloc-latest/doc/jemalloc.html
Вот ещё пост в фейсбуке от автора jemalloc
https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919
https://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919
Рукожопые быдлокодеры тормозилы пытаются отмазаться, почему у них память течет?
P.S. Кто мне скажет, как показывать потоковое видео jpeg'ами, чтобы не приходилось каждые несколько минут перегружать iframe с видео?
P.S. Кто мне скажет, как показывать потоковое видео jpeg'ами, чтобы не приходилось каждые несколько минут перегружать iframe с видео?
Вы про mjpeg?
Если да, то проверьте FF 34 (а ещё лучше — текущую dev ветку). multipart response довольно заковыристый стандарт, его реализация довольно закрученная (насколько я понимаю, ответ может быть совершенно произвольным, после картинки может придти HTML-страничка), но недавно пофиксили некоторые баги, связанные с ним.
Вообще, несмотря на распространённость данного формата в области стриминга с различных веб-камер, я бы посоветовал использовать что-то более «мейнстримовое», что используется медиаресурсами для онлайн-стриминга видео. Конкретных советов, к сожалению, дать не могу.
Если да, то проверьте FF 34 (а ещё лучше — текущую dev ветку). multipart response довольно заковыристый стандарт, его реализация довольно закрученная (насколько я понимаю, ответ может быть совершенно произвольным, после картинки может придти HTML-страничка), но недавно пофиксили некоторые баги, связанные с ним.
Вообще, несмотря на распространённость данного формата в области стриминга с различных веб-камер, я бы посоветовал использовать что-то более «мейнстримовое», что используется медиаресурсами для онлайн-стриминга видео. Конкретных советов, к сожалению, дать не могу.
FF 34 — рукожопое вырвиглазное дерьмо. Оно выглядит как хромоногая порнография, и тупит так же. У меня сейчас 24.8.0, это последний стабильный огнелис, не зараженный говномесами.
А память как текла, так и течет. И delete() в жабоскрипте объекты не удаляет!
Надо будет, конечно, попробовать стриминг через вебсокеты, но я читал на форумах, что этот способ тоже вызывает утечку памяти.
P.S. Интересно: сколько гомосятины минусующей набежало…
А память как текла, так и течет. И delete() в жабоскрипте объекты не удаляет!
Надо будет, конечно, попробовать стриминг через вебсокеты, но я читал на форумах, что этот способ тоже вызывает утечку памяти.
P.S. Интересно: сколько гомосятины минусующей набежало…
А что делать, если буфер уже размером в гигабайт и нам не хватает 1-4килобайт на операцию? Удвоим не глядя? Конечно, это граничный случай и зачастую такого не бывает… как и описанного в статье.
НЛО прилетело и опубликовало эту надпись здесь
Можно немного по-другому об этом подумать. Есть баланс между тем, как аккуратно используется память, и сколько времени занимает добавление одного элемента в среднем. Скажем, если память увеличивать в 2 раза, то добавление элемента будет стоить 4 условных такта, а если в 1.01 — то примерно 100 таких условных тактов.
При наличии MMU realloc не производит копирований и по сути является бесплатной операцией. Все свои выкладки относительно большого количества «кумулятивно задействованной памяти» можете выбрасывать.
Этот механизм поможет только для больших блоков (больше страницы памяти). По приведенной вами ссылке написано:
И кроме того, такой механизм требует вызова ядра, что само по себе не быстро.
Для очень больших запросов (>= 128 Кб по умолчанию) используются системные средства сопоставления памяти, если они поддерживаются
И кроме того, такой механизм требует вызова ядра, что само по себе не быстро.
И кроме того, такой механизм требует вызова ядра, что само по себе не быстро
Отсутствие затрат на копирование должно покрывать такой overhead.
Этот механизм поможет только для больших блоков (больше страницы памяти)Именно. А маленькие блоки копируются быстро.
Имхо при аддитивной стратегии (каждый раз увеличивать размер на некоторую фиксированную константу) вы на одних вызовах аллокатора просядете, даже если копирование у вас будет дешевым или вообще никогда не будет происходить. Например, если вы будете увеличивать размер со 128 кб до 256 блоками по 64 байта (допустим у нас массив int32 и мы добавляем по 16 элементов каждый раз), то вместо одного-двух вызовов аллокатора вы сделаете 128 * 1024 / 64 = 2048 вызовов, не говоря уж о том, когда счет пойдет на десятки-сотни мегабайт. Так что без какого-либо масштабирования константы такая стратегия в общем случае имхо обречена.
Ну, это уже про игру «обобщённый аллокатор пытается угадать, как его будут использовать». Касательно этого момента посыл был про то, что для перемещения больших блоков в другое место их не надо полностью копировать. Это играет роль в «плохом» случае, когда аллокатор не оказался достаточно сообразительным™ и ему надо что-то перемещать вместо простого сравнения и инкремента. Суть в том, что плохой случай не такой уж и плохой, каким его рисуют, и особенно не такой плохой для больших объёмов данных.
Согласен, но аддитивную стратегию сей факт лучше не делает (о чем собственно и статья). Даже если одно перемещение недорогое, нам придется делать их много, но даже если нам сказочно повезет и ничего никогда перемещать не придется, то все равно имхо мы должны сильно просесть за счет частоты вызова аллокатора.
Это для Linux'а же.
НЛО прилетело и опубликовало эту надпись здесь
Почему неа? Windows умеет realloc in-place делать?
НЛО прилетело и опубликовало эту надпись здесь
Потому что по той ссылке речь идёт о том, что можно реализовать realloc так, чтобы он не копировал память, а вместо этого в ядре перемапить те же страницы в новое место. Для этого необходима поддержка со стороны ядра, конкретно в том случае для этого используется вызов mremap, который является Linux-специфичным.
При том, что ОС следит за распределением памяти и должна помнить, что у какого процесса куда отображается. Нельзя просто так взять и из своего драйвера поправить таблички MMU, ничего не поменяв в объектах системы. У Linux структурки известны и модуль может их спокойно поправить, если ему надо. У Windows кишки ядерного API не документированы, а публичных функций нет, так что поправить тоже можно, но байтики и смещения придётся реверсить.
Во-первых, кишки винды документированы, и вполне неплохо (да, да, я не сравниваю с Линуксом. Неплохо для проприетарной ос).
Во-вторых, в Линуксе модуль структурки не правит, это делается все равно через ядро и стандартный вызов, насколько я понимаю.
В Win есть Mdl, с которыми можно поиграться, но это на уровне драйверов/ядра.
Во-вторых, в Линуксе модуль структурки не правит, это делается все равно через ядро и стандартный вызов, насколько я понимаю.
В Win есть Mdl, с которыми можно поиграться, но это на уровне драйверов/ядра.
Я как раз про уровень ядра.
У Линуксового ядерного модуля есть документированный интерфейс к этим структуркам и даже если бы в ядре не было системного вызова mremap(), я могу написать модуль, который реализует этот функционал, и отправлять ему запросы из юзерленда через специальный файлик в /proc/self или ещё что, получив таким образом свой эразац-сисколл.
А вот для драйвера под Виндоус, судя по документации на MDL, такого интерфейса нет. Конечно, он может поиграться с байтиками, поредактировать какую-то память, и оно может даже заработает, но…
У Линуксового ядерного модуля есть документированный интерфейс к этим структуркам и даже если бы в ядре не было системного вызова mremap(), я могу написать модуль, который реализует этот функционал, и отправлять ему запросы из юзерленда через специальный файлик в /proc/self или ещё что, получив таким образом свой эразац-сисколл.
А вот для драйвера под Виндоус, судя по документации на MDL, такого интерфейса нет. Конечно, он может поиграться с байтиками, поредактировать какую-то память, и оно может даже заработает, но…
Возможно, я совсем-совсем ошибаюсь, но мне кажется, что мы можем описать mdlкой ряд страниц, смапить в виртуальное пространство, потом при расширении, смапить на следующие вирт. адреса встык новый кусок новой Mdlкой. Но может это работает только для драйверов, только для nonpaged памяти — не уверен. Так, чисто в порядке бреда.
О документированности: вот, пожалуйста, виндовые структурки:
О документированности: вот, пожалуйста, виндовые структурки:
//
// I/O system definitions.
//
// Define a Memory Descriptor List (MDL)
//
// An MDL describes pages in a virtual buffer in terms of physical pages. The
// pages associated with the buffer are described in an array that is allocated
// just after the MDL header structure itself. In a future compiler this will
// be placed at:
//
// ULONG Pages[];
//
// Until this declaration is permitted, however, one simply calculates the
// base of the array by adding one to the base MDL pointer:
//
// Pages = (PULONG) (Mdl + 1);
//
// Notice that while in the context of the subject thread, the base virtual
// address of a buffer mapped by an MDL may be referenced using the following:
//
// Mdl->StartVa | Mdl->ByteOffset
//
typedef struct _MDL {
struct _MDL *Next;
CSHORT Size;
CSHORT MdlFlags;
struct _EPROCESS *Process;
PVOID MappedSystemVa;
PVOID StartVa;
ULONG ByteCount;
ULONG ByteOffset;
} MDL, *PMDL;
На Windows можно попробовать сэмулировать подобное поведение, выделяя память с помощью CreateFileMapping(), отображая её себе с помощью MapViewOfFileEx(), а потом UnmapViewOfFile() и снова MapViewOfFileEx() в новое место. (Ни разу не разработчик под Windows, только бегло просмотрел MSDN. Может, там есть нативный вызов, который делает это быстрее.)
А зачем пользователям прошивки игровых приставок браузер? Да и вообще программировать под эту прошивку, если только они не игропейсатели?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Почему буфер должен расти экспоненциально