Здравствуйте, Ikemefula, Вы писали:

I>Это как то решает проблемы с фрагментацией ?

Да.
Вторая тонкость -- грануляция. Так что куски легко переиспользуются.

Здравствуйте, Erop, Вы писали:

E>Да.
E>Вторая тонкость -- грануляция. Так что куски легко переиспользуются.
Не надоело еще? NET — это уровень сильно выше, чтобы разбираться в том, как работают менеджеры памяти, это же не С и не С++, где без оного знания никуда. Ну вычитал он где-то немного странную сказку и теперь всем ее травит.

Здравствуйте, Erop, Вы писали:

I>>Это как то решает проблемы с фрагментацией ?

E>Да.

Покажи каким образом. Представь себе такое — есть свободной памяти ажно 2гб

Выюзаем блоками по 60кб всю память, как ты утверждал — все это пойдет чуть не напрямую через VirtualAlloc
Освобождаем каждый второй блок — свободной памяти стало ажно гигабайт.
Теперь делаем тоже самое, но размер блока делаем 100кб — раз ты утверждаешь, что проблемы фрагментации решаются через VirtualAlloc, то стало быть нет никаких проблем.

Вопрос — как имеено тебе поможет VirtualAlloc в этом сценарии ?

Здравствуйте, Ikemefula, Вы писали:

I>Вопрос — как имеено тебе поможет VirtualAlloc в этом сценарии ?
Почитай про то как работают менеджеры памяти, начни хотя бы с того же Рихтера или википедии.

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, gandjustas, Вы писали:

G>>Даже если начальный размер 4, то это не сильно влияют на все остальное. В этом и суть нелинейного увеличения, при увеличении N затраты на добавление в конец стремятся к о(1) пока не упремся в память.

I>Не в память, а в адресное пространтсво. И с этого момента все интересное только начинается.
Уже года 3 как только в x64 работаю, там в первую очередь в память упираешься. Обо когда оперативка забивается GC начинает работать активнее, что еще сильнее бьет по производительности.

I>>>Фактически получается так, что

I>>>1 В реальном приложении память уже юзается кем то и АП всегда хоть немного но фрагментировано, включая LOH
G>>Да, но все равно будет максимум 1 Gen0 и 1 Gen2.
I>Профайлер с тобой категорически не согласен. Хотя для приложений на коленке возможно так и будет.
Даже если будет 2-3 GC по другим причинам — это небольшой impact. Если будет сильно больше сборок мусора, тогда надо причину в другом месте искать.

G>>Это все нерелевантно, так как обсуждение идет разворота списка.
I>Ты не волнуйся, я хорошо помню, как реверс списка ты реализовал в виде реверса строки через стрингбилдер.
Я реверс списка еще тут писал: http://rsdn.ru/forum/job/4633021.1

Автор: gandjustas
Дата: 24.02.12

А разворот строки был совсем из дугой ветки.


G>>Я же писал про бесполезность "разворота списка" как задачи, проверяющей знание чего-либо.
I>Она не проверяет знание, она проверяет умение решить нетиповую задачу, воспользовавшись базовыми вещами — циклами, ссылками и головой.
Я как-то всегда через fold и рекурсию выводил. Задача кстати вполне типовая для ФП. А для императивных языков она бесполезная, ибо никто даже близко ничего похожего не пишет.

Здравствуйте, Nuzhny, Вы писали:

N>Здравствуйте, gandjustas, Вы писали:

N>>>С++ лагерь говорит, что vector<T> не является списком и показанным выше способом с ним никто в здравом уме не орудует.

G>>Что значит не является списком? С точки зрения Д. Кнута таки является. а и его устройство аналогично .NETовскому List<T>.

