Репутація українського ІТ. Пройти опитування Асоціації IT Ukraine
×Закрыть

Оптимизировать С код

Подскажите, а можно-ли оптимизировать следующий С код (SSE, AVX).

void mtlb2opcv(uint8_t* dst, uint8_t* src, size_t sz_r, size_t sz_c)
{
	uint8_t* mat_temp_ptr = NULL;

	const long layer_size = sz_r*sz_c;

	for (int ch = 0; ch<3; ch++)
	{
		mat_temp_ptr = src + ch*layer_size;
		int rd = 2 - ch;
		for (size_t c = 0; c < sz_c; c++)
		{
			for (size_t r = 0; r < sz_r; r++)
			{
				size_t id = (r*sz_c+c)*3+rd;
				size_t is = c*sz_r+r;
				dst[id] = mat_temp_ptr[is];
			}
		}
	}
}

Это код конвертации изображения из матлаба в OpenCV формат.
Фактически изображения в матлабе лежит по слоям и в каждом слое по столбцам.
В OpenCV по строкам и цвета пикселя последовательно.

Нюанс, порядок слоев в матлабе RGB, а в OpenCV стандартно BGR.

Этот код работает в 40 раз дольше, чем последовательное копирования того же объема данных с использованием AVX.
Понятно, что граница данных выравнена.

Update:
Вот что получилось

inline void mtlb2opcv_8UC3(uint8_t * const dst, const uint8_t * const src, const size_t sz_r, const size_t sz_c)
{
	const size_t layer_sz = sz_r*sz_c;

	const uint8_t * layer_r = src;
	const uint8_t * layer_g = layer_r + layer_sz;
	const uint8_t * layer_b = layer_g + layer_sz;
	const size_t n = 8;
	const size_t sz_rem = sz_c/n*n;

	for (size_t c = 0; c < sz_rem; c+=n)
	{
		for (size_t r = 0; r < sz_r; r++)
		{
			const size_t _id = (r*sz_c+c)*3;
			for(size_t i=0; i<n; ++i)
			{
				const size_t id = _id+i*3;
				const size_t is = (c+i)*sz_r+r;
				dst[id+0] = layer_b[is];
				dst[id+1] = layer_g[is];
				dst[id+2] = layer_r[is];
			}
		}
	}
	for (size_t c = sz_rem; c < sz_c; c++)
	{
		for (size_t r = 0; r < sz_r; r++)
		{
			const size_t id = (r*sz_c+c)*3;
			const size_t is = c*sz_r+r;
			dst[id+0] = layer_b[is];
			dst[id+1] = layer_g[is];
			dst[id+2] = layer_r[is];
		}
	}
}
Это работает 15ms против того что вверху ~70 ms на FX-8320 на 1920×1080×3.
И
inline void opcv2mtlb_8UC3(uint8_t * const dst, const uint8_t * const src, const size_t sz_r, const size_t sz_c)
{
	const size_t layer_sz = sz_r*sz_c;

	uint8_t * layer_r = dst;
	uint8_t * layer_g = layer_r + layer_sz;
	uint8_t * layer_b = layer_g + layer_sz;
	const size_t n = 4;
	const size_t sz_rem = sz_c/n*n;

	for (size_t c = 0; c < sz_rem; c+=n)
	{
		for (size_t r = 0; r < sz_r; r++)
		{
			const size_t _id = (r*sz_c+c)*3;
			for(size_t i=0; i<n; ++i)
			{
				const size_t id =_id+i*3;
				const size_t is = (c+i)*sz_r+r;
				layer_b[is] = src[id+0];
				layer_g[is] = src[id+1];
				layer_r[is] = src[id+2];
			}
		}
	}
	for (size_t c = sz_rem; c < sz_c; c++)
	{
		for (size_t r = 0; r < sz_r; r++)
		{
			const size_t id = (r*sz_c+c)*3;
			const size_t is = c*sz_r+r;
			layer_b[is] = src[id+0];
			layer_g[is] = src[id+1];
			layer_r[is] = src[id+2];
		}
	}
}
Это работает 30ms против того что вверху ~70 ms на FX-8320 на 1920×1080×3.
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

ОО, круто, дайте і мені причаститись :)

void mtlb2opcv_1(uint8_t* d, uint8_t* s, size_t sz_r, size_t sz_c)
{
	const size_t sz = sz_r * sz_c;
	const size_t pl = 3 * sz_c - 3;
	const size_t mn = 3 * sz - 3;	
	const uint8_t* edst = d + sz * 3;
	const uint8_t* esrc = s + sz;
	for (uint8_t *s1 = s + sz, *s2 = s1 + sz; s < esrc; d -= mn)
		for (; d < edst; *d++ = *s2++, *d++ = *s1++, *d++ = *s++, d += pl);
}

А статистика какая?

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

Ну и еще подобная же задачка стоит с учетом ROI (работать только с задаваемыми блоками). В этом случае выравнивание летит к черту. Ну и сравнить получающиеся у меня решения с IPP — как-то попробовал, сходу по скорости ее работы не впечатлила.

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

Рассчитать размеры блока часто просто невозможно заранее, надо экспериментировать. Тем более, что по любому эксперимент — мать истины :) Я тоже думал, что после R_SUBSTEP == 64 улучшения в моей версии не будет, но до 256 оно улучшалось — подозреваю, за счёт встроенного read-ahead prefetch процессоров (то есть, чтения нескольких строк после текущей просто в расчёте, что они будут скоро нужны).

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

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

A region of interest (ROI) is a portion of an image that you want to filter or perform some other operation on.

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

void mtlb2opcv(uint8_t* dst, uint8_t* src, size_t sz_r, size_t sz_c)
{
  const unsigned long layer_size = sz_r*sz_c;
  const uint8_t * const src_r = src;
  const uint8_t * const src_g = src + layer_size;
  const uint8_t * const src_b = src + 2*layer_size;

  const size_t R_SUBSTEP = 256; // оптимум
  for (size_t r1 = 0; r1 < sz_r; r1 += R_SUBSTEP)
  {
    for (size_t c = 0; c < sz_c; c++)
    {
      for (size_t r2 = 0; r2 < R_SUBSTEP; ++r2) {
        size_t r = r1 + r2;
        size_t is = c*sz_r + r;
        size_t id = (r*sz_c + c) * 3;
        dst[id] = src_b[is];
        dst[id+1] = src_g[is];
        dst[id+2] = src_r[is];
      }
    }
  }
}

Теперь устойчиво 120 мс вместо секунды.
Увеличение R_SUBSTEP степенями двойки от 1 до 256 сокращает время, 512 — то же самое, 1024 — стало хуже (уже 190 мс).
i3-4170, DDR3.

Зато простановка restrict на параметры по методу Andrew Sevastianov тут уже ничего не дала (-O2, -O3 проверил, до лампочки, как и Clang vs. GCC).

Остаток теста (заголовки исключены)

