Здравствуйте, Evgeny.Panasyuk, Вы писали:
S>>>>... 3. Использовать постоянный (кратный) размер блоков E>>>Да, грануляция, я про то и говорил с самого начала. Только это хорошо бы, что бы поддерживалось таки в контейнере самом. Как называется аналог листа, но с грануляцией размеров буфера? S>>Обычно зовётся paged list или chunked list. Из готовых есть BigList в PowerCollections
EP>BigList это аналог std::map<std::size_t, T>, с O(log(N)) random access. А нужен именно аналог листа, чтобы после замены не выросла сложность алгоритма
С чего ты взял, что random access всегда является узким местом array-like структурах ?
Это может сказать только профайлер. Нужно знать, насколько критичен этот random access. Во многих случаях List можно заменить на BigList или даже ScanList или даже LinkedList, а во многих случаях random access можно на раз получить с помощью простого словаря, который будет создаваться-разрушаться на каждую операцию. Если время работы алгоритма больше долей секунды, то издержками на копирование в словарь можно пренебречь.
Здравствуйте, Erop, Вы писали:
E>Был задан прямой вопрос, что делали, если таки нужны были боьлшие непрерывные куски памяти, например в алгоритме требовались большие списки с доступом по индексу?
Кому? Икемефуле? А почему тогда ты сделал вывод о "С#-разрабов в массе своей"? Я пока логики у тебя не улавливаю.
E>Кстати, что бы опровергнуть этот ой вывод, вполне достаточно таки выкатить это внятное, общепринятое масштабируемое решение...
Решение чего? Сферической задачи в вакууме?
E>>>Вот ты, например, что использовал?.. НС>>Для чего? E>Всё для того же.
Для чего того же? Для разворота списка?
E> В алгоритме нужен большой вектор с доступом по индексу, но GC на таком листе дохнет из-за неудачной политики работы своего аллокатора больших объектов. Что в таком случае дылал лично ты, например?
Если обязательно с доступом по индексу, то ChunkedList. В какой то мере его можно воспринимать как упрощенную вариацию деки на чанках. Но обычно доступа по индексу и не нужно.
E> Или общего рецепта нет и каждый раз надо смотреть по месту?
Здравствуйте, Ikemefula, Вы писали:
EP>>BigList это аналог std::map<std::size_t, T>, с O(log(N)) random access. А нужен именно аналог листа, чтобы после замены не выросла сложность алгоритма I>С чего ты взял, что random access всегда является узким местом array-like структурах ?
Есть List, нужно заменить его на что-то более fragmentation-friendly, и естественно желательно не ухудшив сложность операций
I>Это может сказать только профайлер.
Слушай, тут уже обсудили сложность вставки N элементов в std::vector-like без reserve, и ты уже проделал нелёгкий путь O(2^N) -> O(N^2) -> O(N*log(N)) -> O(N): http://www.rsdn.ru/forum/flame.comp/5325486.1
I>Если N объектов в списке коррелирует с Е количеством объектов в системе, то на ровном месте получается плохая зависимость, т.к. время работы GC это O(E+V), где E количетсво объхектов, V количество ссылок между ними.
I>Итого, N коррелирует с E и это значит, что нагрузка на GC будет практически N^2.
I>Я чучка погорячился про квадратичность, но сути это не меняет. N*log(N) с подключением свопа мало чем отличается для обсуждаемого размера АП.
Давай ты не будешь разводить демагогию на тему node-based tree vs indexed chunks, необходимость профайлеров и всё-такие, ок?
I>Нужно знать, насколько критичен этот random access. Во многих случаях List можно заменить на BigList или даже ScanList или даже LinkedList, а во многих случаях random access можно на раз получить с помощью простого словаря, который будет создаваться-разрушаться на каждую операцию. Если время работы алгоритма больше долей секунды, то издержками на копирование в словарь можно пренебречь.
Здравствуйте, Ночной Смотрящий, Вы писали:
E>> В алгоритме нужен большой вектор с доступом по индексу, но GC на таком листе дохнет из-за неудачной политики работы своего аллокатора больших объектов. Что в таком случае дылал лично ты, например? НС>Если обязательно с доступом по индексу, то ChunkedList. В какой то мере его можно воспринимать как упрощенную вариацию деки на чанках. Но обычно доступа по индексу и не нужно.
Существует ли какая-нибудь распространённая реализация ChunkedList?
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Есть List, нужно заменить его на что-то более fragmentation-friendly, и естественно желательно не ухудшив сложность операций
Не всех операций, а только критичных, что покажет __профайлер__. Вообще оптимизируются исключительно __узкие__ места, а не все подряд.
Узкое место, например RemoveAt(0) — можно заменить на деку что на массивах
А если узкое место, например RemoveAt(index) — заменять на ту же деку СМЫСЛА НЕ ИМЕЕТ, ибо будет ровно та же проблема, только слегка амортизированая
I>>Это может сказать только профайлер.
EP>Давай ты не будешь разводить демагогию на тему node-based tree vs indexed chunks, необходимость профайлеров и всё-такие, ок?
Демагогия это у тебя, т.к. общие рассуждения о прекрасном при отрицании необходимости профайлера.
В реальном приложении обращения к коллекции не все одинаковые, а это разные операции у которых, внезапно, разная частота использования. И вот этот расклад, внезапно, показывает профайлер !
У меня в проекте IndexOf/Contains/RemoveAt/InsertAt каждый по отдельности работали несравнимо дольше, чем ElementAt, foreach, AddLast, RemoveLast, более того, намного дольше чем сам собтсвенно алгоритм.
При этом, наиболее частые операции добавления-удаления это InsertAt(0) и RemoveAt(0). бОльшая часть коллекций короткие, до 100, еще небольашя часть до 4000, больше этого всего 5-10 коллекций и в них от 100 тыс элементов. При этом, что в больших, что в малых коллекциях, суммарно одинаково элементов. То есть, сумма элементов больших коллекций == сумме элементов малых коллекций.
Ну и LOH, куда же без него.
Где узкое место ?
1 Первые четыре операции, в особенности InsertAt(0), RemoveAt(0)
2 LOH
Вот их и нужно оптимизировать, а на все остальное — насрать. В силу особенностей алгоритма количество вызовов зависит от количества хранимых элментов, то есть, при линейной асимптотике операций нарисовывается квадратичная сложность основного алгоритма. Реально она еще больше, сам алгоритм нелинейный.
Правильная оптимизация такая — подобрать структуру, которая радикально улучшит первые четыре, LOH, а на остальное можно даже забить. Например, насрать, если ElementAt станет линейным, а не константным. Когда это станет узким местом, вот тогда и надо будет оптимизировать.
Я, например, выбрал такую оптимизацию —
Contains — O(1)...O(N/chunk_size)
RemoveAt/InsertAt O(1)-O(N/chunk_size + K/4),
ElementAt — O(N/chunk_size + K/4)
RemoveAt(0),InsertAt(0) — O(1)
IndexOf — 0 (нуль)
N для малых, С*N, где С конская константа, примерно 32 или 64, точно не помню, для больших
LOH test — passed
Руководствуясь рассуждениями о прекрасном, я все только опаскудил, ибо ElementAt сделал линейным, а память распылил до невозможности
А по факту — общее время алгоритма с 6 часов стало менее 10 минут, OOM исчез, GC стал работать без лагов
Почему так получаетс ? потому что
1. ElementAt по частоте сильно уступал Contains и он так и не стал критическим местом.
2. С*2*N — только для больших коллекций и из этих больших коллекций осталась не 5-10, а 2-3
Итого — если у тебя есть возражения, покажи где я ошибся и что сделал неправильно, если тебе конечно есть что сказать. Рассуждения о прекрасном оставь для детей.
Здравствуйте, Ikemefula, Вы писали:
I>Итого — если у тебя есть возражения, покажи где я ошибся и что сделал неправильно, если тебе конечно есть что сказать.
У тебя был случай, где нужны были InsertAt(0)/RemoveAt(0)/InsertAt(random)/RemoveAt(random), и изначально ты выбрал List, а потом заменил на что-то более подходящее?
И ты пытаешься сказать что из этого следует, что std::deque вообще не нужна, и является лишь "рассуждением о прекрасном", а нужно что-то что даёт быструю вставку в середину?
Здесь обсуждаются случаи где изначально был List, и он был адекватным выбором, без всяких вставок в начало/середину, но из-за плохого аллокатора нужна альтернатива.
То что тебе когда-то потребовалось что-то типа std::set/unordered_set/etc, и ты это смог распознать, это конечно чрезвычайно полезный для тебя опыт, и видимо отпечатался в памяти как что-то необычное и чрезвычайно увлекательное. Но к данной дискуссии это не имеет никакого отношения
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>У тебя был случай, где нужны были InsertAt(0)/RemoveAt(0)/InsertAt(random)/RemoveAt(random), и изначально ты выбрал List, а потом заменил на что-то более подходящее?
Другие операции тоже были нужны List был выбран 10 лет назад, только сначала это был ArrayList, потом поменяли из за дженериков, и только в 2012м году профайлер показал, что узкое место это коллекции. До этого были другие узкие места, что вполне объяснимо.
EP>И ты пытаешься сказать что из этого следует, что std::deque вообще не нужна, и является лишь "рассуждением о прекрасном", а нужно что-то что даёт быструю вставку в середину?
Пока операция не является узким местом, List самое оптимальное во всех отношениях решение и достаётся забесплатно.
EP>Здесь обсуждаются случаи где изначально был List, и он был адекватным выбором, без всяких вставок в начало/середину, но из-за плохого аллокатора нужна альтернатива.
Вставки в начало-середину становятся критичными только когда размер коллекции превышает определенный порог, до этого они даже незаметны.
EP>То что тебе когда-то потребовалось что-то типа std::set/unordered_set/etc, и ты это смог распознать, это конечно чрезвычайно полезный для тебя опыт, и видимо отпечатался в памяти как что-то необычное и чрезвычайно увлекательное. Но к данной дискуссии это не имеет никакого отношения
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Кому?
Всем, это же публичный форум, не?..
НС>Икемефуле? А почему тогда ты сделал вывод о "С#-разрабов в массе своей"? Я пока логики у тебя не улавливаю.
Бывает. В целом я не обещал, что до всех дойдёт...
Так что там у нас с общепринятым решением?
НС>Для чего того же? Для разворота списка?
Очень трудно поймать чёрную кошку в тёмной комнате, особенно если её не ловить...
НС>Но обычно доступа по индексу и не нужно.
Это можно интерпретировать так, что обычно алгоритмы, где таки нужно, программируют на более иных языках?..
НС>Разумеется, абсолютно универсального рецепта нет.
Ну вот я про то же самое, как бы...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
НС>>Но обычно доступа по индексу и не нужно. E>Это можно интерпретировать так, что обычно алгоритмы, где таки нужно, программируют на более иных языках?..
Где таки нужно — нужно рассматривать конкретные случаи под профайлером. Если профайлер покажет, что узкое место это обращение по случайному индексу, и средствами дотнете не удастся обеспечить должное быстродействие, то будет использован С а может и С++
НС>>Разумеется, абсолютно универсального рецепта нет. E>Ну вот я про то же самое, как бы...
Здравствуйте, Ikemefula, Вы писали:
EP>>У тебя был случай, где нужны были InsertAt(0)/RemoveAt(0)/InsertAt(random)/RemoveAt(random), и изначально ты выбрал List, а потом заменил на что-то более подходящее? I>Другие операции тоже были нужны List был выбран 10 лет назад, только сначала это был ArrayList, потом поменяли из за дженериков, и только в 2012м году профайлер показал, что узкое место это коллекции. До этого были другие узкие места, что вполне объяснимо.
Ещё раз, этот твой конкретный опыт выбора структур данных (видимо вообще единичный), мало относится к текущему обсуждению
EP>>Здесь обсуждаются случаи где изначально был List, и он был адекватным выбором, без всяких вставок в начало/середину, но из-за плохого аллокатора нужна альтернатива. I>Вставки в начало-середину становятся критичными только когда размер коллекции превышает определенный порог, до этого они даже незаметны.
До определённого порога, они будут быстрее в обычных массивах — это, например, одно из оснований использовать boost::flat_map-like. Но как это относится к данному топику? У нас же "огромные и ужасные List'ы"
Здравствуйте, Evgeny.Panasyuk, Вы писали:
EP>Ещё раз, этот твой конкретный опыт выбора структур данных (видимо вообще единичный), мало относится к текущему обсуждению
Это общий оптимизации любых структур данных — смотреть расклад частоте вызовов + издержкам на отдельные операции
А вот подход "у нас большой List давайте заменим на Dequee, потому что асимптотика подходит" это рассуждения о прекрасном.
EP>>>Здесь обсуждаются случаи где изначально был List, и он был адекватным выбором, без всяких вставок в начало/середину, но из-за плохого аллокатора нужна альтернатива. I>>Вставки в начало-середину становятся критичными только когда размер коллекции превышает определенный порог, до этого они даже незаметны.
EP>До определённого порога, они будут быстрее в обычных массивах — это, например, одно из оснований использовать boost::flat_map-like.
То есть, оптимизировать без реальной на то обходимости ? "у нас небольшой List давайте заменим на flat_map, потому что асимптотика подходит"
>Но как это относится к данному топику? У нас же "огромные и ужасные List'ы"
Правильно. И ответ, на что менять List, дает ответ профайлер и требования, а не рассуждения о прекрасном
.
Здравствуйте, Ikemefula, Вы писали:
EP>>До определённого порога, они будут быстрее в обычных массивах — это, например, одно из оснований использовать boost::flat_map-like. I>То есть, оптимизировать без реальной на то обходимости ? "у нас небольшой List давайте заменим на flat_map, потому что асимптотика подходит"
у flat_map вставка O(N)
>>Но как это относится к данному топику? У нас же "огромные и ужасные List'ы" I>Правильно. И ответ, на что менять List, дает ответ профайлер и требования, а не рассуждения о прекрасном.
Профайлер дал ответ, что нужен random-access, что было ясно и без него(например, потому что реализуется heap), дальше что?
Здравствуйте, Erop, Вы писали:
НС>>Кому? E>Всем, это же публичный форум, не?..
Когда ты задаешь вопросы, кому то отвечая, по умолчанию эти вопросы относятся к тому кому ты отвечаешь.
НС>>Икемефуле? А почему тогда ты сделал вывод о "С#-разрабов в массе своей"? Я пока логики у тебя не улавливаю. E>Бывает. В целом я не обещал, что до всех дойдёт...
Перешел на личности — слил.
E>Так что там у нас с общепринятым решением?
Ты так и не ответил — решением какой задачи?
НС>>Для чего того же? Для разворота списка? E>Очень трудно поймать чёрную кошку в тёмной комнате, особенно если её не ловить...
Т.е. ты не знаешь для чего?
НС>>Но обычно доступа по индексу и не нужно. E>Это можно интерпретировать так, что обычно алгоритмы, где таки нужно, программируют на более иных языках?..
Не перестаешь меня поражать вершинами своей логики.
НС>>Разумеется, абсолютно универсального рецепта нет. E>Ну вот я про то же самое, как бы...
Нет, ты про то что "С#-разрабы в массе своей не смогли разобраться в причинах проблемы и просто перестали использовать большие вектороподобные коллекции".
Здравствуйте, Evgeny.Panasyuk, Вы писали:
I>>То есть, оптимизировать без реальной на то обходимости ? "у нас небольшой List давайте заменим на flat_map, потому что асимптотика подходит"
EP>у flat_map вставка O(N)
То есть, даже рассуждения о прекрасном не помогают ?
>>>Но как это относится к данному топику? У нас же "огромные и ужасные List'ы" I>>Правильно. И ответ, на что менять List, дает ответ профайлер и требования, а не рассуждения о прекрасном.
EP>Профайлер дал ответ, что нужен random-access, что было ясно и без него(например, потому что реализуется heap), дальше что?
Профайлер должен сообщить следующе
1. время работы некоего алгоритма который использует коллекцию слишком велико
2. основное время работы это тот самый random-access
Вот тогда можно подбирать конкретную оптимизацию. И вот именно random-access как правило редкий случай, почти что экзотический. Там где он становится узким местом, почти наверняка проблема не в коллеции, а в платформе, если алгоритм верный. Чем тебе здесь дека поможет — совершенно не ясно.
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Нет, ты про то что "С#-разрабы в массе своей не смогли разобраться в причинах проблемы и просто перестали использовать большие вектороподобные коллекции".
"... и перестали строить боевых человекоподобных роботов-гигантов"
Здравствуйте, Ночной Смотрящий, Вы писали:
НС>Для чего того же? Для разворота списка?
Кстати, о развороте списка.
Насколько я понял из обсуждения, с фрагментацией всё будет плохо после того, как размер буфера перевалит несколько сотен метров, но в решении с листом, у нас же был лист ссылок, так что его размер буфера равнялся, как раз, издержкам твоего односвязного списка на ссылках, это если нет других накладных расходов на аллокацию. Кстати, они таки есть?
В любом случае, такое решение становится неработоспособно только тогда, когда уже и сам односвязный список слишком дорог, так как если элемент в нём больше, чем ссылка, то память закончится раньше, чем скажутся ограничения листа, а если меньше, то выходит, что там очень низкий кпд какой-то...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Evgeny.Panasyuk, Вы писали:
I>>Это может сказать только профайлер.
EP>Слушай, тут уже обсудили сложность вставки N элементов в std::vector-like без reserve, и ты уже проделал нелёгкий путь O(2^N) -> O(N^2) -> O(N*log(N)) -> O(N):
спокойно. к чему глумиться-то? Есть люди, которые могут оценить сложность алгоритма без профайлера, а есть, таки и такие, которые не могут.
Ну бывает жеж. Ну не всем же программистам обязательно иметь хоть какие-то знания по математике и информатике?
Некоторым не до того. Они повышают свою эффективность и изучают для этого ИНСТРУМЕНТЫ, которые РАЗГРУЖАЮТ голову, а не всякую математическу придурь (AKA колхоз), которая наоборот, голову ЗАГРУЖАЕТ.
Тоже подход, между прочим, и вовсе не всегда неправильный, кстати...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Ikemefula, Вы писали:
I>Не всех операций, а только критичных, что покажет __профайлер__. Вообще оптимизируются исключительно __узкие__ места, а не все подряд.
а пессимизируются, зато все? Или как? В целом, подход весьма экологичен, и мне нравится. Если какие-то операции, не дай Бог преждевременно оптимизируешь, то профайлер покажет, что остальные тормозят, и надо ускорять код, а вот если тормоза аккуратненько ровным слоем размазать, то профайлер "покажет", что тормозит сервер, и надо ускорять датацентр...
В целом прикольно, чё.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Ikemefula, Вы писали:
I>Другие операции тоже были нужны List был выбран 10 лет назад, только сначала это был ArrayList, потом поменяли из за дженериков, и только в 2012м году профайлер показал, что узкое место это коллекции. До этого были другие узкие места, что вполне объяснимо.
А как ты думаешь, тормоза из-за неадекватного выбора коллекции, возникли 0 лет назад, и только в 2012 тебе их удалось заметить профайлером, или сначала их не было?
А то может у вас там всё так же неадекватно было запрограммировано, и вы потом профайлером 10 лет выпрямляли изначально кривую архитектуру?..
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
