О хвостовой рекурсии

и видим, что железный стек сливает софтовому в 2 раза — у меня софтовый исполняется 4.5 секунды, железный 8.5 секунды

А ничего, что в твой «софтверный» стек записывается в 2-3 раза меньше данных?

это потому ПО на жабе заслужило заслуженную репутацию тупого и неповоротливого тормоза?

Нет. Потому что у некоторых графических библиотек есть проблема с interface latency, либо у самих прикладных программ есть такая проблема, либо потому что кто-то использует не ту JVM и/или с неправильными опциями. Если взять HotSpot у Оракла, нормально её приготовить и использовать нормальные приложения с нормальными библиотеками, то особых проблем не будет. К теме MM это не относится.

оно будет лучше системного только в одном случае

http://stackoverflow.com/q/5815936/1337941

http://www.jwz.org/doc/gc.html

http://dlang.org/garbage.html

http://people.cs.umass.edu/~emery/pubs/gcvsmalloc.pdf

...

Что мы собственно и наблюдаем IRL, глядя на тормозной жабокод.

Глядя на тормозной жабокод где? На десктопе? Кто-то использует жабокод на десктопе кроме пользователей IDE и других специфичных приложений без аналогов на более компактных языках? :) Или вот тут - это «тормозной жабокод» или нет? Как бы надо смотреть на область применения, а то можно написать ls на java которая будет разогреваться по несколько секунд и из этого делать какие-то выводы.

А так, да, по последней ссылке как раз про это, то есть про space / time tradeoff, если нужно получить выигрыш от GC и аллокатора в котором аллокация суть инкрементация указателя, то нужно обеспечить достаточное количество памяти. Такая аллокация в своём языковом окружении будет явно лучше чем любая реализация malloc в любой libc. Просто потому что malloc хочет сделать хорошо для всех, так же как и ядерный MM, ядерный планировщик и т.п. А если нужно более специфичное поведение, то тут уже начинаются разные VM которые как раз занимаются реализацией функций ядра и библиотеки си альтернативным образом.

Такая аллокация в своём языковом окружении будет явно лучше чем любая реализация malloc в любой libc. Просто потому что malloc хочет сделать хорошо для всех

если ты пишешь на C/C++, то почему ты обязан использовать malloc()/::new? Сделай mymalloc()/my::new, в чём проблема? Выше я уже привёл пример того, как замена malloc() на alloca() ускоряет программу вдвое. Можно и на что-то другое заменить, никто не мешает. А вот как мне быть с твоей жабой? А никак. Твоя жаба делает лучше исключительно для своего сферического коня в вакууме, а не для моего реального кода.

оно будет лучше системного только в одном случае

http://stackoverflow.com/q/5815936/1337941 http://www.jwz.org/doc/gc.html http://dlang.org/garbage.html http://people.cs.umass.edu/~emery pubs/gcvsmalloc.pdf ...

и что?мне по этим сцылкам ходить, и разбираться с вашими проблемами?

Или они что-то доказывают?

почему ты обязан использовать malloc()/::new?

Мы же говорим про реализации нелинейного MM. malloc & co., GC, region-based, если есть что-то ещё аналогичное - нужно конкретно говорить что именно. Сравнивать линейное, то есть on stack, с нелинейным, то есть on heap, это уже тёплое с мягким. Так-то, конечно, в C/C++ лучше обходиться статичными данными, потом - данными на стеке, и только потом - в куче, но вопрос в том как управлять этими данными в случае стека и кучи (особенно - кучи).

Сделай mymalloc()/my::new, в чём проблема?

А что там будет в реализации этого mymalloc? Можно и для C/C++ написать счётчик ссылок, или лёгкий аллокатор с одиночной преаллокацией и GC, либо лёгкий аллокатор для регионов с деаллокацией at once, о том и речь - есть разные алгоритмы у которых свои преимущества и недостатки, но «хранить всё в куче и вызывать malloc на каждый чих - разные вещи».

мне по этим сцылкам ходить

Конечно.

Или они что-то доказывают?

Они содержат утверждения относительно того почему аллокатор MM с GC может быть быстрее системного аллокатора и почему GC может быть предпочтительнее как MM для кучи нежели перманентное ручное совещание с ядром и libc.

То есть, с кучей можно работать с преаллокацией больших блоков и лёгкой аллокацией внутри блоков без звонков в libc и вообще куда-либо, с автоматической сборкой или сбросом всего блока (что практикуется, кстати, в APR, nginx, etc.). Как раз то что ты спрашивал.

и разбираться с вашими проблемами?

Тебе => 2 человек ITT на что-то жаловались? По-моему - нет :)

Мы же говорим про реализации нелинейного MM. malloc & co., GC, region-based, если есть что-то ещё аналогичное - нужно конкретно говорить что именно. Сравнивать линейное, то есть on stack, с нелинейным, то есть on heap, это уже тёплое с мягким.

stack он не такой уж и линейный IRL. Точнее, когда стек становится линейным, он становится ненужным. Пример с массивом выше уже был. Стек имеет смысл лишь на нелинейных алгоритмах, например на деревьях, и в этом случае есть смысл совмещать стек из процессора со своим, а не изобретать ещё один сбоку. О чём я и говорил.

Так-то, конечно, в C/C++ лучше обходиться статичными данными, потом - данными на стеке, и только потом - в куче, но вопрос в том как управлять этими данными в случае стека и кучи (особенно - кучи).

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

А что там будет в реализации этого mymalloc? Можно и для C/C++ написать счётчик ссылок, или лёгкий аллокатор с одиночной преаллокацией и GC, либо лёгкий аллокатор для регионов с деаллокацией at once, о том и речь - есть разные алгоритмы у которых свои преимущества и недостатки, но «хранить всё в куче и вызывать malloc на каждый чих - разные вещи».