N>Во-первых, std::vector<T>- это умная обёртка над буфером. Похожим на список его делают разве что итераторы, но итераторы можно прикрутить и к обычному куску памяти.
N>Во-вторых, от std::vector<T> никто не ждёт поведения типичного для работы со списками: быстрая вставка и удаление элементов, то же реверсирование и другие подобные задачи. Он не для этого сделан и, повторюсь, не используется для вышеперечисленных задач. Всем плевать, какое определение давал спискам Кнут и как устроен дотнетовский List<T> — std::vector<T> просто не предназначен, он плох для выполнения тех задач, под которые не заточен. Поэтому его и не назвали списком, а дали имя вектор. Подумай об этом.
N>Ну и в-третьих, если кто-нибудь захочет всё таки использовать std::vector<T> для несвойственных ему задач, то напишет (или найдёт в сети) подходящий для этого аллокатор, который будет вести себя оптимальным образом на конкретной задаче. И при этом будет работать лучше, чем любой универсальный GC.

N>Вот как поступает С++ лагерь.

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

Здравствуйте, Codechanger, Вы писали:

C>Сейчас вроде бы имеет смысл в подобных случаях применять Bcl.Immutable. Там хоть с выделением памяти нет такого беспредела,ну и перфоманс в целом поровнее и побыстрее в среднем.

А есть практический опыт применения Immutable Collections? А то я про них читал, немного тыкал, но в реальных нагруженных проектах пока не довелось использовать.

Кто их использовал, поделитесь ощущениями.

Здравствуйте, Erop, Вы писали:

НС>>Да не особо большие. Списочек в десяток миллионов ссылок при активном использовании уже такое вполне способен обеспечить.
E>40 метров буфера уже хватает? Не особо хорошо работает тогда в дотнете менеджмнт памяти

Не в дотнете все еще хуже, имею, так сказать, опыт.

E>Если мы пока что про винду, то msvc'шная куча, например, большие аллокации делает сразу через VirtualAlloc, и потом их же и освобождает, так что отдают обратно системе, при освобождении...

Фрагментация, это не когда адресное пространство кончилось, это когда оно фрагментировано.

Здравствуйте, LaptevVV, Вы писали:

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

Здравствуйте, Vzhyk, Вы писали:

V>Не надоело еще? NET — это уровень сильно выше, чтобы разбираться в том, как работают менеджеры памяти, это же не С и не С++, где без оного знания никуда. Ну вычитал он где-то немного странную сказку и теперь всем ее травит.

С одной стороны, я так понял, что у него часто бывают с этим проблемы. Может почитает чего, посмотрит, углубится в тему чуть дальше и всё такое...
С другой стороны, он тут не единственный читатель жеж...

Здравствуйте, Ikemefula, Вы писали:

I>Вопрос — как имеено тебе поможет VirtualAlloc в этом сценарии ?

В этом никак. Но этот сценарий не имеет ничего общего с политикой аллокаций листа, ровно как и вообще с реальностью. Да, реальные кучи на реальных сценариях фрагментируются до некоторой степени, но современные кучи обычно фрагментируются до степени фрагментации меньше двух... И ты, на минуточку, в своём фантастическом сценарии, тем не менее съел половину памяти и не отдал

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Не в дотнете все еще хуже, имею, так сказать, опыт.
Ну, охотно верю. Там же с аллокаторами баловаться не получится? Так что вся надежда, что GC не слажает и не фрагментируется...

НС>Фрагментация, это не когда адресное пространство кончилось, это когда оно фрагментировано.


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

Здравствуйте, Erop, Вы писали:

E>Ну, охотно верю. Там же с аллокаторами баловаться не получится? Так что вся надежда, что GC не слажает и не фрагментируется...

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

E>Я понимаю, но если ваш список гранулирует размеры своих буферов, то он не особо будет фрагментировать свой аллокатор.

Не факт. Гранулы в 40кб при списках в десятки мегабайт — что мертвому припарка.

E> Все списки по очереди будут юзать одни и те же блоки

Это если все блоки идентичного размера.

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Не факт. Гранулы в 40кб при списках в десятки мегабайт — что мертвому припарка.

Обычно не так гранулируют, а на логарифмическую шкалу.


E>> Все списки по очереди будут юзать одни и те же блоки

НС>Это если все блоки идентичного размера.

Ну мы про списки ссылок говорим же?...

Здравствуйте, Erop, Вы писали:

I>>Вопрос — как имеено тебе поможет VirtualAlloc в этом сценарии ?

E>В этом никак.

Правильно, и в любом другом тоже. Помогает не функция VirtualAlloc, а дефрагментация или руками писаные аллокаторы, ре-аллокаторы.

