Re[4]: собеседования, Реверс списка
От: Abyx Россия  
Дата: 15.10.13 05:30
Оценка:
Здравствуйте, -n1l-, Вы писали:

N>Лол, сейчас неосилятор ссылок расскажет нам всем, как нужно писать код.


каких ссылок?
In Zen We Trust
Re[17]: собеседования, Реверс списка
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 15.10.13 06:07
Оценка:
Здравствуйте, Marty, Вы писали:

M>Ну это level 2, так то. Твой GC level 1 проходит?


Не понял вопроса.

M>Даешь примеры, когда GC уделывает стандартный MSVS2005 runtime heap manager!


Посмотри в статьях прямо на этом сайте.
Re[17]: собеседования, Реверс списка
От: Evgeny.Panasyuk Россия  
Дата: 15.10.13 07:12
Оценка:
Здравствуйте, Ночной Смотрящий, Вы писали:

EP>>3. показать лёгкость замены вектора на деку (которой afaik нет в стандартном .net'е)

НС>Есть. LinkedList называется.

И random access у него O(1), как и у деки?
LinkedList это аналог std::list, но никак не std::deque
У деки random access, push_back и push_front константные, причём она достаточно cache-friendly в отличии от std::list, так как де-факто реализуется как набор больших chunk'ов.
Re[18]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 07:52
Оценка:
Здравствуйте, Marty, Вы писали:

M>А вообще, было бы круто, если бы аллокаторы поддерживали изменение grow factor, и его можно было бы поменять через интерфейс контейнера. Что ни говори, а 32 бита еще не скоро сойдут с дистанции, а объемы данных растут постоянно. Закиньте что ли предложение в комитет


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

Но в любом случае, надеяться, что тебе отдадут в рамках контейнера и аллокатора общего назначения 25% АП, или даже больше -- IMHO, черезмерный оптимизм. Тут надо что-то иное делать, в рамках С++ дешевле всего уйти на дек или на какой-то самописный контейнер.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[16]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 07:54
Оценка:
Здравствуйте, Marty, Вы писали:


M>при том, что под данные у Win32 процесса обычно есть честные 2Гб.


Под данные, стеки нитей, код, ресурсы и прочие нужды...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[20]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 07:59
Оценка:
Здравствуйте, Marty, Вы писали:

M>Ок, похоже на правду Как бы прошу заметить, что я тут независимое расследование провожу, так что попрошу без подxyzколок



Лично я без подколок, просто делюсь результатами аналогичных исследований и последующего чтения...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[17]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 08:05
Оценка:
Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Это где такое? В CLR для LOH этого пока нет, а в С++ это просто невозможно без замены ссылок на спецконструкции, которые можно отслеживать. Или речь про склейку прилегающих блоков? Если последнее, то это не спасает.


В С++ под виндой двигать блоки, что бы бороться с фрагментацией -- тупиковый путь, так как пересылки память-память очень дороги, а пересылки своп-своп дороги бесконечно
Так что практической ценности такое поведение не имело бы. Кстати, 16-битная винда что-то такое умела с глобальной памятью делать, но оно всё умерло, так как тормоза нереальные.

Но если на скорость плевать и главное, что бы хоть как-то, но работало, то почему бы нет? Только я не уверен, что даже для С# это главное
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[17]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 08:09
Оценка: +1
Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Я так понимаю, примерно 100% вновь присоединившихся чуть выше по нитке даже не читают. Тогда напомню тебе, что речь изначально шла про проблемы именно в дотнете, а про С++ разговор зашел, потому что Ероп начал рассказывать, что в С++ таких проблем нет.


До 100 метров -- нет, выше -- это уже процентов 10 от доступного АП, что как бы намекает нам, что программе надо быть готовой к тому, что все данные в непрерывны кусок не лягут.

Про С++ я рассказывал не потому, что там лучше или хуже, а потому, что про то, как в С++ я знаю. Я не думаю, что в С# как-то катастрофически хуже с этим делом и листом пользоваться нельзя-нельзя. Собственно я подставил под сомнение алармистское сообщение I. именно в том смысле, то не верю, что всё настолько плохо и поинтересовался у экспертов в дотнете как оно есть на самом деле, а не в фантазиях нашего напуганного фрагментацией АП коллеги
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[18]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 08:12
Оценка: +1
Здравствуйте, Marty, Вы писали:

M>Т.е. в дотнете проблемы есть, в плюсах нет?

M> о чем речь шла изначально, факт на лице, как говорят.

Самое паскудное, что никто из знатоков дотнета так и не привёл никаких конкретных цифр.
Типа любой лист сфрагментирует всё АП при достаточно долгой работе. И всё тут.
Я вот конкретный вопрос задал, лист объёмом буфера в метр сфрагментирует или нет? А в 10, а в 100? Нет ответа, хотя по плюсам я дал и оценки и цифры, а ты даже тест выкатил
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[19]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 08:14
Оценка:
Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Изначально речь шла о том, что при развороте большого односвязного списка загонять его в List — можно получить проблемы с фрагментацией.


Ну, как бы, если мы про список в сотню миллионов членов, то там тока на указателях оверхеда будет 400 метров...
А если про миллион членов, то я не верю, что сфейлится,..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[19]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 08:20
Оценка: +1
Здравствуйте, Marty, Вы писали:

M>Мой тест #1 сказал, что можно выделить одномоменто в свежей программе 1900Мб. Ты этот момент пролистал не глядя?

M>Не совсем понял, как одномоментная аллокация памяти поможет опровергнуть гипотезу, что фрагментация мешает?

Дык 1900 / 2.5 = 720 где-то не?..


M>На 64х битах можно в 99.9(9)% задач говорить о бесконечной памяти (вернее, о бесконечном АП), и проблема фрагментации тут не стоит.


Ну вот представь, что у тебя бесконечное АП, а памяти, тем не менее, есть всё те же 1900, скока удастся тут байтиков в вектор запихать?..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[20]: собеседования, Реверс списка
От: Sinix  
Дата: 15.10.13 08:41
Оценка: -2
Здравствуйте, Erop, Вы писали:

E>Ну вот представь, что у тебя бесконечное АП, а памяти, тем не менее, есть всё те же 1900, скока удастся тут байтиков в вектор запихать?..


При известной настойчивости — вплоть до исчерпания max_size()
Re[19]: собеседования, Реверс списка
От: Sinix  
Дата: 15.10.13 09:06
Оценка: :)
Здравствуйте, Erop, Вы писали:

