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

I>>То есть, фокус в том, что эта стратегия выделения очень неудобная для GC.
I>>Итого — суммарно выделится памяти примерно (с*(1-q^n))/(1-q), где q = 2, с примерно 11 или близко к этому.
I>>Столько же памяти и освободится, но из за фрагментации АП это как мертвому припарки — на больших списках это будет фейл, хотя свободной памяти будет хоть в 10 раз больше.

G>Вроде все правильно написал, но вот с деталями накосячил. А дьявол, как известно, именно в них.

ля-ля-ля

G>Начальный размер List<T> — 16 или 32 (надо уточнить, давно не смотрел сборки).

4, просто 11 круглее И вообще — 11 это в троичной системе будет 4. Короче — не знаю, откуда взял это значение.

G>Далее LOH — он вроде как кусками по 16мб выделяется. И собирается только при Gen2. Соответственно если выделяется новый кусок, то запускается Gen2 GC. Он идет в фоне и в общем случае не влияет на скорость работы.
G>Чтобы список разросся до 16мб надо еще 10-11 увеличений размеров буфера.
G>То есть 1,000,000 (миллион) элементов и максимум один Gen2 GC.

G>Фактически одиночный разворот списка до миллиона элементов таким некрасивым образом не даст значительной нагрузки на GC.

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

1 В реальном приложении память уже юзается кем то и АП всегда хоть немного но фрагментировано, включая LOH
2 паттерн ниже встречается слишком часто, при чем список часто состоит в т.ч. из структур и размеры >миллиона

var list = new List<Item>();
while (condition())
{
  list.Add(current());
}

3 в дженерик лист кладутся не только ссылки, а еще и структуры, я откопал похожий паттерн при добавлении 10млн гуидов
4 рассчитывать на память в LOH или забывать про неё крайне глупо

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

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

G>>На самом деле они очень хорошо оттюнингованы под GC .NET и могут хранить миллионы элементов.

НС>Хранить то могут, но в реальных приложениях, если нам надо работать под 32 битами (или даже в чужом 32-битном процессе) и миллионными списками, приходится писать специальный список, который внутри хранит данные чанками меньше 85К размером.
В реальных приложениях структура зависит от использования.

G>>Но это не значит что вставка в цикле в список без выделения размера — хорошая идея.
НС>А если размер заранее неизвестен?
Значит оценка есть какая-то. Не зная статистических характеристик бесполезно пытаться что-то оптимизировать в реальном приложении.

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

LVV>Залезте в STL и посмотрите.
LVV>Внутренний массив есть у вектора, и список массивов есть у дека.
LVV>У списков — нет массива. Там память выделяется индивидуально.
Нечего там смотреть, более того смотрел и не раз, учить меня не надо. То что вы называете вектором — в .net BCL называется списком, иногда это же люди называют динамическим массивом. Связные списки и всякого рода деревья как ни странно в .net тоже есть, а чего нет — так же само можно реализовать. Зачем путать ADT с реальными имплементациями структур, которые везде одинаковые.

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


G>>Начальный размер List<T> — 16 или 32 (надо уточнить, давно не смотрел сборки).

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

G>>Далее LOH — он вроде как кусками по 16мб выделяется. И собирается только при Gen2. Соответственно если выделяется новый кусок, то запускается Gen2 GC. Он идет в фоне и в общем случае не влияет на скорость работы.
G>>Чтобы список разросся до 16мб надо еще 10-11 увеличений размеров буфера.
G>>То есть 1,000,000 (миллион) элементов и максимум один Gen2 GC.

G>>Фактически одиночный разворот списка до миллиона элементов таким некрасивым образом не даст значительной нагрузки на GC.

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

I>1 В реальном приложении память уже юзается кем то и АП всегда хоть немного но фрагментировано, включая LOH
Да, но все равно будет максимум 1 Gen0 и 1 Gen2.

I>2 паттерн ниже встречается слишком часто, при чем список часто состоит в т.ч. из структур и размеры >миллиона
I>

I>var list = new List<Item>();
I>while (condition())
I>{
I>  list.Add(current());
I>}
I>

I>3 в дженерик лист кладутся не только ссылки, а еще и структуры, я откопал похожий паттерн при добавлении 10млн гуидов
I>4 рассчитывать на память в LOH или забывать про неё крайне глупо
Это все нерелевантно, так как обсуждение идет разворота списка.

