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

E>Ну то решение, которое не нравится НС, если его сделать более или менее по уму, оно всего в два раза медленнее + одна-две аллокации под буфер массива, что на GC полная фигня, как бы...

Алё ! Ты математик или погулять вышел ?

НС>var list = new List<Item>();
НС>while (current != null)
НС>{
НС>  list.Add(current);
НС>  current = current.Next;
НС>}

Объясняю популярно
выделение памяти здесь НЕ линейное, хотя это не очевидно на первый взгляд.

Вот как выделяется память

T[] array = new T[value]; // здесь выделили
                if (this._size > 0)
                {
                    Array.Copy(this._items, 0, array, 0, this._size);
                }
                this._items = array; // а здесь появится основание для выделения

А вот как вычисляется новый размер

int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);

Здесь будет геометрическая прогрессия с первым членом навроде 11 и знаменателем 2.
Свойство вот этой конкретной прогрессии такое, что каждый следующий блок больше суммы всех предыдущих.

пример — 11, 22, 44, 88
Будет так, надо выделить 22, 11 освободить. остается дыра в 11. выделяем 44, остается дыра в 33, выделяем 88, остается дыра 77 и тд и тд
Память то будет освобождаться, но GC будет жрать все новую и новую память, ибо старый блок дохнет после того, как будет инициализирован новый.
Более того, память будет фрагменироваться не только массивами, но и хипами

Теоретически, GC может и будет двигать неудобные блоки. Но факт в том, что это работает до ~85кб, дальше GC (не в курсе про последние версии), ничего двигать не будет и память будет выделяться-освобождаться как попало.
На самом деле в GC есть оптимизации из за таких вот случаев, но я бы не сказал, что они сработают всегда. Если приложение нормально разогрето, в нем не будет нужного количества свободных блоков должного размера.
То есть, GC будет стараться двигать мелкие объекты(<85 кб), даже не двигать, а гонять их по адресному пространству.

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

Вообще с добавлением большого количества элементов в ArrayList, List'T или Dictionary нужно быть осторожным, если не знаешь количество элементов для добавления.
Более того, очень осторожно нужно быть со скрытыми массивами, например в инвокейшнлистах и тд и тд. Казалось бы — сделали N подсписчиков, что тут такого ?
А реально выходит хаос память или заканчивается на ровном месте или GC будет педалить, педалить, педалить

E>>>Я так понимаю, если товарищ напишет тебе сортировку за O(N^3) или O(N!), ты этот код одобриши на том основании, что не было никаких требований про производительность ?

E>Нет. Не одобрю. Это очень плохой показатель, а у обсуждаемого "неправильного" кода, показатели-то не такие уж и плохие же. Просто тратит память, но не факт, что это проблема.

Нагрузка на GC — O(2^N) и вот такое решение ты яростно защищаешь, и на ровном месте у тебя Out Of Memory exception с долгими мучениями GC

P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.

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

I>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
C++ лагерь говорит что в С++ у списков нет внутреннего массива

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

I>Теоретически, GC может и будет двигать неудобные блоки. Но факт в том, что это работает до ~85кб, дальше GC (не в курсе про последние версии), ничего двигать не будет и память будет выделяться-освобождаться как попало.
I>На самом деле в GC есть оптимизации из за таких вот случаев, но я бы не сказал, что они сработают всегда. Если приложение нормально разогрето, в нем не будет нужного количества свободных блоков должного размера.
I>То есть, GC будет стараться двигать мелкие объекты(<85 кб), даже не двигать, а гонять их по адресному пространству.
В 4.5.1 будет LOH compacting.
Но в принципе, если кто сталкивался с реальным, а не теоретическим энтерпрайзом — Windows Server 2012+ — в основном там только сниться, или на новых инсталляциях, или нету. Так, что в ближайшее время — как бы пофигу на все их новые флюшки со своей дурацкой lock-in политикой.

Так что, как ни странно, но таки да.

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

I>>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
A>C++ лагерь говорит что в С++ у списков нет внутреннего массива
Ой ли.

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

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

I>>>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
A>>C++ лагерь говорит что в С++ у списков нет внутреннего массива
F> Ой ли.
Залезте в STL и посмотрите.
Внутренний массив есть у вектора, и список массивов есть у дека.
У списков — нет массива. Там память выделяется индивидуально.

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

I>>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
A>C++ лагерь говорит что в С++ у списков нет внутреннего массива

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

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