int main() {
  const unsigned long sz_r = 6016;
  const unsigned long sz_c = 6016;
  const unsigned long layer_size = sz_r*sz_c;
  const unsigned long full_size = layer_size * 3;
  unsigned char *src = malloc(full_size);
  if (src == NULL) { err(1, "malloc"); }
  unsigned char *dst = malloc(full_size);
  if (dst == NULL) { err(1, "malloc"); }
  for (size_t i = 0; i < full_size; ++i) {
    src[i] = 0xff & i;
  }
  struct timespec ts0, ts1;
  clock_gettime(CLOCK_MONOTONIC, &ts0);
  mtlb2opcv(dst, src, sz_r, sz_c);
  clock_gettime(CLOCK_MONOTONIC, &ts1);
  printf("%llu nsecs\n", (unsigned long long)(
      (ts1.tv_sec - ts0.tv_sec) * 1000000000 +
       ts1.tv_nsec - ts0.tv_nsec));
  if (getenv("PRINT_RESULT_BUT_NEVER_SET_IT") != NULL) {
    // Без этого clang вообще выкидывает вычисления
    for (size_t i = 0; i < full_size; ++i) {
      printf("%d", dst[i]);
    }
  }
}

У меня падает. buffer size 1920*1080*3 = 6220800

Program terminated with signal SIGSEGV, Segmentation fault.
#0 0×00000000004006dd in mtlb2opcv_netch (dst=0×17cd480 „‚, src=0×11de880 ’”, sz_r=1080, sz_c=1920) at a.c:46
46 dst[id] = src_b[is];
(gdb) display is
1: is = 1081
(gdb) display id
2: id = 6226560

p.S. Выделяй память через mmap() + __PAGESIZE и делай последнюю страницу всегда PROT_NONE.

У меня падает. buffer size 1920*1080*3 = 6220800

sz_r должно быть кратно R_SUBSTEP. Откорректируй размеры в своём тесте.
Хотя бы замени на 128, раз уж тебе надо 1920 (не знаю, зачем — измерение времени на бо́льших размерах данных интереснее для контроля алгоритма в целом).

Выделяй память через mmap() + __PAGESIZE

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

А есть ли под такие задачи эмулятор, скрещенный с отладчиком и профайлером, способный на каждом шаге показывать состояние кеш-линий? (Диагностика на живой системе, понятно, будет интрузивной).

valgrind/cachegrind

И еще: поганяй под Valgrind на тему промахов кеша. Вдруг что-то интересное обнаружится.

Да и так понятно, что промахов море будет.

(в якості припущення) може, взагалі відмовитись від роботи з 2D — перетворити в 1D і працювати з ним ?

Поясни как? Все одно же по памяти прыгать надо будет. А данные в памяти и так 1D — это и бесит.

Хорошо бы если бы память была не линейная, а например ND и кеши и остальное — такая вот многомерная. Ты не представляешь какая безумная куча математики стала бы на порядки быстрее работать и код был бы элементарный.
Надо мне пространство размерности N, я указал и работаю с ним влоб.

Пока же у нас есть псевдоразмерность в виде SIMD с кучей нюансов при юзаний.
Ну и вариант GPGPU со своими большими нюансами при юзании.

Вот только такое может и появиться в процессорах и памяти, только лет через 100-200.
Пока же даже 2D памяти и процов не предполагается.
И пока даже транспонирование матрицу элементарная операция в математике и сильно нетривиальная при реализации. Когда джунов нанимал предлагал им в качестве домашки написать (или разобраться и содрать) класс для матриц, реализовать операцию умножения в блочном многопоточном варианте и задавал вопрос на собеседовании, а как бы ты в твоей реализации сделал транспонирование. Фактически после этой беседы было четко ясно, что джун может, а что нет. А да на мелкие ошибки в коде не обращал внимания совсем. Мне главное было увидеть, смог-ли разобраться и понять то, что написал (если содрал откуда).

в смислі розвернути дані в потрібному тобі порядку (повернувши на 90 градусів), в 1D масив [B, G, R, B,G,R, ..., B, G, R] в три потоки паралельно (один читає R — пише в ячейки для R, другий G, третій B), потім послідовно пройтись по цьому масиву, зчитуючи дані і пишучи в новий масив, де в тебе по одній ячейці на колір.

Так это код выше и делает.
А потоки для этой задачи слишком тяжелы. По крайней мере я не умею их написать так, чтобы не тяжелы были. Ну и кроме того, после этот код уже юзается в многих параллельных потоках на матлабе — там более высокий уровень и грузит все ядра на 100%.

Хорошо бы если бы память была не линейная

А в нашей песочнице она есть %) en.wikipedia.org/...​ry_access_pattern#Strided

Ты лучше расскажи, как это заюзать на С или С++ на x86_64.
Если речь про gpu, то 2D есть, но туда запихать данные и забрать часто дольше, чем собственно вычисления. Т.е. тоже не всё просто и на блюдечке с голубой каёмчкой.
С кодом выше, я сильно не уверен, что GPU в этом случае имеет смысл.

Пиши больше деталей:

1. Какое железо?
2. какой режим работы?

Ну и общие рекомендации:

1. Используй restrict если возможно
2. Не забываем о ключах оптимизации для компилятора.

SSE и AVX появились на чем-то, кроме x86_64?
Матлаб тоже не поползет на чем-то другом нынче.

Если было что-то специфическое, то я явно бы написал об этом.

SSE это еще допотопная технология. Я точно непомню когда она появилась но x86_32 ее умеет. AVX, да — это посвежее, но это не повод не указать тот же x86_64 в изначальном посте.

Вобщем как щитовидка отпустит — гляну глубже :-)

SSE и AVX появились на чем-то, кроме x86_64?

SSE появилось, когда x86_64 был только в радужных мечтах. Все SSE и AVX доступны в 32 и 64 битах (но AVX уже недоступно в 16; SSE ещё доступно).

С другой стороны, я бы тоже предполагал x86_64 по умолчанию и не спрашивал о контексте — в силу специфики задачи и того, что десктоп/workplace/сервер на 32 битах это уже пару лет как считается тупо неадекватным, пропадают дистрибутивы, софт не тестируется на 32 битах и т.п.

NEON має майже все те, що і SSE. В мене навіть був написаний інтерфейсний модуль, щоб librealsense запустити на ARM

1) Если эта функция не пользуется в куче разных мест, замени её на инлайн. Вроде бы компилятор это позволяет. То есть вместо функции будет инлайн-код. В идеале ты это сделаешь сам, руками.
2) Первый for — избавься руками. Если массив приличный, постарайся распараллелить по ch, если твоё железо это позволяет.
3) Избавься от создания переменных в цикле. Это для тебя кажется мелочь, но в реале за каждым таким вызовом стоит malloc, достаточно серьёзная системная функция. Создай переменные за пределами циклов.
4) В условиях цикла ты используешь size_t, а сравниваешь с типом int. Преобразуй константы в size_t. То же самое с rd. Иначе ты получаешь неявное преобразование типов, это тоже время. К тому же плохо оптимизируемая операция с точки зрения кеша.
5) Убери конструкцию for (){ for () {...}}, замени на for() for(){...}, то есть избавься от одного JMP — оператора. Мелочь, а может неприятно сбрасывать кеш.
6) Создай итераторы для for за пределами for. Опять же, чтобы не плодить неявный malloc.
7) Не совсем понятно, зачем ты вообще цикл по ch гонишь. В одном проходе напиши по 3 строчки существенных команд с нужными константами. Снова ж таки, не забывай о размерности контстант. Хотя преобразовывает ли современный компилятор целочисленные константы автоматом — ХЗ.