Я же писал про бесполезность "разворота списка" как задачи, проверяющей знание чего-либо.

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

I>>Никак. В С++ при подобной технике увеличения ровно те же проблемы, только быстрее.
E>ну, то есть ты хочешь сказать, что std::vector в С++ прогаммах не испольуется, так как если используется, то жрёт память гигами?

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

I>>Не лист, а добавление большого количества элементов последовательно без указания стартового размера, как это было сделано в примере.

E>Э-э-э-э-э, разве это не основной сценарий?..

Частый, но не основной. Основной все таки когда количетсво элементов пару тысяч, ну десятков тысяч.

I>>Ну ты доказывал, что решение отличное, а нагрузку O(2^N) просчитать не смог. Ты математику забыл что ли ?

E>Про нагрузку O(2^N) ты ошибаешься. Всего будет примерно log2 (N / 11) аллокаций, общим объёмом примерно в 2N максимум...

В данном сценарии основную нагрузку дает суммарный объем аллокаций — O(2^N), если списки достаточно длинные, и это не синтетическое приложение, то OOM гарантирован даже если свободной памяти с 10-кратным запасом.

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

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

I>>Массивы, буфферы всякие — проблема одна и та же, если просто выделять да копировать. Проблема известна со времен Си, и везде говорилось, что надо юзать realloc, но стандартный хип не может гарантировать, что realloc увеличит размер, а не выделит на новом месте.

I>>Судя по тому, что мне доводилось видеть, в С++ старую технику realloc давно забыли
V>И этот человек собеседует плюсовиков... ЧТД!

Во первых — лет 8 как не собеседую плюсовиков.
Во вторых — код говорит сам за себя.

Что бы сократить, угадаю твой следующий аргумент

V "Кого набрал, такой и код"

Ответ тебе напомнить или ты сам вспомнишь ?

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

I>Судя по тому, что мне доводилось видеть, в С++ старую технику realloc давно забыли
realloc не гарантирует сохранения адреса буфера, к сожалению, поэтому для сложных данных не годится,..

Зато есть VirtualAlloc с возможностью резервировать и комитить, ну в *правильных системах* в смысле
А вообще-то затраты на переаллокации вектора ты сильно преувеличиваешь. Конечно лучше их избегать, но они всё равно малы, по сравнеию с работой с самими данными. Просто аллокации/освобождения, если не из пула в С++ дорогие.

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

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

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

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

I>>1 В реальном приложении память уже юзается кем то и АП всегда хоть немного но фрагментировано, включая LOH
G>Да, но все равно будет максимум 1 Gen0 и 1 Gen2.

Профайлер с тобой категорически не согласен. Хотя для приложений на коленке возможно так и будет.

I>>2 паттерн ниже встречается слишком часто, при чем список часто состоит в т.ч. из структур и размеры >миллиона
I>>

I>>var list = new List<Item>();
I>>while (condition())
I>>{
I>>  list.Add(current());
I>>}
I>>

I>>3 в дженерик лист кладутся не только ссылки, а еще и структуры, я откопал похожий паттерн при добавлении 10млн гуидов
I>>4 рассчитывать на память в LOH или забывать про неё крайне глупо
G>Это все нерелевантно, так как обсуждение идет разворота списка.

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

G>Я же писал про бесполезность "разворота списка" как задачи, проверяющей знание чего-либо.

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

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

I>>Судя по тому, что мне доводилось видеть, в С++ старую технику realloc давно забыли
E>realloc не гарантирует сохранения адреса буфера, к сожалению, поэтому для сложных данных не годится,..

Спасибо, капитан, ты повторил ровно мои слова.

E>А вообще-то затраты на переаллокации вектора ты сильно преувеличиваешь. Конечно лучше их избегать, но они всё равно малы, по сравнеию с работой с самими данными. Просто аллокации/освобождения, если не из пула в С++ дорогие.

В который раз говорю — не затраты на переаллокации, а скорость потребления адресного пространства.

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

I>В данном сценарии основную нагрузку дает суммарный объем аллокаций — O(2^N),

Не мог бы ты пояснить, откуда такая оценка?
Я вернопонимаю, то уже для списка в 400 элемнтов, например, сумарный объём аллокаций привысит 10^100, то есть гугол?..