I>>Теоретически, GC может и будет двигать неудобные блоки. Но факт в том, что это работает до ~85кб, дальше GC (не в курсе про последние версии), ничего двигать не будет и память будет выделяться-освобождаться как попало.
I>>На самом деле в GC есть оптимизации из за таких вот случаев, но я бы не сказал, что они сработают всегда. Если приложение нормально разогрето, в нем не будет нужного количества свободных блоков должного размера.
I>>То есть, GC будет стараться двигать мелкие объекты(<85 кб), даже не двигать, а гонять их по адресному пространству.
F> В 4.5.1 будет LOH compacting.
F> Но в принципе, если кто сталкивался с реальным, а не теоретическим энтерпрайзом — Windows Server 2012+ — в основном там только сниться, или на новых инсталляциях, или нету. Так, что в ближайшее время — как бы пофигу на все их новые флюшки со своей дурацкой lock-in политикой.

F> Так что, как ни странно, но таки да.

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

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

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

E>>Ну то решение, которое не нравится НС, если его сделать более или менее по уму, оно всего в два раза медленнее + одна-две аллокации под буфер массива, что на GC полная фигня, как бы...

I>Алё ! Ты математик или погулять вышел ?
Начинаем новый тред с оскорблений? Занятно...

I>Объясняю популярно
I>выделение памяти здесь НЕ линейное, хотя это не очевидно на первый взгляд.
1) Ну будет логорифм от длины аллокаций, горе-горе-беда-беда...
Всё равно это o(N)...
2) Неужели этому вашему листу с решёточкой нельзя намекнуть скока памяти брать сразу?

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

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

I>Более того, очень осторожно нужно быть со скрытыми массивами, например в инвокейшнлистах и тд и тд. Казалось бы — сделали N подсписчиков, что тут такого ?
I>А реально выходит хаос память или заканчивается на ровном месте или GC будет педалить, педалить, педалить

Ну, конкретно в задаче со списком можно сначала посчитать длину, если это так уж критично. Будет ещё лишнее чтение всех указателей, а не толкьо лишняя запись

I>Нагрузка на GC — O(2^N) и вот такое решение ты яростно защищаешь, и на ровном месте у тебя Out Of Memory exception с долгими мучениями GC

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

I>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
Чё, правда что ли?

Если чё, ты не сообщил ничего нового. Только сильно краски сгустил, а так всё нормуль

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

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

I>Здесь будет геометрическая прогрессия с первым членом навроде 11 и знаменателем 2.
I>Свойство вот этой конкретной прогрессии такое, что каждый следующий блок больше суммы всех предыдущих.

I>пример — 11, 22, 44, 88
I>Будет так, надо выделить 22, 11 освободить. остается дыра в 11. выделяем 44, остается дыра в 33, выделяем 88, остается дыра 77 и тд и тд
I>Память то будет освобождаться, но GC будет жрать все новую и новую память, ибо старый блок дохнет после того, как будет инициализирован новый.
I>Более того, память будет фрагменироваться не только массивами, но и хипами

I>Теоретически, GC может и будет двигать неудобные блоки. Но факт в том, что это работает до ~85кб, дальше GC (не в курсе про последние версии), ничего двигать не будет и память будет выделяться-освобождаться как попало.
I>На самом деле в GC есть оптимизации из за таких вот случаев, но я бы не сказал, что они сработают всегда. Если приложение нормально разогрето, в нем не будет нужного количества свободных блоков должного размера.
I>То есть, GC будет стараться двигать мелкие объекты(<85 кб), даже не двигать, а гонять их по адресному пространству.


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

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

Начальный размер List<T> — 16 или 32 (надо уточнить, давно не смотрел сборки).
Простая математика говорит что границу LOH (85кб) пересекаем через 10-11 увеличений размеров буфера, за это время будет выделено 128кб.
Первое поколение GC кажись около 256кб, то есть за время такого "разворота" максимум будет одна Gen0 GC. И то вероятность крайне мала.
То есть до 1,000 элементов вроде как все ОК.

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

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

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

ЗЫ. Профилирование памяти говорит что самую большую нагрузку на GC дают строки. Больше любого алгоритма. И это не только веб-приложения.

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

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

I>>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
A>C++ лагерь говорит что в С++ у списков нет внутреннего массива
vector<T> таки имеет внутренний массив, да еще и коэффициент увеличения 1.5, что приводит к более частым выделениям\освобождениям памяти.

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