PS. В любом случае будет медленнее, чем копирование. Потому что копирование очень предсказуемая операция. Но за счёт избавления от циклов и обработки сразу 3 слоёв в одном проходе, ты локализуешь данные в одном коротеньком участке кеша.

Да, ещё такой вопрос: а в чём суть поэлементной перестановки? Если ты говоришь, что копирование идёт быстрее, не проще ли целым массивом скопировать в новый объект, и уже внутри одного объекта совершить перестановку? В чём выгода: объект даже если целиком в кеш не лезет, то уж точно будет читаться в один проход, то есть всего одна прокачка через кеш 1-го уровня, и прекрасная предсказуемость для кеша 2-го уровня.

IMHO основной тормоз у тебя в неявных malloc.

IMHO основной тормоз у тебя в неявных malloc.

Какие маллоки, пение? Там же всё статическое. :)

Впиxни эту функцию в «мэйн», откомпилируй, посмотри ассемблерный листинг — и найди там хоть 1 маллок.

П.С. Но вот, от умножений я бы избавился — тем более, возможности есть. Но тут уже, куда более радикальных вещей ниже нарекомендовали...

Сам сделай, тогда расскажешь.

Что сделать, флудер? Маллоки найти, там где их нет и быть не может? :)

malloc — выделение на куче, а тут всё на стеке.

IMHO основной тормоз у тебя в неявных malloc.

Отсыпь немножко?

Чего именно, мат.части? Я не спорю, что оптимизаторы может и научились это выправлять, но факт что именно по коду создаётся новая переменная в цикле. Куда по-твоему должна разместиться эта переменная? Правильный ответ — в лучшем случае отделаешься одним только malloc, в худшем — выгребешь ещё и создание зоны видимости с таблицей (не уверен точно насчёт именно С, без ++).

Да, есть одна очень древняя оптимизация — называется «сегмент данных». Почитай об этом, на досуге...

Чего именно, мат.части?

Травы :-)

Чего именно, мат.части?

Угу. Той её версии, которая заставляет предположить malloc в этом коде.

Куда по-твоему должна разместиться эта переменная?

В регистр.

Вот компиляция исходного кода Виктора, с обычным -O. Найди тут хоть один malloc.

Блин, я всерьёз не понимаю, ты троллишь, или настолько не знаешь C.

Вот еще удобный сайт gcc.godbolt.org для того, чтобы быстро видеть асм из C и С++.

Пусть пока на готовом потренируется читать :)

девочки, не ссорьтесь
иногда гцц неявно маллочит большие структуры данных, вместо размещения на стеке
но явно не в этом случае

Это ты про увеличение стека при необходимости? Но это можно ключами компиляции регулировать. Но к данному коду это не относиться, а во вторых там никаких маллоков. Там отдельная хрень, что увеличивает стек, а как она запрашивает память у системы, это мне кажется зависит от конкретной версии компилятора, его ключей и ОС.

Действительно, под x86 архитектуру даже по-дефолту вменяемо оптимизирует, де-факто за тебя вынося инициализацию за пределы циклов.

На ARM с этим гемора куда больше.

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

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

Ну я имел когда-то дело с тем, что по невыровненным исключения проца кидал, вот и подумалось, что и у всех армов так.

