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


I>Аналог этого списка это vector или чтото навроде.

Что? Более того, кому в здравом уме и твердой памяти может понадобиться реверсить вектор?

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

Сейчас вроде бы имеет смысл в подобных случаях применять Bcl.Immutable. Там хоть с выделением памяти нет такого беспредела,ну и перфоманс в целом поровнее и побыстрее в среднем. Ну и опять же, народ к элементам ФП приучать, к тому, что коллекцию изменить нельзя.

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

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

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

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

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

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

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

Дотнет пока не дорос до таких коллекций, любое добавление в коллекцию фактически создание нового и разрушение старого. С фрагментацией проблем не будет, но увеличивается количество объектов значительно и получается тот же хаос. Собтсвенно ФП коллекции безбожно тормозят сами по себе.

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

I>>Аналог этого списка это vector или чтото навроде.

L>Что? Более того, кому в здравом уме и твердой памяти может понадобиться реверсить вектор?

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

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

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

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

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

256К ссылок даст всего 18 аллокаций, это небольшая проблема.

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

Объясняю в который раз — речь про адресное пространство, а не память.

Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.
Адресное пространство != память.

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

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

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

Еще раз — речь про адресное пространство, а не оверхед по памяти.

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

I>Объясняю в который раз — речь про адресное пространство, а не память.

I>Адресное пространство != память.
I>Адресное пространство != память.
<...>
I>Адресное пространство != память.
I>Адресное пространство != память.
I>Адресное пространство != память.
I>Адресное пространство != память.

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

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

I>Еще раз — речь про адресное пространство, а не оверхед по памяти.

У тебя убогий GC неконтролируемо адресное пространство процесса фрагментирует? У-ти-у-ти-у-ти, как я тебе сочувствую.

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

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

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

Цена вопроса == стабильность приложения. Дальше зависит от того, что это за приложение.

Проблема актуальная для больших приложений в архитектуре навроде x86, где АП ограничено — всего 2гб, но в силу естественной фрагментации размер непрерывного отрезка АП может быть намного меньше, в 10 и более раз.

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

I>>Еще раз — речь про адресное пространство, а не оверхед по памяти.

E>У тебя убогий GC неконтролируемо адресное пространство процесса фрагментирует? У-ти-у-ти-у-ти, как я тебе сочувствую.

Не GC, а аллокации фрагментируют. GC с этим борется.

E>Оценки масштаба трагедии, вызванной списком ил миллиона или четверти миллиона коротких строк, таки будут?..

Оценка мастштаба трагедии для твоего случая уже дадена в первых ответах — никакой трагедии, абсолютно, ибо GC не выйдет за пределы одного-двух хипов (16мб).

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

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

Да не особо большие. Списочек в десяток миллионов ссылок при активном использовании уже такое вполне способен обеспечить.

E> Таких и в память влезет несколько десятков только...

Не важно сколько их влезет в память. Даже один крупный пересоздаваемый список способен со временем фрагментировать весь доступный спейс.

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

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

В дотнете зря поменяли название ArrayList, когда решили добавить дженерики. Был бы толковй ArrayList'T и не было бы многих проблем.

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

E>Так что мне всё равно не ясен весь этот ужас перед последовательным добавлением...

Ситуация довольно редкая, если граф объектов небольшой, миллион-два, в LOH никто не гадит и нативных модулей, сборок немного.
А если загружено N нативных модулей, граф объектов большой, интенсивно используется интероп, большое количество сборок, в LOH уже есть много хипов, то рассчитывать более чем на два три хипа(каждый 16мб) я бы не стал. И для больших приложений, если никто не опимизировал АП, это обычное дело.
Скажем гибридные приложения это просто АДъ , когда в одном процессе сразу всё.

В промежуточных вычислениях периодически случаются списки длиной 10млн и более, бывает и до 100 млн. Вроде запас по памяти приличный, но прилага ведет себя странно — преиодически мерзнет надолго, потом отмерзает или иногда сваливается от OOM.
Начинаешь сокращать расход памяти, местами помогает, а местами становится еще хуже — сваливается быстрее. Еще сокращаешь — на одних сценариях работает лучше, на других еще быстрее сваливается Фокус в том, что простое сокращение расхода памяти большей частью в АП ничего кардинально не меняет — как были дырки, так и остались.

У GC нет никакой информации о том, где лучше искать свободные блоки. Потому выбран сценарий который удовлетворяет 80% приложений — освобождаем наобум(почти) до тех пор пока не найдем. Не нашлось — двигаем блоки до тех пор пока не найдем. Двигать любые блоки нельзя — часть блоков не двигаются. Как только уперлись в это — OOM.

В х64 эта проблема неактуальна, АП много больше чем доступно памяти. Для х86, проблема очень актуальна, если приложение большое, см выше.

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

I>Собтсвенно ФП коллекции безбожно тормозят сами по себе.

Однако построенный на них компилятор шарпа работает в разы быстрее нативного.

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

I>Проблема актуальная для больших приложений в архитектуре навроде x86, где АП ограничено — всего 2гб, но в силу естественной фрагментации размер непрерывного отрезка АП может быть намного меньше, в 10 и более раз.


Ну не надо массивы больше 100 метров хреначить просто и всё. Они на это не рассчитаны просто. Но это довольно-таки специфическая проблема, вообще-то...

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

I>Оценка мастштаба трагедии для твоего случая уже дадена в первых ответах — никакой трагедии, абсолютно, ибо GC не выйдет за пределы одного-двух хипов (16мб).

И к чему тогда весь кипишь и стоны, что все умрут?

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

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

40 метров буфера уже хватает? Не особо хорошо работает тогда в дотнете менеджмнт памяти

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

Странно, а чё, про грануляцию там не слыхали что ли?

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

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

I>В х64 эта проблема неактуальна, АП много больше чем доступно памяти. Для х86, проблема очень актуальна, если приложение большое, см выше.

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

Кстати, а раскидать объекты/подсистемы по нескольким процессам не помогает?

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

L>>Что? Более того, кому в здравом уме и твердой памяти может понадобиться реверсить вектор?

I>Проблемы вызывает код ниже. Выдели болдом строчки, в которых тебе видится реверс списка
I>

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

Я в код н вчитывался , по заголовку оценил.
Но в C++ список — это тебе не массив какой, описанных тобой ужасов с распределением памяти не ожидается.