Самый быстрый способ применить простую функцию к блокам памяти

У меня есть две пары файлов; A1, A2, B1, B2; все одинакового размера. Я хочу, чтобы файл C составлял байты из первого файла в каждой паре на основе сравнения одного и того же байта в соответствующем файле; в моем случае, эта специфическая функция: C[i] = (A1[i] < B1[i]) ? A2[i] : B2[i]. Файлы находятся на порядок, я думаю, 16 мегабайт.Самый быстрый способ применить простую функцию к блокам памяти

Каков абсолютный самый быстрый способ сделать это? Каковы последующие узкие места в скорости, о которых я не знаю? Что изменится, когда у вас есть N пар входных файлов (но все же только один вывод)?

Примечание: Я знаю, что это зависит от процессора, но на данный момент я не знаю достаточно, чтобы задавать вопросы о зависимых от процессора вещах.

PS - Бонусные баллы, если вы можете порекомендовать, какие инструменты, среда и т. Д. Необходимы, чтобы начать работать с этим и на этом уровне.

PPS - Отметьте! Я не знаю достаточно, чтобы узнать, что еще нужно отметить этим вопросом.

источник

2016-12-05 Narfanator

В то время как 'сборка 'доставит вас к основным основным требованиям, которые иногда приравниваются к скорости, поскольку вы, кажется, начинаете с нуля, вы, вероятно, должны искать утилиты« Файл »или« Извлечь передачу нагрузки »(ETL), поскольку, вероятно, было написано ранее. –

Спасибо, что пытались помочь @FrankC., Но это не похоже на то, что мне нужно. Можете ли вы рассказать о том, почему вы думаете, что это поможет? – Narfanator

Основным фактором здесь является то, нужно ли читать файлы с диска/сети или они уже находятся в памяти. Если вам нужно их прочитать, просто напишите самый наивный цикл (в основном, что вы имеете в виду) на C++ (или вообще что-нибудь, может быть, даже javascript будет быстрее, чем дисковый ввод-вывод, хотя я сомневаюсь, C/C++/Java/C# являются безопасными) и оптимизировать часть чтения/записи файлов для использования буферов с разумным размером, а также самый быстрый доступный OS API для чтения/записи файлов. Поскольку это займет столько времени, что даже неоптимизированный цикл будет обрабатывать данные за долю времени ввода-вывода. – Ped7g

На современных x86 CPU самый быстрый способ будет весьма вероятно, вариация на тему инструкции SIMD:

чтения A1, B1 пакет байтов в 2-х регистров.
читать A2, B2 пакет байтов в другие 2 регистра
сравнить A1, B1, чтобы создать байтную маску, такую как 00FF00FFFF00 ... маркировка, размер которых был меньше A1.
чистый A2 маски (побитовое and)
инвертировать маску (так что теперь он помечает разыскиваемые байты из B2)
чистого B2 по маске
or модифицированного A2 + B2 вместе и записать его в результат буфер.
петля.

Сколько упакованных байтов вы сможете обрабатывать одновременно, зависит от вашей целевой x86 (какая инструкция SIMD она поддерживает). Возможно, последние могут обрабатывать это в блоках объемом 512 бит (64 байта), хотя я не изучал конкретные инструкции, поэтому не уверен, что для них доступны требуемые байт-упакованные сравнения и/или/xor.

Во всяком случае, это чисто теоретическое упражнение ИМО, поскольку дисковый/сетевой ввод-вывод будет настолько медленным, что любой цикл, кодирующий одиночные байты, сможет голодать очереди ввода-вывода.

Так что нет смысла беспокоиться о том, что цикл обработки очень важен, просто убедитесь, что размеры вашего буфера имеют смысл, и что вы не делаете что-то глупое, как копирование байтов назад и вперед (обычная вещь в основном не в C/Языки C++, где менее опытные программисты понятия не имеют, как данные структурированы в памяти, и они бросают их влево/вправо с помощью нескольких бесполезных конверсий, чтобы получить «что-то работающее»).

Часть кода ввода/вывода будет иметь решающее значение для общей производительности.

Вторым фактором будет использование кеша (совместимость с кэшем структур данных).

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

источник

2016-12-05 11:43:00 Ped7g

О, теперь я вижу, что вы говорите только о небольших 16-мегабайтных файлах, хм ... ну, код может немного повлиять на общее время выполнения, но все же IMO - это большая часть его ввода-вывода ОС чтения 2x 16MiB и запись 1x 16MiB. Если вы будете работать над некоторыми большими файлами, тогда стоимость кода будет полностью покрыта ожиданием ввода-вывода. – Ped7g

Фантастический! Файлы будут в памяти определенно; хотя atm я не знаю достаточно, чтобы это означало больше, чем «в ОЗУ». Имеет ли значение это делать на процессоре или графическом процессоре, по крайней мере, с точки зрения обработки? Не могли бы вы рассказать мне больше о кешировании? – Narfanator

С помощью SSE4.1 вы можете использовать [PBLENDVB] (http://www.felixcloutier.com/x86/PBLENDVB.html) для замены шага PANDN/PAND/POR. Это немного более эффективно. AVX2 имеет 256b целых векторов. AVX512f не имеет байтовых элементов, поэтому вам понадобится AVX512BW. (Я думаю, что единственное имеющееся в настоящее время оборудование AVX512f (Knight's Landing Xeon Phi) этого не имеет.) Но если ваши элементы являются 32-битными целыми числами, я думаю, вы все настроены на KNL. Сравнение AVX512 является опрятным: назначение - это регистр маски, и вы можете затем использовать маску с более поздними инструкциями. Смесь - это только MOVDQA в масках. –

Самый быстрый способ применить простую функцию к блокам памяти

ответ

Смежные вопросы