Реальность несколько отличается от твоего взгляда на вещи. Самая большая аллокация будет ближайшая сверху к N степень двойки, например для 400, это будет 512.
Суммарный объем всех предыдущих будет меньше 512, то есть общий объём для списка из 400 элементов не превысит 1023, а на самом деле и того меньше, то есть потратится где-то до 4К памяти, половина из которой ещё и остантся удобных размеров для переиспользования ДРУГИМИ списками...

Что-то я вообще никакой трагедии в этом не вижу

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

I>В который раз говорю — не затраты на переаллокации, а скорость потребления адресного пространства.


Оценки какие-то будут?..

ну, например, как ты думаешь, если вот тупо взять и написать на плюсах std::vector<char> и начать в него добавлять по одному, миллион символов добавить удостся?..

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

I>>В данном сценарии основную нагрузку дает суммарный объем аллокаций — O(2^N),

E>Не мог бы ты пояснить, откуда такая оценка?

Я все уже показал.

E>Я вернопонимаю, то уже для списка в 400 элемнтов, например, сумарный объём аллокаций привысит 10^100, то есть гугол?..

n это было количетсво аллокаций, а не размер списка.

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

I>>В который раз говорю — не затраты на переаллокации, а скорость потребления адресного пространства.

E>Оценки какие-то будут?..

2 в степени (количество аллокаций)

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

I>n это было количетсво аллокаций, а не размер списка.

Ну так оно же логарифмически растёт с размером? В результате получаем, что оверхед примерно линейный от размера списка. Да ещё и с коэффициентом от 2 до 3 где-то. В чём тогда трагедия?

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

I>2 в степени (количество аллокаций)

Ну вот хотим мы, например, мегабайтный список замутить. Типа 256 * 1024 ссылки положить в него.

На какой-нибудь простой объектик, ну, например, на короткие случайные строчки.

не мог бы ты оценить, если средний размер случайной строки, скажем 16, то сколько памяти уйдёт на строки, а ксколько на аллокации самого списка?..

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

E>не мог бы ты оценить, если средний размер случайной строки, скажем 16, то сколько памяти уйдёт на строки, а ксколько на аллокации самого списка?..

А чего тут оценять? Взял профайлер да померял

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

НС>А чего тут оценять? Взял профайлер да померял

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

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

НС>>А чего тут оценять? Взял профайлер да померял
E>Ну я та подозреваю, что на список уйдёт меньше, чем на строчки...

Вот ты тоже невнимательно читаешь. Ikemefula говорит не про расход памяти как таковой, а про фрагментацию VA-спейса в 32-хбитном процессе. CLR компактифицирует только поколения, LOH у него управляется как в обычном менеджере памяти. Штатный менеджер памяти плюсовых рантаймов обычно вообще компактификацией не занимается никогда, так что эта проблема не исключительная фича CLR. Таким образом, рано или поздно при очередной переаллокации списка тебе просто не удастся найти непрерывный кусок спейса нужного размера, а на стандартных 2 гб по нынешним временам это не такая уж и уникальная ситуация. Если же мы, к примеру, плагин к студии пишем, то на более менее крупных солюшенах 2гб превращаются в 400-600 мег.
Но это, конечно, очень далеко за пределами собеседований. Искать человека, который с этим уже сталкивался — задача на годы .

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

НС>Вот ты тоже невнимательно читаешь. Ikemefula говорит не про расход памяти как таковой, а про фрагментацию VA-спейса в 32-хбитном процессе.

Я это понимаю, и даже сталкивался, только это уже очень большие списки нужны. Таких и в память влезет несколько десятков только...

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

I>Вообще, не ясно, почему List'T до сих пор в таком вот виде, все что надо, уменьшить дефолтный grow factor, скажем 1.5, будет медленнее, зато окна будут заполняться сами собой в большинстве сценариев. Или хотя бы дать возможность юзать свой. Тоже самое нужно во всех коллекциях и особенно в инвокейшнлистах, а то забавляет когда студенты крик подымают "я добавляю эвентхандлер, памяти сто мегов а летит Out Of Memory"
Такой — скорее всего потому, что достаточно хорош для большинства вещей/людей. Я честно говоря от List'T никогда не страдал, хотя и в зауженных местах старался ему задать капасити сразу, если оно вдобавок доподлинно заранее известно.
Но в принципе — на перерасход памяти натыкался, что с плюсами, что с нетом, хотя это всегда было связано с ошибками/недосмотром в самом коде.
Самое клёвое — это когда в одном процессе борятся несколько независимых сборщиков мусора. Тогда происходит всё то о чём ты написал, но только в квадрате.