если хранить всё в куче, то вызывать malloc на каждый чих придётся по любому. Пусть даже твой malloc просто увеличит счётчик ссылок на +1, и создаст ещё один умный указатель на те же данные. IRL это не такой уж и плюс - не забывай о том, что при _использовании_ этой переменной тебе придётся вызвать уже системный тормозной malloc(3) - ты его не отменил, а лишь отсрочил его вызов. Это полезно разве что для синтаксического сахара вроде operator=() из C++, который действительно не должен сразу делать malloc(), ибо возможно, что мы вовсе не копируем, а переносим переменную, и потому выделять память нам тут не нужно. Но это сахар. В C, где такого сахара нет, мы просто скопируем указатель на память, и опять-таки ничего не будем выделять/освобождать.

Они содержат утверждения относительно того почему аллокатор MM с GC может быть быстрее системного аллокатора

и что в этом странного? Конечно, если в своём коде ты вызываешь malloc/free там где не нужно, это будет ощутимо медленнее, чем если-бы ты вызывал malloc/free только когда нужно. Что в этом странного-то? GC это один из вариантов алгоритма, который убирает ненужные вызовы malloc/free. Очевидно он иногда быстрее. И очевидно - когда. Тогда, когда ты делаешь ненужные malloc/free. Тут есть целых 3 проблемы:

1. часто обёртка над malloc/free получается сравнимой или даже дороже, чем просто malloc/free.

2. GC забирает огромное число памяти «на всякий случай» из системы. Если-бы это было единственное приложение - проблем-бы не было. Но есть и другие задачи, которые тоже хотят память. А её уже и нет. Это приводит к тормозам и использованию свопа. По этой причине, выигрыш от GC часто отрицательный (запусти какую-нить IDE на жабе, открой код в жалких 1000 строк, на системе с гигом-другим памяти. Сам увидишь).

3. GC должен чётко отслеживать периметр, в котором ВСЕ обращения к памяти должны идти ТОЛЬКО через него. Это лишний уровень, и он ессно тормозит. Но избавится от него внутри периметра нельзя - если попытаться, то получится такое г-но, по сравнению с которым код с malloc/free - сказка. Но malloc/free мы можем применять всегда, а можем - не всегда. В отличие от GC, который применяется только *всегда*.

Тебе => 2 человек ITT на что-то жаловались? По-моему - нет :)

мне все жалуются на то, что «жаба == тормозное УГ». почему так?

ты это for the great justice ведёшь общение, чтобы у тех, кто будет читать тред была бы адекватная информация, а не только бредни, или серьёзно пытаешься убедить человека, который разговаривает с голосами в голове?

stack он не такой уж и линейный

Я там переврал терминологию. С точки зрения теории субструктурных типов линейные системы типов отражают как раз механизмы управления кучей, тогда как механизмы управления стеком даже более специфичны чем линейные - их отражают упорядоченные (ordered) системы типов. Субструктурные системы типов связаны таким отношением:

N - number of objects allowed
E - exchange allowed
W - weakening allowed
C - contraction allowed

                    ordered (N = 1)
                       |
                    linear (N = 1, E)
                   /      \
(N <= 1, E, W) affine    relevant (N >= 1, E, C)
                   \      /
                 unrestricted (N >= 0, E, W, C)

Упорядоченные типы требуют порядка в управлении ресурсами (в частности - памятью), то есть соблюдения FIFO отношения - что-то последовательно появляется, существует в своей области видимости в виде уникальных объектов и потом последовательно исчезает в обратном порядке. Стек и конструкторы локальных объектов в C++ ведут себя именно так:

{
    A x; // allocate x on stack
    B y; // allocate y on stack

    // x-y scope

} // deallocate y (unroll stack)
  // deallocate x (unroll stack)

то есть это то что обзывают RAII. Линейные типы добавляют возможность передачи ссылок на объекты между областями видимости, то есть отменяют упорядоченность, но всё ещё оставляют требование уникальности объектов (= линейность):

B&(exchange!) f(...)
{
    A &x = new ...; // allocate x on heap
    B &y = new ...; // allocate y on heap

    // x-y scope

    return y; // exchange y

} // deallocate x from heap

g(...)
{
    B &z = f(...);

    // z = y scope

} // deallocate z = y

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

Вот любое обычное лямбда исчисление и любая обычная (классическая или интуиционистская) логика неограниченны (и у машины-тьюринга бесконечная лента), позволяют свободно забывать и копировать вещи, то есть никак не адекватны вопросу об управлении ресурсами, адекватные этому вопросу языки и логики линейны, они позволяют следить за вещами как за ресурсами.

То есть я хотел сказать, что либо мы рассматриваем одни механизмы управления ресурсами (ordered, стек), либо другие (linear, куча). С точки зрения реализаций MM мы говорим, конечно, про кучу, так как стек управляется автоматически.

лучше не использовать статические данные и кучу - и то и другое нужно выделять и освобождать

А как выделяют и освобождают статические данные (их размер, по определению, известен во время компиляции)?

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

если хранить всё в куче, то вызывать malloc на каждый чих придётся по любому.

Нет. Выделяется (системно) один регион фиксированного размера (который можно настраивать), дальше все (не системные!) аллокации производятся просто инкрементацией внутри этого региона. Если регион кончается, то производится системная аллокация следующего большого куска - по линейному или экспоненциальному закону (вот вектора в glib растут по экспоненциальному :)). Деаллокация производится целыми регионами, со статическим выводом регионов, либо динамически с помощью GC (связыванием с «регионами» root set). Вот (_static_ infered) region-based MM это heap-based MM done right, но его сложно реализовать, потому в языках в которых ресурсы управляются явно (C и C++) всё делают руками (за исключением RAII в C++, но оно локально и для стека), если не считать _динамических_ решений (библиотечные GC).

