Как эффективно использовать SIMD для подсчета четырехсимвольных совпадений в большой сетке поиска слов (включая вертикал ⇐ C++

[Anonymous]

На четвертый день появления кода в 2024 году возникла проблема: вам нужно определить, сколько строк «XMAS» содержится в сетке символов, например
MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

Слово может появляться в любом из 8 направлений: по горизонтали (вверх/вниз)/вертикально (влево/вправо) или по любой из 4 диагоналей.
Из постановки задачи неясно, предполагается ли фиксированный размер сетки.

Фактический тестовый пример, который они вам дают, составляет 140x140.

Как я решил эту проблему заключалось в загрузке всех 32 символов из 8 возможных направлений, начиная с X, в регистр SIMD и сравнения его с маской.
Это сработало и относительно быстро (достигло скорости 460 МБ/с). когда я увеличил размер входного файла, чтобы проверить его предел), но когда мы говорили о наших решениях на сервере Discord, на котором работает много разработчиков и несколько разработчиков с более чем 15-летним профессиональным опытом, один из них сказал мне, что для этой конкретной проблемы использование инструкций SIMD — это не то, что заставит код работать быстрее, а сам базовый алгоритм станет более важным.
Итак, мне интересно, в каких ситуациях стоит использовать SIMD? Как распознать ситуацию, когда использование инструкций SIMD может иметь заметное значение? Я думал, что сравнение всех 32 символов в одной инструкции будет иметь большое значение вместо вложения двух циклов for, но, возможно, я ошибался?
typedef struct {
std::vector chars;
uint32_t line_length;
} Data;

Data readFile() {
std::ifstream file("./input/day4_input.txt", std::ios::binary | std::ios::ate);
std::streamsize size = file.tellg();
file.seekg(0, std::ios::beg);
std::vector buffer(size);
file.read(buffer.data(), size);
file.close();

uint32_t line_length = std::ranges::find(buffer, '\n') - buffer.begin();
buffer.erase(std::remove(buffer.begin(), buffer.end(), '\n'), buffer.end());

Data input_data { buffer, line_length };
return input_data;
}

int main(int argc, char** argv) {

Data idata = readFile();

auto coordsToIdx = [&idata] (uint32_t i, uint32_t j) -> uint32_t { return i*idata.line_length + j; };
auto idxToCoords = [&idata] (uint32_t idx) -> std::pair {
return std::make_pair(static_cast(idx / idata.line_length), static_cast(idx % idata.line_length));
};

unsigned int res = 0;

const __m256i _mask = _mm256_setr_epi8(
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S',
'X', 'M', 'A', 'S'
);

std::array out_buff;

for(size_t i = 0; i < idata.chars.size(); i++) {
if(idata.chars != 'X') continue;

char buff[32] = {0};

std::pair coords = idxToCoords(i);
bool u = coords.first >= 3;
bool d = coords.first = 3;
bool r = coords.second

Подробнее здесь: https://stackoverflow.com/questions/792 ... ord-search