>Но этот сценарий не имеет ничего общего с политикой аллокаций листа, ровно как и вообще с реальностью.

Это потому, что ты не понимаешь разницу между адресным пространством и памятью.

>Да, реальные кучи на реальных сценариях фрагментируются до некоторой степени, но современные кучи обычно фрагментируются до степени фрагментации меньше двух...

Ну, допустим. Другой сценарий — выделяем 900мб, потом 200, потом 900. Итого — занято 2гб. Удаляем большие блоки по 900, свободной — 1800.
Выделяем 1гиг.

Итого — на этот раз степень фрагментации копеечная. Как здесь поможет VirtualAlloc ?




>И ты, на минуточку, в своём фантастическом сценарии, тем не менее съел половину памяти и не отдал

Здравствуйте, gandjustas, Вы писали:

I>>Не в память, а в адресное пространтсво. И с этого момента все интересное только начинается.
G>Уже года 3 как только в x64 работаю, там в первую очередь в память упираешься. Обо когда оперативка забивается GC начинает работать активнее, что еще сильнее бьет по производительности.

Вроде было ясно сказано — х86. В 64 бита фрагментация АП никого не интересует, спасибо, Капитан Очевидность.

>>>>1 В реальном приложении память уже юзается кем то и АП всегда хоть немного но фрагментировано, включая LOH
G>>>Да, но все равно будет максимум 1 Gen0 и 1 Gen2.
I>>Профайлер с тобой категорически не согласен. Хотя для приложений на коленке возможно так и будет.
G>Даже если будет 2-3 GC по другим причинам — это небольшой impact. Если будет сильно больше сборок мусора, тогда надо причину в другом месте искать.

Ты снова про свои 64 бита. Это неинтересно.

G>>>Это все нерелевантно, так как обсуждение идет разворота списка.
I>>Ты не волнуйся, я хорошо помню, как реверс списка ты реализовал в виде реверса строки через стрингбилдер.
G>Я реверс списка еще тут писал: http://rsdn.ru/forum/job/4633021.1

Автор: gandjustas
Дата: 24.02.12

G>А разворот строки был совсем из дугой ветки.

Поздно уже отмазываться, это, считай, уже отягчающее обстоятельство.

I>>Она не проверяет знание, она проверяет умение решить нетиповую задачу, воспользовавшись базовыми вещами — циклами, ссылками и головой.
G>Я как-то всегда через fold и рекурсию выводил. Задача кстати вполне типовая для ФП. А для императивных языков она бесполезная, ибо никто даже близко ничего похожего не пишет.

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

Здравствуйте, Vzhyk, Вы писали:

I>>Вопрос — как имеено тебе поможет VirtualAlloc в этом сценарии ?
V>Почитай про то как работают менеджеры памяти, начни хотя бы с того же Рихтера или википедии.

Рихтер прямо говорит — никак не поможет.

Вот тебе стоит Рихтера почитать, глядишь, узнаешь что такое адресное пространство.

Здравствуйте, Ikemefula, Вы писали:

I>Правильно, и в любом другом тоже. Помогает не функция VirtualAlloc, а дефрагментация или руками писаные аллокаторы, ре-аллокаторы.

Нет, помогает то, что в конце-концов все аллокации где-то внутри сводятся к распределению выделенной по VA порции памяти. Таку порцию потом трудно отдать. Вот и весят эти сегменты алолокаторов, повышают фрагментацию АП. Если же большие аллокации делать сразу на VA, то когда ты эти блоки освободишь, АП дефрагментируется...

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

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

I>Это потому, что ты не понимаешь разницу между адресным пространством и памятью.
Это ты себе придумал. Я даже понимаю разницу между физическим и логичемким АП, а не только между памятью и АП

I>Ну, допустим. Другой сценарий — выделяем 900мб, потом 200, потом 900. Итого — занято 2гб. Удаляем большие блоки по 900, свободной — 1800.
I>Выделяем 1гиг.

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

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

В нагруженной ситуации лучше не рассчитывать получить больше сотни метров, в ненагруженной и под виндой можно поднять аппетиты метров до 300-400, дальше уже ненадёжно очень будет.

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