при _использовании_ этой переменной тебе придётся вызвать уже системный тормозной malloc(3) - ты его не отменил, а лишь отсрочил его вызов.

Регион большой, «переменная» ссылается на его кусок и может свободно использоваться. То есть регион делится на аллоцируемые объекты, а куча - на регионы. Системная аллокация вроде malloc производится редко, только когда нужно создать новый регион. Сама куча реализуется в ядре на определённом куске виртуальной памяти, точно так же в user-space можно взять у ядра кусок памяти (гигабайт, например :)) и в нём реализовать такой MM, какой нам нужен (так же как ядро реализует свой).

GC это один из вариантов алгоритма, который убирает ненужные вызовы malloc/free.

Нет, это алгоритм который просто другой, он не связан с malloc/free.

1. часто обёртка над malloc/free

Нет никаких обвёрток над malloc/free. Они используются только потому что MM данной VM работает на хост-оси и не имеет прямого доступа к памяти.

GC забирает огромное число памяти «на всякий случай» из системы.

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

Если-бы это было единственное приложение - проблем-бы не было.

Вот поэтому толстые VM обычно применяют для серверов приложений и прочих приоритетных задач. Не для утилиток.

Это приводит к тормозам и использованию свопа.

Случай со свопом это вообще абзац, памяти должно хватать, иначе запускать толстую VM нет смысла.

3.

Опять же, malloc/free (как средства управления кучей) как данность это заслуга ядра и libc в которых _уже_ реализован нужный алгоритм. VM и библиотечные GC просто реализуют другой способ управления кучей.

В отличие от GC, который применяется только *всегда*.

Зачем? Статические и локальные объекты могут работать статично и через стек без всякого GC, GC by design управляет только нелокальными по отношению к скопу объектами, если эти объекты иммутабельны, то GC может ими управлять ещё лучше.

4. Ты забыл сказать, что GC расходует процессорное время (чего не делает статический вывод регионов) и требует структур данных для своей работы. Но ядерный MM и libc - тоже.

мне все жалуются на то, что «жаба == тормозное УГ». почему так?

Не знаю. Может у них 1Gb памяти и swap? Или не те приложения запускают. Вот у меня на десктопе самое жирное приложение (до запуска всякого специфичного софта) это gnome-shell (системный WM! жаба[скрипт] == тормозное УГ!1).

/me ↑ только что написал очередную портянку :)

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

«голоса в голове» это не степень неадекватности, а скорее способ вести дискуссию, поскольку drBatty сам придумывает аргументы за собеседников (иногда похожие на аргументы собеседников) и успешно их опровергает.

То есть я хотел сказать, что либо мы рассматриваем одни механизмы управления ресурсами (ordered, стек), либо другие (linear, куча). С точки зрения реализаций MM мы говорим, конечно, про кучу, так как стек управляется автоматически.

безусловно это так. Однако, IRL есть выбор - где хранить данные, в стеке или в куче? Так вот я изначально говорил о том, что

1. в стеке ресурсы выделяются и освобождаются почти бесплатно

2. верхушка стека практически всегда в самом ближнем кеше, и потому штрафных тактов на доступ к стеку не будет. В отличие от кучи.

А то, что это последовательная (order) структура - это конечно недостаток, однако часто он не принципиален.

А как выделяют и освобождают статические данные (их размер, по определению, известен во время компиляции)?

вот на этапе компиляции и приходится их выделять/освобождать. Т.е. если нам нужен массив в 100500 байт, а потом массив в 100501 байт, то нам придётся сделать статический массив в 100501 байт, и дважды его использовать. Ну если мы хотим, что-бы он был статическим.

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

я с этим и не спорил.

Нет. Выделяется (системно) один регион фиксированного размера (который можно настраивать), дальше все (не системные!) аллокации производятся просто инкрементацией внутри этого региона.

«просто инкрементация» это и есть malloc(). Я и не говорил, что это именно системный вызов.

Нет, это алгоритм который просто другой, он не связан с malloc/free.

связан с my_malloc()/my_free(). Так лучше?

Вот поэтому толстые VM обычно применяют для серверов приложений и прочих приоритетных задач. Не для утилиток.

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

Случай со свопом это вообще абзац, памяти должно хватать, иначе запускать толстую VM нет смысла.

а почему мне навязывают эти толстые VM в десктопе? Ну в тех же IDE?

Зачем? Статические и локальные объекты могут работать статично и через стек без всякого GC, GC by design управляет только нелокальными по отношению к скопу объектами, если эти объекты иммутабельны, то GC может ими управлять ещё лучше.

я говорил про все объекты внутри периметра, которым управляет GC.

4. Ты забыл сказать, что GC расходует процессорное время (чего не делает статический вывод регионов) и требует структур данных для своей работы. Но ядерный MM и libc - тоже.

сам спросил - сам ответил.

Не знаю. Может у них 1Gb памяти и swap?

это что, по твоему плохо? на _десктопе_ должно быть 16Гб памяти? а зачем?

связан с my_malloc()/my_free(). Так лучше?

Только my_free это уже internal/optional, звонок на него может плохо сказываться на поведении GC. Так что в базовом API такого аллокатора по сути будет только my_malloc/my_realloc.

а когда запускаешь ДВА(и более) серверов приложений на одной системе

В этом случае делается один сервер вычислений - один инстанс VM в который загружаются разные приложения. Да и то, можно и несколько инстансов запустить (на Android Dalvik же запускается).

а почему мне навязывают эти толстые VM в десктопе? Ну в тех же IDE?

А ещё в браузерах. Только никто не навязывает - если есть альтернативы, то пожалуйста, если нет - и выбора нет.

на _десктопе_ должно быть 16Гб памяти?

Я про 16 не говорил - _одного_ явно не достаточно для современного десктопа. Два ещё куда не шло. Лучше четыре. Скажем, когда я использовал gentoo + xfce + awesome и прочие лёгкие приложения я мог себе поставить ulimit -m в 50-100mb, сейчас уже не могу.

