Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>>Проблема действительно не в List, и чтение документации List'а тут ничем бы не помогло. Так как дефект был в аллокаторе. I>>Это не дефект, а свойство аллокатора. Если это называть дефектом, то любая особенность станет дефектом EP>Ну да, и кубическая сортировка — тоже не дефект?
...а в киеве дядька.
I>>Скажем, если вместо ручного копирования взять Array.resize и сделать так, что бы GC выделял память не последовательно, а скажем, примерно так — если блок находится в большом окне, выделить память в противоположном конце окна, то, внезапно, проблема с фрагментацией исчезнет и можно выделить больше чем N/3, что очевидно — четные аллокации будут в начале фрейма, нечетные — в конце. Середина будет оставаться свободной и выделить можно будет больше половины размера доступного АП.
EP>Давай, включайся, уже вообще не интересно
EP>Вот тебе картинка, * — это то, что занято list'ом: EP>[ | | | | | | | | | | | | | |*|*|*|*|*|*|*|*] EP>внешняя фрагментация нулевая EP>Покажи как ты увеличишь capacity вдвое
Ты в какой то частный случай уперся и не хочешь думать.
Предположим, АП 50, размер списка — 32, это больше чем 50/3. Согласно твоей логике, более 16 выделить не получится, если двигать блоки нельзя.
Проверяем, стрелками указана граница АП: > нижняя, < верхняя
Начальный блок в листе это 4, итого
>4 8 16
В последовательной аллокации 16 лежит ровно посередине АП и действительно, АП/3 превзойти не получается.
Теперь выделение так, как я предложил:
>4
8< >16
<32
Опаньки — 32,внезапно, влезло и это больше АП/3. Дальше уже не фрагментация, а тупо нехватка памяти.
Ровно тот же фокус можно повторить, если GC умеет менять размер блока или, по простому, сразу установив капасити 32.
Итого — все случаи, которые не позволяют выделить память более 16 это тупо, фрагментация и именно это я хотел сказать. Все твои рассуждения, идут лесом, ибо ты не удосуживаешься прочесть, надо по пять раз напоминать одно и то же.
Здравствуйте, Ikemefula, Вы писали:
I>Предположим, АП 50, размер списка — 32, это больше чем 50/3. Согласно твоей логике, более 16 выделить не получится, если двигать блоки нельзя.
EP>Даже при полном отсутствии всякой фрагментации, у тебя capacity не сможет вырасти в два раза, когда ты уже съел треть памяти, хоть ты тресни. Тебе уже это на протяжении нескольких страниц объясняли
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>>>Точно: "Getting or setting an item takes time O(log N), where N is the number of items in the list" против O(1) у std::deque. То есть это, по идее, аналог std::map<std::size_t,T>. I>>Биглист это точно отстой. Примитивная, на коленке, реализация деки рвет биглист как тузик грелку как раз потому что биглист это не аналог деки.
EP>Поиски распространённого аналога std::deque продолжаются. Ведь что-то должно было вымучиться за 10 лет плохого аллокатора
EP>>Даже при полном отсутствии всякой фрагментации, у тебя capacity не сможет вырасти в два раза, когда ты уже съел треть памяти, хоть ты тресни. Тебе уже это на протяжении нескольких страниц объясняли
Во первых — что мешает задать капасити изначально ?
Во вторых — если ты выделяешь треть и она не по середине, то слева или справа будет две трети, то есть, удваивается. Покажи на моём примере, где было АП 50, а то я твои идеи не понимаю
Здравствуйте, Ikemefula, Вы писали:
EP>>Поиски распространённого аналога std::deque продолжаются. Ведь что-то должно было вымучиться за 10 лет плохого аллокатора I>А чем не угодила дека из STL.Net ? I>http://msdn.microsoft.com/en-us/library/bb398188.aspx I>Я правда не пользовался, только что нашел
Во-первых пишут что она не работает в C#.
А во-вторых — её тут никто не упоминал. Уже вроде как три C#'иста пытались безрезультатно найти аналог
.
Во-вторых, мы же всё ещё обсуждаем тот пример где нет никакого reserve? Так вот, речь о том, что если аллокация фейлится когда grow_factor*capacity > total_free_memory, то будь хоть у тебя нулевая внешняя фрагментация — тебе бы это не помогло.
Точно такая же ситуация будет и в x64.
I>Во вторых — если ты выделяешь треть и она не по середине, то слева или справа будет две трети, то есть, удваивается.
Треть это порог. Перешагнёшь через него — и больше твоя capacity не сможет вырасти в два раза.
I>Покажи на моём примере, где было АП 50, а то я твои идеи не понимаю
Если мы пришли в любую capacity > 16 — то больше сделать 2x не получится
. EP>Во-вторых, мы же всё ещё обсуждаем тот пример где нет никакого reserve? Так вот, речь о том, что если аллокация фейлится когда grow_factor*capacity > total_free_memory, то будь хоть у тебя нулевая внешняя фрагментация — тебе бы это не помогло. EP>Точно такая же ситуация будет и в x64.
Спасибо, капитан, речь то про другое была.
I>>Во вторых — если ты выделяешь треть и она не по середине, то слева или справа будет две трети, то есть, удваивается. EP>Треть это порог. Перешагнёшь через него — и больше твоя capacity не сможет вырасти в два раза. I>>Покажи на моём примере, где было АП 50, а то я твои идеи не понимаю EP>Если мы пришли в любую capacity > 16 — то больше сделать 2x не получится
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Во-первых пишут что она не работает в C#. EP>А во-вторых — её тут никто не упоминал.
Она работает, только параметризовать её нельзя. Т.е. все решается чз генеренный враппер, будет работать с небольшим пенальти из за этого.
т.е. тупо
std.deque<SomeCustomType> deque = new std.deque<SomeCustomType>();
Напрямую работать не будет. Но как минимум можно сделать кое какие обходным маневры, из за того, что темплейты разворачивает компилятор, а генерики — рантайм.
А вот так — будет
var x = instance.GetDeque();
>Уже вроде как три C#'иста пытались безрезультатно найти аналог
Здравствуйте, Ikemefula, Вы писали:
I>Я и говорю что ты не программист, твои каменты это однозначно демонстрируют.
Вот ты и говоришь, что по сути дела тебе сказать нечего и ты перешёл к личности собеседника
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
I>>Я и говорю что ты не программист, твои каменты это однозначно демонстрируют.
E>Вот ты и говоришь, что по сути дела тебе сказать нечего и ты перешёл к личности собеседника
Профориентация не является частью личности, не льсти себе.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Поиски распространённого аналога std::deque продолжаются. Ведь что-то должно было вымучиться за 10 лет плохого аллокатора
Судя по тому, что говорят коллеги, складывается такое впечатление, что проблему предпочитали не лечить. а обходить, вообще избегая больших блоков, предпочитая структуры данных собранные из большого количества небольших...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Тем и не угодила, что хотелось бы понять как проблему решали НА ПРАКТИКЕ...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
I>>Я правда не пользовался, только что нашел
E>Тем и не угодила, что хотелось бы понять как проблему решали НА ПРАКТИКЕ...
Здравствуйте, Erop, Вы писали:
EP>>Поиски распространённого аналога std::deque продолжаются. Ведь что-то должно было вымучиться за 10 лет плохого аллокатора E>Судя по тому, что говорят коллеги, складывается такое впечатление, что проблему предпочитали не лечить. а обходить, вообще избегая больших блоков, предпочитая структуры данных собранные из большого количества небольших...
В этой Large Object Heap основные жители это массивы.
Как я понял, Large Object в виде структуры/класса при пороге 85kB получить крайне трудно. Особенно учитывая то, что fixed-size массивы там крайне неудобные (только unsafe context).
В такой ситуации std::deque, особенно с одинаковым размером chunk'а среди разных типов, решил бы кучу проблем. Все эти chunk'и можно было бы аллоцировать в простейшем и быстром free-list'е.
Из крупных объектов остался бы какой-нибудь interop, и внутренние массивы дэки (где указатели на chunk'и) — но их во-первых немного, а во-вторых они сравнительно маленькие.
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>В этой Large Object Heap основные жители это массивы. EP>Как я понял, Large Object в виде структуры/класса при пороге 85kB получить крайне трудно. Особенно учитывая то, что fixed-size массивы там крайне неудобные (только unsafe context).
Наоборот, очень легко. Для хештейбла это всего 5000 элементов.
EP>В такой ситуации std::deque, особенно с одинаковым размером chunk'а среди разных типов, решил бы кучу проблем. Все эти chunk'и можно было бы аллоцировать в простейшем и быстром free-list'е.
С одинаковым не получится, в том то и проблема. Если хранить в листе вещи навроде гуидов, то получается чунк 85кб/16 = 5000 элементов
EP>Из крупных объектов остался бы какой-нибудь interop, и внутренние массивы дэки (где указатели на chunk'и) — но их во-первых немного, а во-вторых они сравнительно маленькие. EP>
Немаловажный фактор это суммарный оверхед по памяти и всякие косвенные расходы. Без профайлера сравнивать две коллекции занятие имеющее не сильно много смысла.
Здравствуйте, Ikemefula, Вы писали:
EP>>В этой Large Object Heap основные жители это массивы. EP>>Как я понял, Large Object в виде структуры/класса при пороге 85kB получить крайне трудно. Особенно учитывая то, что fixed-size массивы там крайне неудобные (только unsafe context). I>Наоборот, очень легко. Для хештейбла это всего 5000 элементов.
Ну так а что у hashtable внутри? Не массив случайно?
EP>>В такой ситуации std::deque, особенно с одинаковым размером chunk'а среди разных типов, решил бы кучу проблем. Все эти chunk'и можно было бы аллоцировать в простейшем и быстром free-list'е. I>>С одинаковым не получится, в том то и проблема. Если хранить в листе вещи навроде гуидов, то получается чунк 85кб/16 = 5000 элементов
Ты о том, что много на один chunk получается?
1. Их можно попробовать за-pool'ить, порезать куски 85kB на несколько chunk'ов
2. Я не предлагаю отказываться совсем от массивов — я показываю альтернативу
3. MS могли бы снизить размер, добавить chunk heap или ещё что-нибудь, а не мариновать 10 лет плохим аллокатором.
4. Расход лишних 85kB на массив, это не так ужасно по сравнению с OOM.
5. Сделать гибридный массив/дэку, который сам подменяет реализацию.
да много вариантов
EP>>>Из крупных объектов остался бы какой-нибудь interop, и внутренние массивы дэки (где указатели на chunk'и) — но их во-первых немного, а во-вторых они сравнительно маленькие. EP>>> I>>Немаловажный фактор это суммарный оверхед по памяти и всякие косвенные расходы. Без профайлера сравнивать две коллекции занятие имеющее не сильно много смысла.
А что там сравнивать — у deque'и при random access на одну косвенность больше. Линейная итерация, если реализовывать максимально эффективно, то получается практически также
Здравствуйте, Evgeny.Panasyuk, Вы писали:
K>>Я не могу ручаться, но вполне вероятно в полностью управляемой среде спрятать от прикладных программеров почти все подобные аспекты.
EP>Вряд ли такое возможно в языке достаточно широкого назначения.
Ну почему же. В шарпе к этому очень хорошо приблизились. А c# — язык широкого назначения. Конечно, не все детали низкого уровня спрятаны, но лишь потому, что управляемую среду натянули поверх неуправляемой. Вот и текут абстракции.
EP>Детерминизм действительно важен, и поэтому в C# есть using, в Java — try-with-resources , в Python — with — и везде требуется подобие IDisposable.
Чуть вернёмся назад. Возможно, я не совсем понял, когда влез в обсуждение. Основной пойнт в упоминании Dispose был в том, что его всё равно нужно вызывать вручную, несмотря на наличие GC? И так же как в неуправляемом коде в многопоточке непонятно, когда именно удалять объект, так же и в управляемом коде в многопоточке непонятно, когда вызывать Dispose? Правильно я понял?
Опять же, я считаю, что эта проблема лишь из-за того, что управляемая среда работает поверх неуправляемой. Вполне можно было бы сделать автоматическое удаление/освобождение любого ресурса детерминированно. Возможно, это будет чуть накладнее, чем ручной вызов диспоза. Но для прикладного кода в большинстве случаев это было бы приемлемо.
EP>Мой поинт в том, что ресурсы существуют сами по себе, а не являются какой-то особенностью native.
Согласен. Тем не менее, вполне можно сделать их детерминированное автоматическое освобождение (в изначально управляемой среде).
Здравствуйте, koodeer, Вы писали:
K>>>Я не могу ручаться, но вполне вероятно в полностью управляемой среде спрятать от прикладных программеров почти все подобные аспекты. EP>>Вряд ли такое возможно в языке достаточно широкого назначения. K>Ну почему же. В шарпе к этому очень хорошо приблизились. А c# — язык широкого назначения. Конечно, не все детали низкого уровня спрятаны, но лишь потому, что управляемую среду натянули поверх неуправляемой. Вот и текут абстракции.
Ну вот например соединение с базой данных — эта такая абстракция которая течёт из native'а?
EP>>Детерминизм действительно важен, и поэтому в C# есть using, в Java — try-with-resources , в Python — with — и везде требуется подобие IDisposable.
K>Чуть вернёмся назад. Возможно, я не совсем понял, когда влез в обсуждение. Основной пойнт в упоминании Dispose был в том, что его всё равно нужно вызывать вручную, несмотря на наличие GC?
Marty. Что конкретно он подразумевал я не знаю — тут могут быть несколько вариантов.
K>Тем не менее, вполне можно сделать их детерминированное автоматическое освобождение (в изначально управляемой среде).
Можно. Например using/try-with-resources/with, да и вообще управляемые среды не исключают RAII.
