Кольцевой буфер: недостатки при перемещении памяти назад?

Question

Кольцевой буфер: недостатки при перемещении памяти назад?

Возможно, это не зависит от языка, но я спрашиваю об истории C ++.

Я взломал кольцевой буфер для встроенной системы (AVR, 8-разрядный). Давайте предположим:

const uint8_t size = /* something > 0 */;
uint8_t buffer[size];
uint8_t write_pointer;

Там это аккуратный трюк &указатели записи и чтения с size-1 сделать эффективный ролловер без ответвлений, если буфер size это степень двойки, вот так:

// value = buffer[write_pointer];
write_pointer = (write_pointer+1) & (size-1);

Однако, если размер не является степенью двойки, запасной вариант, вероятно, будет сравнивать указатель (то есть индекс) с размером и выполнять условный сброс:

// value = buffer[write_pointer];
if (++write_pointer == size) write_pointer ^= write_pointer;

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

Это предполагает, однако, что указатели должны двигаться вперед в памяти. Хотя это интуитивно понятно, это требует нагрузки size в каждой итерации. Я предполагаю, что в обратном порядке (продвижение назад) даст лучшие инструкции процессора (т.е. jump if not zero) в обычном случае, так как size требуется только во время сброса.

// value = buffer[--write_pointer];
if (write_pointer == 0) write_pointer = size;

так

TL; DR: мой вопрос: Влияет ли обратный переход по памяти на время выполнения из-за пропусков кэша (поскольку память не может быть просто прочитана вперед), или это допустимая оптимизация?

1

avr c++circular-buffer embedded language-agnostic

Решение

Другие решения

Оказывает ли движение назад по памяти негативное влияние на
время выполнения из-за отсутствия кэша (так как память не может быть просто прочитана
вперед)

Почему вы думаете, что у вас будет пропустить кэш? Если вы попытаетесь получить доступ вне кеша (вперед или назад), вы потеряете кеш.

0

Есть ряд моментов, которые требуют уточнения:

Этот размер необходимо загружать каждый раз (он постоянный, поэтому должен быть неизменным)
Это твой код правильный. Например, в индексе на основе 0 (как используется в C / C ++ для доступа к массиву) значение 0' is a valid pointer into the buffer, and the valueразмер «нет. Точно так же нет необходимости xor когда вы могли бы просто назначить 0одинаково по модулю будет работать оператор (writer_pointer = (write_pointer +1) % size).
Что происходит в общем случае с виртуальной памятью (т. Е. Логически смежные адреса могут быть повсюду на реальной карте памяти), подкачкой страниц (вещи могут быть кэшированы постранично) и другими факторами (давление со стороны внешние процессы, прерывания)

Вкратце: это тот тип оптимизации, который приводит к большему количеству травм, связанных с ногами, чем к подлинным улучшениям производительности. Кроме того, это почти наверняка тот случай, когда вы получаете намного, гораздо лучшие выгоды, используя векторизованный код (SIMD).

РЕДАКТИРОВАТЬ: И в интерпретируемых или JIT-языках может быть немного оптимистичным предположить, что вы можете положиться на использование из JNZ и другие вообще. В этот момент вопрос в том, насколько велика разница между loading size и сравнивая и сравнивая с 0,

0

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

Таким образом, ваш вопрос наполнен различными странными предположениями:

Во-первых, вы предполагаете, что write_pointer = (write_pointer+1) & (size-1) более эффективен, чем что-либо еще, например, пример XOR, который вы опубликовали. Здесь вы только догадались, вам придется разобрать код и посмотреть, какие из них дают меньше инструкций процессора.

Потому что при написании кода для крошечного, примитивного 8-битного MCU в ядре мало что происходит для ускорения вашего кода. Я не знаю AVR8, но кажется, что у вас есть небольшой канал инструкций и все. Кажется маловероятным, что у вас есть много способов прогнозирования ветвлений. Похоже на то очень маловероятно, что у вас есть кеш данных и / или инструкций. Прочитайте дружественное руководство по ядру процессора.
Что касается движения назад по памяти, оно вряд ли окажет какое-либо влияние на производительность вашей программы. На старых дрянных компиляторах вы получили бы немного более эффективный код, если бы условие цикла было сравнением с нулем вместо значения. На современных компиляторах это не должно быть проблемой. Что касается проблем с кеш-памятью, я сомневаюсь, что у вас есть кеш-память для беспокойства.

Лучший способ написать эффективный код на 8-битных MCU — это по возможности придерживаться 8-битной арифметики и избегать 32-битной арифметики, такой как чума. И забудьте, что вы когда-либо слышали о чем-то, что называется плавающей точкой это это то, что сделает вашу программу эффективной, вы вряд ли найдете лучший способ вручную оптимизировать ваш код.

0

Источник

Accepted Answer

У вас 8 битный avr с кешем? А ветка предсказания?

Какое значение имеют значения «вперед» или «назад» для кэшей? Попадание или нехватка кеша происходит где угодно в пределах строки кеша, начало, середина, конец, случайный, последовательный, значения не имеет. Вы можете работать от начала до конца или от передней части к задней части строки кэша, это та же самая стоимость (при условии, что все остальное остается неизменным), первый туман вызывает заполнение, затем эта строка находится в кэше, и вы можете получить доступ к любому из предметов в любом образце с более низкой задержкой, пока не будут выселены.

На таком микроконтроллере вы хотите приложить усилия, даже ценой потери некоторой памяти, для выравнивания кругового буфера таким образом, чтобы его можно было замаскировать. Кеша нет, выборки инструкций болезненны, потому что, скорее всего, они происходят из флэш-памяти, которая может быть медленнее тактовой частоты процессора, поэтому вы хотите уменьшить количество выполненных инструкций или сделать их выполнение чуть более детерминированным (одинаковое количество команд в каждом цикле). пока эта задача не будет выполнена). Возможно, существует конвейер, который оценит маскировку, а не «если-то-еще».

TL; DR: Мой вопрос: есть ли движение назад по памяти?
отрицательное влияние на время выполнения из-за отсутствия кэша (так как
память не может быть просто прочитана) или это действительная оптимизация?

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

3