а зачем?

Потому что 1GB сейчас явно не хватает. Так же как 640KB :)

А ничего, что в твой «софтверный» стек записывается в 2-3 раза меньше данных?

скорее всего именно из-за этого

но вопрос был адресован drBatty, и если бы он на него так ответил, то можно было бы заключить, что у drBatty в голове помимо Таинственных Голосов, с которыми он тут на форуме разговаривает, имеются также и мозги

ну а пока наличие мозгов у него остается такой же гипотезой, как и наличие лунного единорога

ладно, теперь по делу

я не думаю, что при *равном* объеме записываемых данных будет какая-то разница, т.к. х86 внутрях это risc; впрочем, не исключено (хотя и маловероятно) нарваться на баг трансляции х86-->risc

ну и опять же интересно, до какой степени жцц умеет оптимизировать — он вполне мог бы оптимизировать ее до руками развернутого варианта, только память выделять на стеке

апдейт: напомню контекст: анонимус говорил о том, что развернутая руками функция будет быстрее

я не думаю, что при *равном* объеме записываемых данных будет какая-то разница, т.к. х86 внутрях это risc; впрочем, не исключено (хотя и маловероятно) нарваться на баг трансляции х86-->risc

Не будет. Но RISC тут не причем - это шина памяти и кэш.

подтверждаю феномен — разницу в скорости между SOFT2 и SOFT (SOFT2 быстрее в 1.5 раза при -О3)

причина этому похоже в том, что я поленился написать

static uint counter=1;

а не просто

uint counter=1;

компилятору приходится сбрасывать регистр в память, и все тормозит

а после модификации скорости SOFT2 и SOFT сравнялись

Не будет. Но RISC тут не причем - это шина памяти и кэш.

зависит от проца

попробуй сделай так:

res = s[i] + (res ^ s[i] ^ ((s[i] & 7) << 3)) + (s[i]<<5)|(res<<6);
                                                ^^^^^^^^^^^^^^^^^^^

у меня время исполнения увеличивается на 10-15%, что говорит о том, что тормоза уже не в кэше и памяти

апдейт: я имел в виду, что в SOFT2-верcии тормоза уже не в кэше и памяти

А вот ты возьми задачу, где без стека не обойтись по любому. Ну к примеру те же деревья. Эта структура рекурсивная по определению, и потому, стек здесь _нужен_. Вот и сравни свой костыль, и железный стек на такой задаче.

нет чувак

это ТЫ сказал, что «железный стек всё равно быстрее», поэтому именно ТЫ должен это доказывать

т.е. ТЫ должен предъявить код, который использует железный стек и который я не смогу переписать на софтовый стек без потери скорости

а если я перепишу, и он будет исполняться с той же скоростью на моем «костыле» — то ты слил, т.к. говорил «быстрее», а не «не медленнее»

а пока мы ждем твоего лунного единорога код, который на моем костыле (бугага!!!) будет работать плохо, мы тут общаемся, че-то бенчим, но это не значит, что я буду делать ТВОЮ работу

при этом, я думаю, ты все-таки не ограничен 1 попыткой — тебе можно сделать несколько попыток

т.е. мне будет не лень посмотреть несколько твоих лунных единорогов программ, и показать, что на софтовом стеке они работают не медленнее, а то и быстрее!

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

как мы уже говорил, брать задачу должен ТЫ

но я могу поучаствовать в обсуждении задачи; навскидку кажется, что задача «сначала одной функцией создать дерево, заполнив его листья например по формуле f(i), где i — номер созданного листа, а затем другой функцией пройти по этому дереву и просуммировать все значения в листьях» достаточно простая, и подойдет

ну или чуть усложнив — не просуммировать значения, а вычислить

в корне х=1

дальше x=g(значение_в_текущем_листе, прошлое_x)

но тебе решать, какую задачу выбрать

Только my_free это уже internal/optional, звонок на него может плохо сказываться на поведении GC. Так что в базовом API такого аллокатора по сути будет только my_malloc/my_realloc.

нет. В C/C++ допускается

void my_free()
{
}

void foo()
{
 //....
 my_free();
}

В этом случае делается один сервер вычислений - один инстанс VM в который загружаются разные приложения. Да и то, можно и несколько инстансов запустить (на Android Dalvik же запускается).

это было-бы хорошо, вот только не все приложения так умеют...

А ещё в браузерах. Только никто не навязывает - если есть альтернативы, то пожалуйста, если нет - и выбора нет.

браузеры - совсем другая песня. Там VM нужно далеко не только для GC и прочего такого.

Я про 16 не говорил - _одного_ явно не достаточно для современного десктопа. Два ещё куда не шло. Лучше четыре.

у меня сейчас 384Mb. Брат жив.

Потому что 1GB сейчас явно не хватает. Так же как 640KB :)

почему мне хватает?

но вопрос был адресован drBatty, и если бы он на него так ответил, то можно было бы заключить, что у drBatty в голове помимо Таинственных Голосов, с которыми он тут на форуме разговаривает, имеются также и мозги

зачем отвечать, если уже ответили?

апдейт: напомню контекст: анонимус говорил о том, что развернутая руками функция будет быстрее

вот с ЭТИМ заключениям я и не особо-то спорил, ибо ИМХО компилятор и сам развернёт, если сможет. Голоса скорее у тебя в голове, а не у меня: я-то спорил с тем, что самодельная реализация _стека_ будет быстрее, а вот вопрос что быстрее: развёрнутая ручками функция или развёрнутая компилятором - ИМХО не интересно: какая разница? Развёрнутая функция в коде будет выглядеть одинаково, и не важно, кто её развернул. Ну а вот со стеком всё иначе: самописный стек будет медленнее хотя-бы потому, что для него понадобится лишние sp и bp. Для стека эти регистры и так есть. Конечно этот «железный» стек будет работать лишь в случае, если его работа не помешает использованию стека в других целях, т.е. не получится например вернуть автоматическую переменную из функции.