E>Типа любой лист сфрагментирует всё АП при достаточно долгой работе. И всё тут.

E>Я вот конкретный вопрос задал, лист объёмом буфера в метр сфрагментирует или нет? А в 10, а в 100? Нет ответа, хотя по плюсам я дал и оценки и цифры, а ты даже тест выкатил

It depends. При правильно написанном коде фрагментации практически не будет (например, если избегать промежуточных аллокаций, задать capacity или поискать реализацию ChunkedList вместо стандартного List<T>). При неправильном — упадёт и при практически пустом АП. В 4.5 с этим полегче: аллокатор чаще переиспользует пустые фрагменты +(начиная с 4.5.1) добавлена возможность дефрагментацию LOH по требованию.
Re[20]: собеседования, Реверс списка
От: Erop Россия  
Дата: 15.10.13 09:12
Оценка: +1
Здравствуйте, Sinix, Вы писали:

S>It depends. При правильно написанном коде фрагментации практически не будет (например, если избегать промежуточных аллокаций, задать capacity или поискать реализацию ChunkedList вместо стандартного List<T>). При неправильном — упадёт и при практически пустом АП. В 4.5 с этим полегче: аллокатор чаще переиспользует пустые фрагменты +(начиная с 4.5.1) добавлена возможность дефрагментацию LOH по требованию.


И снова никакой конкретики. До скольки метров буфера типичного листа в программе ещё можно не парится о фрагментации АП?

Просто если речь о том, что до 100, как в С++, то я бы тут уже начал парится скорее за то, что бы всё своевременно освободилось, скорее. А если до 10, например, то тут, уже порядок плюсам проигрываем, а если и до 1, то это вообще просто полный фейл листа...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Re[19]: собеседования, Реверс списка
От: vdimas Россия  
Дата: 15.10.13 09:20
Оценка:
Здравствуйте, Ikemefula, Вы писали:

I>

I>Error: bad allocation


I>"не дохнет" это оно ?


Дык, область в 2 гига кончилась. Как и должно быть. 680*3=x. )))
Re[17]: собеседования, Реверс списка
От: vdimas Россия  
Дата: 15.10.13 09:32
Оценка:
Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Это только если такая работа — единственная активность в процессе.


Коль речь о больших объемах памяти, то в любом случае это так и для дотнета и для нейтива.

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

Как пример boost::pool. Хотя и до него подобный вид аллокаторов — самый что ни на есть популярный в плюсах. Самое главное — он на заметно эффективнее даже управляемого GC. Вряд ли ты найдешь сейчас хоть одну плюсовую контору, где бы не использовали страничные аллокаторы и пулы объектов на них.
Re[21]: собеседования, Реверс списка
От: Sinix  
Дата: 15.10.13 10:07
Оценка:
Здравствуйте, Erop, Вы писали:

E>И снова никакой конкретики. До скольки метров буфера типичного листа в программе ещё можно не парится о фрагментации АП?

