Ползущий массив (сравнение скоростей)

[Artem.spb]

Добавьте еще один вариант для сравнения. Характеризуется принципиальным отсутствием перевыделения памяти.

Дорабатываю тест, чтобы он был больше приближен к реальности (описал пару постов ранее).

11.png (11.94 КБ) 1858 просмотров

Не могу понять, откуда в вашем варианте брать выборку

[Artem.spb]

Добавил Build+subset и в каждом прогоне из буфера извлекаю последние 1000 значений (как бы на графике отображаю).
in place вообще никак не повлияло на результаты. кривые полностью совпадают, поэтому отключил их
Build+subset идёт по центру (фиолетовая), в остальном результаты прежние - быстрее всего вращать массив, или удалять нулевой и прибавлять в конец новый.

[Юрий]

Но для тестовых условий он не подходит, т.к. массив не ползёт.

Я не зря оговорился о том для чего нужен такой ползущий массив. Вот, например, оперативное преобразование фурье для одной гармоники. Традиционно надо бы как раз такой массив и использовать. Но вот оптимизированный рабочий вариант, в котором используется упомянутое мной заполнение массива. В этой трактовке его тоже можно назвать ползущим.

2021-12-09_233150.png (8.26 КБ) 1842 просмотра

А что касается в выборке из массива нужной части, то по отношению к моему вариану это вопрос только индексации.

[Artem.spb]

А что касается в выборке из массива нужной части, то по отношению к моему вариану это вопрос только индексации.

В моём понимании это и есть кольцевой буфер.
Вы можете привести "простой" пример выборки из него произвольного фрагмента? Например, когда начало фрагмента в конце массива, а его хвост в начале.
Меня смущает только заморочность этой части, в остальном "всё прекрасно"

[Borjomy_1]

Добавьте еще один вариант для сравнения. Характеризуется принципиальным отсутствием перевыделения памяти.

Дорабатываю тест, чтобы он был больше приближен к реальности (описал пару постов ранее).
11.png

Не могу понять, откуда в вашем варианте брать выборку

Сдвиговые регистры:
Буфер in - основной циклический буфер
Буфер out - текущая выборка

[ujin1]

Прогноз: проворачивать массив - одно из самых долгих дел. Тут или поэлементное копирование, или выделение нового буфера и перенос туда.
Split array должен работать быстро, потому что массивы можно оставить на месте, просто добавить ещё одну ссылку (на вторую часть).

Указатель начала занимаемой области памяти, размер занимаемой области памяти, указатель начала массива, указатель конца массива (в пределах занимаемой области)
Для проворота достаточно изменить указатели начала и конца массива. И не запутаться с переносом из начального в конечный адрес или наоборот.
На ассемблере когда программировал так делал. Это к тому, что копировать необязательно.

[Borjomy_1]

Прогноз: проворачивать массив - одно из самых долгих дел. Тут или поэлементное копирование, или выделение нового буфера и перенос туда.
Split array должен работать быстро, потому что массивы можно оставить на месте, просто добавить ещё одну ссылку (на вторую часть).

Указатель начала занимаемой области памяти, размер занимаемой области памяти, указатель начала массива, указатель конца массива (в пределах занимаемой области)
Для проворота достаточно изменить указатели начала и конца массива. И не запутаться с переносом из начального в конечный адрес или наоборот.
На ассемблере когда программировал так делал. Это к тому, что копировать необязательно.

Недостаточно. Потому что используется все равно копия. И массивы простых типов хранятся в памяти последовательно, без указателей на каждый элемент массива.

[Artem.spb]

Указатель начала занимаемой области памяти, размер занимаемой области памяти, указатель начала массива, указатель конца массива (в пределах занимаемой области)

Зачем указатель на конец?
начало, размер (тип) элемента, длина массива (В штуках).

При разбивке на два, я бы в исходном поменял длину, второму назначил новый указатель с середины исходного. Копировать ничего не нужно.

[Chupakabra]

Конкретизирую задачу.
Массив - это буфер, который копит историю значений за несколько часов. И при каждом добавлении элемента из буфера надо взять фрагмент неопределённой длины и из неопределённого места. Сколько и откуда - зависит от того, что просматривает пользователь. Может пару минут в самом конце смотрит, а может весь график. Поэтому очереди при видимом удобстве не подходят - придётся извлекать весь массив и брать из него фрагмент.

Есть еще такая штука In-Memory SQLite. По скорости ничего не скажу, нужно пробовать. Но можно временные ряды хранить в памяти и извлекать со всеми плюшками sql.

[Artem.spb]

Есть еще такая штука In-Memory SQLite. По скорости ничего не скажу, нужно пробовать. Но можно временные ряды хранить в памяти и извлекать со всеми плюшками sql.

Крайне странная, но интересная идея. Я In-Memory использовал для быстрых нестандартных поисков, а вот для буферов - идея не возникала.

[Юрий]

Вы можете привести "простой" пример выборки из него произвольного фрагмента? Например, когда начало фрагмента в конце массива, а его хвост в начале.

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

Если быстродействие желательно иметь максимальным, а двойной размер массива приемлем, то возможен такой вариант:

И здесь в полной мере видна истина: "Выигрываеш в быстродействии - проигрываеш в памяти и наоборот".

[Artem.spb]

Есть еще такая штука In-Memory SQLite. По скорости ничего не скажу, нужно пробовать. Но можно временные ряды хранить в памяти и извлекать со всеми плюшками sql.

лень
начал было делать, и почти сразу "да ну нафиг". Во-первых, надо отслеживать индексы в самой базе. Тут, конечно, может быть упрощение в случае поиска по времени, а не просто по индексам.
Дальше, работа со строками "where id = %d" - явно не самые быстрые операции, так что даже не стал заморачиваться

[Artem.spb]

Сдвиговые регистры:
Буфер in - основной циклический буфер
Буфер out - текущая выборка

Встроил в тестирование, но всё же выделение массива оставил, т.к. предполагается постоянное копирование выборки на график.

Если быстродействие желательно иметь максимальным, а двойной размер массива приемлем, то возможен такой вариант:

И здесь в полной мере видна истина: "Выигрываеш в быстродействии - проигрываеш в памяти и наоборот".

А вот это оказалось фантастически привлекательной идеей.

Итак, третий раунд тестирования, in place убрал, потому что толку от него никакого, только в предпоследний метод добавил, но в данном случае стало только хуже (самая верхняя кривая).
Вообще, этот кольцевой буфер оказался самым неудачным вариантом. Подозреваю, из-за поэлементного копирования.
А вот двойной перерасход памяти дал просто фантастическую скорость работы.

[ujin1]

Указатель начала занимаемой области памяти, размер занимаемой области памяти, указатель начала массива, указатель конца массива (в пределах занимаемой области)

Зачем указатель на конец?
начало, размер (тип) элемента, длина массива (В штуках).

При разбивке на два, я бы в исходном поменял длину, второму назначил новый указатель с середины исходного. Копировать ничего не нужно.

На ассемблере так было удобней. Да и тип был только один - int8.

[ujin1]

Если быстродействие желательно иметь максимальным, а двойной размер массива приемлем, то возможен такой вариант:

Гениально.
Делал график. Начальная загрузка с базы данных значений за выбранный период (обычно час) чтобы сразу история появлялась. А далее подгрузка недостающих значений с этой же базы. Теперь таких графиков открыто много и можно сократить загрузку процессора. Памяти как раз хватает.