т.е. ТЫ должен предъявить код, который использует железный стек и который я не смогу переписать на софтовый стек без потери скорости

ты называешь «софтовым стеком» совсем другую сущность, нежели я. По твоему, «софтовый стек» это такая _выделенная_ область памяти, но не та, которая индексируется регистром sp. Очевидно, если регистров хватает, то эта эксклюзивная область будет работать даже немного быстрее, чем стек, который используется и для других целей. Ну а регистров хватит - я так подозреваю, что в наших CPU всякие [ebp+0x10] это _тоже_ такой регистр. Потому «автоматические» переменные всё равно являются регистровыми с т.з. скорости. Т.е. даже если компилятор пихает переменную в стек, то она всё равно лежит в регистре, если конечно у нас не первый или второй пентиум.

В C/C++ допускается

Ничего не понял. Где выделение памяти и зачем пустой my_free? GC предполагает получение памяти по T *x = (T*)gc_malloc(size), и, в общем-то, всё. gc_free(x) должен быть вызван неявно самим GC (man 3 gc, если поставить Boehm GC, только он конвенциональный и тормозной). Явное управление предполагает T *x = (T*)malloc(size) и последующий явный free(x) - если его нет, то это уже вне статической семантики управления кучей, то есть такого быть не должно в принципе.

вот только не все приложения так умеют...

С точки зрения «хочу запустить Eclipse и IDEA в одной машине» - да, с точки зрения «хочу пускать свои поделки в одной машине» - никаких проблем. Начиная с emacs --daemon, и вплоть до написания загрузчиков кода для SBCL, Erlang, JVM, etc.

почему мне хватает?

Что, и 640KB? :) 384Mb - icewm, w3m/lynx, mc, nano/vim, ...? Говоря «сейчас не хватает» я имею в виду «мейнстримовые» дистрибутивы и ОС вообще с «мейнстримовым» софтом. Чисто экспериментально - берём железку, ставим ОС, запускаем пару-тройку приложений - не хватает. Ну хотя бы - какой браузер, поддерживающий основные фишки CSS3/HTML5/JS/Flash, влазит в эти 384Mb? А если вкладок наоткрывать? При том, что DDR3 память относительно дешёвая.

самописный стек будет медленнее хотя-бы потому, что для него понадобится лишние sp и bp.

Теоретически, оно будет медленнее за счёт того, что pop и push (на значениях и регистрах) это по одной микро-операции, тогда как mov m,r+inc и dec+mov r,m - по две (на памяти - ещё по одной и для push/pop и для эмуляции). Взять какой-нибудь r10 для sp - не проблема, только на ассемблере писать придётся, так как в си нельзя сказать register глобальной переменной, а gcc не хочет писать нормальные pop и push (из двух инструкций). Раскручивание вызовов и замена call на jmp это уже немного другое.

Где выделение памяти

поскипано. Есть оно там. Куча my_malloc().

и зачем пустой my_free?

ну я же сказал: по двум причинам

1. код становится универсальным, и работает с любым MM. Если это чистый GC, то компилятор выкидывает пустой my_free(). Если не чистый, то работает сабж.

2. можно некоторые эл-ты явно удалять. Вот в php для этого есть полезная функция unset(), которая позволяет экономить огромное количество памяти.

С точки зрения «хочу запустить Eclipse и IDEA в одной машине» - да, с точки зрения «хочу пускать свои поделки в одной машине» - никаких проблем.

обычный usecase это «хочу запустить Eclipse и свою поделку в одной машине!». Или «хочу запустить http://ru.wikipedia.org/wiki/Vuze и IDEA одновременно!». А твои случаи притянуты за уши ИМХО. Кому нужны две IDE сразу?

384Mb - icewm, w3m/lynx, mc, nano/vim, ...?

icewm, FireFox(последний), Thunar, таки да, Vim.

Ну хотя бы - какой браузер, поддерживающий основные фишки CSS3/HTML5/JS/Flash, влазит в эти 384Mb?

ну десяток страничек форумов/сайтов работает отлично. всякие google тоже(подтормаживают, но гугл сейчас везде подтормаживает).

А если вкладок наоткрывать?

10..20 можно легко. Дальше хуже (при 50и может начать свопится и даже сдохнуть(сам FF)).

При том, что DDR3 память относительно дешёвая.

ну найди мне мамку с iPentiumIII и DDR3. Или высылай деньги на DDR1 (впрочем не надо, вряд ли эта мать поддерживает больше 384, а если даже поддерживает, то дешевле купить что-то с DDR3)

в наших CPU всякие [ebp+0x10] это _тоже_ такой регистр

Это про RSE? А оно в каких моделях работает?

Теоретически, оно будет медленнее за счёт того, что pop и push (на значениях и регистрах) это по одной микро-операции, тогда как mov m,r+inc и dec+mov r,m - по две

угу. Я сейчас проверил на деревьях - результат следующий: разница между железным и софтовым стеком незначительная (в разных случаях разная, но не больше 10%). С одной стороны железный стек конечно быстрее работает, но с другой стороны, если делать стек ручками, то можно развернуть рекурсивные вызовы. Это тоже даёт экономию. В итоге, то на то и выходит. Вот код функций:

