На самом деле, возможно, здесь больше подойдёт другой контейнер.
Инты в массиве могут идти с пропусками. Разница двух значений ключей прямо пропорциональна времени между их добавлением. (Но ключ -- не UNIX epoch time.)
Содержимое массива не изменяется. Кроме двух случаев:
1) Время от времени в массив, всегда в конец, добавляются новые объекты.
2) Есть поток (GC), который раз в N секунд откусывает у массива все устаревшие элементы — с ключами меньше некоторого значения. Как выбирается значение — не принципиально, если нужно, алгоритм его выбора можно поправить под решение. Этот поток синхронизирован с операцией добавления.
Массивом пользуются некоторое количество "читателей":
Читатель берёт некоторый элемент массива (чаще всего с самым большим ключом, но возможно и из середины) и делает несколько итераций в направлении уменьшения величины ключа. Допустимо запретить читать глубже некоторой заданной минимальной величины ключа.
Побочный вопрос: безопасно ли в отсутствии синхронизации читателя с процессом добавления элементов выбирать из массива начальную точку итерирования?
Очень хочется (из-за производительности) сделать чтобы процесс чтения не заботился о синхронизации с процессом сборки мусора. Можно конечно играть ограничением на минимальный ключ для чтения — сделав его, например, в два раза ближе к нам чем максимальный ключ на удаление (минимально допустимый период читаемости будет секунд тридцать). Но это (1) выглядит как-то подозрительно и (2) есть подозрение, что будет накапливаться слишком много объектов и GC будет недостаточно агрессивен...
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Очень хочется (из-за производительности)...
Мне просто интересно — действительно производительность не удовлетворительная получается или это просто из-за стремления к прекрасному?
Я не из тех, кто типа чуть заслышит про оптимизацию сразу кричит "преждевременная оптимизация, вы все ламеры, что что-то там оптимизируете, вот я ничего никогда не оптимизирую [гордый удар в грудь]" Я скорее даже наоборот. Но последнее время мне не так часто встречаются ситуации, когда производительность именно не удовлетворительная/не отвечает требованиям. Так что начинаешь чувствовать себя немного Дон Кихотом, сражающимся с ветреными мельницами
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Побочный вопрос: безопасно ли в отсутствии синхронизации читателя с процессом добавления элементов выбирать из массива начальную точку итерирования?
Нет. Если все только читают, то можно одновременно. Если хоть кто-то изменяет, то нельзя.
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Очень хочется (из-за производительности) сделать чтобы процесс чтения не заботился о синхронизации с процессом сборки мусора. Можно конечно играть ограничением на минимальный ключ для чтения — сделав его, например, в два раза ближе к нам чем максимальный ключ на удаление (минимально допустимый период читаемости будет секунд тридцать). Но это (1) выглядит как-то подозрительно и (2) есть подозрение, что будет накапливаться слишком много объектов и GC будет недостаточно агрессивен...
А в чём именно проблема?
Проблема в наличии периода взаимного исключения, когда читатели не могут читать?
Проблема в необходимости затрачивать такты на выполнение какой-то синхронизации каждый раз при начале чтения и завершении чтения?
Проблема в том, что решение не масштабируется на SMP системы?
Без этой информации нельзя ответить, т.к. ответы будут совершенно разными в зависимости от того, в чём именно проблема.
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Побочный вопрос: безопасно ли в отсутствии синхронизации читателя с процессом добавления элементов выбирать из массива начальную точку итерирования?
T_B>
T_B>Основной вопрос: T_B>Очень хочется (из-за производительности) сделать чтобы процесс чтения не заботился о синхронизации с процессом сборки мусора. Можно конечно играть ограничением на минимальный ключ для чтения — сделав его, например, в два раза ближе к нам чем максимальный ключ на удаление (минимально допустимый период читаемости будет секунд тридцать). Но это (1) выглядит как-то подозрительно и (2) есть подозрение, что будет накапливаться слишком много объектов и GC будет недостаточно агрессивен...
Типичная реализация std::map — бинарное дерево. При любой модификации, в т.ч. и при добавлении в конец может произойти перебалансировка этого дерева, а получение начального итератора, тем более, доступ по чтению произвольного ключа, сопряжено со спуском по этому дереву. Значит без синхронизации никак. Как я догадываюсь, ожидается, что чтение будет случаться на порядки чаще, чем модификация, правильно? Можно подумать в том направлении, чтобы смастерить "хитрую" синхронизациию, при которой писатели синхронизуются друг с другом и с читетелями, а читатели друг с другом не синхронизуются. Можно стандартный контейнер обернуть в собственную обертку, в которой начальный итератор будет кэшироваться, благо, после модификации std::map его итераторы остаются валидными (разумеется, при окусывании начального элемента кэш нужно будет "освежать").
... << RSDN@Home 1.2.0 alpha rev. 787>>
--
Не можешь достичь желаемого — пожелай достигнутого.
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Всем привет!
T_B>На самом деле, возможно, здесь больше подойдёт другой контейнер.
А может использовать гибрид очереди и вектора? например, кольцевой буфер с доступом по индексу в середину, как к вектору.
T_B>Инты в массиве могут идти с пропусками. Разница двух значений ключей прямо пропорциональна времени между их добавлением. (Но ключ -- не UNIX epoch time.)
То есть очередь получается сортированная по возрастанию.
T_B>Содержимое массива не изменяется. Кроме двух случаев: T_B>1) Время от времени в массив, всегда в конец, добавляются новые объекты. T_B>2) Есть поток (GC), который раз в N секунд откусывает у массива все устаревшие элементы — с ключами меньше некоторого значения. Как выбирается значение — не принципиально, если нужно, алгоритм его выбора можно поправить под решение. Этот поток синхронизирован с операцией добавления.
Натурально очередь и есть.
T_B>Массивом пользуются некоторое количество "читателей": T_B>Читатель берёт некоторый элемент массива (чаще всего с самым большим ключом, но возможно и из середины) и делает несколько итераций в направлении уменьшения величины ключа. Допустимо запретить читать глубже некоторой заданной минимальной величины ключа.
Здравствуйте, remark, Вы писали:
T_B>>Очень хочется (из-за производительности) сделать чтобы процесс чтения не заботился о синхронизации с процессом сборки мусора. Можно конечно играть ограничением на минимальный ключ для чтения — сделав его, например, в два раза ближе к нам чем максимальный ключ на удаление (минимально допустимый период читаемости будет секунд тридцать). Но это (1) выглядит как-то подозрительно и (2) есть подозрение, что будет накапливаться слишком много объектов и GC будет недостаточно агрессивен...
R>А в чём именно проблема? R>Проблема в наличии периода взаимного исключения, когда читатели не могут читать? R>Проблема в необходимости затрачивать такты на выполнение какой-то синхронизации каждый раз при начале чтения и завершении чтения? R>Проблема в том, что решение не масштабируется на SMP системы?
R>Без этой информации нельзя ответить, т.к. ответы будут совершенно разными в зависимости от того, в чём именно проблема.
В плане "преждевременной оптимизации" — пока что всё на стадии проектирования / прототипирования.
Система будет стоять под большой нагрузкой — поэтому есть желание сразу сделать всё максимально быстрым.
С другой стороны, в принципе, понятно как прозрачно масштабировать её на несколько машин — так что *безумные* средства в оптимизацию вкладывать не целесообразно.
Наверное, начну ещё раз, с более абстрактного уровня. Чего я хочу добиться:
1. Есть сортированный по времени набор данных: Временной тэг => Данные. Данные всегда добавляются в один конец ("свежий", по одной штуке), удаляются с другого конца ("старый", оптом, со временным тэгом меньше заданного) и читаются от свежих к старым. Специально не говорю "начало", поскольку данные можно расположить и по убыванию и по возрастанию — как будет удобнее при реализации.
"Временной тэг" — целое число, прямо пропорциональное прошедшему времени (в долях секунды, по прикидкам где-то 1/4). В общем случае тэги не идут подряд — но при необходимости можно добавлять данные-пустышки чтобы обеспечить непрерывность.
Выборка данных происходит минимум на порядок чаще чем их добавление. Удаление данных (GC) неприоритетно по производительности вообще — главное, чтобы данные не накапливались "чрезмерно" и процесс удаления не тормозил выборку.
Выборка в общем случае происходит от "середины" набора данных — но при необходимости можно ограничиться тем, что начинать её только от "свежего" конца (большая часть выборок всё так и происходит). При этом абсолютной свежести начала выборки не требуется — достаточно чтобы оно было "где-то около" свежих данных, допустимая погрешность -- один-два элемента тэга.
2. Удаление и добавление происходит из (ровно) двух отдельных потоков. Для облегчения реализации можно объединить потоки (но можно и не объединять).
3. Выборка происходит асинхронно из нескольких потоков (отдельных от потока удаления и потока добавления).
Вот, собственно, задача. Хочется в первую очередь максимально оптимизировать читателей.
Здравствуйте, Tuo_Bellas, Вы писали:
T_B>Что посоветуете?
Я так понимаю, что надо как-то сделать так, чтобы асинхронно добавлять записи, и асинхронно убирать их потом.
Для каждой операции предлагаю сделать независимую структуру.
Типа пока добавляешь всё складывается в какой-то буффер, который можно пополнять без синхронизации c читателями. То есть заводим критическую сессию и по ней добавляем.
Скажем что-то типа такого:
struct record_data{
int tag;
Bar data;
};
const int chunk_size = 1024; // Это число можно настроить, и можно, даже, довольно легко сделать динамическим.
// Главное не менять его по мере заполнения кусочкаtypedef std::map< int, record_data*, std::greater<int> > my_map_t;
struct storage_chunk {
storage_chunk* next;
bool is_frozen;
my_map_t frozen_data;
int count;
record_data buffer[chunk_size];
};
Теперь имеем указатель на storage_chunk, который указывает на 0-терминированный список chunks.
Процедура добавления синхронизируется критической сессией и действует так.
Смотрит на первый chunk в списке. Если он уже frozen, то заводит новый, пустой chunk, в его поле next пишет указатель на первый в списке, в поле count пишет 0.
После чего форсирует запись всего этого в память из кэша (например можно всегда иметь chunk "про запас", тогда скорее всего можно даже ничего и не форсировать)
После чего chunk можно публиковать (записать указатель на него в указатель на весь список).
Так что теперь можно считать, что первый chunk в спсиске не frozen.
Соответсвенно можно записать в buffer[count] данные, как-то озаботиться их выбросом в память, а потом сделать count++;
Ну и добавить свежедобавленную запись в frozen_data;
Теперь надо ещё проверить, что в chunk'е осталось свободное место. Если не осталось, то надо пометить его, как frozen. (Выброс этой метки в память можно и не форсировать, в принципе. Главное форсировать выброс самого map, но как это сделать -- , так что возможно дешевле сего просто подождать, перед тем, как помечать, как frozen )
Теперь, как писать читалку.
Это тривиально. Надо идти по списку, до 0, границы тэгов для каждого chunk определяются легко. Внутри chunk ищем бинарным поиском, если он ещё не frozen, и через map, если уже frozen.
Ну а как писать GC -- тоже понятно. Где-то в GC есть массив storage_chunk*
Когда приходит время, мы помещаем в соответсвующее поле next ещё остающегося в списке chunk 0, и как-то форсируем его выброс в память и подождать какое-то время, пока не закончатся те, кто ещё идёт по списку.
Ну а потом просто грохаем chunk выведенный таким образом из общественного использования.
Вроде бы нигде никого ждать не надо, только добавлятелям прийдётся ждать друг-друга, но я так понял, что добавляете вы несколкьо раз в секунду, так что коллизий быть не должно бы...
Да и подождать нежалко вроде как... Ресурсы-то не тратятся...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Garrett, Вы писали:
G>Здравствуйте, Tuo_Bellas, Вы писали:
T_B>>Всем привет!
T_B>>На самом деле, возможно, здесь больше подойдёт другой контейнер. G>А может использовать гибрид очереди и вектора? например, кольцевой буфер с доступом по индексу в середину, как к вектору.
Кольцевой буфер не избавляет от необходимости взаимного исключения. В чём выгода?
Здравствуйте, Erop, Вы писали:
E>Ну а как писать GC -- тоже понятно.
Имхо это как раз единственный стоящий вопрос здесь.
Особенно смотри выделенное:
E>Когда приходит время, мы помещаем в соответсвующее поле next ещё остающегося в списке chunk 0, и как-то форсируем его выброс в память и подождать какое-то время, пока не закончатся те, кто ещё идёт по списку. E>Ну а потом просто грохаем chunk выведенный таким образом из общественного использования.
T_B>Наверное, начну ещё раз, с более абстрактного уровня. Чего я хочу добиться:
Ок. Ещё один вопрос — кол-во читающих потоков постоянно или они могут создаваться и уничтожаться во время работы? Это не очень принципиальный вопрос, но в первом случае можно сделать значительно более простую и чистую реализацию.
Нужен список и синхронизация "один писатель-много читателей".
Можно завести два списка — "чистый", с которым работают читатели. И "грязный", в который происходит добавление новых и удаление старых. После обработки "грязного" списка просходит переключение между ними. Переключение можно произвести быстро. После чего GC может сразу добавлять новые элементы в "грязный" список, а для удаления старых надо ждать, пока читатели закончат работу с "грязным" списком (как я понял, производительность удаления непринципиальна) и перейдут на новый.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, Garrett, Вы писали:
G>>Здравствуйте, Tuo_Bellas, Вы писали:
T_B>>>Всем привет!
T_B>>>На самом деле, возможно, здесь больше подойдёт другой контейнер. G>>А может использовать гибрид очереди и вектора? например, кольцевой буфер с доступом по индексу в середину, как к вектору.
R>Кольцевой буфер не избавляет от необходимости взаимного исключения. В чём выгода?
Эээ.. под взаимным исключением имеется в виду синхронизация доступа к элементам буфера?
Тут надо смотреть, что на самом деле делают читатели. Если они только читают, не изменяя сами данные — то голову очереди, где работает GC, накрываем критической секцией или мутексом, границу передвигаем вперед по мере работы GC. Доступ к элементам в середине, получается, синхронизировать не надо — мы только читаем. За исключением случаев, когда мы переаллоцируем буфер — ну тут вообще все сложно, лучше такого не допускать. Хвост очереди можно тоже накрыть синхронизацией, если только добавление не сделано атомарной операцией.
Если они не только читают, но еще и изменяют — тут уже надо выкручиваться. Можно разбить буфер на куски и синхронизировать не доступ к буферу как к целому, а к каждому куску.
Повторюсь — все это имеет смысл городить, когда мы знаем, что данные добавляются уже отсортированными.
Здравствуйте, Garrett, Вы писали:
G>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, Garrett, Вы писали:
G>>>Здравствуйте, Tuo_Bellas, Вы писали:
T_B>>>>Всем привет!
T_B>>>>На самом деле, возможно, здесь больше подойдёт другой контейнер. G>>>А может использовать гибрид очереди и вектора? например, кольцевой буфер с доступом по индексу в середину, как к вектору.
R>>Кольцевой буфер не избавляет от необходимости взаимного исключения. В чём выгода? G>Эээ.. под взаимным исключением имеется в виду синхронизация доступа к элементам буфера? G>Тут надо смотреть, что на самом деле делают читатели. Если они только читают, не изменяя сами данные — то голову очереди, где работает GC, накрываем критической секцией или мутексом, границу передвигаем вперед по мере работы GC.
Ну хорошо, границу передвинули. А как узнать, когда все читатели заметили это передвижение границы и уже не работают с элементами, которые оказались за границей?
Любое решение этой проблемы можно переложить и на вариант со списком. Использование кольчевого буфера ничего не даёт в данной ситуации.
G>Можно разбить буфер на куски и синхронизировать не доступ к буферу как к целому, а к каждому куску.
Фактически это уже не кольцевой буфер, а тот же связанный список (пусть даже и гнездовой).
Здравствуйте, rus blood, Вы писали:
RB>Нужен список и синхронизация "один писатель-много читателей".
Тут будет зависеть от длины списка и работы, выполняемой с элементами читателями.
Зачастую, самые лучшие реализации reader_writer_mutex, работают медленнее и масштабируются хуже, чем простейший спин мьютекс с пассивным спином.
RB>Можно завести два списка — "чистый", с которым работают читатели. И "грязный", в который происходит добавление новых и удаление старых. После обработки "грязного" списка просходит переключение между ними. Переключение можно произвести быстро. После чего GC может сразу добавлять новые элементы в "грязный" список, а для удаления старых надо ждать, пока читатели закончат работу с "грязным" списком (как я понял, производительность удаления непринципиальна) и перейдут на новый.
Здравствуйте, remark, Вы писали:
RB>>Можно завести два списка — "чистый", с которым работают читатели. И "грязный", в который происходит добавление новых и удаление старых. После обработки "грязного" списка просходит переключение между ними. Переключение можно произвести быстро. После чего GC может сразу добавлять новые элементы в "грязный" список, а для удаления старых надо ждать, пока читатели закончат работу с "грязным" списком (как я понял, производительность удаления непринципиальна) и перейдут на новый.
R>Самый интересный момент выделен. Как?
Под win — interlocked-счетчик читалей с manual-ивентом.
На "грязном" списке счетчик будет работать только на уменьшение.
Здравствуйте, rus blood, Вы писали:
RB>Здравствуйте, remark, Вы писали:
RB>>>Можно завести два списка — "чистый", с которым работают читатели. И "грязный", в который происходит добавление новых и удаление старых. После обработки "грязного" списка просходит переключение между ними. Переключение можно произвести быстро. После чего GC может сразу добавлять новые элементы в "грязный" список, а для удаления старых надо ждать, пока читатели закончат работу с "грязным" списком (как я понял, производительность удаления непринципиальна) и перейдут на новый.
R>>Самый интересный момент выделен. Как?
RB>Под win — interlocked-счетчик читалей с manual-ивентом. RB>На "грязном" списке счетчик будет работать только на уменьшение.
Ок. Но это будет InterlockedIncrement/InterlockedDecrement на каждое чтение. Мьютекс дешевле.
Здравствуйте, remark, Вы писали:
R>Особенно смотри выделенное:
E>>пока не закончатся те, кто ещё идёт по списку.
R>
В общем случае да. Но, насколько я понял автора вопроса, ему пофиг насколько быстро сработает GC, главное чтобы сработал.
Если читатели могут работать быстро (например копировать к себе все данные и отваливаться), то можно просто подождать.
Я так понял, что читатели быстрые, добавляют запись несколько раз в секунду, а GC работает разы в час. Так что можно на кажлм шаге работы GC грохать chunks, которые уже были помещены в буфер на удаление, и потом добавлять туда новые (если уже пршла пора)
Так что у читателя будет минимум десять минут на выполнение своей быстрой операции...
Не абсолютная гарантия, конечно, но, зато, можно не синхронизировать читателей...
Кроме того, в читателе можно просто явно замерять время, в течении которого мы уже читаем, и если читаем дольше минуты, скажем, или там секунды (главное что время это меньше времени между двумя запусками GC), то искать текущую позицию читателя с начала спсика.
Хотя в описанной задаче есть и более простое решение.
Можно иметь глобальное значение (самый ранний валидный тэг), обновлять его при помещении chunk в карантин GC, и тормозить читателя, если он хочет читать более ранние тэги.
(в абстрактном смысле, так как именно пиво я не пью )
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, remark, Вы писали:
R>>>Кольцевой буфер не избавляет от необходимости взаимного исключения. В чём выгода? G>>Эээ.. под взаимным исключением имеется в виду синхронизация доступа к элементам буфера? G>>Тут надо смотреть, что на самом деле делают читатели. Если они только читают, не изменяя сами данные — то голову очереди, где работает GC, накрываем критической секцией или мутексом, границу передвигаем вперед по мере работы GC.
R>Ну хорошо, границу передвинули. А как узнать, когда все читатели заметили это передвижение границы и уже не работают с элементами, которые оказались за границей?
По условию GC у нас — неторопливый, так что он вполне может обождать, пока элемент, на который он собирается распространить влияние, выйдет из-под влияния читателей. Кроме того, они могут продолжать с ними работать, но уже под чутким наблюдением GC.
R>Любое решение этой проблемы можно переложить и на вариант со списком. Использование кольчевого буфера ничего не даёт в данной ситуации.
Я не настаиваю на кольцевом буфере, это просто первый способ, который пришел мне в голову. А в списке сложнее сделать быстрый поиск.
Здравствуйте, Garrett, Вы писали:
G>Здравствуйте, remark, Вы писали:
R>>>>Кольцевой буфер не избавляет от необходимости взаимного исключения. В чём выгода? G>>>Эээ.. под взаимным исключением имеется в виду синхронизация доступа к элементам буфера? G>>>Тут надо смотреть, что на самом деле делают читатели. Если они только читают, не изменяя сами данные — то голову очереди, где работает GC, накрываем критической секцией или мутексом, границу передвигаем вперед по мере работы GC.
R>>Ну хорошо, границу передвинули. А как узнать, когда все читатели заметили это передвижение границы и уже не работают с элементами, которые оказались за границей? G>По условию GC у нас — неторопливый, так что он вполне может обождать, пока элемент, на который он собирается распространить влияние, выйдет из-под влияния читателей. Кроме того, они могут продолжать с ними работать, но уже под чутким наблюдением GC.
Проблема в том, что это касается не только потока GC. Ты не можешь это сделать без какого-либо вовлечения читателей. А это может сводить на нет всю идею и сделать этот вариант медленнее чем простой мьютекс.
Я скорее даже наоборот. Но последнее время мне не так часто встречаются ситуации, когда производительность именно не удовлетворительная/не отвечает требованиям. Так что начинаешь чувствовать себя немного Дон Кихотом, сражающимся с ветреными мельницами 
, так что возможно дешевле сего просто подождать, перед тем, как помечать, как frozen 
