суббота, 7 ноября 2009 г.

[comp.prog] Сравнение GC и malloc/free

Ссылки на эту работу уже проскакивали на разных ресурсах, но поскольку мне самому приходится периодических их разыскивать, решил опубликовать их еще раз:

Quantifying the Performance of Garbage Collection vs. Explicit Memory Management – 14-ти страничная статья с описанием сравнения (PDF).

Quantifying the Performance of Garbage Collection vs. Explicit Memory Management – 36-ти страничная презентация с более наглядным изложением материала из первой статьи, поэтому легче воспринимается (PDF).

Обе работы датируются 2005-м годом.

В сухом остатке: GC может быть даже быстрее (до 10%), чем ручное управление памятью, но для этого ему требуется в 5 (пять) раз больше свободной памяти.

30 комментариев:

Skynin комментирует...

Добавлю еще из серии "Теория и практика Java":
Аллокация гораздо быстрее, чем вы думаете, и все больше ускоряется

А про расход памяти, да - либо частый запуск GC либо - хип будет чаще всего забит умершими объектами.

Правда, у JVM есть возможности тюнинга, причем пораздельного для юного и старого поколений, но с ручным управлением все равно сравнится не удасться.

eao197 комментирует...

Спасибо, посмотрю (хотя от статей на IBM DeveloperWorks у меня, обычно, впечатления неважные).

Skynin комментирует...

Да, java-сообщество ждет 7ой версии потому что:
java 5 <= 18% faster Java 6 < =46% faster Java 7
За счет:
G1: Java's Garbage First Garbage Collector

В CLR .NET чуть по другому пути пошли - там для выделения памяти меньше 20К используется отдельный хип и сборщик

eao197 комментирует...

>Аллокация гораздо быстрее, чем вы думаете, и все больше ускоряется

Посмотрел эту статью. В ссылках у нее анализ использования malloc/free в C/C++ программах от 1994-го года. Не есть хорошо :)

К тому же, когда сравнивают GC и ручное управление памятью, почему-то умалчивают, что в C/C++ есть еще такие практики, как собственные аллокаторы и пулы.

В разделе про escape-анализ мне показалось, что весь этот сложный механизм приходится городить из-за того, что в Java все объекты -- это экземпляры ссылочных типов. В языках, где есть еще и value-типы и, особенно, иммутабельность данных, ситуация должна быть, имхо, изначально лучше.

>java 5 <= 18% faster Java 6 < =46% faster Java 7

Тут у меня какое-то дежа-вю :) Уже лет девять из стана Java раздаются обещания: "мы еще больше ускорили JVM и уж теперь то мы можем конкурировать с C++ по быстродействию". Но каждая новая Java обещает тоже самое. Если бы эти обещания были выполнены ;), то Java уже давно обогнала бы C++, и не только C++ :)))

Все это шутка. Если Java 7 действительно будет на 46% быстрее Java 6 -- то это просто здорово. Тогда Java действительно будет очень привлекательна в роли этакого высокоуровневого ассемблера для JVM, с помощью которого будут создаваться более продвинутые языки вроде Scala и Fan.

Skynin комментирует...

мы еще больше ускорили JVM и уж теперь то мы можем конкурировать с C++ по быстродействию
Вообще так и есть. За года после появления JIT компилятора в JVM - Java все приближается к скорости кода на С++. При этом сами программисты на java как не думали об, так и не задумываются о всяких auto_ptr'ах.
По тестам в бенчмарк гейм картина показательна, особенно в сравнении с самой собой но в режиме чистой интерпретации - Java 6 -Xint

Но, считаю очевидным что управляемый ЯП никогда не догонит С/С++. Даже когда ядер процессоров будет хватать на потоки сборщиков мусора.

то Java уже давно обогнала бы C++, и не только C++
А вот тут интересно - кого ей осталось обогнать :) Разве что с CLR .NET от MS тягаться.

eao197 комментирует...

