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

[Artem.spb]

Продолжу тему тестирования.
Задача: создать "ползущий массив", т.е. при обновлении данных выкинуть первый элемент из массива и добавить в конец новый. Библиотеки кольцевых буферов не использовал по ряду причин.
Задачу можно решить несколькими методами, и вот я наконец решил окончательно определиться, какой вариант работает быстрее.
Варианты:
Rotate array (на -1) + заменить последний элемент
Удалить (delete)нулевой + вставить (insert) (n-1)
Удалить (delete)нулевой + Build array
Split array (по индексу 1) + вставить (insert) (n-1)
Split array (по индексу 1) + Build array.

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

Реальность: всё совсем не так.

Вращение массива оказалось самым быстрым вариантом. Точно такой же по скорости - удаление+build
Непонятно, почему Build и Insert в разных комбинациях дают обратные результаты.

Вот код теста. Гонял на 2015. Может позже на 2018 прогоню.

[Borjomy_1]

Надо обращать внимание в том числе еще и на повторное использование памяти. Потому что от этого зависит время на ее выделение. Плюс фрагментация выделенной памяти со временем. Для приложений 23/7/365 это критично
Еще не рассмотрен вариант Build Array + Array Subset

[dadreamer]

Ещё было бы интересно рассмотреть варианты с участием In Place Element Structure, а также "прямую" работу с памятью (MoveBlock) (и как частный случай, вызовы CLFN без создания копий).

[Artem.spb]

Надо обращать внимание в том числе еще и на повторное использование памяти. Потому что от этого зависит время на ее выделение. Плюс фрагментация выделенной памяти со временем. Для приложений 23/7/365 это критично

Согласен, это одна из причин искать лучший вариант.
Но тут у меня иногда сомнения закрадываются. Да, в документации на версии ~5 строго рекомендовали на баловаться с выделением памяти, но в последние годы я не смог в разумных условиях создать ситуацию утечек.
В этот тесте за памятью строго не следил, да и тест прошёл довольно быстро, но роста занятой памяти не заметил.

Еще не рассмотрен вариант Build Array + Array Subset

почему бы и да

Ещё было бы интересно рассмотреть варианты с участием In Place Element Structure, а также "прямую" работу с памятью (MoveBlock) (и как частный случай, вызовы CLFN без создания копий).

In Place Element Structure можно, но по-моему тут оно бесполезно, потому что "на месте" не получится, массивы постоянно перевыделять нужно. Разве что поворот будет работать.
А последние два варианта мне не ведомы.

[Юрий]

Не смог перетащить Snippet. Не знаю для чего нужен Ваш массив, но я когда то использовал такой вариант.

СкользящийМассив.png (11.96 КБ) 2565 просмотров

[Artem.spb]

но я когда то использовал такой вариант.
СкользящийМассив.png

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

[Kosist]

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

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

[Borjomy_1]

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

[Artem.spb]

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

Пруфы есть? Опять же в доках читал, что так "нельзя" делать с while loop, а вот for знает количество итераций и может выделить массив заранее.
Тема очередного эксперимента

[Artem.spb]

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

Можно в 15, чтобы не пересобирать?

[Chupakabra]

Еще можно использовать очередь. Я тестировал на скорость заполнения: только добавление элементов (без изъятия) и считывание массива целиком в конце по сравнению с расширением массива с помощью build array. Build array оказался быстрее в несколько раз. Можно обойтись только одним блоком Lossy Enqueue Element
Прогнал данный тест для очереди. Добавление в очередь очень быстрое, быстрее всех предложенных вариантов, а вот извлечение массива (Get Queue Status ) если делать в каждом цикле очень медленное медленнее всех вариантов. В тесте не очевидно, где нужно извлекать массив. Если только во внешнем цикле, то работает быстрее всех, если в каждом вложенном цикле, то медленнее всех.

[Artem.spb]

Еще можно использовать очередь. ...Build array оказался быстрее в несколько раз.

Тогда зачем сравнивать, если Build array быстрее :)

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

[Artem.spb]

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

Мануалы бесконечно устарели. Даже while работает вполне шустро, хотя возможно, это потому что заранее известно количество шагов.
Но предварительное выделение массива нисколько не ускоряет дело. Возможно, дело в накладных расходах на сдвиговый регистр.

[Borjomy_1]

Еще можно использовать очередь. Я тестировал на скорость заполнения: только добавление элементов (без изъятия) и считывание массива целиком в конце по сравнению с расширением массива с помощью build array. Build array оказался быстрее в несколько раз. Можно обойтись только одним блоком Lossy Enqueue Element
Прогнал данный тест для очереди. Добавление в очередь очень быстрое, быстрее всех предложенных вариантов, а вот извлечение массива (Get Queue Status ) если делать в каждом цикле очень медленное медленнее всех вариантов. В тесте не очевидно, где нужно извлекать массив. Если только во внешнем цикле, то работает быстрее всех, если в каждом вложенном цикле, то медленнее всех.

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

[Borjomy_1]

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

Можно в 15, чтобы не пересобирать?