#ifdef HARD_STACK
void rtree_sum(int *sum, rtree_node *n)
{
	if(!n)	return;
	rtree_sum(sum, n->left);
	*sum += n->data;
	rtree_sum(sum, n->right);
}
#else
#define STACK_SIZE 12345
void rtree_sum(int *sum, rtree_node *n)
{
	static rtree_node *stack_nodes[STACK_SIZE];
	static int stack_dir[STACK_SIZE];
	if(!n) return;
	int sp = 0;
	int dir = 0;
	do {
		if(!dir && n->left)
		{
			stack_nodes[sp] = n;
			stack_dir[sp++] = 1;
			n = n->left;
			continue;
		}
		*sum += n->data;
		if(n->right)
		{
			n = n->right;
			dir = 0;
			continue;
		}
		if(sp)
		{
			n = stack_nodes[--sp];
			dir = stack_dir[sp];
			continue;
		}
		break;
	}while(1);
}
#endif

Это про RSE?

э... Что такое RSE?

код становится универсальным

Тогда, как минимум, my_free должна иметь сигнатуру void(*)(void*), а не void(*)(). Раздельная компиляция / LD_PRELOAD и my_malloc -> malloc / my_free -> free, my_malloc -> custom_malloc / my_free -> cusrom_free, my_malloc -> gc_malloc / my_free -> gc_free, my_malloc -> gc_malloc / my_free -> nothing - да, может иметь смысл для разного дебага и тюнинга. Но тут проблема в том, что для C/C++ нет нормальных GC (так как они всегда конвенциональны).

А твои случаи притянуты за уши ИМХО. Кому нужны две IDE сразу?

Ну да, пусть будет Vuze и IDEA. JVM так устроена - в ней один тред может сломать всю VM. Поэтому нет общепринятых средств для такого use casа. Только если ручками под свою же ответственность.

iPentiumIII

Так он 32-битный? x86_64/Linux сам по себе больше памяти расходует, так что «не хватает» ещё и из-за этого.

register stack engine

Тогда, как минимум, my_free должна иметь сигнатуру void(*)(void*), а не void(*)().

да, наверное.

Но тут проблема в том, что для C/C++ нет нормальных GC (так как они всегда конвенциональны).

это как?

Ну да, пусть будет Vuze и IDEA. JVM так устроена - в ней один тред может сломать всю VM. Поэтому нет общепринятых средств для такого use casа. Только если ручками под свою же ответственность.

ИМХО глючить будет. С т.з. надёжности лучше в разных VM, а это тормоза. На боевом сервере ответственность тоже на себя брать как-то не хочется... А запускать несколько приложений таки надо... Вот и выходит, что жаба - тормозное УГ. Что на десктопе, что на многозадачном сервере (а кому нужен однозадачный?).

Так он 32-битный? x86_64/Linux сам по себе больше памяти расходует, так что «не хватает» ещё и из-за этого.

ну 64х битный код жрёт не намного больше памяти на самом деле. Далеко не вдвое. У меня на другом десктопе x86_64, и 1.5Gb RAM. Потому я могу сравнивать...

а... вот именно. В itanium'е получается ажно 96 регистров для этой цели. Пруф: http://software.intel.com/en-us/articles/itaniumr-processor-family-performanc...

Вот только я не понял, есть-ли такое в «бытовых» процессорах? А если есть, то в каких?

это как?

Конвенциональны^W консервативны (conservative GC), то есть должны считаться с тараканами C/C++. Лучше получается если GC существует на уровне рантайма конкретного языка, заточен именно под него и, наоборот, язык запрещает некоторые вещи облегчая работу GC - небезопасные касты, арифметику, сравнение и прочие свободные операции для указателей, множественное наследование, неконтролируемую мутабельность и т.п. Для примеров таких ограничений можно посмотреть на D (всё что по ссылке), Go (касательно того что они выкинули из того что было в си) и Rust (про memory model и pointer types), и дальше уже на любые толстые VM без указателей и сырой памяти вообще (по крайней мере в safe части) - Java (тут ещё нет множественного наследования), Haskell (на тему «иммутабельность во славу GC») и т.д.

Вот только я не понял, есть-ли такое в «бытовых» процессорах? А если есть, то в каких?

В GPU обычно по 128 регистров (а бывает и больше). Они при этом еще и 128-битные все.

Вот только я не понял, есть-ли такое в «бытовых» процессорах?

В бытовых (>= PentiumM) есть dedicated stack engine. Именно регистры для стека - такого нет.

консервативны (conservative GC), то есть должны считаться с тараканами C/C++. Лучше получается если GC существует на уровне рантайма конкретного языка, заточен именно под него и, наоборот, язык запрещает некоторые вещи облегчая работу GC - небезопасные касты, арифметику, сравнение и прочие свободные операции для указателей, множественное наследование, неконтролируемую мутабельность и т.п.

среди тараканов C++ есть умные указатели. Они позволяют скрыть от пользователя класса как сам указатель(обычный), так и всякий интерфейс к нему. В итоге получается что-то вроде

class smart_pointer {
private:
    int *x;// это указатель на наши данные
public:
    // тут разные методы
};

void foo()
{
    smart_pointer X = 10;// тут мы выделяем память для объекта. Например GC MM. А может и простым системным MM. А может и в стеке.
    smart_pointer Y = 20;
    Y += X;// тут мы увеличиваем Y до 30.
    X = Y;// а тут мы создаём копию Y, причём старое X уничтожается(а может и нет).
}// а вот тут X и Y освобождаются. Если это GC, то ничего не происходит, иначе вызывается free()/::delete

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

А как они отменяют весь набор свободных операций над сырыми указателями, небезопасные касты и т.д. и т.п.? Позволяют замести их под ковёр? То есть, универсального аллокатора с семантикой malloc и автоматической сборкой у нас не будет, будет только аллокатор для умных шаблонных указателей которые ведут себя очень капризно и не отдают скрываемых указателей. Либо универсальный аллокатор с семантикой malloc и автоматической сборкой, который ведёт себя консервативно.

smart_pointer X = 10;

    int *p = new int(10);
    std::unique_ptr<int> x(p);
    delete p;
    ^_^