>При этом сами программисты на java как не думали об, так и не задумываются о всяких auto_ptr'ах.

Это да, от многих заморочек Java программистов освобождает.

>А вот тут интересно - кого ей осталось обогнать :) Разве что с CLR .NET от MS тягаться.

На вычислительных задачах есть еще и теже самые OCaml с Haskell-ем ;)

Skynin комментирует...

На вычислительных задачах есть еще и теже самые OCaml с Haskell-ем
А-а-а, это там где, молочные реки в кисельных берегах...

Врядли ФП ЯП могут генерить код более скоростной. В силу бОльшей оторванности от представления в железе.
Даже если и могут, ну пусть "догоняют" Java :) Java видит только C/C++ и C#, остальные шибко мелкие :)

А вот что для определенных задач разработка на OCaml с Haskell быстрее и надежней - это конечно.

eao197 комментирует...

>Врядли ФП ЯП могут генерить код более скоростной. В силу бОльшей оторванности от представления в железе.

Не могу говорить о Haskell-е, но у OCaml-а вполне себе императивное подмножество языка имеется. Что и показывают некоторые микробенчмарки (http://www.ffconsultancy.com/languages/ray_tracer/comparison.html и http://wikis.sun.com/display/WideFinder/Results).

Skynin комментирует...

но у OCaml-а вполне себе
Спасибо, еще больше зауважал OCaml и понятней почему MS добавила в ассортимент языков на CLR .NET F#

Skynin комментирует...

Наткнулся на О пресловутой "эффективности" С++
То есть мораль смешная - С++ ведет себя хорошо ровно до того момента, пока не начинается работа с кучей - и с этого момента он превращается в полную ж... даже по сравнению с O'Caml

eao197 комментирует...

>Наткнулся на О пресловутой "эффективности" С++

Это вообще за гранью добра и зла. Исходная задача естественным образом решалась на C++ через возврат Compex по значению. Затем, по предложению какого-то неуча в C++ный вариант добавили использование new. Получилась, мягко говоря, херня, но зато заголовок ну очень громкий :)

Skynin комментирует...

Это вообще за гранью добра и зла.
Вообще-то заголовок постинга "GC и malloc/free". Или подвариант - new в ЯП с GC и без оного. Там он так же указал что в данной задаче new - незачем, но проверить то решил - new, а не оптимальное решение на С++ (оно было проверено в исходном постинге)

То что ручное управление памятью в С/C++ обозначает - создавай свои аллокаторы используя частности задачи (а не - используй штатные malloc/new) там не оспаривалось.
Мало того, сам создавал, когда был в геймдеве. Причем использовал частность - объектов такого-то класса не будет больше n и в самом тяжелом случае они отъедят n*m памяти - и сделал аллокатор который вообще не освобождал память, а по исчерпанию "хипа" начинал с начала, затирая "устаревшие" данные и не проверяя ничего.

Если б рассматривался вопрос - ручное управление против GC - то конечно по эффективности(память и скорость) решений ручное управление не обойти.

eao197 комментирует...

>Вообще-то заголовок постинга "GC и malloc/free". Или подвариант - new в ЯП с GC и без оного.

Так ведь хочется рассматривать случаи, которые имеют смысл. А не как в этом примере -- есть в Scala-варианте new, значит и в C++ должен быть. Тем более в случае, когда используется shared_ptr -- он же вообще два new/delete делает.

Skynin комментирует...

Так ведь хочется рассматривать случаи, которые имеют смысл.
Думается что вопрос тогда - перетекает в область философии по поводу лингвистической проблемы - однозначный перевод с языка на язык - невозможен (только с кучей оговорок насчет частных случаев).

Да, можно сказать что использовать new в С++ в такой ситуации - нечестно.
А если в языках реализованных на JVM не имеет смысла создавать свой аллокатор - и только использовать new (даже нет возможности указать - держи это на стеке!) это честно?