I>Итого — на этот раз степень фрагментации копеечная. Как здесь поможет VirtualAlloc ?




>>И ты, на минуточку, в своём фантастическом сценарии, тем не менее съел половину памяти и не отдал

Здравствуйте, Ikemefula, Вы писали:

Коллеги, объясните мне, что здесь происходит ? Какие реаллокации ? Линейный однонаправленный список в С/C++ на базе ссылочной реализации переворачивается без какого бы то ни было выделения памяти.

Или я что-то не понял ?

Примечание : нехватка памяти при добавлении не обрабатывается.

struct ListElement
{
    int data;
    ListElement* next;
};

class List {
private :
    ListElement* begin;
public:
    List() { begin = NULL;}
    void AddToBegin(int x)
    {
        ListElement * temp = new ListElement;
        temp->data = x;
        temp->next = begin;
        begin = temp;
    }

    void Reverse()
    {
        ListElement * newBegin = NULL;
        ListElement * cur = begin;
        while(cur)
        {
            ListElement * next = cur->next;
            cur->next = newBegin;
            newBegin = cur;
            cur = next;
        }
        begin = newBegin;
    }

    void Print()
    {
        for(ListElement * cur = begin; cur; cur = cur->next)
            printf("%d\n",cur->data);
    }
};

int _tmain(int argc, _TCHAR* argv[])
{
    List l;
    l.AddToBegin(4);
    l.AddToBegin(3);
    l.AddToBegin(2);
    l.AddToBegin(1);
    l.Print();
    l.Reverse();
    l.Print();
    return 0;
}

Здравствуйте, Erop, Вы писали:

E>Нет, помогает то, что в конце-концов все аллокации где-то внутри сводятся к распределению выделенной по VA порции памяти.

То есть, вся твоя мега идея "VirtualAlloc" заключается в том, что есть два хипа — для малых и больших объектов. Один управляется либой, второй — виндой.

Вопрос — при чем здесь VirtualAlloc ? Хип для больших объектов можно сделать самому и это всего лишь скажется на перформансе.

То есть, VirtualAlloc помогает с перформансом, а с фрагментацией помогает разделение хипов на два штуки минимум — для малых и больших объектов.


> Таку порцию потом трудно отдать. Вот и весят эти сегменты алолокаторов, повышают фрагментацию АП. Если же
большие аллокации делать сразу на VA, то когда ты эти блоки освободишь, АП дефрагментируется...

Я показал два сценария, ни в одном из них ты не показал где именно помогает VirtualAlloc.

E>Но это одна сторона медали, вторая -- правильные политики аллокации, которые обеспечивают переиспользование блоков и снижение фрагментации. Конкретно для плюсовго вектора/вашего листа — такой политикой является грануляция. Если выделять куски памяти не случайного размера, а всегда выбирать какой-то и жёстко заданой линейки размеров гранул, то такие блоки будут чаще переиспользоваться и реже резаться на ошмётки...

Правильно, и VirtualAlloc ничем, кроме перформанса, не помогает.

I>>Это потому, что ты не понимаешь разницу между адресным пространством и памятью.
E>Это ты себе придумал. Я даже понимаю разницу между физическим и логичемким АП, а не только между памятью и АП

Ты так и не смог показать, где и чем тебе помогает VirtualAlloc

I>>Ну, допустим. Другой сценарий — выделяем 900мб, потом 200, потом 900. Итого — занято 2гб. Удаляем большие блоки по 900, свободной — 1800.
I>>Выделяем 1гиг.

E>Ты опять хочешь занять от половины свободной памяти...

Я показал тебе самый минимальный случай фрагментации — всего два куска. Меньше просто не бывает. Если VirtualAlloc не может разрулить этот самый простой случай, значит, что он тебе ничем помочь в принципе не может.

Объясняю еще раз — фрагментации, меньше чем 2 куска, не бывает. Где помощь VirtualAlloc ? Её нет и быть не может.

E>В целом такие большие куски априори недоступны. Даже если вообще ничего не аллокировать, туда что-то может загрузиться, какая-нибудь dll-ка или хук, например, так что рассчитывать, что ты получишь половину АП одним куском наивно...

Ты помоему так и не понял, что такое адресное пространство.