Эффективное выполнение логического выражения на растровом изображении в C или переполнении стека

Question

Эффективное выполнение логического выражения на растровом изображении в C или переполнении стека

Каков наиболее эффективный способ выполнения логического выражения на растровом изображении в C или C ++? Например, скажем, у меня есть 4-битное растровое изображение (a, b, c, d), Теперь, скажем, у меня есть простое логическое выражение, как (a AND b) OR (c AND d), Как мне представить логическое выражение, чтобы я мог эффективно применить его к моему растровому изображению? Я ищу общее решение, которое можно применить к любому логическому выражению, а не только к тому, которое приведено в качестве примера. Другими словами, я ищу какой-то способ «скомпилировать» логическое выражение в другую структуру данных, которая может быть использована для эффективного преобразования моего растрового изображения в логическое.

Структура растрового изображения является результатом операций фильтрации в записях базы данных. Каждая запись имеет собственный битовый массив, и каждый бит в битовом массиве является результатом отдельного правила фильтрации. Логическое выражение используется для объединения этих правил фильтрации, чтобы решить, должна ли запись быть включена в результаты запроса к базе данных. Может быть до 64 отдельных правил фильтрации, которые могут быть объединены с помощью логической операции, следовательно, битовая карта может быть представлена как unsigned long long int если необходимо.

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

Заметки:

Логическое выражение использует только вложенные операции AND и OR (нет
ЕСЛИ заявления).
Решение должно предполагать наличие 64-битного процессора.
Решение не должно зависеть от процессора (помимо 64-битной адресации).
Решение не должно предполагать наличие какого-либо другого конкретного оборудования (например GPU).
Все растровые изображения находятся в памяти.
Там может быть очень большое количество растровых изображений (миллиарды).
Растровые изображения обновляются по одному.

5

bitmapdata boolean-expression c++

Решение

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

Если растровые изображения ГАРАНТИРОВАНО чтобы всегда быть 4 бита, тогда они поместятся в младшие 4 бита символа, и для любого растрового изображения будет только 16 возможных значений.

Для конкретного логического выражения вы затем оцениваете его для каждой из шестнадцати возможных комбинаций битов, что дает вам набор из шестнадцати битов результата. Соберите их в шестнадцати бит: false, false, false, false в нулевом бите, false, false, false, true в бите 1 и так далее.

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

Рассматривайте растровое изображение как 4-битное int, оценивайте 1 << (4 bit int),
Возьмите результат этого сдвига и используйте C ++ & оператор для проверки кешированного 16-битного значения int логической операции.

Это вернется == 0 за ложь и != 0 за правду.

Сокращение до двух инструкций: shift и and это самый быстрый, который я могу видеть, делая это.

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

1

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

typedef unsigned long long Bitmap;
Bitmap bitmap;

struct Node {
virtual bool value()=0;
};

struct AbsNode : public Node {
int bit;
bool value() {return (bitmap>>bit)&1; }
}

struct AndNode : public Node {
Node *operandA, *operandB;
etc.
}

0

Источник

Accepted Answer

Наиболее эффективный метод использования операций И или ИЛИ для растровых изображений — это использование аппаратной помощи. Многие графические процессоры могут выполнять операции над двумя растровыми изображениями. Для этого не существует стандартной библиотеки C ++.

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

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

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

Вы также должны выбирать в группах, используя размер слова процессора. 32-битный процессор любит получать 32-битные за раз. Так что это даст вам 8 наборов 4-битных пикселей, которые загружаются с одной выборкой. В противном случае вам придется выбирать 8 бит за раз, что приводит к 4 выборкам по 8 бит по сравнению с 1 выборкой из 32 бит.

Вот основной алгоритм:

uint8_t * p_bitmap_a = &Bitmap_A[0];
uint8_t * p_bitmap_b = &Bitmap_B[0];
uint8_t * p_bitmap_c = &Bitmap_C[0];

// C = A AND B

for (unsigned int i = 0; i < bitmap_size / 4; ++i)
{
uint32_t  a = *((uint32_t*) p_bitmap_a);
uinte2_t  b = *((uint32_t*) p_bitmap_b);
uint32_t  c = a & b;
*((uint32_t *) p_bitmap_c) = c;
p_bitmap_a += sizeof(uint32_t);
p_bitmap_b += sizeof(uint32_t);
p_bitmap_c += sizeof(uint32_t);
}

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

Изменить 2:
Многопоточность & Параллельная обработка.

Если ваши растровые изображения не являются большими, накладные расходы на поддержку нескольких потоков выполнения или параллельного выполнения могут перевесить выгоду. Например, если накладные расходы на синхронизацию с другим ядром ЦП составляют 200 мс, а обработка растрового изображения без прерывания — 1000 мс, вы теряете время, используя параллельную обработку для одного растрового изображения (1200 мс, чтобы другое ядро обрабатывало растровое изображение).

Если у вас много растровых изображений, вы можете выиграть некоторое время, используя параллельную обработку или несколько потоков:

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

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

2