Сравнение ЯП, по моему вообще только и возможно, нечестное, потому что если сравнивать в целокупности - то сравнение преватится в - а какой язык лучше японский, английский, вьетнамский или русский?
А в котором алфавит проще, а в котором среднеее число фонем в слове меньше, а в котором неоднозначности построения предложений меньше, а в котором работа языка и связок проще...

eao197 комментирует...

>Да, можно сказать что использовать new в С++ в такой ситуации - нечестно.
А если в языках реализованных на JVM не имеет смысла создавать свой аллокатор - и только использовать new (даже нет возможности указать - держи это на стеке!) это честно?


По мне это более чесно. У Java программистов ограничены возможности по оптимизации -- да, ограничены. Зато ему автоматом дают очень быстрое выделение памяти. У C++ программистов органичены возможности по оптимизации new -- нет. Но зато оптимизации эти очень дороги и опасны, а штатный new в мейнстримовых компиляторах медленнее, чем аналогичный для Java/.NET.

Продемонстрировать это можно на разных примерах. Например, на примере binary trees -- там как не крути, а нужно создавать объекты в динамической памяти. Или, например, реализация Hash-таблицы или B+ дерева: хочешь, не хочешь, не хочешь, но хип использовать придется. И такое сравнение будет чесным, поскольку для каждого языка выбирается оптимальный для этого языка способ.

Skynin комментирует...

Например, на примере binary trees ... ... поскольку для каждого языка выбирается оптимальный для этого языка способ.
Такое сравнение покажет какой язык+существующая_реализация более пригоден для задачи binary_trees, [b]если[/b] исключить затраты времени программиста на написание, читабельность кода, и т.д. и т.п.
Но никак не сравнение GC и malloc/free :)

По поводу деревьев слышал о соревнованиях: база в 100ти раз больше ОЗУ, данные по природе своей плохо нормализуемы, задача - случайные выборки, поиск по дереву, вставка и удаление: MUMPS vs SQL. Только кто в глаза видел MUMPS сейчас :) Потому что нечестное сравнение - а на табличного вида данных? А скорость разработки? и т.д.

Или - в одном языке список и операции над ним - встроены, а в другом - написаны на самом языке. Несложно догадаться какой козырь будет у компилятора который знает что это - получение следующего элемента, а не - функция которой передали какой-то там указатель.

Я к тому и привел список мерил к обычным языкам.
Нужно оговаривать, понимать что же именно сравниваем.

При таких уточнениях я считаю оба подхода честными в - "C++ vs Java" 1. реализуем используя все возможности языка, 2. реализуем используя только штатные средства работы с кучей.
Только так тогда понятно - что получаем чем жертвуя, где потолок возможностей программиста, а где беззаботность.

eao197 комментирует...

>При таких уточнениях я считаю оба подхода честными в - "C++ vs Java" 1. реализуем используя все возможности языка, 2. реализуем используя только штатные средства работы с кучей.
Только так тогда понятно - что получаем чем жертвуя, где потолок возможностей программиста, а где беззаботность.


Нет, не согласен. Должны сравниваться оптимальные реализации на каждом из языков. Если для какой-то задачи оптимальными окажутся совсем разные подходы, значит, эта задача не подходит для сравнения.

Skynin комментирует...

P.S.
Кстати, обратите внимание на разницу в результатах на С, при использовании
malloc
GC_malloc
GTrashStack
apr_palloc

Хозяева "Computer Language Benchmarks Game" очень правильно делают что сохраняют по несколько реализаций.

Skynin комментирует...

Должны сравниваться оптимальные реализации на каждом из языков.

Тогда, как я говорю:
Лучшим языком будет тот в котором есть оператор H!
Он максимально быстро выводит:
Hello World!
и H!*
для любителей GUI: выводит Hello World! в окошко с кнопкой ОК.

eao197 комментирует...

На мой взгляд, корректное сравнение, это когда берется задача и ее нормальое решение, скажем, на C++. В этом решении меняются разные способы работы с динамической памятью: auto_ptr, shared_ptr, intrusive_ptr, с кастомными аллокаторами, с пулами и пр.