Но можно запрещать это через сервисный регистр (только нафига?

Нафига было разрешать? Они это сделали из-за линукса, в котором тонны говнокода и невыравненный доступ был через исключения, что приводило к потере производительности. Теперь потери немного меньше, но всё равно серьёзные. По-хорошему надо очень постараться, чтобы получить невыравненный доступ. А так — обычное маскирование «багов» в коде, ничего хорошего.

Нафига было разрешать?

Нафига запрещать? Разрешение дёшево. Запрещение создаёт кучу бессмысленных проблем.
Вот что пишет народ из RISC-V:

>> Misaligned accesses are occasionally required when porting legacy code, and are essential for good performance on many applications when using any form of packed-SIMD extension. Our rationale for supporting misaligned accesses via the regular load and store instructions is to simplify the addition of misaligned hardware support. One option would have been to disallow misaligned accesses in the base ISA and then provide some separate ISA support for misaligned accesses, either special instructions to help software handle misaligned accesses or a new hardware addressing mode for misaligned accesses. Special instructions are difficult to use, complicate the ISA, and often add new processor state (e.g., SPARC VIS align address offset register) or complicate access to existing processor state (e.g., MIPS LWL/LWR partial register writes). In addition, for loop-oriented packed-SIMD code, the extra overhead when operands are misaligned motivates software to provide multiple forms of loop depending on operand alignment, which complicates code generation and adds to loop startup overhead. New misaligned hardware addressing modes take considerable space in the instruction encoding or require very simplified addressing modes (e.g., register indirect only).
>> We do not mandate atomicity for misaligned accesses so simple implementations can just use a machine trap and software handler to handle some or all misaligned accesses. If hardware misaligned support is provided, software can exploit this by simply using regular load and store instructions. Hardware can then automatically optimize accesses depending on whether runtime addresses are aligned.

Учитывая, что у них в главных архитекторах Паттерсон (это который „... A quantitative approach” и прочая), очевидно, что ущерба производительности не будет. А вот воспитательные закидоны я лично не поддерживаю в данном случае.

Теперь потери немного меньше, но всё равно серьёзные.

Я подозреваю, что про „серьёзные потери” — городские байки вашего квартала. Цифры покажешь? На современных изделиях, разумеется, и не на задачах для SIMD.

Запрещение создаёт кучу бессмысленных проблем.

Разрешение создаёт кучу подводных камней.

Вот что пишет народ из RISC-V:

Я их называю теоретиками, которые рассматривают процессор в отрыве от всей остальной обвязки. Их мнение не интересно от слова совсем.

Я подозреваю, что про «серьёзные потери» — городские байки вашего квартала. Цифры покажешь? На современных изделиях

Увы, тебе придётся или верить или нет. Задача была USB драйвер для DisplayLink адаптера. У которого абсолютно странная поддержка компрессии, начиная с RLE и заканчивая JPEG, ты формируешь буфер в потоке команд и записываешь пиксели туда же. Адаптер по умолчанию поддерживает RGB565, которые писалиь как два байта сразу — uint16_t. Для армов пришлось переделывать запись в буфер через специальные функции, которые аккумулировали значения до тех пор пока нельзя было сбросить 32 бита за раз по выравненому указателю. Потери были около 70% по производительности, причём одинаковые, что на i.mx6, i.mx8, omap5, jacinto6, r-car h2, etc.

Второй момент, которые не учитывают в вашем «квартале» — это bus load, AXI шине по-боку ты будешь читать байт или слово или двойное слово — оно залочит шину для твоего реквеста. Ты можешь выбирать буфер по байтам и иметь 30% загрузку пропускной способности шины, а утилизацию шины под 90%. Ты даже об этом знать не будешь. В случае грамотной реализации у тебя будет соотношение 1:2 — 50% load, 100% bus utilization при невыравненном доступе. А если твое железо ещё что-то рендерит и пишет с камеры или просто отображет контент с камеры, то для Full HD разрешения ты утилизируешь шину 60-75%, у которых по системному QOS’у приоритеты выше, а ты получишь 25% для процессора, в котором ты ещё собираешься делать unaligned access — мои поздравления.

Второй момент, которые не учитывают в вашем «квартале» — это bus load

Я не понял, относится первый пример к normal memory или device memory.
По сути же оба примера у тебя свелись к одному утверждению: невыровненный доступ требует 2 операций на шине вместо одной, и там, где загрузка шины в этом случае может превзойти её пропускную способность, это критично.

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

Я их называю теоретиками, которые рассматривают процессор в отрыве от всей остальной обвязки.

Ну то есть ты про них ничего не знаешь. OK, ясно.

Я не понял, относится первый пример к normal memory или device memory.

А в случае USB драйверов ты можешь этого и не знать. Что дадут, то и юзаешь.

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

Нет. Невыравненный доступ — это не только две операции на шине, а ещё и простой процессора.

Ну то есть ты про них ничего не знаешь. OK, ясно.

Я много кого знаю, ещё больше, кого не знаю. Только разговор с людьми, которые рассматривают всё в отрыве друг от друга напоминает этот анекдот:

Идет мужик по пустыне, чувствует — чем-то воняет. Видит — сидит индеец.
Он его спрашивает:
— Слушай, ты не знаешь, чем это тут воняет?
— О, это долгая история!
— Ну, рассказывай.
— Жили на двух берегах два племени, в одном племени жил красивый юноша, а в другом красивая девушка. Они любили друг друга, но родители были против, и они утопились в речке.
— Ну а чем воняет-то?
— Да насрал кто-то.

Нет. Невыравненный доступ — это не только две операции на шине, а ещё и простой процессора.

Ну для полноты описания — ok. Аж на ровно то же время, сколько нужно для операции шины, и если нет других задач при OoO.
В остальном — у тебя есть возможность проверить выровненность доступа по указателю, а если надо — сделать выровненый? Безусловно есть.
Ты жалуешься, что другим облегчили работу там, где это всё не критично?
«Кокая трогедия» ©

Только разговор с людьми, которые рассматривают всё в отрыве друг от друга напоминает этот анекдот:

Отрыв тебе только мерещится.

Аж на ровно то же время, сколько нужно для операции шины

Ну да, процессор склеивает части по божьей воле за 0 тактов.

В остальном — у тебя есть возможность проверить выровненность доступа по указателю, а если надо — сделать выровненый? Безусловно есть.

Перед каждой записью? Браво.

Ты жалуешься, что другим облегчили работу там, где это всё не критично?

Не облегчили работу, а сделали доступным для домохозяек. АРМ платформа до сих пор на 99% для встраиваемых применений. Чтобы в обычном сферическом приложении получить невыравненный доступ нужно быть реально альтернативно-одарённым программером. В случае алгоритмов обработки данных разных размеров лучше бы они не маскировали эти проблемы, либо довели поддержку невыравненного доступа до уровня интелловских платформ, где им действительно можно пренебречь.

Ну да, процессор склеивает части по божьей воле за 0 тактов.

Не по божьей воле, а с помощью прохода через barrel shifter вместо прямой записи в регистр.
И да, это можно сделать за ноль тактов, даже ты это сможешь, если выключишь сарказм :)

Перед каждой записью? Браво.

Один раз на алгоритм. Перед каждой — конечно, не нужно (и снова, ты элементарно об этом бы догадался, если бы не ёрничал тут).

Не облегчили работу, а сделали доступным для домохозяек. АРМ платформа до сих пор на 99% для встраиваемых применений.

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

Не по божьей воле, а с помощью прохода через barrel shifter вместо прямой записи в регистр.

Бесплатно ничего не бывает, даже поддержка более эффективного byte swizzling вместо шифтера, когда регистра как такого не существует — он сборная солянка, просто уменьшает глубину конвеера. Одна команда занимает два слота.

Один раз на алгоритм. Перед каждой — конечно, не нужно

Я же тебе привёл элементарный пример с DisplayLink, например, блиттинг 7×7 картинки сделает указатель невыравненным 7 раз. А ты предлагаешь один раз на алгоритм.

Ну я не буду активно вспоминать, что если ARM хочет в десктоп/сервер/etc., то домохозяйкам надо помогать.

Я не вижу ни одного преимущества арма на десктопах, если они допилят процессор и обвязку до нужной кондиции, то оно мало чем будет отличаться от x86. Только цена будет заоблачная. Их потолок сейчас — это хром-ноуты.

Я же тебе привёл элементарный пример с DisplayLink, например, блиттинг 7×7 картинки сделает указатель невыравненным 7 раз. А ты предлагаешь один раз на алгоритм.

Я и имею в виду один раз на алгоритм — отразить ситуацию и написать выровненный под это вариант. Даже если компоновать все детали раздельно в зависимости от субсдвига.

Я не вижу ни одного преимущества арма на десктопах, если они допилят процессор и обвязку до нужной кондиции, то оно мало чем будет отличаться от x86.

Простота. x86 это триста слоёв кривого легаси. С ARM, даже если их будет 100 вместо 300, это огромный шанс для развития.

Простота. x86 это триста слоёв кривого легаси. С ARM, даже если их будет 100 вместо 300, это огромный шанс для развития.

АРМ уже горбатый по самое нехочу %) Такой же франкенштейн, что и x86.

По-моему, в ARM до таких ляпов ещё не доходили. Чтобы сбить с толку всех до единого авторов крупных ОС...

Вопрос в массовости. Trustzone пошла в массы и сразу полезли горбы. Только тут ещё хуже, в массовых дивайсах стоит только Линукса — одна ошибка и пользуйся на здоровье на всех устройствах.

Чтобы в обычном сферическом приложении получить невыравненный доступ нужно быть реально альтернативно-одарённым программером.

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

На ARM с этим гемора куда больше.

И в GCC, и в Clang блоки, которые занимаются данными вопросами, универсальны. MD оптимизации в этом не участвуют. Можно посмотреть результат на том же godbolt.
Откуда утверждение, что на ARM тут что-то иначе, совсем непонятно. Какой-то особый компилятор?

нет, я про аллоцирование сравнительно больших кусков локальных данных в скоупе функции

Не ведись на троллинг. У компилера должны весьма убедительные аргументы чтобы так забить на стандарты.

_malloca, alloca — это все троллинг.
просто выделяют на стеке

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

The latest version of this topic can be found at _malloca.

Allocates memory on the stack. This is a version of _alloca with security enhancements as described in Security Features in the CRT.

Извини, но он выделяет на стеке и если об автоматическом расширении стека не позаботился ключиками, то при переполнении стека получишь стек оверфлов.
К хипу оное отношения не имеет. Ну и С компиляторы (в С стандартах есть такое) последние умеют на стеке массивы не константного размера на стеке.
Так что эти функции — это убогий костыль, еще и глючный иногда.