I>>>>P.S. Крикунам из лагеря С++ — для многих плюсовых контейнеров, которые ресайзят внутренний массив как это показано выше, п..ц наступит гораздо быстрее, практически мгновенно.
A>>>C++ лагерь говорит что в С++ у списков нет внутреннего массива
F>> Ой ли.
LVV>Залезте в STL и посмотрите.
LVV>Внутренний массив есть у вектора, и список массивов есть у дека.

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

Судя по тому, что мне доводилось видеть, в С++ старую технику realloc давно забыли

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

I>>Объясняю популярно
I>>выделение памяти здесь НЕ линейное, хотя это не очевидно на первый взгляд.
E>1) Ну будет логорифм от длины аллокаций, горе-горе-беда-беда...
E>Всё равно это o(N)...
E>2) Неужели этому вашему листу с решёточкой нельзя намекнуть скока памяти брать сразу?

До конца ты, понимаю, ниасилил, решил побыстрее блеснуть познаниями.

E>Всё-таки я надеюсь, что эту "мегапроблему" как-то да решили, листов-то в шарпе просто тонны же заводят?..

Никак. В С++ при подобной технике увеличения ровно те же проблемы, только быстрее.

I>>Более того, очень осторожно нужно быть со скрытыми массивами, например в инвокейшнлистах и тд и тд. Казалось бы — сделали N подсписчиков, что тут такого ?
I>>А реально выходит хаос память или заканчивается на ровном месте или GC будет педалить, педалить, педалить

E>Ну, конкретно в задаче со списком можно сначала посчитать длину, если это так уж критично. Будет ещё лишнее чтение всех указателей, а не толкьо лишняя запись

Можно. Фокус в том, приведеный код не содержал этого подсчета, а с подсчетом алгоритм становится еще сложнее.

I>>Нагрузка на GC — O(2^N) и вот такое решение ты яростно защищаешь, и на ровном месте у тебя Out Of Memory exception с долгими мучениями GC

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

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

E>Если чё, ты не сообщил ничего нового. Только сильно краски сгустил, а так всё нормуль

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

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

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

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

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

E>2) Неужели этому вашему листу с решёточкой нельзя намекнуть скока памяти брать сразу?
Конечно можно, прямо в конструкторе или выделить скоканадо потом.

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

I>>То есть, фокус в том, что эта стратегия выделения очень неудобная для GC.
E>Ну, что ещё раз говорит нам о том, что базовая стркутура данных несовсемтима с встроенным же в язык GC, и это типа хоршо? Я думаю, что те самые "оптимизации" таки работают
На самом деле они очень хорошо оттюнингованы под GC .NET и могут хранить миллионы элементов.
Но это не значит что вставка в цикле в список без выделения размера — хорошая идея.

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

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

A>>C++ лагерь говорит что в С++ у списков нет внутреннего массива
G>vector<T> таки имеет внутренний массив, да еще и коэффициент увеличения 1.5, что приводит к более частым выделениям\освобождениям памяти.

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

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

E>2) Неужели этому вашему листу с решёточкой нельзя намекнуть скока памяти брать сразу?

Намекнуть то можно, вот только откуда ты узнаешь размер списка? Еще раз по нему пробежишься? И ты продолжаешь утверждать, что такой код, с вычислением и передачей размера, все равно проще правильного варианта?

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

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

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

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

А если размер заранее неизвестен?

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

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

I>Можно. Фокус в том, приведеный код не содержал этого подсчета, а с подсчетом алгоритм становится еще сложнее.
Ну я сильно подозреваю, что это тоже преждевременная оптимизация

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

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

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

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

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

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

G>Аналогично и для других структур данных есть антипаттерны использования, но и в них .NET показывает себя не хуже ************ контейнеров STL.

Что-то я всё раво сомневаюсь, что добавление в массив по одному -- это такой уж антипатерн.
Всё-таки массив под это проетировался. Я так понимаю, что в обсуждаемом листе будут храниться ссылки, так что размеры блоков будут типа стандартными и будут переиспользоваться всеми массивами в программе, так что с грануляцией всё в порядке.
Алолокаций будет логарифмическое количество, то есть o(N), а мы понимаем, что затраты времени на пополнение массива это по любому никак не меньше, чем O(N)...
Суммарный объём аллокаций будет тоже O( N ) и коэффициент там будет какой-то не очень грандиозный, типа от двух до трёх будет колебаться, в зависимости от того, как N близко к 11 * 2^K...

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

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

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

A>>>C++ лагерь говорит что в С++ у списков нет внутреннего массива
G>>vector<T> таки имеет внутренний массив, да еще и коэффициент увеличения 1.5, что приводит к более частым выделениям\освобождениям памяти.

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

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