Но когда в C++ решение добавляется new только потому, что в Java варианте new нет -- это неправильно. Так, я могу потребовать, чтобы из Java варианта new убрали, поскольку в C++ решении нет new. И могу объявить, что у Java полная ж... со стековыми объектами, поскольку в Java есть только new. Но ведь это же абсурд.

eao197 комментирует...

Опечатался:
только потому, что в Java варианте new есть -- это неправильно

Skynin комментирует...

Так, я могу потребовать, чтобы из Java варианта new убрали, поскольку в C++ решении нет new
Можете. А "С какой целью?"

Например с целью: "объявить, что у Java полная ж... со стековыми объектами"
Так у нее полная ж..., которая кое-как лечится escape-анализом JITкомпилятора в серверном режиме (в -client - нет). Хотя вот дальше Вы пишете: "этот сложный механизм приходится городить из-за того" - опять неточность - КОМУ приходится городить? Программисту? Мы ж не будем обсуждать что там за ключик -O3 у компилятора ставится ;)

Все о чем я говорил в этой теме можно свести к двум тезисам:
1. НЕ надо искать абсолютов, потому что даже не во всех религиях они есть.
2. НЕ надо рассматривать результаты тестов как разборки в суде, с прокурором, адвокатом, судьей и присяжными.

А надо быть прагматичным технарем. а) Ставить конкретные вопросы, б) ставить эксперементы, [b]устраняющие[/b] влияние на рассматриваемые вопросы, в) правильно интерпретировать результаты - с ответа на узкий вопрос нельзя делать - глобальный выводы вообще о ЯП.

Где в природе мыши толстеют в 3 раза? А зачем тогда в лабораториях их закармливают? Что проверить таблетки для похудения, а не доказать что мыши - обжирающиеся созданья.

Skynin комментирует...

P.S. Просто меня "с детства" учили что malloc - это медленно, плохо и некрасиво (Си мой первый профессионально используемый ЯП)

Что и видно по результатам тестов. Что и говорят разработчики GC у JVM и CLR .NET.

А Вы как бы, толи обижаетесь за С/С++ вообще, толи "религия" - "как у храма угол облупленный?! Богохульство!!!" :)

eao197 комментирует...

>Можете. А "С какой целью?"

С целью показать абсурдность эксперимента, на который вы дали ссылку.

>P.S. Просто меня "с детства" учили что malloc - это медленно, плохо и некрасиво (Си мой первый профессионально используемый ЯП)

Да, это именно так. И в multithread-программах он еще более дорог. И есть отличные примеры, которые это показывают. Тот же binary trees. Поэтому хочется, чтобы использовались адекватные сравнения.

Skynin комментирует...

С целью показать абсурдность
Там сразу
Time=2.19 (калибровочный исходный тест) - как нужно
Time=41.44 (heap+auto_ptr) как не нужно

И в чем же абсурдность показа количественно - поменьше пользуйтесь malloc'ом когда программируете на С/С++?
Где обман, если сразу показано время выполнения - правильно написанного кода?

По моему - убедительная, потому что в цифрах - демонстрация. Ее можно использовать как наглядное пособие начинающему Сишнику. Чтобы не верил в "эффективность" С/С++, типа раз я пишу на Си а не на джава, то автоматически у меня программа будет лучше.
Вот такое расхожее мнение - абсурд.

Skynin комментирует...

P.S.
И еще почему согласен с броским заголовком:
Malloc настолько плох, что программиста на Си/++ не просто должен сам вызывать free(как то считают единственным неудобством "студенты знающие С++" по сравнению с ЯП с GC) - он обязан писать свои аллокаторы. Иначе "джавы" делают Сишное приложение в разы. ОБЯЗАН, а не - свои аллокаторы это просто оптимизация, она не обязательна.

eao197 комментирует...

>Где обман, если сразу показано время выполнения - правильно написанного кода?