А вообще я подобные функции сильно не люблю. На некоторых компиляторах от мелкомягких они конкретно глючили. Нарывался когда-то давно.

Даже в случае стека, даже в случае сегмента данных — это всё равно заставляет вести жизненный цикл переменной.

Да, я не исключаю возможности оптимизации для примитивных типов данных. Ценой памяти, разумеется. Если я не прав, это значит только то что проблемы нет. Но в общем случае правило таково, что переменных в циклах нагруженной логики лучше не плодить, особенно если эта логика условная (то есть практически всегда).

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

Стек при старте программы выделяется, а дальше только указатель вершины ползает. Затраты минимальны (пару быстрых команд — о них уже компилятор позаботится). Если ключиком позволишь увеличивать стек, то он будет блоками расширяться по необходимости.

Единственная сложность со стеком — это рекурсия — можешь выжрать стек и упасть.
Не путай жабу с ссями.

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

Так вот, сейчас по дефолтной оптимизации даже стэк не ползёт. Компилятор СРАЗУ тебе в стэке выделяет место под все твои переменные (и ещё вопрос в стэке ли, но не важно). Но суть в том, что всё то что ты мог сделать руками — делать всё равно нужно, просто делаешь это не ты. Ты по коду создаёшь переменную в цикле — а компилятор тебе её создал уже на этапе объявления функции, поместив в один блок с параметрами.

Почему и говорю, что разницы мало. Одно сложение — это не много на самом деле. Хотя я и его не понимаю, если честно, почему компилятор сразу не формирует константы. Видать, сложение быстрее обращения к константе. Я бы на этот момент пока наплевал.

А вот весь мусор с условными и безусловными переходами IMHO можно и выкосить попробовать.

ПОСМОТРИ ассемблерный код, и дай регистры тем переменным, которым так или иначе приходится в регистр попадать.

Даже в случае стека, даже в случае сегмента данных — это всё равно заставляет вести жизненный цикл переменной.

После перевода в SSA уже переменных как таковых нет (кроме случая, когда ты от переменной берёшь адрес и передаёшь куда-то ещё). Есть значения, у которых есть жизненный цикл. Эти значения могут модифицироваться, объединяться и т.п. любым корректным образом.
А дальше распределитель держит самое часто и плотно используемое в регистрах, а остальное в стеке.

И от того, оформлено значение как переменная или нет, вообще ничего не зависит. (При том же условии.)
Можешь его называть переменной или не называть — пофиг, внутри всё переварится в иные конструкты.

Вот не-SSA компиляторы типа старого MSVC (до 2015R3) могут к этому иначе относиться.
И всегда будут компиляторы, которые переводят 1:1, хотя бы для контроля логики более продвинутых представителей. Но они используются — для широких масс пользователей — чуть реже, чем никогда.

иногда гцц неявно маллочит большие структуры данных, вместо размещения на стеке

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

Я думаю что вы что-то очччень сильно путаете, но скорее всего просто несете ахинею ...

да, скорее всего, сильно путаю ахинею

Если ты говоришь, что копирование идёт быстрее, не проще ли целым массивом скопировать в новый объект, и уже внутри одного объекта совершить перестановку?

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

На сколько часов это «возиться»? Может стоит сделать?
Насчёт блочного — смотри прежде всего на разнос данных. Твоя задача — сделать выборку в кеш предсказуемой, то есть чтение с адресов — линейным, а операций ветвления — минимум. В идеале ты даже от умножения отказаться должен, в этом и смысл блочной обработки. Поменяй умножение на сложение в каждой итерации, посмотришь есть ли выигрыш. Должен быть!

Если размерность цикла известна, или кратность этой размерности (например, ряд кратный 128 элементам), то действительно имеет смысл дать линейный блок команд и воспользоваться регистрами. Можешь попробовать раскрыть циклы компилятором, но как по мне, проще написать самому. Даже если это 2 страницы кода, он достаточно примитивный. Особенно если запишешь весь код итерации в 1 строку, и потом скопипастишь эту строку, поменяв константы. Кстати, не факт, что константы лучше, чем простое сложение в регистре, это надо эксперимент проводить.

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

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

Немного может так помочь...
void mtlb2opcv(uint8_t * restrict const dst, const uint8_t * const src, const size_t sz_r, constsize_t sz_c)
Проблема в том, что любая операция записи по указателю сбрасывает кеш и заставляет компилятор перечитывать значения всех других указателей, препятствуя оптимизации.

А вообще главная проблема это кэши, поэтому надо думать о том, чтобы конвертировать блоками, а размер блоков подбирать для каждого конкретного процессора предварительной настройкой. Т. е. надо иметь указатель для каждого слоя, плюс одновременно брать N столбцов и писать сразу в N строк. И желательно обрабатывать порции по 12-24 байта и работать с uint32_t/uint64_t.

Вот схожая проблема: Перемножение матриц в С++

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

Откуда эта дичь?

Из стандарта C99 и описания restrict. Компилятор никоим образом не может знать, что указатели dst и src не перекрываются, или не указывают на одно и то же значение. Поэтому, когда мы что-то пишем по адресу dst, то это (теоретически) может изменить любое значение src. Поэтому мы не можем использовать закешированное в регистрах значения, использовать предчтение, а обязаны честно перечитать его из памяти. Поэтому компилятор вынужден копировать по одному байту.

Это, кстати, одно из немногих отличий C от C++. В С++ инвалидируются только указатели одного типа с тем, по которому прошла запись. В C инвалидируются все.

Из стандарта C99 и описания restrict.

Нет такого в стандарте С99.

В С++ инвалидируются только указатели одного типа с тем, по которому прошла запись. В C инвалидируются все.

В С нет понятия инвалидация указателя.

Нет такого в стандарте С99.

Есть.
Пункт 6.5.16 определяет смысл понятия assignment как access, который устанавливает новое значение объекта.
Пункт 6.5(7) определяет допустимые варианты этого самого access, который сводится, грубо говоря, через lvalue того же типа (квалификаторы несущественны) или character type (!)

Отсюда, любой доступ через char* любых видов заставляет забыть запомненные (кэшированные) значения, потому что доступ мог изменить объект; аналогично про запись — её нельзя откладывать.
Да, я, в отличие от ещё кое-кого тут, правильно понял «кэширование» не как процессорные L1/L2/L3 или TLB, а как использование ранее прочитанного значения или откладывание записи.

В С нет понятия инвалидация указателя.

Формулировка у него может быть и крива, но результат передан точно.

Есть

В упор не вижу, где «и заставляет компилятор перечитывать значения всех других указателей, препятствуя оптимизации.» Ты уже в другую степь полез — dereference.

Формулировка у него может быть и крива, но результат передан точно.

Да ну, я не вижу ни в одном из примере загрузки указателя заново из стека или из переменной.

В упор не вижу, где «и заставляет компилятор перечитывать значения всех других указателей, препятствуя оптимизации.»

Я ж говорю — формулировки кривые, но позже он выправился. Не самих указателей, а того, что лежит по ним.

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

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

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

