[jewish humor] malloc
Это не только С, но и С++ касается, хе хе. И потом они гонят волну на GC.
И потом они гонят волну на GC.за ГЦ пасть порву!
не стоит просто кидаться фразами, что ГЦ гавно, тормозит или вообще не может в принципе справляться со своей задачей, пока не заботаешь основательно принципы его работы
> Ходит по связанным спискам блоков в поисках свободной дыpки. Если сделать
> подpяд несколько malloc полyчится как pаз алгоpитм Шлемазла.
Откуда такие сведения? malloc вообще-то не глупые люди писали. Есть алгоритмы, которые работают за время с асимптотикой O(log N) или лучше.
> подpяд несколько malloc полyчится как pаз алгоpитм Шлемазла.
Откуда такие сведения? malloc вообще-то не глупые люди писали. Есть алгоритмы, которые работают за время с асимптотикой O(log N) или лучше.
log n это тоже немало. Особенно если сравнивать с gc-шным выделением.
А вот кстати давно хочу спросить: стандартная библиотека она на сколько стандартна (компиляторонезависима)?
В ISO же о том как конкретно функции реализовывать не написано?
В ISO же о том как конкретно функции реализовывать не написано?
Особенно если сравнивать с gc-шным выделениемЧто это за зверь ?
А GCшное выделение память у святого духа берёт что ли? Тоже на какой-нибудь куче выделяет и тоже имеет накладные расходы. А в C++ malloc никто тебя не заставляет юзать. Переопределяешь new и юзаешь любой удобные тебе аллокатор, хоть стековый, хоть стандартный виндовый, хоть из стандартной сишной библиотеке, хоть специальный для строк. У них у всех свои плюсы и минусы и свои области применимости - где то приходится платить накладными расходами при выделении, где-то - при освобождении, где-то - большой фрагментацией и т.д. Но gc тут не выигрывает нисколько, а в сложных случаях - проигрывает.
А GCшное выделение память у святого духа берёт что ли?Большинство GC выделяет память за O(1 т.к. заполняют память последовательно.
И что? Они же её рано или поздно освобождают всё равно. После этого имеют либо огромную фрагментацию, либо очень большой гемор с переиспользованием памяти. И что GC будет делать, когда адресное пространство исчерпает? Перекраивать всю память?
И что GC будет делать, когда адресное пространство исчерпает? Перекраивать всю память?Да. Он проходит по всей памяти, находит дохлые куски, схлопывает живые, переписывает ссылки. Процесс называется сборка мусора и подробно описан, например, тут.
Достоинствами GC является быстрое выделение памяти и отсутствие необходимости ручного контроля за удалением, за что приходится платить периодическими сборками мусора
Ну вот, я тебе могу афторитетно заявить, что пока адресное пространсто 32-битное, стандартный виндовый аллокатор в среднем более эффективен, чем такая сборка мусора с перекраиванием всех ссылок. А если память у тебя 64-битная и адресного пространства у тебя дохрена, то можно заюзать стековый аллокатор, что ещё эффективнее.
И, внимание, сюрприз. Отображение виртуальной памяти в физическую тоже ведь какими-то аллокациями пользуется. И GC в любом случае использует эти аллокации, которые работают не за O(1 а асимптотически так же, как и стандартные сишные, наверное.
PS. На самом деле про асимптотику тут говорить глупо, время на работу с памятью тратится не на асимптотике, а на коэфициентах при них, т.е. надо всё в секуднах и тактах мерить.
И, внимание, сюрприз. Отображение виртуальной памяти в физическую тоже ведь какими-то аллокациями пользуется. И GC в любом случае использует эти аллокации, которые работают не за O(1 а асимптотически так же, как и стандартные сишные, наверное.
PS. На самом деле про асимптотику тут говорить глупо, время на работу с памятью тратится не на асимптотике, а на коэфициентах при них, т.е. надо всё в секуднах и тактах мерить.
> Большинство GC выделяет память за O(1 т.к. заполняют память последовательно.
В теории оно, конечно, так, но на практике память быстро кончается и нужно делать какой-нибудь mark-sweep или copying collection. И то, и то — достаточно тормозная вещь. Если почитать книжку, то становится ясно, что не все так просто, как хотелось бы. Могу дать PDF с книжкой (куда выложить? — думаю многим будет интересно).
В результате получается 1+1+..+МЕГА_БОЛЬШОЕ_ЧИСЛО+1+1, и среднее (амортизированное) время будет достаточно приличное
Кроме того, при GC сильно разрушается локальность. Допустим, ты в цикле создаешь объект и удаляешь его. При malloc/free память будет отдаваться сразу, поэтому все это будет крутиться на одном куске памяти. В GC будет происходить что-то типа heap = heap - size, поэтому каждый раз будут выделяться новые куски. Рано или поздно засрется весь объем памяти, выделяемый на кучу, что вызовет GC. То есть программа, у которой working set size равен 1 Mb при работе с GC может легко засрать 1000 Mb. Ну и кроме того, все это негативно влияет на кэш.
Думаю, Kim меня поправит, ему скоро диссер защищать по этой теме
В теории оно, конечно, так, но на практике память быстро кончается и нужно делать какой-нибудь mark-sweep или copying collection. И то, и то — достаточно тормозная вещь. Если почитать книжку, то становится ясно, что не все так просто, как хотелось бы. Могу дать PDF с книжкой (куда выложить? — думаю многим будет интересно).
В результате получается 1+1+..+МЕГА_БОЛЬШОЕ_ЧИСЛО+1+1, и среднее (амортизированное) время будет достаточно приличное
Кроме того, при GC сильно разрушается локальность. Допустим, ты в цикле создаешь объект и удаляешь его. При malloc/free память будет отдаваться сразу, поэтому все это будет крутиться на одном куске памяти. В GC будет происходить что-то типа heap = heap - size, поэтому каждый раз будут выделяться новые куски. Рано или поздно засрется весь объем памяти, выделяемый на кучу, что вызовет GC. То есть программа, у которой working set size равен 1 Mb при работе с GC может легко засрать 1000 Mb. Ну и кроме того, все это негативно влияет на кэш.
Думаю, Kim меня поправит, ему скоро диссер защищать по этой теме
>Это не только С, но и С++ касается, хе хе. И потом они гонят волну на GC.
В адекватных С/С++ программах, для которых выделение памяти критично, она выделяется за ~O(1). Проблема как всегда, отнюдь не в языке, а в программистах
ЗЫ Любителям GC предлагаю в воспитательных целях поработать в Windows Vista на компе с 512Mb RAM.
В адекватных С/С++ программах, для которых выделение памяти критично, она выделяется за ~O(1). Проблема как всегда, отнюдь не в языке, а в программистах
ЗЫ Любителям GC предлагаю в воспитательных целях поработать в Windows Vista на компе с 512Mb RAM.
ЗЫ Любителям GC предлагаю в воспитательных целях поработать в Windows Vista на компе с 512Mb RAM.Vista не на основе GC сделана
По просьбам трудящихся выложил книжку: http://www.rapidshare.ru/465410
спасибо.
А ты не забываешь про внутренную фрагментацию?
Если в 4 кб странице лежат два объекта в 4090 и 6 байт соответственно, а ты решишь удалить второй, внутренняя фрагментация скушает 4090 байтов физической памяти/места в swap. Если этого пытаться избежать, O(1) в аллокаторе, основанном на неуправляемой куче уже не добиться без специальной ручной обработки запросов.
Если в 4 кб странице лежат два объекта в 4090 и 6 байт соответственно, а ты решишь удалить второй, внутренняя фрагментация скушает 4090 байтов физической памяти/места в swap. Если этого пытаться избежать, O(1) в аллокаторе, основанном на неуправляемой куче уже не добиться без специальной ручной обработки запросов.
В адекватных С/С++ программах, для которых выделение памяти критично, она выделяется за ~O(1).Адекватные - это где аллокаторы руками написаны, как отцы тут советуют ?
Адекватные - это где аллокаторы руками написаны, как отцы тут советуют ?Зачем всё усложнять? Есть уже готовые аллокаторы, например, dmalloc от Doug Lea. Работает очень хорошо, намного быстрее стандартного виндового malloc'а. Кроме того, можно всегда проанализировать, что происходит или будет происходить в твоей программе и исходя из этого грамотно пользоваться выделением памяти. Если алгоритм создания новых объектов написан хорошо, то можно будет использовать стандартные аллокаторы без ущерба производительности. (А если плохо, то даже O(1) не спасёт.)
В результате получается 1+1+..+МЕГА_БОЛЬШОЕ_ЧИСЛО+1+1, и среднее (амортизированное) время будет достаточно приличноеТы не рюхаешь. В нормальном аллокаторе с GC МЕГА_БОЛЬШОЕ_ЧИСЛО равно числу освободившихся блоков со времени последней сборки мусора. А оно не больше числа всех выделенных объектов. Поэтому амортизированное время всё равно равно O(1).
Ты не рюхаешь. В нормальном аллокаторе с GC МЕГА_БОЛЬШОЕ_ЧИСЛО равно числу освободившихся блоков со времени последней сборки мусора. А оно не больше числа всех выделенных объектов. Поэтому амортизированное время всё равно равно O(1).Если написать GC грамотно, то можно сделать так, что время его работы будет иметь вид C*число выделенных блоков. И среднее время получается C+1 = O(1). Но фишка в том, что C очень большое. Достаточно хороший C реализован в OCaml (вроде бы). В Java-подобных языках C оказывается весьма приличной величиной.
И, кроме того, ты не учитываешь, что такие бегания по всей памяти взад-вперед при обходе ссылок очень плохо влияют на кэш и virtual memory.
В С++ очень много объектов удается создавать на стеке — это дает большой выигрыш в производительности.
Предлагаю написать какой-нибудь бенчмарк. В цикле создавать кучу объектов и присваивать ссылки туда-сюда. Интересно посмотреть, сколько это будет работать на Java и на C++.
придумать примеры и контрпримеры можно на любой алгоритм
- доктор, у меня GC тормозит когда я в цикле создаю и удаляю миллион хитросвязанных объектов
- не делайте так
- доктор, у меня GC тормозит когда я в цикле создаю и удаляю миллион хитросвязанных объектов
- не делайте так
Если в 4 кб странице лежат два объекта в 4090 и 6 байт соответственно, а ты решишь удалить второй, внутренняя фрагментация скушает 4090 байтов физической памяти/места в swap.Ты, наверное, имел в виду "удалить первый"? :]
> алгоритм создания новых объектов
а что это такое то?
типа объекты нужно создавать не тогда, когда они потребуются?
а что это такое то?
типа объекты нужно создавать не тогда, когда они потребуются?
> алгоритм создания новых объектовТипа объекты нужно создавать грамотно. Например, наращивать вектор логарифмически.
а что это такое то?
типа объекты нужно создавать не тогда, когда они потребуются?
Типа объекты нужно создавать грамотно. Например, наращивать вектор логарифмически.Таки либо это функциональность стандартной библиотеки (как в этом примере либо всё же собственный аллокатор.
Ещё к грамотности относится, например, то, что, если ты заранее знаешь размер массива - лучше бы этот массив сразу такого размера делать, а не добавлять в него по одному элементу.
И этим должен заниматься именно сам разработчик.
И этим должен заниматься именно сам разработчик.
Таки либо это функциональность стандартной библиотеки (как в этом примере либо всё же собственный аллокатор.Что ты понимаешь под собственным аллокатором? Если я сам в каком-нибудь массиве буду выделять память так, чтобы уменьшить количество копирований - это уже собственный аллокатор?
Ну а что это по-твоему?
Ну а что это по-твоему?Это грамотное выделение памяти. Точно так же её выделяют в Java/C#: никто не наращивает массивы по одному элементу.
> Если я сам в каком-нибудь массиве буду выделять память так
выделять память под ссылки на элементы, или под сами элементы.
если под сами элементы, то скорее это уже свой собственный аллокатор получается.
выделять память под ссылки на элементы, или под сами элементы.
если под сами элементы, то скорее это уже свой собственный аллокатор получается.
выделять память под ссылки на элементы, или под сами элементыДело в том, что в си++ это может совпадать.
> Дело в том, что в си++ это может совпадать.
Если есть массив ссылок - то это уже нельзя назвать грамотным выделением памяти (в тех случаях, которые мне приходят в голову, может и другие есть): кеш и/или prefetch-логика процессора сильно неоптимально используется.
> Точно так же её выделяют в Java/C#: никто не наращивает массивы по одному элементу.
Это делает стандартная библиотека. В ней реализован специальный аллокатор для массивов.
Если программист делает подобное сам, значит, и он реализует свой аллокатор.
Если есть массив ссылок - то это уже нельзя назвать грамотным выделением памяти (в тех случаях, которые мне приходят в голову, может и другие есть): кеш и/или prefetch-логика процессора сильно неоптимально используется.
> Точно так же её выделяют в Java/C#: никто не наращивает массивы по одному элементу.
Это делает стандартная библиотека. В ней реализован специальный аллокатор для массивов.
Если программист делает подобное сам, значит, и он реализует свой аллокатор.
Если есть массив ссылок - то это уже нельзя назвать грамотным выделением памяти (в тех случаях, которые мне приходят в голову, может и другие есть): кеш и/или prefetch-логика процессора сильно неоптимально используется.Здесь было сравнение языков с GC и без. Не вижу, как GC помогал бы хранить элементы ссылочного типа подряд в памяти.
> Точно так же её выделяют в Java/C#: никто не наращивает массивы по одному элементу.В Си++ тоже есть стандартная библиотека. И ещё boost. Этого в 99% случаев вполне хватает для грамотной работы с памятью.
Это делает стандартная библиотека. В ней реализован специальный аллокатор для массивов.
Если программист делает подобное сам, значит, и он реализует свой аллокатор.
Оставить комментарий
state7401281
MG>>> Производительность программы - зависит. Кто гарантирует, что в плохоMG>>> написанном интерпретаторе не проявится алгоритм Шлемиэля
MG>>> (http://russian.joelonsoftware.com/Articles/BacktoBasics.htm l)?
AF>> От этого зависит и пpоизводительность пpогpаммы на C. Как пpавило, в
AF>> pеализации стандаpтной библиотеки алгоpитм Шлемазла пpисyтствyет по
AF>> меньшей меpе в malloc.
VN> Шлемиэля, однако.:)
Это пpосто Joel не знал слова "шлемазл". Оно сюда подходит гоpаздо лyчше. ;-)
VN> А что с malloc?
Ходит по связанным спискам блоков в поисках свободной дыpки. Если сделать
подpяд несколько malloc полyчится как pаз алгоpитм Шлемазла.
http://www.dore.ru/perl/nntp.pl?f=1&gid=22&mid=20065