Приведу пример. В языке Ada есть возможность передачи аргументов по именам. Причем в этом случае порядок следования аргументов не важен. Что-то вроде:

fuction MakeXYZ(x, y, z): XYZ is
...
end
a := MakeXYZ(1,2,3);
b := MakeXYZ(z => 3, x => 1, y = 2)

В Java такой возможности нет. Там нужно писать:

static XYZ makeXYZ(x, y, z) {...}
a = makeXYZ(1,2,3)

Потом находится некий умник, который говорит -- а не так! Нужно, чтобы и в Java можно было порядок аргументов менять. И пишет передачу аргументов в makeXYZ через Hashtable. Замеряет скорость работы обоих вариантов и оказывается, что вариант с Hashtable медленнее простой передачи аргументов на порядок.

Такое сравнение имеет для меня ровно столько смысла, сколько и обсуждаемые замеры в C++.

>Malloc настолько плох, что программиста на Си/++ не просто должен сам вызывать free(как то считают единственным неудобством "студенты знающие С++" по сравнению с ЯП с GC) - он обязан писать свои аллокаторы.

За 15 лет моего профессионального программирования на C++, в продакшен не пошел ни один проект с собственными аллокаторами. Максимум из того, что было -- это использование dlmalloc-а или использование placement new в пулах памяти. Все уже украдено до нас :)

Skynin комментирует...

Нужно, чтобы и в Java можно было порядок аргументов менять.
"С какой целью" :) Что хотел проверить этот умник в Вашем примере я не понял.


в продакшен не пошел ни один проект с собственными аллокаторами
...
Все уже украдено до нас :)

Ну не хватало чтобы за столько лет развития С/С++ приходилось писать все с нуля :)

Я действительно неверно выразился:
Программист на С/С++ обязан знать, понимать как работают применяемые им аллокаторы.

eao197 комментирует...

>"С какой целью" :) Что хотел проверить этот умник в Вашем примере я не понял.

Смотрим в первоисточник:
Ну т.е. получается, что тест опять не верный ? Что в скале было выделение памяти на объекты (насчёт окмля не знаю), а c++ не было ? и А мой пойнт был в том, что в с++ забыли добавить выделение памяти, которое было в скале.
(ведь именно с этих комментариев началась модификация оригинальной программы). Замечу так же, что само по себе исходное сравнение C++/OCaml/Scala вообще не меряло затраты на память, оно меряло затраты на повышение уровня абстракции.

Т.е. человек не увидел в C++варианте операторов new и потребовал их добавить. Точно так же при сравнении накладных расходов на вызов функции в Ada и Java я могу потребовать, чтобы аргументы в Java передавались по имени и в произвольном порядке. Просто потому, что в Ada это есть.

Skynin комментирует...

Смотрим в первоисточник:
Понятно, пропустил этот комментарий.
Меня удовлетворили следующие комментарии:
Цифры
"зачем здесь куча" - отвечаю - здесь - ни зачем, ... есть конечно всякие аллокаторы, пулы и прочие финты ушами, ... у меня немножко другой пойнт - существует куча народа, которая уверена, что С++ - "эффективный язык", а Жаба - "неэффективный" - до известной степени это оправдано (что первоначальные примеры показывают) - но попасть на инверсию по эффективности - раз плюнуть.

То есть автор осведомлен и не опротестовывал результаты первоначального теста. Как я понял его замысел - удивить "знатоков". (Мне это близко, потому что из опыта собеседований - если студент говорит что знает С++ то с вероятностью 99% он не знает ничерта. Если Дельфи или C# или Java - то может быть что-то и знает.)

Другой для меня пример подобного массового заблуждения - раз в Java есть GC то не бывает утечек памяти. И какие же делаются глаза когда программа через пару часов работы вываливается с Out of memory. Какие потом начинаются упорные отрицания - это не утечки памяти, в Java их быть не может!!!
А они - вполне бывают. (и в C# аналогичные)