Но факт что не только процессор имеет доступ в память, другие устройства тоже, и им подобные блоки выделяются. А вот можно ли выделить блок конкретному ядру, заставив остальные ядра о нём забыть — а вот ХЗ. Формально это слишком узкоспециализированная задача, которая очень слабо верится что прошла согласование между конкурентами, производящими вычислительное железо.

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

Если нужна производительность, допускают и дыру в безопасности. Управление кэшом в режиме «сейчас заполнять 1-ю четверть», «зафиксировать 3-ю четверть и дальше не менять» была в Pentium Pro. Наши видеодрузья показывали, как монтажный софт на PPro/180 работал быстрее P3/500 за счёт этой возможности.

С другой стороны, и такое управление кэшом можно сделать безопасным, если назначать задачам разные id и допускать только к данным своего id (примерно как Intel сейчас или IBM уже очень давно делают с TLB). Но это пока не лежало в их концепциях; посмотрим, что поменяется в моделях после Spectre.

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

Это замечательные рассуждения, но к проблеме, обсуждаемой в субтреде, они не относятся, от слова «вообще». Севастьянов правильно назвал проблему, а тебя понесло куда-то совершенно не туда. Видя соседние сообщения, я не удивляюсь.

То есть операции будут происходить, но не будут гарантированно отображаться в оперативную память конкретного блока.

Не представляю себе смысл подобной задачи. Если какая-то память должна быть доступна только одному ядру, то операции чтения/записи из других ядер просто должны обламываться. Лучше — через процессорное исключение.

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

Да, так не делают. Пока.
Делают secure monitor, SMM mode и тому подобное.
Хотя, если считать Intel ME отдельным ядром, то там это сделано.
Реального смысла я по-прежнему не вижу. Если уж ломать SMP, то так, чтобы иметь возможность создавать каждому ядру свою песочницу, включая I/O, и давать доступ по списку разрешений, а не запрещений. Но сейчас «простая» полная виртуализация явно выгоднее.

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

Именно так. Программно другие ядра в эту память и не полезут. Если полезут, то явно «нелегальными» методами и с нелегальными целями, то есть должны лососнуть тунца.

Виртуализация — да выгоднее. Но честная виртуализация достаточно требовательна к реусурсам, это во-первых, а во-вторых, не всегда цель именно виртауализовать. Чаще наоборот — целью является ускорить конвейрную обработку очень критического участка кода или данных, например в задачах шифрования потока. А инвалидация кеша, тем более в общей DRAM — задача совсем не быстрая, и очень тяжёлая с позиции синхронизации.

Поэтому мы не можем использовать закешированное в регистрах значения

В регистрах «значения не кэшируются», кэшируются страницы памяти в кэше...

Если реально хочется запилить cache-streaming — лучше глянуть в сторону мануального prefetch’а.

Конкретно в OpenCV уже есть все абстракции в HAL’e для SIMD’а. Их можно использовать для конверсии в CV_8U.

cvtColor уже использует SSE под капотом — не вижу смысла изобретать велосипеды.

Если реально хочется запилить cache-streaming — лучше глянуть в сторону мануального prefetch’а.

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

prefetch создает дополнительную нагрузку на планировщик процессора, по этому применим только для cache stream’инга, когда явно загружаются и освобождаются нужные страницы. Cам по себе prefetch без инвалидации (clflush lfence) создаёт действительно очень много проблем. Я не особо понимаю по каким причинам prefetch стоило использовать в ядре.

Я не особо понимаю по каким причинам prefetch стоило использовать в ядре.

Для пре-кеширования данных перед доступом.

Я не думаю что там достаточно данных что бы был смысл тянуть всю страницу (4Кб).

Откуда там страница? Там кешлайн — «Fetches the line of data from memory.»

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

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

Нет. MMU грузит только трансляцию виртуальный адрес -> {физический адрес, права доступа} в тот кэш, который зовётся TLB.
Тянуть содержимое всей страницы, даже в L3, тут в голову никому, к счастью, не приходит.

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

Да, видимо привык с PPC работать ...

На процессорах попроще, контроллерах на Линуксе и прочих железяках, где аппаратного кеша не предусмотрено как такового.

Во-первых, это преобразование картинки из матлаба в OpenCV формат. И кстати с советом Севастьянова я уже получил выйгрыш при юзании в mex файле в 6 раз (чуть расширил его совет). До линейного копирования через AVX не добрался, но уже мне сильно легче от этого.

Во-вторых, у OpenCV под капотом всё очень никак и заявленные MKL и SSE и подобное там сделано так, что часто без них даже быстрее работает (может за ближайшие лет 2 и починят, но мне столько ждать неохота, а во вторых через 5 лет уже массово везде будет в процах AVX2 и AVX512). Я уже столкнулся с их реализациями алгоритмов — в итоге OpenCV хороша тем, что там уже куча алгоритмов и их легко заюзать и попробовать, но для прода очень часто приходиться или найти более качественную реализацию или переписать самому.

Думаю, можно оптимизировать ещё. Пробовать по 2-4 столбца сразу, вычислять в памяти готовый uint64_t и писать его сразу (память узкое место), поиграться с порядком циклов, ... Просто это уже выходит за рамки совета, сорри.

а во вторых через 5 лет уже массово везде будет в процах AVX2 и AVX512

Тут всё плохо, если верить рассказам, что AVX256 уже перегревает процессор и выключается (и Intel и AMD), пока не используется. А AVX512 вообще превратит его в выхлопную сторону самолётной турбины. Не знаю, что именно им так плохо (вроде ж АЛУ не настолько прожорливы?), но надо ждать коренных реформ.
А с учётом того, что сейчас они все заняты переделкой чуть менее чем всего на защиту от Spectre с аналогами — ждать придётся долго.

Сейчас AVX256/512 нормально работает только на Xeon Scalable.
Даже AVX2 у CloudFlare в свое время вызвал проблемы с перегревом на Xeon D’шках.
Большая часть процессоров сейчас имеет 1-2 AVX512 конвеера, по этому возникают сложности с монопольным доступом.

Кешировать можно значение из базы, результат запроса в переменной... Можно реализовать свой кэш. Этот термин необязательно связан с железом.

Попытаюсь на примере

void f(int8_t * dest, int8_t * src)
{
  dest[0] = scr[0];
  dest[1] = src[1];
}

Может ли тут компилятор объединить две 8-битные операции в одну 16-битную? В общем случае не может, потому что если dest = src + 1, то первая строка меняет значение src[1] в результате чего поведение будет неэквивалентным.

Но если написать так:

void f(int8_t * dest, const int8_t * src)
{
  dest[0] = scr[0];
  dest[1] = src[1];
}

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

Аналогично, если написать так

void f(int8_t * restrict dest, int8_t * src)
{
  dest[0] = scr[0];
  dest[1] = src[1];
}

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

Этот термин необязательно связан с железом

Ок, видимо у меня чуть терминология от общепринятой отличается.

сможет выполнить указанную оптимизицию

У меня чуть другие представления о ситуации с Memory SSA в LLVM и GCC.