Ну и как ты в таком коде получишь доступ к smart_pointer::x?

reinterpret_cast<int**>(&X) ?

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

вот и получи доступ к smart_pointer::x... Так и отменяют - инкапсуляция называется.

То есть, универсального аллокатора с семантикой malloc и автоматической сборкой у нас не будет,

не будет. Будет new. Если захочешь, то и не просто new, а с GC, картами, и девочками.

будет только аллокатор для умных шаблонных указателей которые ведут себя очень капризно

это от тебя зависит, как оно себя ведёт.

и не отдают скрываемых указателей.

в твоей любимой яве или там в схеме можно получить указатель на int или там на char?

^_^

что это значит?

reinterpret_cast

ну это ненормативная лексика в C++. За неё нужно гнать вон из профессии.

Не будет. Но RISC тут не причем - это шина памяти и кэш

у меня это, похоже, отнюдь не тормоза на шине

я гоняю этот тест с чуть другими количеством итераций, так вот:

хард-версия делает чуть больше 3Г итераций с 8МБ на фрейм, т.е. читает 26 ГБ и записывает 26 ГБ за 13 секунд => 4ГБ/с на шине

софт-версии делают 3Г итераций с 4МБ на «фрейм», т.е. читает 13 ГБ и записывает 13 ГБ за 8.5 секунд => 3 ГБ/с на шине

учитывая, что максимальный объем стека составляет всего 1МБ, т.е. все хозяйство влезает в кэш (и даже в быструю его часть), говорить про тормоза на шине, по-моему, смешно

да даже последовательное чтение или запись памяти даст скорость на шине существенно больше, чем 4ГБ/с

моя версия — то, что на чтение лишних 13 ГБ и запись лишних 13 ГБ в хард-версии тратятся *команды* процессора и значит лишние такты (очень ориентировочно 26ГБ/4Б=6.5 Гигатактов, что довольно близко к 4.5 секундам), а шина тут не лимитирует

з.ы. «8МБ на фрейм» определено исходя из объема стека в 8МБ и того, что глубина рекурсии в 900К вызовов еще не приводит к sigsegv

Так и отменяют - инкапсуляция называется.

Ок, оставим всё небезопасное в стороне - мы делаем хорошие годные указатели на С++ с pointer-bump аллокацией, нормальным общением с ядром через sbrk/mmap, компактификацией и неконсервативным сборщиком каким-нибудь.

Будет new. Если захочешь, то и не просто new, а с GC

Можешь примерно показать как это будет выглядеть? Не представляю как такое возможно.

в твоей любимой яве или там в схеме можно получить указатель на int или там на char?

Перечислить языки в которых есть managed references? Выше уже были ссылки.

что это значит?

int* из кучи оборачивается в unique_ptr for the greater good, освобождается и «умный» указатель роняет процесс в корку.

ну это ненормативная лексика в C++. За неё нужно гнать вон из профессии.

А static_cast<int**>((void*)&X) или просто c-style (int**)&X - тоже нельзя? Тогда столько людей можно будет гнать из профессии - всех пользователей opaque data types хотя бы (например, sockaddr / sockaddr_in / и далее для прочих протоколов).

Можешь примерно показать как это будет выглядеть? Не представляю как такое возможно.

в C++ CLI свой gcnew, но я ничего толком о нем не знаю

Будет new. Если захочешь, то и не просто new, а с GC

Можешь примерно показать как это будет выглядеть? Не представляю как такое возможно.

нет, не могу. я просто не очень понимаю, чего ты желаешь добиться. если нужны структуры данных как в скриптовых ЯП, то их можно делать на стеке, как я выше продемонстрировал. Если структуры тяжёлые, можно использовать простую обёртку (smart ptr), которую можно копировать, и создавать. Удаляться она будет автоматически. Ну а внутри обёртки вполне реально запилить свою new, которая собственно и будет выделять память. Ну и свою delete, которая возможно ничего делать не будет.

в твоей любимой яве или там в схеме можно получить указатель на int или там на char?

Перечислить языки в которых есть managed references? Выше уже были ссылки.

и что эти ссылки дают полезного?

int* из кучи оборачивается в unique_ptr for the greater good, освобождается и «умный» указатель роняет процесс в корку.

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

А static_cast<int**>((void*)&X) или просто c-style (int**)&X - тоже нельзя?

нельзя.

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

дык это сильно низкоуровневый Си без плюсов. Там иначе никак. Причём тут твои VM и высокоуровневые структуры данных? Ты как-то больно резво прыгаешь, сначала кастуя в int** мой класс, а потом рассказывая мне про каст низкоуровневых структур в самой сердцевине этих ваших сокетов.

Выглядит как то что в D и прочих подобных языках - reference types вводятся в язык как новые first-class типы вида List<double>^ (вместо list<double>*), создаются с помощью gcnew (вместо new) и управляются .NET, так что, надо полагать, это именно ограниченная форма указателей без арифметики, сравнения и т.п. gcnew для обычных * указателей противоречил бы стандарту который требует сохранения порядка на указателях, тогда как перемещающий GC может перемещать память.

я просто не очень понимаю, чего ты желаешь добиться

«не просто new, а с GC». Хочу, чтобы ты написал GC для плюсов, да :)

Для начала - при чём тут перегрузка операторов new и delete? У new бы был тип результат void* -> наш_указатель<T>*, то есть совсем не то что нужно. Вот у gcnew из C++/CLI должен быть правильный тип, то есть void^ -> T^, но это уже не стандартный С++, а вовсе расширение.

и что эти ссылки дают полезного?

Не понял вопрос.

это совсем не умный указатель

unique_ptr - не умный? А какой тогда умный? Если в умный указатель можно передать обычный, то ничего не спасёт от его порчи и последующего вторичного «умного» вызова delete.

сначала кастуя в int** мой класс