Я ж говорю — it depends. Если поставить цель, то исчерпание LOH под x86 наступит после аллокации <1 гб мусора, достаточно чтобы не было свободных фрагментов

Fail: VM: 1845Mb, chunks:848, allocated 848Mb

  code
        private static void Main(string[] args)
        {
            const int AllocSize = 1024 * 1024;
            const int AllocCount = 1500;
            var currentProcess = Process.GetCurrentProcess();
            List<byte[]> allocated = new List<byte[]>(AllocCount);
            bool ok = false;
            try
            {
                for (int i = 0; i < AllocCount; i++)
                {
                    byte[] temp = new byte[AllocSize + i];

                    byte[] data = new byte[AllocSize + i];
                    allocated.Add(data);

                    GC.KeepAlive(temp);
                }
                ok = true;
            }
            catch (OutOfMemoryException)
            {
                Console.WriteLine(
                    "Fail: VM: {0}Mb, chunks:{1}, allocated {2}Mb",
                    currentProcess.VirtualMemorySize64 / 1024 / 1024,
                    allocated.Count,
                    AllocatedTotal(allocated) / 1024 / 1024);
            }
            if (ok)
            {
                Console.WriteLine(
                    "Allocated: VM: {0}Mb, chunks:{1}, allocated {2}Mb",
                    currentProcess.VirtualMemorySize64 / 1024 / 1024,
                    allocated.Count,
                    AllocatedTotal(allocated) / 1024 / 1024);
            }
            GC.KeepAlive(allocated);

            Console.ReadKey();
        }
        static long AllocatedTotal(List<byte[]> allocated)
        {
            return allocated.Sum(a => (long)a.Length);
        }


Если не извращаться и не грузить аллокатор (заменяем "new byte[AllocSize + i]" на "new byte[AllocSize]") —
Allocated: VM: 1965Mb, chunks:1500, allocated 1500Mb


Поскольку при нужде в гигабайтах клиенты (как правило) уже на x64 — беспокоиться стоит не столько о самой фрагментации, сколько о производительности и нагрузке на GC.

P.S. Насчёт минуса за "исчерпание max_size()" — а что, stxxl::vector уже отменили?
Re[16]: собеседования, Реверс списка
От: vdimas Россия  
Дата: 15.10.13 10:40
Оценка:
Здравствуйте, Marty, Вы писали:

V>>Ты утверждал, что все заткнется из-за дефрагментации, не?

V>>И облажался, по результатам теста. Если в тесте после грубо 660 метров не удалось выделить память, то это значит, что всего было запрошено порядка 660*3=1980 метров. ЧТД.

M>Ты тут не прав

M>660 метров занято. Если grow 1.5

Можно явно переопределить один метод и получить любой grow factor.

Даже если не прав, то не сильно: 3 vs 2.5. Учитывая, что к процессу могут быть приаттачены DLL каждая со своим хипом памяти...
Re[22]: собеседования, Реверс списка
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 15.10.13 11:03
Оценка:
Здравствуйте, Sinix, Вы писали:

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


E>>И снова никакой конкретики. До скольки метров буфера типичного листа в программе ещё можно не парится о фрагментации АП?

S>Я ж говорю — it depends. Если поставить цель, то исчерпание LOH под x86 наступит после аллокации <1 гб мусора, достаточно чтобы не было свободных фрагментов

Если поставить цель, то LOH исчерпается на 20мб
Re[16]: собеседования, Реверс списка
От: Ikemefula Беларусь http://blogs.rsdn.org/ikemefula
Дата: 15.10.13 11:06
Оценка: :)
Здравствуйте, Erop, Вы писали:

M>>Я признаться, тоже не понял, как VirtualAlloc поможет. Тут скорее нужен свой аллокатор с использованием memory mapped files.


E>Я же уже писал.

E>Есть два эффекта.
E>1) Когда куче не хватает памяти, она кусает по VA ещё сегмент, в котором проолжает нарезать блоки, потом ещё сегмент, ещё сегмент и т. д. Трудность в том, что эти сегменты трудно освобождать, так как надо понять, что там нет занятых блоков...
E>2) В программе может быть несколько компонент, пользующихся разными аллокаторами. И тогда все проблемы с сегментами из (1) или ещё какими возводятся в квадрат, и тогда вот и наступает клизма с фрагментацией АП.
E>Но, если все аллокаторы в программе аллокируют слишком большие куски сразу по VA, то тогда их можно освобождать, вопервых, и они могут переиспользоваться потом из ДРУГИХ аллокаторов, во-вторых...

То есть, VirtualAlloc никак не помогает. Ровно тот же результат можно получить если выделять память сразу одним куском в 2гб и потом нарезать его на хипы для больших и малых объектов.

Все что дает VirtualAlloc это быстродействие.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.