Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Память выделяют в куче. Реализация кучи в С++ и в управляемой среде делается по-разному. Обсуждать сейчас не буду, и тот и другой метод имеют свои преимущества и недостатки.
А если реализовать кучу следующим образом ?
Каждый объект, размещаемый в куче, имеет свой размер s. Разделим их по размеру на 3 категории — малые (s <= n), средние ( n < s < =N) и большие ( s > N). Численные значения надо определить экспериментально.
Для малых объектов создадим массивы
массив0 — для объектов с размером от 1 до 8 байт
массив1 — от 9 до 16
массив2 от 17 до 24
и т.д.
Для каждого малого объекта будем выделять память, кратную 8 байт, т.е. отнесем его к массиву0, или массиву1 и т.д. Это, в сущности, и сейчас делается в куче С++ — паять выделяется в размере, округленном в верхнюю сторону до 8 (или до 16 ?).
На базе этих массивов реализуем линейный список свободных ячеек. Для этого достаточно расписать элементы этих массивов указателем на следующий в массиве элемент. При взятии элемента из списка берется элемент, на который показывает pList и он продвигается, при освобождении — освобожденный элемент добавляется в список.
Кстати, эти массивы — не обязательно массивы в истинном смысле этого слова. Они могут лежать в памяти кусками — несмежными страницами, т.е. при необходимости расти.
Теперь выделение памяти для малых объектов сводится просто к взятию элемента из списка, а освобождение памяти (хоть delete, хоть GC) — к возвращению в список. Для неуправляемой кучи не требуется поиск подходящего блока, разбиение его и т.д. Для управляемой кучи не требуется сжатия кучи.
К малым объектам будут отнесены
большинство одиночных экземпляров классов
небольшие массивы (POINT[3], к примеру)
текстовые строки малого и среднего размера.
Для средних объектов оставляем все как есть сейчас. К ним будут отнесены средних размеров массивы, очень крупные экземпляры классов и большие текстовые строки. Как правило, таких объектов в программе намного меньше, чем "малых" переменных.
Для больших объектов память выделяем/освобождаем с помощью VirtualAlloc/Free, т.е округляем до размера страницы в верхнюю сторону. Оверхед при этом незначителен. Если, к примеру, большими считать объекты с размером более 100 Кб, то оверхед будет не более 4%, а при 1 Мб — вообще 0.4%. Можно пренебречь.
Таким образом, для малых и больших объектов выделение и освобождение памяти будет операцией O(1), и только для средних оно будет включать в себя поиск пустого блока или сжатие памяти.
Подводный камень, который я вижу
При пиковой нагрузке списки могут начать бурно расти, а освобождения их не предусмотрено. Ситуация примерно та же, что и со стеком в Win32 — он может расти, но декоммитирование страниц в стеке и передвижение PAGE_GUARD обратно не делается. Решение может заключаться в том же — ограничить размер списков некоторой величиной. При превышении этой величины память для малых объектов выделяется из средней кучи — до тех пор, пока в соответсвующем списке не появятся свободные места. Ничего от этого не пострадает — просто в среднюю кучу, которая от размеров объектов не зависит, изредка будут попадать и малые объекты.
Насколько я знаю, нечто подобное есть в ядре — ассоциативные списки, с фиксированным размером элементов, наиболее употребительные размеры. Почему бы это не реализовать и в приложениях 3 кольца ?
Здравствуйте, Павел Лазаревич, Вы писали:
PD> Custom allocator?
У Александреску свой аллокатор для маленьких объектов очень эффективен, можно взять его реализацию.
The allocator implemented by Loki has a four-layered architecture. The first layer consists of a
private type Chunk, which deals with organizing memory chunks in equally sized blocks. The
second layer is FixedAllocator, which uses a variable-length vector of chunks to satisfy
memory allocation to the extent of the available memory in the system. In the third layer,
SmallObjAllocator uses multiple FixedAllocator objects to provide allocations of any
object size. Small objects are allocated using a FixedAllocator, and requests for large objects
are forwarded to ::operator new. Finally, the fourth layer consists of SmallObject, a class
template that wraps a SmallObjAllocator object.
Для средних используем штатный new/delete;
А для больших сделать страничные аллокации, как предлагаете вы.
Чисто умозрительно рассуждая, должно получиться очень неплохо.
Pavel Dvorkin wrote:
> Таким образом, для малых и больших объектов выделение и освобождение > памяти будет операцией O(1), и только для средних оно будет включать в > себя поиск пустого блока или сжатие памяти.
Оно примерно так и сделано в современных вариантах (см. Hoard Allocator
или любые другие современные реализации). Правда, все осожняется
многопоточностью, но тут тоже можно много чего сделать.
Здравствуйте, Cyberax, Вы писали:
C>Оно примерно так и сделано в современных вариантах (см. Hoard Allocator C>или любые другие современные реализации). Правда, все осожняется C>многопоточностью, но тут тоже можно много чего сделать.
А что же все эти современные варианты в наиболее популярных средах не используются ? Я имею в виду кучу RTL, естественно, а не собственные переопределения new/delete
Pavel Dvorkin wrote:
> C>Оно примерно так и сделано в современных вариантах (см. Hoard Allocator > C>или любые другие современные реализации). Правда, все осожняется > C>многопоточностью, но тут тоже можно много чего сделать. > А что же все эти современные варианты в наиболее популярных средах не > используются ? Я имею в виду кучу RTL, естественно, а не собственные > переопределения new/delete
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А если реализовать кучу следующим образом ?
Так оно примерно и делается, только чтобы для того, чтобы избежать фрагментацию памяти выполняются дополнительные шаги:
1. Списки циклические двусвязные. Это позволяет удалить элемент из списка зная только указатель на этот элемент.
2. Флаги того, является ли текущий и предыдущий блок свободным. Это позволяет на этапе освобождения объелинть существующие блоки.
3. Текущий аллокатор, из которого выделяется память в случае, если нет блока в точности нужного размера.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Идея не странная, а очень даже хорошая — говорю это не с точки зрения теории...
Похожая идея посетила меня примерно 5 лет назад, когда столкнулся с проектом для которого выделение/освобождение памяти было довольно существенной задачей. Решить эту задачу полностью в рамках того проекта — просто не было времени, но у меня появилось хобби связанное с "красивой" реализацией такой задачи.
По поводу "пиковой нагрузки" — собственно это самый "тонкий момент".
Это и есть самый большой недостаток. Ибо в такие моменты — куча будет превращаться в "обыкновенную", лишаясь всех достоинств, которые именно и нужны при "пиковой нагрузке". По мимо этого — установив "некоторый предельный размер" для малых списков (как его найти это ещё одна проблема) лишаемся именно "динамичности" т.е. основного достоинства кучи как таковой.
Собственно в устранении этого подводного камня и состоит задача ... помимо многопоточности и пр.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
Это у Вас всё происходит в вирутальной памяти. Будет сильно эффективнее работать не с виртуальной, а с реальной памятью. Соответственно, менеджер памяти (быть может даже с автоматической сборкой мусора) — это будет некий программно-аппаратный комплекс существующий в единственном экземпляре для всей системы, а не во-множественном — в каждом отдельном виртуальном пространстве. Вот, например, прямо сейчас на моём компьютере под виндос запущено 27 процессов, т.е. есть 27 виртуальных пространств, в каждом из них работает свой собственный программный менеджер памяти (некоторые даже со сборкой мусора), плюс системный программно-аппаратный менеджер памяти. Так вот, будь в системе всего один на всех программно-аппаратный менеджер памяти (а не +27 чисто программных), система работала бы быстрее.
P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Глеб Алексеев, Вы писали:
ГА>>Также рекомендую (не Вам, а Павлу) погуглить на тему dlmalloc и mtmalloc.
PD>OK, спасибо, посмотрел. И все же — почему это не используется в реальном мире Windows ?
Откуда ты знаешь, что именно там используется?
Есть исходные коды WinHeap а?
Для справки. В старых версиях VC++ CRT строила кучу поверх WinHeap а, с добавлением оптимизации для малых объектов. В новых -- фактически напрямую используется WinHeap.
Я подозреваю, что все возможные усовершенствования были перенесены в реализацию WinHeap.
Здравствуйте, Шахтер, Вы писали:
Ш>Здравствуйте, Pavel Dvorkin, Вы писали:
Ш>А ты уверен, что это уже не реализовано в куче в твоём любимом компиляторе?
Уверен на 100%.
1. Как именно реализована куча в VC (malloc и т.д.) — знаю довольно хорошо, копался в ее исходниках. Ничего подобного там нет.
2. Как реализована сама куча Windows (HeapAlloc и т.д.) — в деталях не знаю, но вот такой код
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
если хорошенько подумать, то подавляющее большинство объектов имеет небольшое время жизни — в одной функции выделили, в другой поюзали и удалили
объекты, которые разделяются между потоками — это вообще редкость
с помощью статического анализа программы можно выделить для каждого объекта "точки освобождения" в коде, по достижении одной из которых объект становится ненужным.
объекты, которые освобождаются в одной и той же "точке освобождения", можно объединить в группу (такой точкой может стать выход из функции для всех локальных объектов, например)
таким образом, объекты каждой группы можно выделять из отдельного пула памяти, а при достижении соответствующей "точки освобождения" убивать этот пул одной операцией
таким образом можно избавиться и от фрагментации кучи, и от необходимости отслеживать ссылки на объекты в рантайме со всеми сопутствующими накладными расходами
есть конечно объекты, для которых эта схема не сработает — например, если их нужно передавать внешнему коду, или для выявления "точек освобождения" для этих объектов нужен слишком изощренный статический анализ. Для этого 0,1% можно оставить обычную сборку мусора или использовать подсчет ссылок — на общую производительность это уже не будет оказывать влияния.
Здравствуйте, bkat, Вы писали:
СГ>>P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
B>[offtop] B>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>[/offtop]
[offtop-продолжение]
Один извесный писатель был заклятым врагом Эйфелевой башни, критиковал ее при первом удобном случае и предлагал разобрать вообще. Но ежедневно ходил обедать в ресторан на Эйфелевой башне. Когда же у него спросили, почему он это делает, раз он так ее ненавидит, он ответил:
-- Это единственное место в Париже, где я не вижу эту чертову башню.
Продолжая в том же духе, можно предположить, что только в Обероне не видно проблем, которые можно успешно разрешить с помощью Оберона
[/offtop-продолжение]
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, bkat, Вы писали:
B>[offtop] B>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>[/offtop]
Есть, но они уже 70 лет успешно решаются на Лиспе и Хаскеле .
Здравствуйте, Cyberax, Вы писали:
С>Правда, все осожняется многопоточностью, но тут тоже можно много чего сделать.
Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Здравствуйте, Глеб Алексеев, Вы писали:
B>>[offtop] B>>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>>[/offtop] ГА>Есть, но они уже 70 лет успешно решаются на Лиспе и Хаскеле .
Это теми решается, кто смог освоить языки Лисп и Хаскель
Остальные (Страуструп, Вирт, Грослинг, ван Россум, Уолл, Матцумото, Хальсенберг и др.) придумывали себе языки попроще
В результате каждый может найти себе язык по вкусу. Или свой придумать
... << RSDN@Home 1.1.4 stable rev. 510>>
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
PD>Память выделяют в куче. Реализация кучи в С++ и в управляемой среде делается по-разному. Обсуждать сейчас не буду, и тот и другой метод имеют свои преимущества и недостатки.
PD>А если реализовать кучу следующим образом ?
Если я ничего не перепутал при беглом прочтении, то ты изобрел менеджер памяти Delphi. См. здесь
Pavel Dvorkin wrote:
> С>Правда, все осожняется многопоточностью, но тут тоже можно много > чего сделать. > Кстати, насче многопоточности, здесь как раз проблем меньше. После > выяснения размера объекта нужно захватить только тот список, к > которому он относится. Выделение памяти в других списках можно вести > параллельно.
Просто если имеется только один глобальный набор списков, то нужны
interlocked-операции или мьютексы. А это нежелательно — поэтому есть
схемы с thread-local аренами, очередями запросов и т.п. За долгие годы
на эту тему ооочень много всего написали.
Дарней wrote:
> объекты, которые разделяются между потоками — это вообще редкость > с помощью статического анализа программы можно выделить для каждого > объекта "точки освобождения" в коде, по достижении одной из которых > объект становится ненужным. > объекты, которые освобождаются в одной и той же "точке освобождения", > можно объединить в группу (такой точкой может стать выход из функции > для всех локальных объектов, например) > таким образом, объекты каждой группы можно выделять из отдельного пула > памяти, а при достижении соответствующей "точки освобождения" убивать > этот пул одной операцией
Поздравляю, ты изобрел region inference
Как обычно, несколько "но": вообще говоря, нельзя определить "точку
освобождения" в общем случае. Даже в чистых функциональных языках это не
делается в полном объеме.
В C++ я делал нечто подобное — была иерархия пулов, причем в каждом
указателе лежала ссылка на свой пул. Можно было создавать объекты в
текущем пуле, в пуле другого указателя, или в именованом пуле. Причем
если какие-то указатели переживали свой пул, то их объекты перемещались
в более старший пул. Использовать было достаточно удобно, покрывалось
99% требований.
Это нужно было для одной сложной системы анализаторов, где важна была
скорость.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Cyberax, Вы писали:
С>>Правда, все осожняется многопоточностью, но тут тоже можно много чего сделать.
PD>Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Списки — это зло. Это оверхед sizeof(void*)*2 == 8 байт на блок на 32-х битной машине.
Гораздо лучше массивы юзать. Выделяем большие блоки по 64, 128к или больше и главное чтобы начало блока было выровнено по его размеру. Тогда обнулив у указателя младшие биты автоматически получаем адресс массива в котором он сидит. Тогда и работает быстрее и нет оврехеда на prev,next в списке. А процедура удаления (без учета синхронизации) будет выглядеть вот так:
void free_( void *p )
{
block *pb = (block*)p;
// обнуляя младшие биты находим начало массива:
chunk *c = (chunk*)((size_t)p & (size_t)chunk_mask_);
// пополняем список свободных,
// поскольку блок больше не используется то указатель next прямо в нем (без оверхеда)
pb->next = c->free;
c->free = pb;
// уменьшаем счетчик занятых
c->used_n--;
}
Разбираться в деталях сейчас не буду, но вот это смущает
Алгоритм выделения памяти
Пытаемся найти в массиве smallTab блок в точности нужного размера.
Пытаемся выделить память из текущего выделяемого фрагмента.
Пытаемся найти блок подходящего размера в начале списка avail.
Просматриваем все оставшиеся элементы в списке avail, начиная с элемента, на который указывает rover.
Просматриваем массив smallTab, и, если в нем находится блок большего размера, используем его для выделения памяти.
Мне все эти "пытаемся", а особенно "просматриваем" не нравятся. В том, что я писал, выделение выглядит примерно так
size = sizeof(var);
if(size < nMin) // пограничное значение для малых объектов
{
size = (size +7) / 8 * 8; // округлить до 8
if(pList[size/8 - 1])
{
pRet = pList[size/8 - 1]; // размер 1-8 -> список 0, размер 9-16 - список 1 и т.д.
pList = pList->next;
return pRet;
}
else
{
pList = VirtualAlloc(1 page);
// прописать в этой странице, рассматривая ее как массив из элементов размера size, последние 4 байта каждого элемента, адресом след. элемента
}
}
else
HeapAlloc
Алгоритм выделения памяти достаточно прост – в цикле перебираются все списки в порядке приоритета, и если находится нужный фрагмент, то его и возвращают программе.
Алгоритм освобождения памяти уже не является линейным, как алгоритм выделения памяти. Однако он также не представляет большой сложности, поскольку большинство развилок связано с объединением смежных свободных блоков.
Нет, это явно не то . Я предлагаю их оба иметь как O(1). Точечно. Раз — и готово. Никаких развилок, никаких смежных блоков, никакого объединения чего бы то ни было с чем бы то ни было.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Пытаемся найти в массиве smallTab блок в точности нужного размера. PD>Пытаемся выделить память из текущего выделяемого фрагмента. PD>Пытаемся найти блок подходящего размера в начале списка avail. PD>Просматриваем все оставшиеся элементы в списке avail, начиная с элемента, на который указывает rover. PD>Просматриваем массив smallTab, и, если в нем находится блок большего размера, используем его для выделения памяти.
PD>Мне все эти "пытаемся", а особенно "просматриваем" не нравятся. В том, что я писал, выделение выглядит примерно так
Как ни крути, а написать "идеальный" менеджер памяти под все случаи не получится. Нужно расставить приоритеты и иметь статистические данные.
По поводу менеджера памяти Delphi. В списке avail расположены блоки размером более cSmallSize (4 Кб), что соответствует твоему определению "среднему" размеру. Таким образом в случае небольших объектов подходящим будет первый попавшийся. smallTab просматривается в самую последнюю очередь и только в том случае, когда мв выделяем блок памяти небольшого (до 4 Кб) размера, но при этом у нас нет ни одного свободного блока более 4 Кб... К недостаткам менеджера памяти Delphi я бы отнес тот факт, что он пытается максимально использовать память, выделенную при помощи VirtualAlloc. Т. е. если в системе есть свободный блок подходящего размера, то обращения к функции VirtualAlloc выполнено не будет. В настоящее время вместо просмотра наверное "дешевше" выделить новую страницу памяти (или для очистки совести просмотреть несколько элементов из массива smallTab). Во всяком случае в Delphi 2006 теперь новый менеджер памяти, который работает несколько быстрее, но я его не смотрел.
Как я уже говорил, в менеджере памяти Delphi впециальные свои списки свободных элементов до размера 4096 байт включительно. Если для каждого такого размера вводить свой стисок, то мы получаем 4096 /8 = 512 страниц памяти. Т. е. у нас потенциально до 2 Мб памяти уходит под эти списки. При этом уровень заполняемости их зависит от особенностей приложения. второй минус в том, что Realloc со 100% вероятностью приводит к операции копирования, хотя копировать надо не так иж много.
Здравствуйте, Nickolay Ch, Вы писали: NC>Здравствуйте, Сергей Губанов, Вы писали: СГ>>P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
NC>ЗЫ. Нажал на ссылку интереса ради, и ужаснулся, аж в глазах посинело. Дизайн жуткий, не жмите эту ссылку!
Мда... Видимо, у тех, кто делает проекты на обероне, нету ни денег, ни мозгов, ни друзей — иначе сделать нормальный дизайн для них проблемы не составило бы...
Здравствуйте, Mystic, Вы писали:
M>второй минус в том, что Realloc со 100% вероятностью приводит к операции копирования, хотя копировать надо не так иж много.
Меня давно интересует вопрос: зачем вобще нужен realloc? Сколько пишу программы мне realloc ни разу не понадобился.
... << RSDN@Home 1.1.4 beta 6a rev. 436>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, Шахтер, Вы писали:
Ш>Откуда ты знаешь, что именно там используется? Ш>Есть исходные коды WinHeap а?
Ш>Для справки. В старых версиях VC++ CRT строила кучу поверх WinHeap а, с добавлением оптимизации для малых объектов. В новых -- фактически напрямую используется WinHeap. Ш>Я подозреваю, что все возможные усовершенствования были перенесены в реализацию WinHeap.
Более того помнится кто-то вроде даже стебался над Юниксовыми хипами и говорил, что мол они не могут взять хип как в винде?
В хипе мло быстро выделить память в первый раз. Там важно хорошо переживать фрагментацию. Вот когда хип одинаково быстро выделит память как после запуска, так и через неделю работы, тогда и можно будет говорить, что хип быстрый. А так ну, пусть в двое быстрее по первой все будет работать. А дельее? Там ведь даже такие вещи как попадение кэш начинают влиять.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Кстати, насче многопоточности, здесь как раз проблем меньше. После выяснения размера объекта нужно захватить только тот список, к которому он относится. Выделение памяти в других списках можно вести параллельно.
Вот одно вычисление твое будет дороже чем открутка указателя в ЖЦ. А блокировка где бы не ставилась, все равно время занимает.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Глеб Алексеев, Вы писали:
ГА>Здравствуйте, bkat, Вы писали:
B>>[offtop] B>>Интересно, если в программировании проблемы, которые нельзя свести к оберонам B>>[/offtop] ГА>Есть, но они уже 70 лет успешно решаются на Лиспе и Хаскеле .
Ну, как решите приходите. Спарим ваши Лиспы и Хаскели с Обероном. Получится, наверное, Хлиберон. Или Обелисхк.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Дарней, Вы писали:
Д>если хорошенько подумать, то подавляющее большинство объектов имеет небольшое время жизни — в одной функции выделили, в другой поюзали и удалили
Если эту идею развить, может оказаться, что заметную часть этого большинства можно выделять и удалять в одной функции, для чего хорошо подходят автоматические объекты. Создание и удаление можно считать бесплатными.
Это я вот к чему. Сначала можно найти книжки для начинающих, где делается так:
int main()
{
float * a = new float[200];
///
}
А потом на ровном месте появляются проблемы с фрагментицией кучи
Статический анализ — хорошо, но иногда мы сами в силах немного помочь
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Дарней,
GN>>Статический анализ — хорошо, но иногда мы сами в силах немного помочь
Д>если тебе нравится этим заниматься, то никто не запрещает Д>а я предпочитаю, чтобы рутиной за меня занимался компилятор и рантайм
Я тоже ленивый не хочется лишний раз без повода писать new. Оно ведь может и исключение кинуть. Шутка. ИМХО такие вещи не являются рутиной — делаются на автомате, как расстановка скобочек. Зато могут сделать код более простым для чтения. Я вот до сих пор не могу понять, что хотел сказать автор кода, который я приводил в предыдущем посте
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, Mystic, Вы писали:
WH>Меня давно интересует вопрос: зачем вобще нужен realloc? Сколько пишу программы мне realloc ни разу не понадобился.
>Меня давно интересует вопрос: зачем вобще нужен realloc? Сколько пишу программы мне realloc ни разу не понадобился.
Да ну?
Ты ни разу не делал vector.push_back? И тебя удовлетворяет
1) создать массив побольше
2) скопировать туда старый массив
3) прибить старый массив
ну тогда realloc тебе действительно не нужен.
Я имею в виду не конкретную реализацию realloc в MSVC через виндовый HeapReAlloc, а как философию.
Правильно работающая программа — просто частный случай Undefined Behavior
Вот уже полгода успешно работает в этом проекте (пока не оконченом) + ещё у меня куча благодарственных писем от других пользователей (вроде "у нас скорость сервера выросла на 12%, спасибо большое").
Работает именно через набор пулов блоков фиксированного размера
В Heavy Duty проведена дополнительная оптимизация — на каждый поток свой менеджер памяти, время не тратится даже на синхронизацию.
Правильно работающая программа — просто частный случай Undefined Behavior
_Winnie wrote:
> Ты ни разу не делал vector.push_back? И тебя удовлетворяет > >1) создать массив побольше >2) скопировать туда старый массив >3) прибить старый массив > > ну тогда realloc тебе действительно не нужен. > Я имею в виду не конкретную реализацию realloc в MSVC через виндовый > HeapReAlloc, а как философию.
Вообще, realloc не подходит для вектора по очень простой причине — в
результате realloc'а может измениться расположение данных в памяти, а
это нельзя делать для С++ных объектов.
Нужна другая функция, которая должна пытаться увеличить размер блока, но
в случае неудачи возвращать NULL, а не делать автоматическое выделение и
перемещение. В MSVC для этого есть нестандартная функция _mgrow.
ЗЫ: в моей bycicle template library есть реализация вектора, которая
использует _mgrow (если он есть) для увеления размера хранилища. Если
кому интересно могу прислать.
Здравствуйте, gear nuke, Вы писали:
Д>>если хорошенько подумать, то подавляющее большинство объектов имеет небольшое время жизни — в одной функции выделили, в другой поюзали и удалили
GN>Если эту идею развить, может оказаться, что заметную часть этого большинства можно выделять и удалять в одной функции, для чего хорошо подходят автоматические объекты. Создание и удаление можно считать бесплатными.
Нифига. Ты платишь за стек — время копеечное, зато пространство дорогущее.
1) Сразу возникает ограничение на глубину рекурсии.
2) Освобождение памяти нетривиально, поэтому отделываются полным сбросом всех выделенных блоков при выходе из функции: _alloca есть, а _freea — нет
3) Выделение произвольного блока — по причинам 1) и 2) подрывает безопасность программы. Достаточно сделать _alloca в цикле.
Поэтому _alloca (или её аналогов) в стандартных библиотеках большинства языков нет.
Разве что в Форте, для которого динамическое выделение-освобождение — настолько редкая работа, что базовая куча, фактически, представляет собой ещё один стек.
Здравствуйте, Кодт, Вы писали:
GN>>Если эту идею развить, может оказаться, что заметную часть этого большинства можно выделять и удалять в одной функции, для чего хорошо подходят автоматические объекты. Создание и удаление можно считать бесплатными.
К>Нифига. Ты платишь за стек — время копеечное, зато пространство дорогущее. К>1) Сразу возникает ограничение на глубину рекурсии.
Верно. Но (глубокая) рекурсия достаточно редка, что бы это было критическим моментом.
Кстати, если говорить о windows, то размер стека там равен по умолчанию размеру кучи.
К>2) Освобождение памяти нетривиально, поэтому отделываются полным сбросом всех выделенных блоков при выходе из функции: _alloca есть, а _freea — нет К>3) Выделение произвольного блока — по причинам 1) и 2) подрывает безопасность программы. Достаточно сделать _alloca в цикле.
У многих объектов размер известен на стадии компиляции, другие объекты располагать на стеке — нужно 7 раз подумать.
К>Поэтому _alloca (или её аналогов) в стандартных библиотеках большинства языков нет.
А в С99 добавили в язык variable length array type. Пускай они даже реально на куче распологаться будут — синтаксис проще, и гарантирована "сборка мусора" при выходе из блока. Именно последнее я и считаю плюсами подхода. Даже если всё будет распологаться не в стеке, а в куче — не будет фрагментации, и создание + удаление останутся так же почти бесплатны, поскольку порядок этих операций гарантирован.
К>Разве что в Форте, для которого динамическое выделение-освобождение — настолько редкая работа, что базовая куча, фактически, представляет собой ещё один стек.
Во, я после знакомства с Фортом и пришёл к выводам, что куча может быть не очень нужна
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>ИМХО такие вещи не являются рутиной — делаются на автомате, как расстановка скобочек.
Нельзя заниматься бездумно такой задачей, как управлением памятью — можно оказаться в очень крупном пролете.
Такие вещи надо делать или тщательно обдумав, или отдавать на откуп автоматической системе.
И вообще, лучше не будем развивать эту тему. А то опять понабегут фанатики и начнут бить себя пяткой в грудь.
Здравствуйте, Дарней,
GN>>ИМХО такие вещи не являются рутиной — делаются на автомате, как расстановка скобочек.
Д>Нельзя заниматься бездумно такой задачей, как управлением памятью — можно оказаться в очень крупном пролете.
Я имел ввиду не управление памятью в целом, а использование объектов, тем или иным образом уже инкапсулирующих управление памяти в себе — будь то GC, RAII или ещё что-то. То есть, где подумать надо один раз, а не для каждого экземпляра.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>RAII или ещё что-то. То есть, где подумать надо один раз, а не для каждого экземпляра.
честно говоря, не понимаю, что ты имеешь в виду
если использовать RAII, то думать надо как раз для каждого экземпляра — как минимум, думать, подойдет ли для данной переменной RAII вообще
даже если ты не собираешься возвращать эту переменную из функции, всегда найдется подходящее место для пары граблей
Здравствуйте, Cyberax, Вы писали:
C>Нужна другая функция, которая должна пытаться увеличить размер блока, но C>в случае неудачи возвращать NULL, а не делать автоматическое выделение и C>перемещение. В MSVC для этого есть нестандартная функция _mgrow.
И вполне стандартное
HeapReAlloc
HEAP_REALLOC_IN_PLACE_ONLY Specifies that there can be no movement when reallocating a memory block to a larger size.
If this flag is not specified and the reallocation request is for a larger size, the function might move the block to a new location.
If this flag is specified and the block cannot be enlarged without moving, the function fails, leaving the original memory block unchanged.
Pavel Dvorkin wrote:
> C>Нужна другая функция, которая должна пытаться увеличить размер > блока, но > C>в случае неудачи возвращать NULL, а не делать автоматическое > выделение и > C>перемещение. В MSVC для этого есть нестандартная функция _mgrow. > И вполне стандартное > HeapReAlloc
А Win32 у нас уже стандартный? Я говорил про ANSI/POSIX стандарты.
Поздравляю — это хорошая, проверенная временем идея. Эта схема называется Slab Allocation, и она действительно очень эффективна. Такой аллокатор применяется, например, в оперсистеме Solaris, и в продуктах компании CQG, где я недавно работал.
Только при ее реализации придется решить ряд интересных инженерных проблем, для того, чтобы действительно получилось O(1). Дьявол в деталях — вы должны экономно подходить к расходованию адресного пространства у вас будет много хипов — надо разработать эффективную схему управления ими. Например — интересна проблема быстрого (за O(1)) определения адреса хипа по указателю на выделенный блок . Проблема решаемая. Аллокатор CQG тратит по нескольку машинных инструкций на выделение и деаллокацию. Разумеется, алгоритмы покрыты NDA.
. Пример, можно сказать, неудачный в моём контексте, но он показывает, что можно подумать один раз при дизайне классса, а можно — каждый раз при создании экземпляра.
Больше я не имел ввиду ничего
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Gaperton, Вы писали:
S>[]
S>И решение от CQG — платформонезависимое, или портабельное ?
Только Win32, причем только 32 битные платформы (!) с адресным пространством 2Гб на процесс. И только для своих продуктов — оно не продается. Сделано в рамках работ по улучшению работы legacy клиента и сервера. Результат предельно практический — время старта системы сокращено в несколько раз .
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, srggal, Вы писали:
S>>Здравствуйте, Gaperton, Вы писали:
S>>[]
S>>И решение от CQG — платформонезависимое, или портабельное ?
G>Только Win32, причем только 32 битные платформы (!) с адресным пространством 2Гб на процесс. И только для своих продуктов — оно не продается. Сделано в рамках работ по улучшению работы legacy клиента и сервера. Результат предельно практический — время старта системы сокращено в несколько раз .
Нюансы адресации памяти для выделения места в адресе блока под признак кучи
Здравствуйте, srggal, Вы писали:
G>>Только Win32, причем только 32 битные платформы (!) с адресным пространством 2Гб на процесс. И только для своих продуктов — оно не продается. Сделано в рамках работ по улучшению работы legacy клиента и сервера. Результат предельно практический — время старта системы сокращено в несколько раз .
S>Нюансы адресации памяти для выделения места в адресе блока под признак кучи
Как минимум используется один бит адреса (старший, но может быть и сдвинут — следует из ограничения 2Гб). Вероятно, и несколько младших тоже, поскольку никто не выделяет на куче по байту. Даже у Рихтера было пара строчек о таком хаке (негативных, что ИМХО спорно).
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>Здравствуйте, srggal, Вы писали:
G>>>Только Win32, причем только 32 битные платформы (!) с адресным пространством 2Гб на процесс. И только для своих продуктов — оно не продается. Сделано в рамках работ по улучшению работы legacy клиента и сервера. Результат предельно практический — время старта системы сокращено в несколько раз .
S>>Нюансы адресации памяти для выделения места в адресе блока под признак кучи
GN>Как минимум используется один бит адреса (старший, но может быть и сдвинут — следует из ограничения 2Гб). Вероятно, и несколько младших тоже, поскольку никто не выделяет на куче по байту. Даже у Рихтера было пара строчек о таком хаке (негативных, что ИМХО спорно).
Но вот можно ли много хипов закодировать 3мя битами
Здравствуйте, srggal,
GN>>Как минимум используется один бит адреса (старший, но может быть и сдвинут — следует из ограничения 2Гб). Вероятно, и несколько младших тоже, поскольку никто не выделяет на куче по байту. Даже у Рихтера было пара строчек о таком хаке (негативных, что ИМХО спорно).
S>Но вот можно ли много хипов закодировать 3мя битами
S>Усложнять надо однако/
Если выделяется блоками по 16 байт — уже 5 битов, ну и так далее. Знаковый бит видимо используется как какой-то специальный маркер.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, Gaperton, Вы писали:
S>>>И решение от CQG — платформонезависимое, или портабельное ?
S>>В догонку — а для двухядерных CPU кол-во интсрукций — вырастает ?
G>Этот аллокатор однопоточный. Насколько я понимаю.
Чего-то я не понимаю:
а в какая связь двухядерного CPU с кол-вом потоков в ПО, которое на нем крутится ?
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Gaperton, Вы писали:
S>>>>И решение от CQG — платформонезависимое, или портабельное ?
S>>>В догонку — а для двухядерных CPU кол-во интсрукций — вырастает ?
G>>Этот аллокатор однопоточный. Насколько я понимаю. S>Чего-то я не понимаю: S> а в какая связь двухядерного CPU с кол-вом потоков в ПО, которое на нем крутится ?
Если вы настаиваете на отсутствии связи — то я не понимаю к чему вы задаете этот вопрос вообще. Как количество ядер может повлиять на количество инструкций аллокатора, если может быть не более чем один аллокатор на поток (выполняющийся, естественно, на одном ядре — по другому никак)? С какой стати количество инструкций аллокатора однопоточного приложения должно вырасти, исполняйся он хоть на двадцатиядерном кристалле? Странный вопрос.
Здравствуйте, Gaperton, Вы писали:
G>Здравствуйте, srggal, Вы писали:
S>>Здравствуйте, Gaperton, Вы писали:
S>>>>>И решение от CQG — платформонезависимое, или портабельное ?
S>>>>В догонку — а для двухядерных CPU кол-во интсрукций — вырастает ?
G>>>Этот аллокатор однопоточный. Насколько я понимаю. S>>Чего-то я не понимаю: S>> а в какая связь двухядерного CPU с кол-вом потоков в ПО, которое на нем крутится ?
G>Если вы настаиваете на отсутствии связи — то я не понимаю к чему вы задаете этот вопрос вообще. Как количество ядер может повлиять на количество инструкций аллокатора, если может быть не более чем один аллокатор на поток (выполняющийся, естественно, на одном ядре — по другому никак)? С какой стати количество инструкций аллокатора однопоточного приложения должно вырасти, исполняйся он хоть на двадцатиядерном кристалле? Странный вопрос.
Здравствуйте, gear nuke, Вы писали:
GN>Пример, можно сказать, неудачный в моём контексте, но он показывает, что можно подумать один раз при дизайне классса, а можно — каждый раз при создании экземпляра.
Если использовать везде один и тот же класс — да, наверно можно. Другой вопрос, что одним методом освобождения памяти все равно не обойдешься (если этот метод — не автоматическая сборка мусора ). А когда таких классов становится несколько, то для каждого объекта тебе все равно придется выбирать
Здравствуйте, Gaperton, Вы писали:
G>Только при ее реализации придется решить ряд интересных инженерных проблем, для того, чтобы действительно получилось O(1). Дьявол в деталях — вы должны экономно подходить к расходованию адресного пространства у вас будет много хипов — надо разработать эффективную схему управления ими. Например — интересна проблема быстрого (за O(1)) определения адреса хипа по указателю на выделенный блок .
Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
А я мечтаю о 64-битах. О резервировании для каждого вектора по гигабайту памяти. И о коммите, только когда надо. То есть, получаем невозможное — отсуствие переаллокаций при переполнении (при переполнении просто коммитим следующую страничку) и одновременно линейный кусок памяти...
Правильно работающая программа — просто частный случай Undefined Behavior
Здравствуйте, _Winnie, Вы писали:
_W>Здравствуйте, Cyberax, Вы писали:
_W>А я мечтаю о 64-битах. О резервировании для каждого вектора по гигабайту памяти. И о коммите, только когда надо. То есть, получаем невозможное — отсуствие переаллокаций при переполнении (при переполнении просто коммитим следующую страничку) и одновременно линейный кусок памяти...
Ну... гранулярность страниц все же присутствует Т. е. для каждого вектора будет выделяться минимум 4 Кб памяти, (Какой размер страницы на AMD64 я не знаю ) Основная потребность в realloc присутвует у разработчиков библиотек, когда у тебя нет ни малейшего понятия ни о том, сколько элементов будет располагаться в твоей структуре данных, ни о том, каков размер каждого элемента. Плюс работа со строками.
Здравствуйте, srggal, Вы писали:
S>Но вот можно ли много хипов закодировать 3мя битами
В менеджере памяти Delphi как раз три бита используется для:
-- для указания того, используется ли данный блок
-- для указания того, свободен ли предыдущий блок
-- для указания специального блока "щель"
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Gaperton, Вы писали:
G>>Только при ее реализации придется решить ряд интересных инженерных проблем, для того, чтобы действительно получилось O(1). Дьявол в деталях — вы должны экономно подходить к расходованию адресного пространства у вас будет много хипов — надо разработать эффективную схему управления ими. Например — интересна проблема быстрого (за O(1)) определения адреса хипа по указателю на выделенный блок .
PD>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
ГМ, я лично, воспринял "адресс хипа" — как индекс хипа.
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, srggal, Вы писали:
S>>Но вот можно ли много хипов закодировать 3мя битами
M>В менеджере памяти Delphi как раз три бита используется для: M> -- для указания того, используется ли данный блок M> -- для указания того, свободен ли предыдущий блок M> -- для указания специального блока "щель"
ГМ, я вел речь не о блоке памяти, который распределен на куче, а о самой куче, их должно быть несколько.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, Gaperton, Вы писали:
G>>Только при ее реализации придется решить ряд интересных инженерных проблем, для того, чтобы действительно получилось O(1). Дьявол в деталях — вы должны экономно подходить к расходованию адресного пространства у вас будет много хипов — надо разработать эффективную схему управления ими. Например — интересна проблема быстрого (за O(1)) определения адреса хипа по указателю на выделенный блок .
PD>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
Это все ерунда. Главное — экономно обойтись с адредным пространством (оно должно отжираться плавно и пропорционально выделенной памяти), а вот как ты при этом собираешься делать деаллокацию объекта за О(1) — очень любопытный вопрос. Плюс — хипов у тебя должно быть много разных в любом случае — во избежание фрагментации для обеспечения хранения объектов разных длин. Соответственно, ты никуда не денешься без определения адреса хипа по указателю на объект. Еще немного, и у тебя появится в этом уверенность. Хотя, если у тебя появится уверенность в обратном — обязательно пиши, это уже будет что-то оригинальное. Баллов дадим — сам понимаешь .
[] PD>>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
S>ГМ, я лично, воспринял "адресс хипа" — как индекс хипа.
ГМ, уточню — индекс хипа в таблице адресов хипов -> конструкция чудесно ложится на ассемблерр
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
Может я туплю, но что Вы вкладываете в понятие ХИП ?
Как примитивный вариант -> это просто голова списка выделенных блоков, и вот его-то адрес и будет в таком случае адресом хипа.
Здравствуйте, buriy, Вы писали:
B>Здравствуйте, Nickolay Ch, Вы писали: NC>>Здравствуйте, Сергей Губанов, Вы писали: СГ>>>P. S. Такие сверхбыстрые операционные системы следующего поколения разрабатываются, например, здесь.
NC>>ЗЫ. Нажал на ссылку интереса ради, и ужаснулся, аж в глазах посинело. Дизайн жуткий, не жмите эту ссылку! B>Мда... Видимо, у тех, кто делает проекты на обероне, нету ни денег, ни мозгов, ни друзей - иначе сделать нормальный дизайн для них проблемы не составило бы...
Здравствуйте, Gaperton, Вы писали:
G>Это все ерунда. Главное — экономно обойтись с адредным пространством (оно должно отжираться плавно и пропорционально выделенной памяти),
Да. Это одно любопытное место.
>а вот как ты при этом собираешься делать деаллокацию объекта за О(1) — очень любопытный вопрос. Плюс — хипов у тебя должно быть много разных в любом случае — во избежание фрагментации для обеспечения хранения объектов разных длин.
Нет. Только по хипу на каждую длину (с учетом выравнивания) Хип0 : 1-8, Хип1 : 9-16 и т.д. (ну может, квант не 8, а 16). Все хипы фрагментированы квантами по 4К.
>Соответственно, ты никуда не денешься без определения адреса хипа по указателю на объект. Еще немного, и у тебя появится в этом уверенность.
У меня давно в этом уверенность есть и желание от нее избавиться. . Какое мне дело до хипа в целом, если я знаю указатель на буфер, где лежит удаляемый элемент ? Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . Проблема — как по указателю на элемент узнать размер. Пока придумал только в самом буфере. Не нравится.
А сам хип можно вполне на произвол его судьбы бросить. Не нужно мне о нем ничего знать. Как рос — так и рос. Мне даже не надо знать , какие страницы он занял — достаточно его в непрерывном пространствек вирт. адресов разместить.
>Хотя, если у тебя появится уверенность в обратном — обязательно пиши, это уже будет что-то оригинальное. Баллов дадим — сам понимаешь .
PD>У меня давно в этом уверенность есть и желание от нее избавиться. . Какое мне дело до хипа в целом, если я знаю указатель на буфер, где лежит удаляемый элемент ? Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . Проблема — как по указателю на элемент узнать размер. Пока придумал только в самом буфере. Не нравится.
PD>А сам хип можно вполне на произвол его судьбы бросить. Не нужно мне о нем ничего знать. Как рос — так и рос. Мне даже не надо знать , какие страницы он занял — достаточно его в непрерывном пространствек вирт. адресов разместить.
обсуждение Нюансов адресации памяти, делаем вывод, что свободно 4 бита 3 младших + 1 старший:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа — неправильно — имелось ввиду- аллокатора ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
S>Или я чего-то не понял ?
S>ЗЫ S>при помощи 3х младших бит — мы сможем расширить поддерживаемый диапазон, при желании
Здравствуйте, srggal, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
Я не планировал эту идею использовать. Но подумаю.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали: S>[] PD>>Я не планировал эту идею использовать. Но подумаю.
S>Могу я расчитывать на то, что вы поделитесь хотя-бы идеей реализации, отличной от трансляции адресов ?
Я идею выскажу, но хотел бы сам додумать до того, что получится.
PD>Вот такая странная идея мне в голову пришла вчера во время бессоницы. Что-то меня на странные идеи потянуло
-- Вчера на улице ко мне подошла старуха и предложила
купить вечную иглу для примуса. Вы знаете, Адам, я не купил.
Мне не нужна вечная игла, я не хочу жить вечно. Я хочу умереть.
У меня налицо все пошлые признаки влюбленности: отсутствие
аппетита, бессонница и маниакальное стремление сочинять стихи.
Слушайте, что я накропал вчера ночью при колеблющемся свете
электрической лампы: "Я помню чудное мгновенье, передо мной
явилась ты, как мимолетное виденье, как гений чистой красоты".
Правда, хорошо? Талантливо? И только на рассвете, когда
дописаны были последние строки, я вспомнил, что этот стих уже
написал А. Пушкин. Такой удар со стороны классика! А?
-- Нет, нет, продолжайте, -- сказал Козлевич сочувственно.
P.S. Если мне не изменяет память, встречал описание подобного алгоритма в первом томе
"Искусства Программирования" и еще в паре других источников.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
S>Или я чего-то не понял ?
S>ЗЫ S>при помощи 3х младших бит — мы сможем расширить поддерживаемый диапазон, при желании
Подумал над этой идеей. Если уж ей следовать, то у нас может быть не 3 младших бита и один старший, а 3(или 4) младших плюс 4-5 старших. Для этого достаточно память выделять в некоторой области , заранее зарезервированной по VirtualAlloc/MEM_RESERVE, а возвращать разницу между указателем на выделенный блок и началом этой зарезервированной области
lpHeapBase = VirtualAlloc(... MEM_RESERVE);
// пусть теперь выделили блок, lpBlock — его адрес
(lpBlock-lpHeapBase) >> 3 (или 4) — разница адресов, сдвинутая вправо. В этой величине левые n бит нулевые
n определяется так
Если размер кратен 8 , то
при макс. размере кучи 128 Мб имеем 3 бита (бывших правых) + 5 бит (бывших левых) — итого аж 8 бит. Один из них (старший есть
признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа, а еще 7 — под размер, что даст 128 разных вариантов — от 8 до 1024 байт.
sch>P.S. Если мне не изменяет память, встречал описание подобного алгоритма в первом томе sch>"Искусства Программирования" и еще в паре других источников.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Подумал над этой идеей. Если уж ей следовать, то у нас может быть не 3 младших бита и один старший, а 3(или 4) младших плюс 4-5 старших. Для этого достаточно память выделять в некоторой области , заранее зарезервированной по VirtualAlloc/MEM_RESERVE, а возвращать разницу между указателем на выделенный блок и началом этой зарезервированной области
PD>lpHeapBase = VirtualAlloc(... MEM_RESERVE);
PD>// пусть теперь выделили блок, lpBlock — его адрес
PD>(lpBlock-lpHeapBase) >> 3 (или 4) — разница адресов, сдвинутая вправо. В этой величине левые n бит нулевые
PD>n определяется так
PD>Если размер кратен 8 , то
PD>при макс. размере кучи 128 Мб имеем 3 бита (бывших правых) + 5 бит (бывших левых) — итого аж 8 бит. Один из них (старший есть PD>признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа, а еще 7 — под размер, что даст 128 разных вариантов — от 8 до 1024 байт.
ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
Здравствуйте, srggal, Вы писали:
S>ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>ГМ, конечно я с Вами согласен, но идея была не в тем чтобы максимально увеличить кол-во хипов, ИМХО 4-8 — достаточно .
PD>Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
ГМ, подхипы — я называю хипами, ибо термина подхип — нет, а хип есть.
ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
PD>>Ну тогда не понял я. Что такое кол-во хипов ? Зачем вообще их нужно иметь несколько ? Я полагаю, что нужен один хип, а нем подхиы — один для 1-8, другой для 9-16 и т.д.
S>ГМ, подхипы — я называю хипами, ибо термина подхип — нет, а хип есть.
S>ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
S>Просто вопрос терминологии.
Вот ещё Вас процитирую
Нет. Только по хипу на каждую длину (с учетом выравнивания) Хип0 : 1-8, Хип1 : 9-16 и т.д. (ну может, квант не 8, а 16). Все хипы фрагментированы квантами по 4К.
И вопрос по существу:
Павел а в чем проблема освобождения памяти о которой твердили большивики ?
Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
Здравствуйте, srggal, Вы писали:
S>ИМХО когда мы грим — хип для объектов размером от 1 до 8 байт — звучит нормально, а когда тоже озвучиваем как подхип для объектов размером от 1 до 8 байт — как-то кривовато.
Сергей. я не хочу о терминах спорить. Пусть будут хипы, хотя я намерен все эти хипы в одном месте держать. Я другое не понимаю — если есть желание 3 бита на номер хипа, то объекты размером больше чем 8*8 == 64 сюда не полезут.
Здравствуйте, srggal, Вы писали:
S>И вопрос по существу: S> Павел а в чем проблема освобождения памяти о которой твердили большивики ?
Проблема в следующем. Есть указатель, который надо освободить. Адрес его буфера в 4К найти не проблема. Но какой размер у элементов этого буфера ? К какому хипу он принадлежит ?
S> Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
Я как-то о LRU в этом контексте вообще не думал. Что освобождать-то по LRU ? У меня есть указатель, надо его запись считать свободной и добавить к списку свободных записей для этого хипа. Какое отношение к этому имеет LRU ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>И вопрос по существу: S>> Павел а в чем проблема освобождения памяти о которой твердили большивики ?
PD>Проблема в следующем. Есть указатель, который надо освободить. Адрес его буфера в 4К найти не проблема. Но какой размер у элементов этого буфера ? К какому хипу он принадлежит ?
S>> Имея LRU блоков, освобождение будет легким и безболезненным, я правильно понимаю ?
PD>Я как-то о LRU в этом контексте вообще не думал. Что освобождать-то по LRU ? У меня есть указатель, надо его запись считать свободной и добавить к списку свободных записей для этого хипа. Какое отношение к этому имеет LRU ?
PD>Похоже, мы не об одном и том же говорим.
ИМХО об одном и томже, только отрывочно, причем и с Вашей стороны, и с моей
Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента .
ОК, имеем указатель на буфер, в указатели в "свободных" битах закодирован индекс хипа(подхипа) в котором он выделен, это и есть размер, поскольку из каждого хипа/подхипа память выделяется блоками фиксированного размера.
Т.е. это массив элементами которого являются головы списков LRU свободных блоков.
ТОгда освобождение блока это:
1) Проверка на то, что этот блок был выделен CQG like allocator;
2) Получения из адреса индекса хипа/подхипа в котором был распределен этот блок;
3) Освобождаемый блок делаем головой списка pEmptyListStart[ index_of_heap ] ( это и есть LRU )
Здравствуйте, srggal, Вы писали:
S>Есть управляющая таблица (массив pEmptyListStart) , индекс в ней определяется размером элемента . S>[/q]
S>ОК, имеем указатель на буфер, в указатели в "свободных" битах закодирован индекс хипа(подхипа) в котором он выделен, это и есть размер, поскольку из каждого хипа/подхипа память выделяется блоками фиксированного размера.
S>Т.е. это массив элементами которого являются головы списков LRU свободных блоков.
S>ТОгда освобождение блока это: S> 1) Проверка на то, что этот блок был выделен CQG like allocator; S> 2) Получения из адреса индекса хипа/подхипа в котором был распределен этот блок; S> 3) Освобождаемый блок делаем головой списка pEmptyListStart[ index_of_heap ] ( это и есть LRU )
S>Об этом говорим?
Да. При чем здесь LRU — понял теперь
Но тогда остается вопрос о битах. 3 битов явно не хватит для серьезной работы, так как макс. размер объекта 64 байта при гранулярности 8 байт.
[] PD>Но тогда остается вопрос о битах. 3 битов явно не хватит для серьезной работы, так как макс. размер объекта 64 байта при гранулярности 8 байт.
Нет никакой ложки
Изначально Вы тоже говорили о 3х хипах, я их немного расширил, ведь это пока, с моей стороны, теоретические выкладки, ни строчки кода не написано мной.
ИМХО, реализация несложна, при достаточно детализации теоретических выкладок.
Естетсвенно, что для реальных задач 3х бит недостаточно, но хочется заметить, что для реальной задачи может понадобиться и другая гранулярность.
Если грить о внедрении CQG like allocator в конретный проект, то для достижения максимальной эффективности необходимо воспользоваться memory profiling, в противном случае некоторый процент эффективности может быть утерян из-за универсальности.
Как вывод: хорошобы чтобы CQG like allocator был максимально настраиваемым как с точки зрения интервалов хипов, так и с точки зрения их гранулярности.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>Изначально Вы тоже говорили о 3х хипах, я их немного расширил, ведь это пока, с моей стороны, теоретические выкладки, ни строчки кода не написано мной.
Нет. я имел в виду произвольное (ограниченное, конечно) количество хипов, просто писал Хип0- 1..8, Хип1 — 9..16 и имел в виду, что далее и т.д. Сорри, если тем самым ввел в заблуждение.
S>ИМХО, реализация несложна, при достаточно детализации теоретических выкладок.
S>Естетсвенно, что для реальных задач 3х бит недостаточно, но хочется заметить, что для реальной задачи может понадобиться и другая гранулярность.
Насчет грануляронсти — или 8, или 16. Я не думаю, что иные значения имеют смысл — будет просто рост накладных расходов. А вообще в той модели, о которой писал утром сегодня, хипов может быть до 128-256, так что это не проблема.
S>Если грить о внедрении CQG like allocator в конретный проект, то для достижения максимальной эффективности необходимо воспользоваться memory profiling, в противном случае некоторый процент эффективности может быть утерян из-за универсальности.
Туманное это дело. Возможно, что и да.
S>Как вывод: хорошобы чтобы CQG like allocator был максимально настраиваемым как с точки зрения интервалов хипов, так и с точки зрения их гранулярности.
S>ЗЫ S>Хорошо, что мы наконец друг друга поняли.
Мне одно пока что не нравится. В результате автору запроса возвращается нечто, из чего он может сделать указатель. При освобождении он дожен передать нам это нечто, а не указатель. Да и вообще возврат этого нечто означает, что будет специализированный код — заменить вызовы malloc вызовом MyAlloc просто так не удастся.
Я хочу, чтобы просто возвращались указатели. Настоящие, чтобы к ним * применить и все! Без игр с младшими/старшими битами
PD>Насчет грануляронсти — или 8, или 16. Я не думаю, что иные значения имеют смысл — будет просто рост накладных расходов. А вообще в той модели, о которой писал утром сегодня, хипов может быть до 128-256, так что это не проблема.
Т.е. таки два варианта всеже есть
PD>Мне одно пока что не нравится. В результате автору запроса возвращается нечто, из чего он может сделать указатель. При освобождении он дожен передать нам это нечто, а не указатель. Да и вообще возврат этого нечто означает, что будет специализированный код — заменить вызовы malloc вызовом MyAlloc просто так не удастся.
PD>Я хочу, чтобы просто возвращались указатели. Настоящие, чтобы к ним * применить и все! Без игр с младшими/старшими битами
Хочется тогоже.
Пока вижу один вариант
Блок под объект выделяется чуть большего размера и в нем хранится допинфо.
— дополнительный расход памяти.
Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле:
адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
Здравствуйте, srggal, Вы писали:
S>Пока вижу один вариант
S>Блок под объект выделяется чуть большего размера и в нем хранится допинфо. S> — дополнительный расход памяти.
Да, я об этом уже думал. Мне не жалко дополнительный расход иметь, но только при малых размерах блока. Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
Здравствуйте, srggal, Вы писали:
S>Имеем N хипов.
S>Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле: S> адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
S>Что думаете по этому поводу Павел ?
Рискованно. Это будет означать жесткое требование — всем хипам одинаковый максимальный размер. Если это не требовать — могут расти те хипы, которым нужно , за счет тех, которым не нужно — при ограничении только суммарного объема. Объектов 1-8 не создавалось, а 9-16 — хоть пруд пруди...
PD>Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
Этого я не понял N — кол-во блоков а 2 — размер допинфо ?
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>Имеем N хипов.
S>>Каждый хип при необходимости расширения использует использует область памяти расчитанную по след. формуле: S>> адрес текущего_фрагмента_хипа + N * размер_фрагмента_хипа
S>>Что думаете по этому поводу Павел ?
PD>Рискованно. Это будет означать жесткое требование — всем хипам одинаковый максимальный размер. Если это не требовать — могут расти те хипы, которым нужно , за счет тех, которым не нужно — при ограничении только суммарного объема. Объектов 1-8 не создавалось, а 9-16 — хоть пруд пруди...
ГМ, правда Ваша. Чтож получается для каждого фрагмента хипа первый (0ой) блок — своя информация о размере элемента.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Все же терять 2^N я не хочу, а поэтому надо резервировать запись, а не 1 байт в 4К. Хотя, между прочим, требование 2^N не обязательно и ни на что не влияет, кроме как на перегрузку кеша. Но и этого достаточно.
S>Этого я не понял N — кол-во блоков а 2 — размер допинфо ?
В начале страницы 4К можно бы хранить размер, т.е. номер хипа Получить адрес начала по указателю — p & 0xFFFFF000. Но на это надо отдать байт хотя бы. После чего в 4К останется 4095 байт и оно на размер элемента (8,16,24...) не делится. А целый элемент отдать — при больших размерах элементов слишком неэкономно.
nBlockSize[nPageNumber++] = nElementSize; // размер элемента, хранимого в этой странице.
Пусть освобождаемый адрес lpElement.
Находим
int nIndex = (lpElement — lpHeapBase) >> 12;
где lpHeapBase — адрес начала области, зарезервированной по VirtualAlloc/MEM_RESERVE для всех хипов.
nIndex и есть тот самый номер страницы, а nBlockSize[nIndex] и есть тот самый размер, а, значит, и номер хипа.
Все это ИМХО уложится в 10-15 ассемблерных команд.
Примечания.
1.Выделение именно квантами в 4К необязательно. Вполне возможно выделение 4К*n, где n можно даже изменять по ходу работы, как это делается у VladD2 http://www.rsdn.ru/article/?53
, да и в куче VC++ тоже. Определить, стоит ли это делать, можно ИМХО только экспериментально.
2. И вообще стоит подумать, не заменить ли 4К на 64К. Это и лучше, меньше дергать VirtualAlloc/MEM_COMMIT. Меня только оверхед смущает...
3. Массив nBlockSize можно даже не занулять.Пусть мусор остается в нем. Использование мусора невозможно по определению
4. Мимоходом — получаем информацию о том, какие 4K блоки отведены каким хипам. Непосредственно она нам не нужна, но можно реализовать функцию GetCurrentHeapSize(int nBlockSize).
5. Освобождение всех хипов (уничтожение кучи) делаем очень просто — VirtualFree/MEM_RELEASE при полном игнорировании того, какие блоки заняты, какие нет, и чем заняты, если заняты . Перед этим в отладочной версии можно проверить блоки и найти memory leaks.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>unsigned char nBlockSize[65536];
PD>Вполне достаточно. Будем иметь до 256 хипов
Гм, пока не нашел к чеиу придраться.
Но вот, об освобождении памяти:
Мы выделяем VP — страницу за страницой, но в том случае если вся память в странице освобождена — сброс страницы — непредусмотрен алгоритмом, я конечно понимаю, кеширование ресурсов и все-такое, но не очень нравится мне этот момент.
Здравствуйте, srggal, Вы писали:
S>Но вот, об освобождении памяти:
S>Мы выделяем VP — страницу за страницой, но в том случае если вся память в странице освобождена — сброс страницы — непредусмотрен алгоритмом, я конечно понимаю, кеширование ресурсов и все-такое, но не очень нравится мне этот момент.
Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
Придумать несложно, но О(1) не получится
PD>ИМХО это не страшно.
Когда-как , но спорить небуду.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>Придумать несложно, но О(1) не получится
Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
PD>>ИМХО это не страшно. S>Когда-как , но спорить небуду.
S>Вроде как решение портабельное получилось
Вроде да. Возможно, для Win64 придется небольшие коррективы сделать. Какой там, кстати, размер страницы, не знаете ?
S>>Вроде как решение портабельное получилось
PD>Вроде да. Возможно, для Win64 придется небольшие коррективы сделать. Какой там, кстати, размер страницы, не знаете ?
Нет пока под руко 64битной винды Не начем вызвать GetSystemInfo.
PD>>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>>Придумать несложно, но О(1) не получится
PD>Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
Павел — такая мысль
nBlockSize это не массив unsigned char, но массив
struct
{
unsigned char block_size;
unsigned int use_counter; // maybe unsigned long at Win64
} page_infos[65536];
Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>>>Не предусмотрен. Я ничего здесь придумать не могу. Отмечу лишь, что для стека Win32 имеем то же. Коммитированное пространство стека растет и никогда не уменьшается.
S>>>Придумать несложно, но О(1) не получится
PD>>Да нет, хуже. Можно, конечно, попробовать поискать блоки, в которых все элементы пусты и откорректировать списки. Но, во-первых, где гарантия, что хоть один найдется, а во-вторых, это несколько усложнит схему выделения (не очень).
S>Павел — такая мысль
S>nBlockSize это не массив unsigned char, но массив S>
S>struct
S>{
S> unsigned char block_size;
S> unsigned short use_counter; // maybe unsigned int/long at Win64
S>} page_infos[65536];
S>
S>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
S>O(1)
Здравствуйте, Pzz, Вы писали:
Pzz>Pavel Dvorkin wrote: >> >> *unsigned char* nBlockSize[65536]; >> >> Вполне достаточно. Будем иметь до 256 хипов
Pzz>Господа,
Pzz>а вы когда-нибудь слышали про buddy allocation system? Если нет, Pzz>рекомендую услышать
ГМ или я чего-то не понял, но здесь написано следующее:
ypically the buddy memory allocation system is implemented with the use of a binary tree to represent used or unused split memory blocks.
srggal wrote: > > Pzz>Господа, > > Pzz>а вы когда-нибудь слышали про buddy allocation system? Если нет, > Pzz>рекомендую услышать > > ГМ или я чего-то не понял, но здесь > <http://en.wikipedia.org/wiki/Buddy_memory_allocation> написано следующее: > > ypically the buddy memory allocation system is implemented with the use > of a *binary tree* to represent used or unused split memory blocks. > > А речь идет об О(1).
Buddy allocation system имеет сложность, для операций выделения и
освобождения памяти, не превышающую O(log2(N)), где N — максимальный
размер блока, который можно зааллоцировать.
Для любых практических целей это то же самое, что O(1), поскольку N —
константа.
S>Павел — такая мысль
S>nBlockSize это не массив unsigned char, но массив S>
S>struct
S>{
S> unsigned char block_size;
S> unsigned int use_counter; // maybe unsigned long at Win64
S>} page_infos[65536];
S>
S>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
Идея неплохая, но дополнительные операции на каждое добавление / удаление. Впрочем, небольшой расход. Но я не очень пойму, что это даст. Освобождать можно только отдельные страницы. Вероятность того, что страницы окажутся совсем пустыми, невелика ИМХО, да даже если это будет и так, какая от этого нам польза ? Я вообще сомневаюсь, что этим надо заниматься. В конце концов commited size еще не есть working set, ненужные страницы уйдут в своп сами. В конце концов никто со стеком такое не делает, а стеков тоже много, по одному на поток.
Здравствуйте, Pzz, Вы писали:
Pzz>Buddy allocation system имеет сложность, для операций выделения и Pzz>освобождения памяти, не превышающую O(log2(N)), где N — максимальный Pzz>размер блока, который можно зааллоцировать.
Pzz>Для любых практических целей это то же самое, что O(1), поскольку N - Pzz>константа.
Если бы речь шла не об операциях, которые вызываются миллионы раз, с этим можно было бы согласиться. В данном же случае даже этот небольшой цикл на 8-12 шагов будет весьма существенным в конечном итоге. ИМХО.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>Павел — такая мысль
S>>nBlockSize это не массив unsigned char, но массив S>>
S>>struct
S>>{
S>> unsigned char block_size;
S>> unsigned int use_counter; // maybe unsigned long at Win64
S>>} page_infos[65536];
S>>
S>>Соответсвенно, выделя память, инкрементируем счетчик, освобождая — декрементируем его.
PD>Идея неплохая, но дополнительные операции на каждое добавление / удаление. Впрочем, небольшой расход. Но я не очень пойму, что это даст. Освобождать можно только отдельные страницы. Вероятность того, что страницы окажутся совсем пустыми, невелика ИМХО, да даже если это будет и так, какая от этого нам польза ? Я вообще сомневаюсь, что этим надо заниматься. В конце концов commited size еще не есть working set, ненужные страницы уйдут в своп сами. В конце концов никто со стеком такое не делает, а стеков тоже много, по одному на поток.
1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
2) Вот то, что они будут в свопе — и не нравится, они же ненужные
Здравствуйте, srggal, Вы писали:
S>1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
Эта опциональная возможность потребует некоторой (пустячной, впрочем) переделки алгоритма выделения некоторого 4К блока. А именно, надо сначала просмотреть для всех уже занятых 4Кблоков page_infos[i].use_counter на предмет нуля. Если оно так и есть, можно его брать вместо выделения нового. Логично.
S>2) Вот то, что они будут в свопе — и не нравится, они же ненужные
Да, это не совсем хорошо. Потенциальный рост свопа без необходимости. В ОП ничего плохого не будет, а вот файл будет (возможно) расти. Но учет пустых блоков эту проблему едва ли решит. Не верю я, что они в реальной жизни будут. Чтобы они были, надо не приложение иметь, а роту солдат — по команде все заняли, по команде освободили... А может, иногда такое и будет.
Вообще-то есть еще одна идея. Правда, это уже будет переход на С++. Вернуть какой-нибудь умный указатель, так чтобы в действительности это был указатель на указатель на запись. Тогда можно будет при необходимости компактировать хип.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
PD>Вообще-то есть еще одна идея. Правда, это уже будет переход на С++. Вернуть какой-нибудь умный указатель, так чтобы в действительности это был указатель на указатель на запись. Тогда можно будет при необходимости компактировать хип.
Не нравится.
Хочется С/С++
PD>Разрабатывать идею не буду
Дык, побольшому счету, мой интерес к CQG like allocator АБСОЛЮТНО теоритический.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>1) Я не грил, что есть от этого мегапольза, но иногда может понадобится, так что, в целом, в CQG like allocator можно предоставить такую ОПЦИОНАЛЬНУЮ возможность. Т.е. не используешь- не плати, хочешь использовать- заплати.
PD>Эта опциональная возможность потребует некоторой (пустячной, впрочем) переделки алгоритма выделения некоторого 4К блока. А именно, надо сначала просмотреть для всех уже занятых 4Кблоков page_infos[i].use_counter на предмет нуля. Если оно так и есть, можно его брать вместо выделения нового. Логично.
ГМ, я имел ввиду случай когда фрагмент хипа равен размеру вмртуальной страницы, в противном случае со сбросом неиспользуемых страниц будет гиммор.
Кроме этого, необходимо предусмотреть ограничение на кол-во распределенных, но неиспользуемых фрагментов хипов, дабы небыло такого, что только сбросили страницу, и тутже её необхлдимо опять использовать.
Не нравится мне переделка освобождения, что-то тревожит, пока сформулировать не могу ; подумаю на выходных.
PD>Да, это не совсем хорошо. Потенциальный рост свопа без необходимости. В ОП ничего плохого не будет, а вот файл будет (возможно) расти. Но учет пустых блоков эту проблему едва ли решит. Не верю я, что они в реальной жизни будут. Чтобы они были, надо не приложение иметь, а роту солдат — по команде все заняли, по команде освободили... А может, иногда такое и будет.
Гм, рота солдат — мощно
std::vector< X > — вот она, то ли рота, то ли батальон, а возможно и дивизия
Что именно — зависит от 3х факторов:
1) sizeof(X)
2) vector.size()
3) специфики работы программы.
Здравствуйте, srggal, Вы писали:
S>Здравствуйте, Pavel Dvorkin, Вы писали:
S>ГМ, я имел ввиду случай когда фрагмент хипа равен размеру вмртуальной страницы, в противном случае со сбросом неиспользуемых страниц будет гиммор.
Естественно.
S>Кроме этого, необходимо предусмотреть ограничение на кол-во распределенных, но неиспользуемых фрагментов хипов, дабы небыло такого, что только сбросили страницу, и тутже её необхлдимо опять использовать.
И это возможно.
S> Не нравится мне переделка освобождения, что-то тревожит, пока сформулировать не могу ; подумаю на выходных.
Я тоже подумаю. Но, в конце концов, от этого и отказаться можно.
S>std::vector< X > — вот она, то ли рота, то ли батальон, а возможно и дивизия
Да, согласен. Захватили этот vector, потом чего-то еще, потом его выбросили — и готовы несколько страниц свободных.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>Дык, побольшому счету, мой интерес к CQG like allocator АБСОЛЮТНО теоритический.
PD>А я вот думаю, не дать ли это третьекурснику в качестве курсовой
Здравствуйте, srggal, Вы писали:
S>П что за предемет ?
Курсовая — не по предмету. Это просто некоторая работа, которую студент должен сделать в течение года. Факультет математический, поэтому либо математика (это не мое), либо программирование. Какая именно область программирования — не так уж важно, определяет научный руководитель.
За выходные придумал еще одно небольшое изменение. Если страница была захвачена и потом была полностью освобождена — не делать ей VirtualFree, а просто оставить ее. При выделении новой страницы ее можно выделить.
Т.е была, к примеру, некая страница выделена под элементы длиной 256. Потом все они были удалены, так что use_counter == 0. Теперь нужна новая страница под элементы с размером 128. Если есть хоть одна страница с use_counter == 0, взять ее, иначе коммитировать еще 4К.
Для нахождения страницы с use_counter==0 можно в приниципе и отказаться от О(1), просто искать ее в массиве. Это не так уж часто будет делаться. Но если уж очень хочется О(1), то можно провязать все нули еще одним LRU списком — освобожденных страниц. Т.е. когда у страницы use_counter становится равным 0, номер ее добавляется в LRU (стек) освобожденых страниц, а при запросе новой страницы берем оттуда , если стек не пуст.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Здравствуйте, srggal, Вы писали:
S>>П что за предемет ?
PD>Курсовая — не по предмету. Это просто некоторая работа, которую студент должен сделать в течение года. Факультет математический, поэтому либо математика (это не мое), либо программирование. Какая именно область программирования — не так уж важно, определяет научный руководитель.
Ок
PD>За выходные придумал еще одно небольшое изменение. Если страница была захвачена и потом была полностью освобождена — не делать ей VirtualFree, а просто оставить ее. При выделении новой страницы ее можно выделить. PD>Т.е была, к примеру, некая страница выделена под элементы длиной 256. Потом все они были удалены, так что use_counter == 0. Теперь нужна новая страница под элементы с размером 128. Если есть хоть одна страница с use_counter == 0, взять ее, иначе коммитировать еще 4К.
PD>Для нахождения страницы с use_counter==0 можно в приниципе и отказаться от О(1), просто искать ее в массиве. Это не так уж часто будет делаться. Но если уж очень хочется О(1), то можно провязать все нули еще одним LRU списком — освобожденных страниц. Т.е. когда у страницы use_counter становится равным 0, номер ее добавляется в LRU (стек) освобожденых страниц, а при запросе новой страницы берем оттуда , если стек не пуст.
Да, я жумал именно об этом, но ак-то слишком много списков
Здравствуйте, gear nuke, Вы писали:
GN>Я имел ввиду не управление памятью в целом, а использование объектов, тем или иным образом уже инкапсулирующих управление памяти в себе — будь то GC, RAII или ещё что-то. То есть, где подумать надо один раз, а не для каждого экземпляра.
RAII — это не автоматическое управление памятью. Это костыль в процессе ручного управления ею. Так что средствами RAII нельзя полностью инкапсулировать работу с памятью. Тебе прийдется продумывать политику владения и вручную ее отслеживать. Причем в мало мальски серьезном проекте ты сталкнешся с тем, что есть чужой код который плевать хотел на твою политику владения. И у тебя в программе появится еще одна политика, а потом еще...
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
дравствуйте, gear nuke, Вы писали:
GN>Даже если всё будет распологаться не в стеке, а в куче — не будет фрагментации, и создание + удаление останутся так же почти бесплатны, поскольку порядок этих операций гарантирован.
Не, батенька. Только стэк практически беслатен. А куча всегда платна. Это и вылет за пределы кэша, и синхронизация.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, _Winnie, Вы писали:
_W>А я мечтаю о 64-битах. О резервировании для каждого вектора по гигабайту памяти. И о коммите, только когда надо. То есть, получаем невозможное — отсуствие переаллокаций при переполнении (при переполнении просто коммитим следующую страничку) и одновременно линейный кусок памяти...
Тсссс! Тут рядом Дворкин. Он же поаусает за такие траты ресурсов.
ЗЫ
Если серьезно, то управление виртуальной памятью двольно дорого. Перезаняите памяти в неком ЖЦ и копирование ее в с помощью SSE2 куда быстрее. У МС при разработке ЖЦ стояла задача сделать сборку нулевого и первого поколения быстрее чем обработка Page Fault и они этого добились (даже на P90).
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, srggal, Вы писали:
S>ГМ, я вел речь не о блоке памяти, который распределен на куче, а о самой куче, их должно быть несколько.
Если подумать, то у кучь разное адрессное пространство (ни же не двигаются). Так что берем адрес и смотрим в какой диапазно он входит. Ну, или еще тупее. Кладем в каждый блок ссылку на кучу. Я в QuickHeap
так делал. В статье этого не сказно, но в дальнейшем по совоету одного орла сделал указатель на следующий блок и ссылку на хип одним юнионом. Результат на лицо
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Я сейчас над этой идеей размышляю, и у меня пока нет уверенности, что мне вообще адрес хипа нужен. Более того, не уверен, что у него вообще должен быть адрес — в смысле , что он должен лежать непрерывным куском.
Только учти в своих размышлениях, что выделение памяти (VirtualAlloc) в ОС довольно дорого.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Gaperton, Вы писали:
G>Это все ерунда. Главное — экономно обойтись с адредным пространством (оно должно отжираться плавно и пропорционально выделенной памяти), а вот как ты при этом собираешься делать деаллокацию объекта за О(1) — очень любопытный вопрос. Плюс — хипов у тебя должно быть много разных в любом случае — во избежание фрагментации для обеспечения хранения объектов разных длин. Соответственно, ты никуда не денешься без определения адреса хипа по указателю на объект. Еще немного, и у тебя появится в этом уверенность. Хотя, если у тебя появится уверенность в обратном — обязательно пиши, это уже будет что-то оригинальное. Баллов дадим — сам понимаешь .
Согласен. Но почему обязательно "экономно обойтись с адредным пространством"? Может у программы важность большая, а памяти она и так не много расходунет (но часто ее перезанимает)? В ООП так часто бывает.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, srggal, Вы писали:
S>старший бит — признак того, что объект размер объекта удовлетворяет диапазонам нашего хипа ,т.е. в Вашкм примере:
S>
S>массив0 — для объектов с размером от 1 до 8 байт
S>массив1 — от 9 до 16
S>массив2 от 17 до 24
S>а младште 3 бита будем использовать для кодирования длины выделенного блока.
А теперь подумай. Ты постоянно будешь терять тучу места на каждый обхект. Не проще ли в него запихать ссылку на нужную структуру? Тогда будешь терять фиксированное количество памяти(4 байта) и иметь возможность адресовать все что хочешь.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Если серьезно, то управление виртуальной памятью двольно дорого.
C чего бы? Управление VM — это по сути просто записи в таблицы.
Обработку страничных ошибок можно тоже значительно ускорить (до
нескольких тысяч тактов — никакому GC такое и не снилось).
Здравствуйте, Cyberax, Вы писали:
C>VladD2 wrote: >> Если серьезно, то управление виртуальной памятью двольно дорого. C>C чего бы? Управление VM — это по сути просто записи в таблицы.
Начнем с того, что все управление виртуалкой осуществляется из нулевого кольца. А сам переход в него из пользовательского режима уже занятие не дешовое. Потом обработка исключения дело не дешовое...
В общем, это вопрос не ко мне. У нас тут на сайте есть Алекс Федотов и другие орлы которые тебе это смогут объяснить на высоком техническом уровне. А я просто знаю, что оно не дешево. И знаю, что в МС специально добивались, чтобы сборка мусора была дешевле обработки сбоя доступа к странице. Иначе можно было бы забить на все и жить на виртуалке.
C>Обработку страничных ошибок можно тоже значительно ускорить (до C>нескольких тысяч тактов — никакому GC такое и не снилось).
Охринительная ссылка — "sun"..."solaris"... И размеры массивов как раз для разговора о ЖЦ (от 50 метров). И время просто выдающееся (от 3 секунд). Речь идет об управлении объектами размер которых порой составляет несколько десятков байт (от двенадцати). И о времени имеряемом микросекундами.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Начнем с того, что все управление виртуалкой осуществляется из нулевого > кольца. А сам переход в него из пользовательского режима уже занятие не > дешовое. Потом обработка исключения дело не дешовое...
Кстати, до меня только сейчас дошло — можно ведь (в случае вектора)
просто явно коммитить память без всяких страничных исключений.
> В общем, это вопрос не ко мне. У нас тут на сайте есть Алекс Федотов и > другие орлы которые тебе это смогут объяснить на высоком техническом > уровне. А я просто знаю, что оно не дешево. И знаю, что в МС специально > добивались, чтобы сборка мусора была дешевле обработки сбоя доступа к > странице.
Добавьте: в операционной системе Windows в 32-битном режиме.
> C>Обработку страничных ошибок можно тоже значительно ускорить (до > C>нескольких тысяч тактов — никакому GC такое и не снилось). > Какие десятки тактов? Преключение в нулевое кольцо вроде как уже сотни > тактов.
Я вообще-то написал слово "тысяч". Кстати, где-то видел исследование о
системе управления VM из обычного пользовательского режима. Там вообще
все в сотни тактов укладывалось.
> C>На эту тему были неплохие исследования (могу поискать на ACM). А вот > C>реализация вектора: > C>http://developers.sun.com/solaris/articles/virtual_memory_arrays.html > Охринительная ссылка — "sun"..."solaris"... И размеры массивов как раз > для разговора о ЖЦ (от 50 метров). И время просто выдающееся (от 3 > секунд). Речь идет об управлении объектами размер которых порой > составляет несколько десятков байт (от двенадцати). И о времени > имеряемом микросекундами.
Ну так никто вроде бы никто не собирается на каждый объект делать
обращение к менеджеру виртуальной памяти.
Здравствуйте, Cyberax, Вы писали:
C>VladD2 wrote: >> Начнем с того, что все управление виртуалкой осуществляется из нулевого >> кольца. А сам переход в него из пользовательского режима уже занятие не >> дешовое. Потом обработка исключения дело не дешовое... C>Кстати, до меня только сейчас дошло — можно ведь (в случае вектора) C>просто явно коммитить память без всяких страничных исключений.
Здравствуйте, VladD2,
GN>>Даже если всё будет распологаться не в стеке, а в куче — не будет фрагментации, и создание + удаление останутся так же почти бесплатны, поскольку порядок этих операций гарантирован.
VD>Не, батенька. Только стэк практически беслатен. А куча всегда платна. Это и вылет за пределы кэша, и синхронизация.
В данном случае я говорю о создании в куче автоматических объектов. С вылетами за кеш всё тоже самое, что и со стеком (а что, стек не имеет таких проблем?). С синхронизацией теоретически проблем тоже может не быть, если компилятор потрудится для каждого треда свою кучу создать (как и стек). В общем-то деление на стек и кучу довольно условное и объясняется в случае x86 наличием аппаратной поддержки (указатель всегда хранится в esp), но никто (кроме здравого смысла) не мешает хранить в другом регистре постоянный указатель на кучу.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>В данном случае я говорю о создании в куче автоматических объектов. С вылетами за кеш всё тоже самое, что и со стеком (а что, стек не имеет таких проблем?). С синхронизацией теоретически проблем тоже может не быть, если компилятор потрудится для каждого треда свою кучу создать (как и стек). В общем-то деление на стек и кучу довольно условное и объясняется в случае x86 наличием аппаратной поддержки (указатель всегда хранится в esp), но никто (кроме здравого смысла) не мешает хранить в другом регистре постоянный указатель на кучу.
В описанном тбой варианте. Новая куча не отличается от стэка. Так что смысла в ней нет. Используй стэк.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>В описанном тбой варианте. Новая куча не отличается от стэка. Так что смысла в ней нет. Используй стэк.
У кучи больше возможностей для роста — она не обязана быть непрерывной (в реально ли сделать фрагментированный стек в неуправляемых языках?). Она может использоваться вместо стека для того, что бы избежать проблем, о которых писал Кодт здесь
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, gear nuke, Вы писали:
GN>У кучи больше возможностей для роста — она не обязана быть непрерывной
Стэк тоже не обязан. Более того в Сингулярити он может состоять измножества сегментов.
GN>(в реально ли сделать фрагментированный стек в неуправляемых языках?).
Неуправляемые языки меня мало трогают. Но в принципе... а почему бы и нет?
GN> Она может использоваться вместо стека для того, что бы избежать проблем, о которых писал Кодт здесь
Здравствуйте, Cyberax, Вы писали:
C>Кстати, до меня только сейчас дошло — можно ведь (в случае вектора) C>просто явно коммитить память без всяких страничных исключений.
1. Все равно не быстро.
2. Это применимо только когда размер массива сильно вызодит за 4-8 килобайта. А это столь редкий случай, что и говорить о нем нет смысла.
C>Добавьте: в операционной системе Windows в 32-битном режиме.
Думашь 64-битном будет положительная разница? Или типа Линукс круче?
По информации из отчета по Сингулярити стоимость вызова API-функции в рзных ОС такова:
Cost (CPU Cycles)
Singularity FreeBSD Linux Windows
ABI call 87 878 437 627
Ну, а в рамках одного процесса это вообще 1-5 циклов процессора. Так что можно казать, что скорее всего во всех ОС аппоратной защитой памяти (на современных процессорах).
C>Я вообще-то написал слово "тысяч". Кстати, где-то видел исследование о C>системе управления VM из обычного пользовательского режима. Там вообще C>все в сотни тактов укладывалось.
А, ну, ну. Просто чистый вызов в нулевое кольцо уже по 500 циклов. А там еще работы немеряно.
C>Ну так никто вроде бы никто не собирается на каждый объект делать C>обращение к менеджеру виртуальной памяти.
Вот для этого и делают шустрые ЖЦ.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2,
GN>>У кучи больше возможностей для роста — она не обязана быть непрерывной
VD>Стэк тоже не обязан. Более того в Сингулярити он может состоять измножества сегментов.
Я знал, что будет именно такой ответ
Очень многое зависит от среды выполнения.
GN>>(в реально ли сделать фрагментированный стек в неуправляемых языках?).
VD>Неуправляемые языки меня мало трогают. Но в принципе... а почему бы и нет?
Да... но после некоторых размышлений о "деталях", появляются мысли о переходе на управляемые языки
Как альтернативу можно рассматривать воплощение в железе — поддержка виртуальной памяти давно есть, стек\куча требуют почти теже механизмы. Но это очень дорого в настоящий момент. Ну и языки всё равно там будут управляемые, только не виртуальной машиной, а реальной.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
VladD2 wrote: > > Думашь 64-битном будет положительная разница? Или типа Линукс круче? > По информации из отчета по Сингулярити <отчета%20по%20Сингулярити> > стоимость вызова API-функции в рзных ОС такова: > > Cost (CPU Cycles) > Singularity FreeBSD Linux Windows > ABI call 87 878 437 627
В MS-DOS'е стоимость системного вызова могла бы быть еще меньше.
VladD2 wrote: > > Pzz>В MS-DOS'е стоимость системного вызова могла бы быть еще меньше. > > Ее там вообще небыло. В прочем как и защиты, процессов, многопоточности, > безопасности...
Кстати, сисколл у MS-DOS'а был очень дорогим, причем, в общем-то, безо
всякой видимой причины...
Здравствуйте, Pzz, Вы писали:
Pzz>Кстати, сисколл у MS-DOS'а был очень дорогим, причем, в общем-то, безо Pzz>всякой видимой причины...
У ДОС-а небыло никаких "сисколлов". Он пользовался стандартными прерываниями процессора. ДОС резервировал Int 21h. А то что некоторые функции могли выполняться по пол часа это уже другой разговор.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > Pzz>В MS-DOS'е стоимость системного вызова могла бы быть еще меньше. > Ее там вообще небыло. В прочем как и защиты, процессов, многопоточности, > безопасности...
В Singularity ее тоже нет. Она полагается лишь на статическую проверку
кода, которая не будет работать в случае unsafe'а.
VladD2 wrote: > C>Кстати, до меня только сейчас дошло — можно ведь (в случае вектора) > C>просто явно коммитить память без всяких страничных исключений. > 1. Все равно не быстро. > 2. Это применимо только когда размер массива сильно вызодит за 4-8 > килобайта. А это столь редкий случай, что и говорить о нем нет смысла.
Не сказал бы. Вообще, для размеров от 0 до 128 байт можно нормально
сделать аллокаторы, работающие с фиксироваными списками. Они будут
работать примерно со скоростью GC (скорее всего можно будет найти тесты
где будет побеждать GC и где будут побеждать аллокаторы).
Так что интересен как раз диапазон 128 байт — 4 Кбайт. GC на этом
диапазоне не особо эффективен — нужно слишком много всего копировать.
Ручной менеджмент тоже не особо эффективен.
На ACM видел исследования систем управления памятью как раз для этого
случая — рассматривался механизм использования страниц по 512 байт
вместо 4Кб.
> C>Добавьте: в операционной системе Windows в 32-битном режиме. > Думашь 64-битном будет положительная разница? Или типа Линукс круче? > А, ну, ну. Просто чистый вызов в нулевое кольцо уже по 500 циклов. А > > там еще работы немеряно.
Во-первых, Линукс действительно круче (я говорю только про ядро).
Во-вторых, есть способы уменьшить оверхед системных вызовов в разы —
посмотрите на микроядерные ОС (тот же Hurd), там стоимость системного
вызова намного меньше.
> C>Ну так никто вроде бы никто не собирается на каждый объект делать > C>обращение к менеджеру виртуальной памяти. > Вот для этого и делают шустрые ЖЦ.
А еще для этого делают нормальные аллокаторы.
Cyberax wrote: > > Во-первых, Линукс действительно круче (я говорю только про ядро). > Во-вторых, есть способы уменьшить оверхед системных вызовов в разы — > посмотрите на микроядерные ОС (тот же Hurd), там стоимость системного > вызова намного меньше.
На микроядрас стоимость "полезного" системного вызова (т.е., не того
низкоуровнего, которое представляет микроядро, типа послать сообщение
факловой системе, а семантически сравнимого с сисколом традиционного
ядра) обычно выше, чем в случае монолитного ядра. Микроядро в таких
системах мало чего делает, лишь координирует работу отдельных частей
системы и это, естественно, добавляет определенный overhead.
На hurd я бы ссылаться не стал, больно уж он мертвый. Но говорят, MacOS
X имеет такую же архитектуру: POSIX-like система, сделанная на основе
микроядра Mach3. Так что при желании можно попробовать поискать цифры
про MacOS.
Здравствуйте, Cyberax, Вы писали:
>> Pzz>В MS-DOS'е стоимость системного вызова могла бы быть еще меньше. >> Ее там вообще небыло. В прочем как и защиты, процессов, многопоточности, >> безопасности... C>В Singularity ее тоже нет. Она полагается лишь на статическую проверку C>кода, которая не будет работать в случае unsafe'а.
Почитай про идею SIP и вообще про задачи ОС и исследования. Тогда может быть желание говорить об unsafe пропадет само собой. Собственно сам первод SIP — "софтовая иззоляция процессов" говорит сам за себя.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>По информации из отчета по Сингулярити стоимость вызова API-функции в рзных ОС такова: VD>
VD> Cost (CPU Cycles)
VD> Singularity FreeBSD Linux Windows
VD>ABI call 87 878 437 627
Если под этим понимается вызов ядра, то:
на неуправляемых системах происходит переход между кольцами аппаратной защиты, что само по себе довольно дорого. (по тем же причинам в ОС используют софтверное переключение задач, а не аппаратное)
Разница в цифрах между FreeBSD\Linux\Windows, по-видимому происходит из-за различных методик верификации передаваемых в ядро аргументов. Эта цифра скорее говорит о том, что где-то проверки делают более "тщательно" либо кто-то просто оптимизировал это дело.
В Singularity аппаратная защита теряет смысл — вот и "оптимизация" — просто исключили лишнее звено. Проверки передаваемых аргументов можно тоже упростить, они судя по всему и в других местах проверяются. Поэтому и разница на порядок. Обычным системам здесь никак не выиграть, выполнять весь код в одном кольце для них защиты смерти подобно.
Остаётся открытым вопрос — насколько практически надёжную защиту сможет дать Singularity?
Теоретические выкладки мало интересны, Java VM как известно ужасно дырява, а Janus у меня вчера без видимых оснований выдал AV при дуступе к 0му адресу
Хотя никто не мешает добавить и аппаратные кольца защиты — запас есть.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
gear nuke wrote: > > Если под этим понимается вызов ядра, то: > на неуправляемых системах происходит переход между кольцами аппаратной > защиты, что само по себе довольно дорого. (по тем же причинам в ОС > используют софтверное переключение задач, а не аппаратное)
А никто не напомнит, сколько там тактов нужно Пентиуму, чтобы
переключиться с 3-го кольца на нулевое при вызове через call gate?
VladD2 wrote: > Почитай про идею SIP и вообще про задачи ОС и исследования. Тогда может > быть желание говорить об unsafe пропадет само собой. Собственно сам > первод SIP — "софтовая иззоляция процессов" говорит сам за себя.
Какая разница как оно называется? Оно может работать по определению
только с safe-кодом.
VladD2 wrote: > Сигулярити и есть ОС в которой вызов сделан самым дешевым (на порядок > дешевле чем в любой другой ОС с защитой). О чет ты пыташся сказать то?
В Сингулярити все работает в нулевом кольце, так что там нечем особо
гордиться. Есть определенные подходы, позволяющие значительно ускорить
обработку сисколов и в обычных ОС с аппаратной защитой.
Здравствуйте, Pzz, Вы писали:
Pzz>А никто не напомнит, сколько там тактов нужно Пентиуму, чтобы Pzz>переключиться с 3-го кольца на нулевое при вызове через call gate?
А где колгейты используются?
В NT — int gate, что по скорости немного быстрее, поскольку far call на каждый параметр ещё время тратит.
В доках от Intel информации не видел, но процессор должен не мало проделать при переключании, ту же IDT обработать. Речь уже не о тактах идёт.
486 тратил 77+4*кол-во_параметров на CALL через шлюз. INT — 71. IRET — 36.
Вряд ли что-то сильно изменилось на новых комнях, SYSENTER не зря добавили (в XP она и используется). Как там себя конвеер ведёт не знаю, наверняка сбрасывается заодно с некоторыми кешами -> дополнительные потери. И это всё ещё без учёта затрат на диспетчер.
Хорошо бы это померить, но плохо представляю, как получить приемлимую точность
Кстати, когда-то читал, во FreeBSD (? точно не уверен) хотели использовать DMA для копирования больших кусков памяти — оказалось медленно.
В общем, тенданция пугающая — hardware sux
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
gear nuke wrote: > > Pzz>А никто не напомнит, сколько там тактов нужно Пентиуму, чтобы > Pzz>переключиться с 3-го кольца на нулевое при вызове через call gate? > > А где колгейты используются? > В NT — int gate, что по скорости немного быстрее, поскольку far call на > каждый параметр ещё время тратит. > В доках от Intel информации не видел, но процессор должен не мало > проделать при переключании, ту же IDT обработать. Речь уже не о тактах идёт. > 486 тратил 77+4*кол-во_параметров на CALL через шлюз. INT — 71. IRET — 36. > Вряд ли что-то сильно изменилось на новых комнях, SYSENTER не зря > добавили (в XP она и используется). Как там себя конвеер ведёт не знаю, > наверняка сбрасывается заодно с некоторыми кешами -> дополнительные > потери. И это всё ещё без учёта затрат на диспетчер. > Хорошо бы это померить, но плохо представляю, как получить приемлимую > точность
OK. И какова доля этих потерь на фоне всех остальных затрат на обработку
сискола?
> Кстати, когда-то читал, во FreeBSD (? точно не уверен) хотели > использовать DMA для копирования больших кусков памяти — оказалось медленно.
В PC нет быстрого DMA (я не имею ввиду busmastering, который
осущствляется всякими там контроллерами — как его использовать для
передачи из памяти в память, не очень понятно).
Кроме того, передача на самом деле нужна не из памяти в память, а из
кеша в кеш. Использование DMA, это явно плохая идея.
Здравствуйте, gear nuke, Вы писали:
GN>Остаётся открытым вопрос — насколько практически надёжную защиту сможет дать Singularity?
Думаю на 99%.
GN>Теоретические выкладки мало интересны, Java VM как известно ужасно дырява, а Janus у меня вчера без видимых оснований выдал AV при дуступе к 0му адресу
Незнаю что ты имешь в виду под жудкой дырявостью Явы. Попробуй завалить ее используя только компилятор Явы, а мы поглядим.
Что касается Януса, то в нем неуправляемого кода пожалуй что больше чем управляемого. Это и Джэт, и Интернет Эксплорер, и куча интеропа. В Сингулярити все прикладные процессы (а скорее всего и остальные) будут управляемыми и безопасными.
GN>Хотя никто не мешает добавить и аппаратные кольца защиты — запас есть.
На фиг они там не упали. Весь смысл в том, что без них прекрасно можно обойтись.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Cyberax, Вы писали:
C>VladD2 wrote: >> Почитай про идею SIP и вообще про задачи ОС и исследования. Тогда может >> быть желание говорить об unsafe пропадет само собой. Собственно сам >> первод SIP — "софтовая иззоляция процессов" говорит сам за себя. C>Какая разница как оно называется? Оно может работать по определению C>только с safe-кодом.
Вот именно, по определению. Точнее по спецификации. И ни с каким другим.
Так что не нужно даже обсуждать что будет в случае если повсеместно начнет использоваться unsafe.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
C>В Сингулярити все работает в нулевом кольце, так что там нечем особо C>гордиться.
Я бы как раз скзал, что там очень даже есть чем гордиться. Именно то, что система надежность которой выше чем у современных ОС не нуждается в аппоратной защите и прекрасно работает в нулевом кольце — это очень нехилое достижение.
C> Есть определенные подходы, позволяющие значительно ускорить C>обработку сисколов и в обычных ОС с аппаратной защитой.
Ага. А в рельных ОС их неиспользуют по морально-этическим соображениям.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > C>В Сингулярити все работает в нулевом кольце, так что там нечем особо > C>гордиться. > Я бы как раз скзал, что там очень даже есть чем гордиться. Именно то, > что система надежность которой выше чем у современных ОС не нуждается в > аппоратной защите и прекрасно работает в нулевом кольце — это очень > нехилое достижение.
Это еще кучу лет назад было в MS-DOS в программах на Бейсике
> C> Есть определенные подходы, позволяющие значительно ускорить > C>обработку сисколов и в обычных ОС с аппаратной защитой. > Ага. А в рельных ОС их неиспользуют по морально-этическим соображениям.
Нет, используются. Но пока это работы исследовательского характера —
например в одной работе предлагалось складывать вызовы сисколов в
расшареную память, которую читает системный сервер. То есть вызов
выглядит просто как копирование аргументов в shared-сегмент.
Сервер (в другом процессе) это замечает, обрабатывает вызов и кладет
туда же ответ. Получается очень хорошая экономия тактов на
Hyper-threading-процессорах.
Учитывая грядущее распространение двухядерных процессоров может быть
эффективным запускать системный процесс в виде потока на одном ядре, с
котороым пользовательский процесс на другом ядре общается с помощью
аппаратного FIFO.
Пока все это находится в процессе исследования, так что в обычных ядрах
появится еще не скоро (хотя во всяких Hurd'ах уже применяются подобные
схемы). Но способы потенциально в разы сократить время все же есть.
Здравствуйте, Pzz, Вы писали:
Pzz>OK. И какова доля этих потерь на фоне всех остальных затрат на обработку сискола?
Это могут быть величины одного порядка.
Если говорить о выделении памяти, то в лучших случаях на выделение достаточно единиц тактов. А не сотен, как при вызове ядра.
Pzz>передача на самом деле нужна не из памяти в память, а из кеша в кеш.
Не могу понять выделенное.
Если копируется память, то она копируется *по определению*
Pzz>Использование DMA, это явно плохая идея.
Он может разгрузить CPU, помимо всего прочего.
В общем-то DMA влюбом случае сейчас не имеет смысла — шина памяти всё равно слишком узкая, при правильном подходе, CPU её прокачает без проблем, ещё и ждать будет.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, VladD2,
GN>>Остаётся открытым вопрос — насколько практически надёжную защиту сможет дать Singularity?
VD>Думаю на 99%.
Всё понятно. Если драйвер не работает в 1 сдучае из 1000000, значит он не работает совсем.
К безопасности требования ещё строже, с такими цифрами это значит: "заходите добры люди, берите что хотите"
VD>Незнаю что ты имешь в виду под жудкой дырявостью Явы.
Я в общем-то тоже не знаю. Но жаба у меня на всякий случай выключена в браузерах, как советую те, кто знает.
VD>Попробуй завалить ее используя только компилятор Явы, а мы поглядим.
Боюсь у меня на это много времени уйдёт, может быть даже несколько лет. А у кого-то уйдёт пара часов. Вот они-то и представляют опасность.
Эти цифры мало о чём говорят, но они есть:
Results 1 — 10 of about 126,000 for JVM exploit. (0.04 seconds)
Results 1 — 10 of about 83,300 for JRE exploit. (0.04 seconds)
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
gear nuke wrote: > > Pzz>OK. И какова доля этих потерь на фоне всех остальных затрат на > обработку сискола? > > Это могут быть величины одного порядка.
Могут, наверное, но не есть. Если же учесть, что сисколы, в большинстве
своем, делают чего-нибудь полезное (например, записывают данные на
диск), то overhead от перехода в другое кольцо защиты кажется уже совсем
незаметным.
> Если говорить о выделении памяти, то в лучших случаях на выделение > достаточно единиц тактов. А не сотен, как при вызове ядра.
А при чем здесь это?
> Pzz>передача на самом деле нужна не из памяти в память, а *из кеша в кеш*. > > Не могу понять выделенное. > Если копируется память, то она копируется *по определению*
Если память копируется какой-нибудь внешней прибамбасой, то происходит
следующее:
1. Скорее всего, данные в том месте, где их надо взять, недавно
подсчитаны. Значит, скорее всего, они в кеше процессора. Их надо слить
оттуда в память.
2. Далее, их надо скопировать в другое место памяти
3. И наконец, если дальше эти данные будут как-то еще обрабатываться,
они должны опять попасть в кеш процессора.
Если же мы говорим о, скажем, записи на диск, то копированые может быть
вообще не нужно. Дисковый контроллер может забрать эти данные прямо из
того места памяти, где user space process их хранит.
Здравствуйте, Pzz, Вы писали:
Pzz>>>OK. И какова доля этих потерь на фоне всех остальных затрат на обработку сискола?
GN>> Это могут быть величины одного порядка.
Pzz>Могут, наверное, но не есть.
Однако, не всё. В NT специально существует несколько отдельныех int gate. Для того, что бы убрать задержки из-за диспетчера. Некоторые структуры разделяются между ядром и юзерлендом — что бы совсем избежать оверхеда. Есть вещи, где эти несколько сотен тактов очень критичны.
Pzz>Если же учесть, что сисколы, в большинстве своем, делают чего-нибудь полезное (например, записывают данные на диск), то overhead от перехода в другое кольцо защиты кажется уже совсем незаметным.
Наличие случаев, где можно пренебречь оверхедом, не спасает остальные.
GN>> Если говорить о выделении памяти, то в лучших случаях на выделение GN>> достаточно единиц тактов. А не сотен, как при вызове ядра.
Pzz>А при чем здесь это?
См. тему. Резервирование, коммит памяти — всё это возможно лишь через ядро. Сами эти операции не слишком дороги.
Pzz>Если память копируется какой-нибудь внешней прибамбасой, то происходит следующее: Pzz> 1. Скорее всего, данные в том месте, где их надо взять, недавно подсчитаны. Значит, скорее всего, они в кеше процессора. Их надо слить оттуда в память. Pzz> 2. Далее, их надо скопировать в другое место памяти Pzz> 3. И наконец, если дальше эти данные будут как-то еще обрабатываться, они должны опять попасть в кеш процессора.
Я говорю о копировании больших объёмов, в кеш они ни как не войдут.
Если же данные только что посчитаны — их можно сразу сохранить в нужном месте.
People who are more than casually interested in computers should have at least some idea of what the underlying hardware is like. Otherwise the programs they write will be pretty weird (c) D.Knuth
Здравствуйте, VladD2, Вы писали:
>>> первод SIP — "софтовая иззоляция процессов" говорит сам за себя. C>>Какая разница как оно называется? Оно может работать по определению C>>только с safe-кодом.
VD>Вот именно, по определению. Точнее по спецификации. И ни с каким другим. VD>Так что не нужно даже обсуждать что будет в случае если повсеместно начнет использоваться unsafe.
Сейчас на белом коне сюда вьедет Сергей Губанов и скажет, что очередную идею сьлямзили у Оберона.
Здравствуйте, Andrei N.Sobchuck, Вы писали:
VD>>Вот именно, по определению. Точнее по спецификации. И ни с каким другим. VD>>Так что не нужно даже обсуждать что будет в случае если повсеместно начнет использоваться unsafe.
ANS>Сейчас на белом коне сюда вьедет Сергей Губанов и скажет, что очередную идею сьлямзили у Оберона.
Идея типобезопасности скорее слямзена у Паскаля. А еще точнее у какого-нибудь Лиспа, так как он появился лет эдак на 20 раньше.
А вообще, это очень старый флэйм. Реальных прорывов и революций в компьютерной индустрии очень не много. И в большинстве случаев они проходят незаметно. Только спустя годы народ анализируя сделанное понимает, что имел место прорыв. Ну, а польза от прорывов появляется только когда множество иноваций собирается воедино в неком продукте полезном для общества. Так что Sun, IBM и MS делают очень полезную работу. Они берут те самые старые идеи и воплощают их на практике. Это тоже требует немалых умстевнных усилий и финансовых затрат. За что им огромное спасибо.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, gear nuke, Вы писали:
GN>Здравствуйте, VladD2,
GN>>>Остаётся открытым вопрос — насколько практически надёжную защиту сможет дать Singularity?
VD>>Думаю на 99%.
GN>Всё понятно. Если драйвер не работает в 1 сдучае из 1000000, значит он не работает совсем.
Процент в данном случае означет не процент отказов, а процент случаев когда Сингулярити позволит создать надежную систему. В том смысле, что всегда найдутся требования котоыре будут не выполнипы в рамках выбранного подхода.
Что до надежности драйверов, то тут ОС в общем-то не причем. Драйвер — это программа. Если в ней ошибка, то проблемы неизбежны. Другое дело что Сингулярити может сделать в этом случае. А сможет она не мало. 1. Изалировать остальной код ОС и пользовательские процессы от сбойного драйвера. 2. Позволить перезапустить драйвер и востановить состояние (оно же не разделяется с драйвером, так что это будет не сложно). 3. Предоставить средства проверки корректности окружения, что позволит избежать проблем вроде несовместимости версий и т.п.
Собственно все это точно больеш чем у Виндовс и Линукс. Одним словом микроядерная ОС с малым оверхэдом.
GN>К безопасности требования ещё строже, с такими цифрами это значит: "заходите добры люди, берите что хотите"
Я не знаю о чем ты тут рассуждашь. Современные ОС имеют куда более плачевные показатели и по безопасности и по надежности.
GN>Я в общем-то тоже не знаю. Но жаба у меня на всякий случай выключена в браузерах, как советую те, кто знает.
Это перестраховка.
GN>Боюсь у меня на это много времени уйдёт,
Думаю, это вообще не выйдет.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > C>Это еще кучу лет назад было в MS-DOS в программах на Бейсике > В ДОС-е Бэйсик не был типобезопасным языком
Ладно-ладно, заменим на Паскаль.
> не поддерживал идею процессов, изолляции, потоков, надежности и т.п. Так что о чем речь не > очень ясно.
Вообще-то Erlang уже в начале 90-х поддерживал все это. Там еще вдобавок
была поддержка hotswap для работающего кода (с автоматическим
распространением обновлений по графу зависимостей).
Было бы намного интереснее, если бы МС с его ресурсами попробовал
исследовать как можно изменить аппаратную защиту так, чтобы
managed-языки более удачно в нее вписывались. А тот факт, что без
аппаратной защиты все работает намного быстрее — это давно известно.
Здравствуйте, Cyberax, Вы писали:
C>Вообще-то Erlang уже в начале 90-х поддерживал все это. Там еще вдобавок C>была поддержка hotswap для работающего кода (с автоматическим C>распространением обновлений по графу зависимостей).
Насколько моне извесно, Erlang работает поверх некоторой ОС. Опять же если тут проводить аналогии, то это будет скорее первые Лисп-машины и Оберон-ОС.
C>Было бы намного интереснее, если бы МС с его ресурсами попробовал C>исследовать как можно изменить аппаратную защиту так, чтобы C>managed-языки более удачно в нее вписывались. А тот факт, что без C>аппаратной защиты все работает намного быстрее — это давно известно.
Тебе не кажется странным предлагать софтовой компании заниматься исследованиями в процессоростроении? Они занимаются исследованиями в области ОС. И как я понимаю, ОС не затачивается на отдельную архитектуру.
Собственно то что они делают очень даже разумно и востребовано. К сожалению идею микроядра и безопсности засунули в задний проход. И слова о том, что железо видите ли тормозит является плохой отмазкой.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VladD2 wrote: > C>Вообще-то Erlang уже в начале 90-х поддерживал все это. Там еще вдобавок > C>была поддержка hotswap для работающего кода (с автоматическим > C>распространением обновлений по графу зависимостей). > Насколько моне извесно, Erlang работает поверх некоторой ОС.
Не обязательно — есть и варианты, работающие на голом железе. Особой
разницы нет — от ОС нужны только достаточно базовые сервисы.
> C>Было бы намного интереснее, если бы МС с его ресурсами попробовал > C>исследовать как можно изменить аппаратную защиту так, чтобы > C>managed-языки более удачно в нее вписывались. А тот факт, что без > C>аппаратной защиты все работает намного быстрее — это давно известно. > Тебе не кажется странным предлагать софтовой компании заниматься > исследованиями в процессоростроении?
Эта "софтовая компания" спроектировала уже два поколения XBox'ов.
> Собственно то что они делают очень даже разумно и востребовано. К > сожалению идею микроядра и безопсности засунули в задний проход. И слова > о том, что железо видите ли тормозит является плохой отмазкой.
Согласен. Мне пока Singularity напоминает изобретение очередного
велосипеда под названием "Managed OS", если что интересное и получится,
то только в следующей итерации проекта.
Здравствуйте, Cyberax, Вы писали:
C>Не обязательно — есть и варианты, работающие на голом железе.
Можно ссылкочки?
C> Особой C>разницы нет — от ОС нужны только достаточно базовые сервисы.
А, ну, да. Ввод/вывод, HAL и т.п.
C>Эта "софтовая компания" спроектировала уже два поколения XBox'ов.
Она их не делат. Процессоры сам знашь какие. Архитектура соотвествующая.
>> Собственно то что они делают очень даже разумно и востребовано. К >> сожалению идею микроядра и безопсности засунули в задний проход. И слова >> о том, что железо видите ли тормозит является плохой отмазкой. C>Согласен. Мне пока Singularity напоминает изобретение очередного C>велосипеда под названием "Managed OS", если что интересное и получится, C>то только в следующей итерации проекта.
С чем согласен? Интересного там уже море. Единственное что не получится в этой итерации — коммерческой ОС.
C>-- C>С уважением, C> Alex Besogonov (alexy@izh.com)
Да, большая просьба... убири ты эту подпись в свой профайл. А то не ясно зачем всю БД забивать совершенно одинаковыми строками.
... << RSDN@Home 1.2.0 alpha rev. 620>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>А если реализовать кучу следующим образом ?
PD>Каждый объект, размещаемый в куче, имеет свой размер s. Разделим их по размеру на 3 категории — малые (s <= n), средние ( n < s < =N) и большие ( s > N). Численные значения надо определить экспериментально.
PD>Для малых объектов создадим массивы
PD>массив0 — для объектов с размером от 1 до 8 байт PD>массив1 — от 9 до 16 PD>массив2 от 17 до 24
PD>и т.д.
Идея здравая. Что-то подобное, только с некоторыми различиями, я и сам "придумывал" недавно. А потом случайно наткнулся в MSDN на Low-fragmentation Heap. Посмотрите функцию HeapSetInformation, там найдете информацию о том, как Microsoft уже позаботилась о нас. Жаль, что о деталях реализации придется только догадываться и работает только начиная с XP.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
1.1.4 stable rev. 510
ну я на всякий случай расставил точки над 'Ё'.
Перекуём баги на фичи!
) Основная потребность в realloc присутвует у разработчиков библиотек, когда у тебя нет ни малейшего понятия ни о том, сколько элементов будет располагаться в твоей структуре данных, ни о том, каков размер каждого элемента. Плюс работа со строками.