у него есть подсказка: значение, на которое указывает src, не меняется в контексте данной функции.

Хм, не уверен, что тут подсказка через const работает.
Стандарт написан очень казённо и искать по нему тяжело (я ожидал чего-то вроде «a const-qualified lvalue is assumed not changed», не нашёл).

Практические тесты на GCC и Clang говорят, что не объединяет :( (хотя они и с restrict не хотят объединять)

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

Это ж x86, тут невыровненный доступ дешёвый. Я сравнил с вариантом расширения до индексов 0...7 — всё равно по байтику тягают, вместо двух movq. Зато memcpy сразу дало те самые movq.
Вывод — там просто нет движка, который бы такое объединял.

В регистрах «значения не кэшируются»,

Кэшируются.

Например, если я сделаю код вида

  int *p1 = чему-то;
  int a = p1[0];
  ++p1[1];
  a = p1[0];
  c = p1[0];

компилятор не только имеет право сделать только одно чтение p1[0] для присвоения ’a’ в обоих случаях и ’c’ в конце, но сделает это при любом уровне оптимизации начиная с 1-го. (А, скорее всего, уже на этапе SSA DAG сделает только одну переменную на оба.)

Или ещё проще и реальнее:

  extern int *p1;
  extern int bar;
  for (int i = 0; i < 100; i++) {
    p1[i] += bar;
  }

при оптимизации будет только одно чтение bar на все итерации цикла.

Точно так же на запись: например:

  extern int foo, foo2;
  int sum = 0, sum2 = 0;
  extern int *p1;
  for (int i = 0; i < 100; i++) { sum += p1[i]; foo = sum; }
  for (int i = 0; i < 100; i++) { sum2 += p1[i+100]; foo2 = sum2; }

компилятор с оптимизацией оставит только одну запись в foo значения sum, а когда она будет — до вычисления sum2, после или посредине вычисления — его, компилятора, персональное дело; и он оставит только одну запись foo2, после завершения второго цикла.
Это и есть кэширование записи и чтения компилятором.

Компилятор не будет делать такое кэширование, если
1) объект чтения/записи обозначен volatile (грубый метод, часто чреват боком)
2) между операциями есть вызов чего-то, про что компилятор не имеет гарантии, что оно не изменит память непредсказуемым образом;
это включает в себя такой хак, как

asm volatile("":::"memory")
который используется, например, в inline-версиях всяких mutex lock/unlock
3) доступ к чему-то через character type (для совместимости с древними багами, но записано в стандарт и его оттуда уже не убрать)
кэшируются страницы памяти в кэше...

Безусловно, это такие диверсионные особенности C/C++, которые даже опытные разработчики часто не знают (а я пару раз забывал и с офигением перечитывал статьи типа такой). Но давайте всё-таки знать их и не флеймить на ровном месте.

cvtColor уже использует SSE под капотом — не вижу смысла изобретать велосипеды.

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

Компилятор не будет делать такое кэширование

Зависит от реализации Memory/Array SSA, можно сделать так что будет ;)
По этому я и не называю такие вещи «кэшированием», для меня это просто результат SSA прохода — на выходе уже может быть почти что угодно.

Зависит от реализации Memory/Array SSA, можно сделать так что будет ;)

Почему, если он не имеет гарантий, что кто-то не изменил память?
Есть примеры таких реализаций?

если он не имеет гарантий

Гарантии можно получить раскрасив «граф доступа к памяти» грубо-говоря.

Есть примеры таких реализаций?

Рабочих OpenSource’ных нет в природе, но в теории эту проблему проблему уже давно решили. Были поделки Azul’a, правда по понятным причинам они не публикуются.

Гарантии можно получить раскрасив «граф доступа к памяти» грубо-говоря.

И его можно раскрасить, не зная суть выполняемого во внешнем вызове между операциями?

Или вы про другой случай — доступ через character type, но как-то вычислив, что оно не пересекается? Тогда возражений нет, но это только один из трёх случаев.

Были поделки Azul’a, правда по понятным причинам они не публикуются.

Для JVM или именно для C/C++? Если первое, то им легко получить данные о любом внешнем вызове (ну, кроме FFI, но вряд ли его активно используют в Azul... или у них свой FFI, не такой тормозной, как оракловый)

не зная суть выполняемого во внешнем вызове между операциями?

Подразумевается что компилятор знает что где и чем будет писаться, даже если это «соседний поток» или FFI.

Для JVM или именно для C/C++?

Там у них LLVM бэкенд под JVM и фронтенд под Java, при некоторых оптимизациях формируется SSA с уже скомпилированных классов. Это можно грубо сравнить с частичной «декомпиляцией» и проверкой «что куда и чем пишеться»,

Подразумевается что компилятор знает

И как компилятор узнает это в случае C, когда в единице трансляции указано только «есть такая функция», а с чем будет линковаться полученый объектный код он не в курсе. Может этот объектный файл вообще скопируют на другую машину и слинкуют уже там?

Попросим его высказаться.

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

void opt_1(uint8_t * restrict const dst, const uint8_t * const src, const size_t sz_r, const size_t sz_c)
{
    const size_t layer_sz = sz_r*sz_c;
    if (layer_sz % sizeof(uint64_t) != 0) {
        fprintf(stderr, "Alligment error");
        exit(1);
    }

    const uint8_t * layer_r = src;
    const uint8_t * layer_g = layer_r + layer_sz;
    const uint8_t * layer_b = layer_g + layer_sz;

    for (size_t c = 0; c < sz_c; c++)
    {
        for (size_t r = 0; r < sz_r; r++)
        {
            const size_t id = (r*sz_c+c)*3;
            const size_t is = c*sz_r+r;
            dst[id+0] = layer_b[is];
            dst[id+1] = layer_g[is];
            dst[id+2] = layer_r[is];
        }
    }
}

2.033683 second vs 8.221542 second

Сорри, это я затупил, действительно такой выйгрыш.

Ради интереса попробовал на x86_32 — твой изначальный вариант на 5% быстрее %)

Странно. Я еще немного ручками развернул цикл выше и на AMD FX-8320 получил ускорение в 6 раз. Ключи: −03 -ftree-vectorize -funroll-loops GCC5.5
Возможно на другом проце будет по другому. Ну и память DDR3-PC12000.

Но мне это нужно в первую очередь на моем локальном компе, для mex. Т.е. код собственно обработки в либе меня удовлетворяет по быстродействию, но я словил тормоза на конвертации картинки и матлаба в opencv формат. Сейчас я получил ускорение с 30 fps до 180 fps именно конвертации картинки. А это уменьшает время прогона на данных с 300 сек до 60-70 где-то.
Дальше то мне нужно подобрать параметры алгоритма — это оптимизационная задача и без градиента. Это порядка нескольких тысяч запусков алгоритма на данных.

Единственная еще проблема железячная. Кулер большой с тремя трубками и большим вентилятором, но при такой загрузке всех ядер температура под 80 взлетает и немного сбрасывается частота с 3500 до 2700 в среднем. Пасту менял месяца 4 назад.

