monah_tuk Apr 7 2014 at 11:29

C++ и копирование перекрывающихся областей памяти

3 min

25K

Programming*C++*

Tutorial

From sandbox

+30

Comments 16

Lockal Apr 7 2014 at 13:00

Стоит заметить, что компиляторы (по крайней мере gcc и clang) в состоянии сами переделать memmove в memcpy, если известно, что блоки не пересекаются (например, благодаря restrict).

До С++11 было достаточно проблематично специализировать шаблонную функцию std::copy на вызов memcpy/memmove из-за отсутствия is_trivially_copy_assignable (и средств на поднятие).

А ещё std::copy_backward перед вызовом memmove проверяет размер копируемого участка на 0, что негативно отражается на оптимизации.

monah_tuk Apr 7 2014 at 14:36

До С++11 было достаточно проблематично специализировать шаблонную функцию std::copy на вызов memcpy/memmove из-за отсутствия is_trivially_copy_assignable (и средств на поднятие).

Согласен, но это можно было обойти (частично) за счёт, хотя бы, специализации шаблонов для всех примитивных типов, или использовать методы типы бустовского has_trivial_copy/has_trivial_assign.

А ещё std::copy_backward перед вызовом memmove проверяет размер копируемого участка на 0, что негативно отражается на оптимизации.

Да, пришлось покликать пока нашёл это место.

В любом случае, эти алгоритмы хороши как generic-решение. Если копирование занимает мизирную долю времени выполнения алгоритма в котором они применены. Если же просадка по скорости ощутима, то тут уже нужно думать об оптимизации. А иначе есть опасность закопаться в мелочах, как описано в соседней статье: habrahabr.ru/post/218345/

Hertz Apr 7 2014 at 13:51

В стандарте C++11 есть std::move и std::move_backward, занимающиеся именно перемещением.

monah_tuk Apr 7 2014 at 14:40

Как оно ловко замаскировалось за своим тёской из utility… Спасибо, у меня опыта промышленной разработки на C++11 вообще нет, старым embedded проектам не до него, так что щупаю на фрилансе, судя по всему щупать ещё долго придётся.

monah_tuk Apr 9 2014 at 06:24

Да, кстати, почитал. Отличие std::move от std::copy, в том, что тут происходит именно перемещение, грубо, с использованием перемещающего конструктора/оператора присваивания. Сравните метакод для std::copy и std::move:
www.cplusplus.com/reference/algorithm/move/
www.cplusplus.com/reference/algorithm/copy/
отличие в одной строчке

Это я к чему, а к тому, что в поведении этих функций нет ничего общего с memmove() — она, несмотря на своё название, не делает перемещения, а так же делает копирование, но отрабатывает корректно ситуацию для пересекающихся областей: manned.org/memmove.3. Но в части оптимизации помнить о них стоит, особенно когда нужно подвинуть массивы не POD элементов.

Hertz Apr 9 2014 at 10:33

Действительно, неверно было приводить std::move как аналог memmove, move_backward вообще очень специфично выглядит. Но и в моих задачах пока не встречалась необходимость двигать значения non-trivially copyable типов.
В псевдокоде именно перемещающий оператор присваивания.
Корректнее будет сказать «массивы не TriviallyCopyable элементов» :-)

monah_tuk Apr 9 2014 at 10:58

Корректнее будет сказать «массивы не TriviallyCopyable элементов» :-)

совершенно верно

Noospheratu Apr 7 2014 at 14:06

Напрашивается класс, который сам принимает решение на основе аргументов и пользуется соответствующими методами или std::move, или std::move_backward.

monah_tuk Apr 7 2014 at 14:51

Во всех случаях, когда мне это было нужно, можно было спрогнозировать, что использовать: copy/copy_backward/mempcy/memmove, так что по-ситуации.

Noospheratu Apr 7 2014 at 17:12

Согласен с Вами. В единичных случаях можно прогнозировать самому, ну а если надо будет массово эти операции проводить — лучше освободить ум для более интеллектуальных вещей.

Gariks Apr 7 2014 at 16:10

ИМХО для задачи с MPEG использовал бы MMF (memory mapped files), искал бы нужную сигнатуру начала блока в памяти, далее копирование в выделенный или подготовленный буфер, нужного участка, обработка.
Как то не оптимально сначала копировать, потом искать что нужно было скопировать… Ну это я придираюсь, статья то не об этом.

monah_tuk Apr 8 2014 at 01:58

Да, для файла на диске я бы так и поступил, но у меня стрим, который сейчас принимается по пайпу, возможно нужно будет читать udp-multicast. Насколько я знаю, mmap() применять тут не совсем корректно.

Gariks Apr 8 2014 at 22:36

Не знаю специфики задачи, но если есть «бесконечный» буфер, когда не известен размер получаемых/обрабатываемых данных использую временные файлы (temporary file). В системе Windows временный файл, это по сути тот-же MMF, но если его размер превышает размер виртуального адресного пространства, он скидывается на диск. Про *nix не знаю.

Алгоритм получается такой: получили в буфер пакет, нашли сигнатуру начала и его длину, создали временный файл, записали туда данные, получили в буфер следующий пакет, во временный скинули данные. Пакет закончился, переместили курсор на начала файла, размер нам известен — анализируем. Ну и так как временный файл = память (для ОС Windows) — все работает быстро.

monah_tuk Apr 9 2014 at 04:29

В таком подходе я вижу только 1 плюс: всегда чтение идёт блоками фиксированной длинны, не приходится делать дочитывать данные более мелкими кусками. Почему только один? Потому, как в этом месте:

создали временный файл, записали туда данные

будет то же самое копирование памяти (если ваше утверждение про «временный файл = память (для ОС Windows)» верно, сам не могу о том судить, т.к. не имею опыта разработки под Windows).

Если обойтись без временного файла, а использовать просто второй буфер, то мы можем вообще не задумываться о применении алгоритма.

Плюс не забываем о буфферизации у fopen/fread, fistream, вычитывание малыми кусками здесь может вообще никак не проявиться.

Да, было бы интересно сравнить быстродействие.

Gariks Apr 9 2014 at 16:59

просто второй буфер

Какого размера? Ведь размер получаемых данных заранее не известен (исходя из условия задачи).

По поводу буферизации чтения записи, это тема отдельного разговора (http://msdn.microsoft.com/en-us/library/windows/desktop/cc644950(v=vs.85).aspx), особенно если дело касается асинхронности.

monah_tuk Apr 10 2014 at 01:17

Какого размера? Ведь размер получаемых данных заранее не известен (исходя из условия задачи).

Я окончательно запутался. В винде можно создавать memory-mapped файлы бесконечного/неизвестного размера? Если нет, то что файл, что вспомогательные буффер должны быть под размер пакета, в данном случае 188 байт. Попробую в псевдокоде:

uint8_t inbuffer[PKT_SIZE];
uint8_t tmpbuffer[PKT_SIZE];

while есть данные {
    stream.read(inbuffer, PKT_SIZE);
    offset = search_sync(inbuffer);
    std::copy(inbuffer + offset, inbuffer + PKT_SIZE, tmpbuffer);
    
    if offset > 0 {
        stream.read(inbuffer, PKT_SIZE);
        std::copy(inbuffer, inbuffer + (PKT_SIZE - offset), tmpbuffer + PKT_SIZE - offset);
        process(tmpbuffer);
        // тут что-то делаем с остатками в inbuffer
    } else {
        process(tmpbuffer);
    }
}

по сути, тут везде, где стоит

std::copy

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