Ну ты спрашивал «как мне получить значение поля структуры?», ответ очевидный - просто получить. Но если язык сломан, то приходится делать костыль-зеркало и делать каст к нему.

Хочу, чтобы ты написал GC для плюсов, да :)

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Если в умный указатель можно передать обычный, то ничего не спасёт от его порчи

можно взять стандартные shared_ptr/make_shared и вообще не пользоваться new, а если есть желание - можно и в той же Java, например, похерить память, от дураков защиты нет

http://www.hpl.hp.com/personal/Hans_Boehm/gc/

Он консервативный.

А shared_ptr - просто счётчик ссылок и обвязка над обычными new/delete.

Но RISC тут не причем - это шина памяти и кэш.

хотя, надо отметить, что если насильно сделать массив stack содержащим фреймы по 8 байт, а не по 4, и заставить читать-писать лишние байты, то время увеличивается с 6.7 сек до 10.0 сек, при этом HARD-версия жрет 12.5 сек

так что шина все же видимо существенную роль играет

«не просто new, а с GC». Хочу, чтобы ты написал GC для плюсов, да :)

слишком расплывчатое требование.

Для начала - при чём тут перегрузка операторов new и delete?

не причём. Просто _внутри_ GC будут таки (возможно перезагруженные) new/delete.

unique_ptr - не умный?

если делает delete и не делает new - значит не умный. Умный указатель тем и отличается от обычного, что самостоятельно делает и new и delete, избавляя программиста от этой работы.

Ну ты спрашивал «как мне получить значение поля структуры?», ответ очевидный - просто получить.

как можно «просто получить» ЗАКРЫТОЕ поле? Очевидно - никак, разве что костылями. Кстати твой костыль работать будет через раз, ибо никто не гарантирует, что

1. указатель будет на целое

2. указатель будет первым в классе.

Наоборот, если я решу реализовать скажем GC с подсчётом ссылок, то очевидно хранить в каждом объекте указатель на данные мне не нужно. Нужно хранить указатель на другой объект, т.е. ссылку, которые в другом объекте мы и будем считать.

слишком расплывчатое требование.

Просто _внутри_ GC будут таки (возможно перезагруженные) new/delete.

Расплывчатое, но тем не менее ты знаешь что там будет внутри. Я вот не совсем представляю - нужно взять struct region который будет держать память отданную mmap (можно для простоты взять на каждый регион по обычному new), struct gc со списком регионов, глобальный менеджер gc gc, потом что-то вроде:

template <typename T>
class ref {

    T *p;
    size_t size; // ?

  public:

    explicit ref()
    {
        size = sizeof(T);
        p = (T*)gc.current_region->pointer;
        gc.current_region->pointer += size;
        // write `size' and `set' flag?
        gc.live(this);
    }

    T operator()() { return *p; }

    T operator=(T x) { return *p = x; }

    // ...

};

gc нужно отдать this чтобы он при компактификации обновлял указатели у живых объектов (а значит сами указатели вытаскивать как раз нельзя, инкапсуляция, да). Ещё решить вопрос с планирование запусков циклов сборки, остановки мира (если много тредов), портабельного получения слепков стека, регистров и глобальных данных.

В любом случае, придём к тому, что без помощи компилятора и ограничения семантики языка перед нами будет bss, регистры и стек (managed кучу мы можем всячески расписать - системный malloc тоже так делает) в которых отличить указатель от не-указателей можно только чисто статистически, так что root set будет тоже угадываемый, GC - консервативным, с возможными утечками. Так что первое что хочется сделать это либо ввести битовые карты над памятью чтобы отличать указатели (довольно большие карты могут быть), либо начать тегировать сами указатели:

template <typename P> // requries P <: uintmax_t
struct ptr {

    explicit ptr(P p) : addr(reinterpret_cast<uintmax_t>(p)) {}

    void tag() { addr |= (1ull << 63); }
    void untag() { addr &= ~(1ull << 63); }
    bool is_tagged() { return addr & (1ull << 63); }

    P get_tagged()
    {
        if (is_tagged())
            return operator()();
        else
            return reinterpret_cast<P>(addr | (1ull << 63));
    }

    P get_untagged()
    {
        if (is_tagged())
            return reinterpret_cast<P>(addr & ~(1ull << 63));
        else
            return operator()();
    }

    P operator()() { return reinterpret_cast<P>(addr); }

    uintmax_t address() { return addr; }

  protected:

    uintmax_t addr;

};

template <typename R, typename P> // requires P(...) ~ R
struct fun_ptr : public ptr<P> {

    explicit fun_ptr(P p) : ptr<P>(p) {}

    template<typename... Args>
    R operator()(Args... args)
    {
        return ptr<P>::get_untagged()(args...);
    }

};

Только так можно придти не к precise/accurate GC _для_ C++, а к VM с таким GC просто _на_ C++. О чём я и говорил - семантически С и С++ слишком сырые (или гибкие, если угодно) чтобы обеспечить работу accurate GC, и наоборот - чтобы оснастить их таким GC нужно их где-то расширять, где-то ограничивать.

как можно «просто получить» ЗАКРЫТОЕ поле?

Я бы предпочёл квалификацию доступа, чем полное закрытие полей (смешно же - не иметь хотя бы const доступа к полям структуры без правки исходников или хаков).

Кстати твой костыль работать будет через раз

Такая техника будет работать всегда - стандарт хоть и не налагает сильных ограничений на выравнивание, но требует соблюдения порядка полей, поэтому, например, sockaddr_in всегда можно привести безопасно к sockaddr, а sockaddr, при проверки поля типа, в sockaddr_in и т.п. Классы с закрытыми полями точно так же можно привести к зеркальным-классам в которых всё открыто.

Не обязательно. Там можно передать просто указатель и задать свой «удалятель». Можно, например, так FILE* закрывать :)