З.Ы. И да на restrict GCC пофиг — код на первый взгляд одинаковый генерит и по скорости одинаково.

Ключи: —03 -ftree-vectorize -funroll-loops GCC5.5

Ты забыл тыцнуть -mavx или -msse4.1, только с ними и с рестриктом он будет склеивать множественный доступ по байтам в одну операцию.

-mavx

А так включен этот ключик. По сути он только разрешает юзать интринсики нужные.
Нет. Это только у GCC 8.1 появилось. gcc.godbolt.org

Или я что-то не так делаю.

Попробуй -Os и -Ofast вместо -O3. А также укажи что у тебя процессор «Native» — насколько я помню в сумме это максимальная оптимизация под конкретное железо.

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

size_t tempIs = 0;
for (size_t c = 0; c < sz_c; c++, tempIs += sz_r)
    {
        size_t tempId = 0;
        for (size_t r = 0; r < sz_r; r++, tempId += sz_c)
        {
            const size_t id = (tempId+c)*3;
            const size_t is = tempIs+r;
            dst[id+0] = layer_b[is];
            dst[id+1] = layer_g[is];
            dst[id+2] = layer_r[is];
        }
    }
Умножения дорогостоящая операция, если конечно это не сдвиг.

Умножения в процессорах выше условного ARM-M1 давно уже стоят копейки — максимум как два сложения. Это не деление на заранее неизвестный делитель, которое действительно зверски дорого (в среднем по больнице — 1 такт на бит делимого).
С другой стороны, компилятор сам может заменить их на сложение — и заменяет, компиляторы сейчас (GCC, Clang как минимум) достаточно умны, чтобы умножение на переменную цикла превращать в добавление фиксированного значения на границе итерации (или наоборот, если выгоднее).
GCC убрал все умножения в цикле и заменил на сложения (причём большинство сложений через lea). Clang оставил умножения через imulq, наверно, он что-то знает :) Это всё при -O.

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

size_t tempIs = 0;
for (size_t c = 0; c < sz_c; c++, tempIs += sz_r)
    {
        size_t tempId = c;
        for (size_t r = 0; r < sz_r; r++, tempId += sz_c)
        {
            const size_t id = tempId*3;
            const size_t is = tempIs++;
            dst[id+0] = layer_b[is];
            dst[id+1] = layer_g[is];
            dst[id+2] = layer_r[is];
        }
    }

А ты получил циферки? Из же просто для этого кода получить, например на 1920×1080×3.
Ну и я в матлабе прогоняю, мне это нужно в мех либе в итоге. Но юзается GCC5.5. Так что разница с лобовой сборкой gcc не большая.
Но я твою идею тоже попробую, интересно же дает подобная оптимизация что-то или нет.
Просто пока еще не проснулся толком, торможу.

Попробуй, я не пробовал. Но прирост скорей всего будет не большой, не в разы . Подозреваю основное время в твоем коде занимает jumping по областям памяти, вот это вот все cache miss.
PS:
Кстате там можно еще от одного умножения избавится во внутреннем цикле, заменить тоже суммированием. Если оптимизация выше даст чтото существенное, то уберем еще и его.

Проверил — разницы в скорости нет на AMD FX-8320. GCC5.5 с ключами оптимизации прекрасно справился с локальными умножениями для индексов и разницы нет. Так что Нечаев прав, нынче компилятор прекрасно с таким справляется и сам.

Ну и в первом цикле

tempIs += sz_r

не нужно.

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

если выделить статические кэши и прыгать не за каждым байтом, а за несколькими? 4, 8, 16?

Сразу на 64 надо (размер строки кэша на x86).

если sse инструкция такое умеет

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

Это «хинт», а не команда, процессор может отказаться её выполнять. Второй момент из-за когерентных кешей между ядрами тебе никто не сможет гарантировать, что оставшиеся N ядер не займут кеш своими данными.

Там еще, вроде, можно самому себе сильно жизнь попортить, если ее задать невовремя, и данные «на потом» вытеснят нужные сейчас из кеша. Интересно, в реальном мире она кому-то помогала?

Хм, ускорение идёт только за счёт restrict.
У меня это 350 мс вместо секунды.

А может можно не поворачивать изображение? Ну пускай оно под 90* — распознавалке же все равно?
Тогда будет 3 прохода копирования, но все последовательные (R layer -> RGB, G layer->RGB, B layer — > RGB).

Сложность не в повороте, а в том, что цвета в матлабе разделены sz_r*sz_c, а в opencv лежат в последовательных байтах. Т.е. в любом случае прыгать по памяти надо.

одно дело — 3 прохода, копируя столбцы в строки (последовательные проходы, без прыжков), другое — прыжки, копируя из последовательного столбца в столбец, раскиданный по целевому массиву.

В OpenCV есть же что-то подобное формату хранения CV_8UC3.

А по теме — ничего ты не сделаешь толкового, тебе надо сделать 16-32 чтений памяти по байтам с дистанцией в несколько мегабайт между ними, собрать в большой регистр и затем выполнить операцию shuffle для перестановки байтов в регистре по маскам. С таким же успехом можно вычитывать данные просто в нужном порядке, чтобы не делать shuffle, затем всё сбрасывать одним куском. Только тут другая проблема — ублюдочный 24 битовый формат хранения с которым у тебя будут дырки при записи, неужели нельзя использовать BGRA/BGRX ?

В OpenCV есть же что-то подобное формату хранения CV_8UC3

Это он и есть в который нужно сконвертить.

неужели нельзя использовать BGRA/BGRX

Нет.

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

А даст-ли мне какой выйгрыш, если я сначала соберу в регистр, а потом выгружу его (пусть и 256 битный). В таком варианте я буду прыгать по памяти при чтении.

А даст-ли мне какой выйгрыш, если я сначала соберу в регистр, а потом выгружу его (пусть и 256 битный). В таком варианте я буду прыгать по памяти при чтении.

Минимальный выигрышь будет, может раза в 1.5 быстрее.

Т.е. я правильно понимаю, что тебе надо просто повернуть каждый слой на 90 градусов? И поменять слои местами?

1) Три быстрых memcpy() по слоям при копировании сразу ложишь слой R, G, B в нужное место.
2) Вызываешь transpose() в OpenCV.

Нет. Еще и скрестить 3 слоя. Слой — это цвет (R или G или B) и он лежит последовательным куском причем по столбцам (а не строкам — это наследие фортрана в матлабе).

Ок, CV_8UC3 — это формат хранения по слоям в OpenCV. Зачем тебе их скрещивать на данном этапе?

Нет. Там цвета лежат в трех последовательных байтах.

Ну а с дырками я боролся работой с 5 пикселями за раз. AVX толком не умеет с байтами работать, только с float и double.
Понятно один байт в регистре игнорил и пришлось четко обработать момент невыровненности данных. Просадка в скорости есть, но небольшая.

ну как бы ответ такой и есть :)
самая быстрая работа будет, если работать не побайтно, а по машинному слову, только тогда текст функции не будет столь гламурен :)

А не по словам работал, а больше. Интринсики заюзал и mm128. AVX не умеет с целыми числами работать, только с плавающими.

Подписаться на комментарии