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);

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

[...] This might not seem so bad: surely the smaller blocks can be put in the large gaps that are left behind?
Well, they can, but there’s a catch. As mentioned previously, .NET prefers to put new memory blocks at the end of the heap, as it has to do less work to find a space where a block will fit: This means that when there’s a new large block on the heap, the next smaller block will be allocated immediately after it, with the consequence that it will have to further extend the heap if the program ever wants to allocate a larger block.

It really takes a large amount of chutzpah to release a product with such a major flaw. It basically makes it almost impossible to write long-running server processes in .NET. This issue almost cost my company a contract since we were experiencing inexplicable OutOfmemoryExceptions in a very important product.

The problem can be solved by
a) treating large objects like normal objects and compacting the LOH during a generation 2 collection or
b) using a classic heap management algorithm like the one from Donald Knuth to ensure that the total size of the heap never exceeds two times the total number of allocated bytes.

I don't expect microsoft to do anything about this issue. After all, they are busy adding new language features like dynamic to C# in order to make it more buzzword compliant. And they did not do anything about any of the other highly rated feedback items I have submitted. But I think everybody should know about this issue so that they can avoid the .NET platform for important applications.

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

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

#if !defined(_IOSTREAM_) && !defined(_STLP_IOSTREAM) && !defined(__STD_IOSTREAM__) && !defined(_CPP_IOSTREAM) && !defined(_GLIBCXX_IOSTREAM)
    #include <iostream>
#endif

#if !defined(_VECTOR_) && !defined(_STLP_VECTOR) && !defined(__STD_VECTOR__) && !defined(_CPP_VECTOR) && !defined(_GLIBCXX_VECTOR)
    #include <vector>
#endif

#if !defined(_EXCEPTION_) && !defined(__EXCEPTION__) && !defined(_STLP_EXCEPTION) && !defined(__STD_EXCEPTION)
    #include <exception>
#endif

#if !defined(_STDEXCEPT_) && !defined(_STLP_STDEXCEPT) && !defined(__STD_STDEXCEPT) && !defined(_CPP_STDEXCEPT) && !defined(_GLIBCXX_STDEXCEPT)
    #include <stdexcept>
#endif

#ifndef WIN32_LEAN_AND_MEAN
    #define WIN32_LEAN_AND_MEAN
#endif

#ifndef STRICT
    #define STRICT
#endif

#if !defined(_WINDOWS_)
    #include <windows.h>
#endif



int main(int argc, char* argv[])
   {
    try{
        const int maxI = 1024*1024*1024;
        std::vector<char> v;
        for(int i=0; i!=maxI; ++i)
           {
            if (i && i%1024 == 0) std::cout<<"i = "<<i<<"\n";
            char ch = ' ' + (char)(i%64);
            //v.append(1, ch);
            v.push_back(ch);
           }
        std::cout<<"Char at random position: '"<<v[GetTickCount()%maxI]<<"'\n";

       }
    catch( const std::exception &e )
       {
        std::cout<<"Error: "<<e.what()<<"\n";
       }
    catch( ... )
       {
        std::cout<<"Error: unknown\n";
       }
    
    return 0;
   }

...
i = 689594368
i = 689595392
Error: bad allocation

На кой ему вообще сдались LOH? Зачем он АП пачками ест? Ну да это всё лирики, таки надо констатировать что тот дотнетовский аллокатор, который работает сейчас в программах у пользователей -- УГ

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

EP>>BigList это аналог std::map<std::size_t, T>, с O(log(N)) random access. А нужен именно аналог листа, чтобы после замены не выросла сложность алгоритма

I>Нагрузка на GC — O(2^N) и вот такое решение ты яростно защищаешь

I>Если N объектов в списке коррелирует с Е количеством объектов в системе, то на ровном месте получается плохая зависимость, т.к. время работы GC это O(E+V), где E количетсво объхектов, V количество ссылок между ними.
I>Итого, N коррелирует с E и это значит, что нагрузка на GC будет практически N^2.

I>Я чучка погорячился про квадратичность, но сути это не меняет. N*log(N) с подключением свопа мало чем отличается для обсуждаемого размера АП.

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;
}

    void Reverse()
    {
        List reversedList;

        while (ListElement* head = sliceHead())
            reversedList.prepend(head);

        *this = reversedList;
    }

    ListElement* sliceHead();
    void prepend(ListElement*);

S>...x....x.....x......x.......x........x..........x.. OuchMyMemoryException
S>

S>Как, очень актуальный сценарий?

In .NET 4.5, we made two improvements to the large object heap. First, we significantly improved the way the runtime manages the free list, thereby making more effective use of fragments. Now the memory allocator will revisit the memory fragments that earlier allocation couldn’t use. Second, when in server GC mode, the runtime balances LOH allocations between each heap. Prior to .NET 4.5, we only balanced the SOH. We’ve observed substantial improvements in some of our LOH allocation benchmarks as a result of both changes.

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

EP>>http://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BB%D0%BB%D0%B8%D0%BE%D0%BD

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

EP>>

I old_successor = successor(first);
set_successor(first, result);

auto next = cur->next;
cur->next = newBegin;

PD>>Почему же ты тогда отстаиваешь свое решение с лишним действием ? Да, для списка — мелочь, но вопрос же в принципе. И речь идет ведь о коде неопределенного назначения, это тебе на обработка нажатия кнопки мыши , за которой следует чтение 10Мб файла, а поэтому можно сказать, что плевать мне на эффективность самого обработчика WM_LBUTTONDOWN. А вдруг где-то именно это лишнее присваивание вызовет потерю производительности ? И что тогда ? Копаться в этом slice, понять, что там лишнее действие, переделать все (его же просто так не уберешь там) ? Сколько времени уйдет на то, чтобы это место обнаружить ? Сколько времени уйдет, чтобы это исправить (то есть переписать в том виде, который я сделал) ? За это время я тебе все next в m_next в этом классе вручную переименую

A>struct Foo {
A>    void bar() { m_b = -m_b; }
A>private:
A>    int m_b;
A>};
A>

void process(AnyClass& p)
{
for(int i = 0; i < p.length; i++)
  doSomething(p[i]);
}