Недавно передо мной стояла задача улучшить скорость кода на дружественном сервере Java. Код был о создании спиральной матрицы:
Поскольку я сейчас читаю о механической симпатии и тому подобном, я считаю, что это отличный случай для экспериментов с подходом, дружественным к процессору.
Первая реализация и узкое место
Первый алгоритм, который я придумал, отражает простую рекурсивную идею. Сначала мы перебираем самоподобные матрицы, и для каждой проходим верхнюю строку заголовка, заполняя записи 4 на 4:
После того, как полностью заполнили границу внешней матрицы, мы увеличиваем масштаб и фокусируемся на нетронутой внутренней матрице. Полный код выглядит следующим образом:
(Не спрашивайте, почему, n - это размерность матрицы, как отдельный параметр.) Мне не понравился этот код, потому что он как бы нарушает механическую симпатию. Фактически, если позволить ему работать на n = 1 << 14, он запустится примерно за 4,5 секунды.
Спойлер: вторая реализация, которую я попробовал, завершила алгоритм за 300 миллисекунд.
Механическая симпатия: предыстория
Прежде чем представить оптимизированный подход, давайте рассмотрим некоторые основные принципы.
В настоящее время мы работаем с двойным массивом целых чисел.
В Java размер целого числа составляет 32 бита, то есть 4 байта. Размер ссылки составляет 64 бита, то есть 8 байтов.
Общий объем хранилища данных, который нам требуется для матрицы размера 1 << n (битовый стиль для 2 ^ n), составляет не менее
(2^n * 8) + 2^n * (2^n * 4) ~>~ 2^(2n + 2)
Для масштаба 1 гигабайт - это примерно 1 << 30. На компьютере, которым я сейчас пользуюсь, осталось чуть меньше 2 гигабайт (без комментариев). Следовательно, у меня не хватит памяти, как только 2n + 2 > 30, следовательно, около n = 14… и действительно, выход за пределы этой точки резко терпит неудачу в OutOfMemoryError, ниже или то же самое - нормально.
Но объем оперативной памяти - не единственный важный момент, который я должен учитывать. Глядя на свой компьютер через диспетчер задач Windows, я вижу, что мой кэш ЦП уровня 1 составляет 256 килобайт. Это примерно 1 << 18bytes.
Также интересно знать, что обычно кэш L1 делится на две части: половина для хранения инструкций, другая половина для хранения данных. Таким образом, количество целых чисел, которые может обработать мой кеш, составляет около 1 << (7+8) (размер делится на два (из-за разделения) и снова делится на четыре (из-за размера int)).
Механическая симпатия: воздействие
Изложенное выше описание моего оборудования подчеркивает несколько фактов.
Данные хранятся в куче, а доступ к ОЗУ занимает около 50 циклов ЦП (быстро). Локальные переменные, подобные тем, которые я использую в алгоритме, скорее всего, будут храниться в регистрах, доступ к которым составляет около 1 цикла (дешево). С другой стороны, обращение к кешу L1 занимает около 5 циклов (супер-факт). Так что я действительно должен попытаться заставить ЦП помещать как можно больше в это место.
Важно знать, что когда мой процессор работает, он пытается предугадать, какие данные будут использоваться в следующих инструкциях. Схема доступа к данным в моей реализации вполне предсказуема. Наивное суждение (которое, должно быть, было у меня на первый взгляд) могло рассматривать его как «дружественное к кешу», потому что мой процессор должен иметь возможность легко предугадывать, какие данные нужно загрузить в кеш.
Плохая новость: ЦП не получает «отдельные записи матрицы». Обычно он выбирает чанки: строки кеша; последовательные кусочки памяти. И это как раз та проблема, с которой я столкнулся! Итерация по строкам - это нормально, потому что ЦП будет извлекать данные, которые находятся в континууме. Всякий раз, когда мы работаем со строкой, данные, скорее всего, будут поступать из кеша, и это быстро. Однако та же стратегия строки кэша также используется для столбцов, приводя к выборке информации, которая на самом деле используется не полностью. Хуже всего: выборка этих бесполезных данных заставляет релевантные покинуть кеш, увеличивая вероятность промаха кеша.
Лечение
Таким образом, я рассмотрел алгоритм глазами (своего!) Компьютера. Как я уже сказал, мой кеш L1 составляет около 1 << 15 целых чисел, что соответствует 2 строкам матрицы с 1 << 14 целыми числами. (Я, вероятно, преувеличу здесь, но это первая пробная оптимизация, которая может быть не полностью эффективной, но пока достаточной.)
Таким образом, я собираюсь провести рефакторинг, обрабатывая сразу 2 строки и только строки. Полный код выглядит так:
Ниже мы опишем основную идею кода. Если вам все равно, и вы хотите перейти к разделу тестов, не стесняйтесь его пропустить!
Первый цикл while и две следующие его инструкции предназначены для заполнения треугольников сверху вниз и снизу вверх. Вот результат этого блока на n=7:
1 2 3 4 5 6 7 0 25 26 27 28 29 0 0 0 41 42 43 0 0 0 0 0 0 0 0 0 0 0 47 46 45 0 0 0 37 36 35 34 33 0 19 18 17 16 15 14 13
Следующий цикл for заполнит левую часть матрицы, заполнив сначала нижние строки, а затем верхние строки. Нижние строки перекомпонованы с использованием трюка, похожего на периметр, с отводом спирали от соседа.
1 2 3 4 5 6 7 24 25 26 27 28 29 0 23 40 41 42 43 0 0 0 0 0 0 0 0 0 21 38 47 46 45 0 0 20 37 36 35 34 33 0 19 18 17 16 15 14 13
Второй внутренний цикл for перекомпоновывает правую часть, используя левую. Опять же, используется трюк со спиральным обратным ходом:
1 2 3 4 5 6 7 24 25 26 27 28 29 8 23 40 41 42 43 30 9 0 0 0 0 0 0 0 21 38 47 46 45 32 11 20 37 36 35 34 33 12 19 18 17 16 15 14 13
И, наконец, если необходимо, средняя строка перекомпонована с использованием верхней или нижней:
1 2 3 4 5 6 7 24 25 26 27 28 29 8 23 40 41 42 43 30 9 22 39 48 49 44 31 10 21 38 47 46 45 32 11 20 37 36 35 34 33 12 19 18 17 16 15 14 13
На каждой стадии итерации улучшение заключается в использовании только двух строк, никогда больше. Я думаю, что время от времени я снова буду терять кеш, потому что мой крайний вариант использования n = 1 << 14 немного пограничный и заполняет в точности мой кеш L1. Однако это явление не должно происходить так часто, как раньше.
Примечание: как видите, я не пытался полностью оптимизировать использование вычислений или локальных переменных во второй реализации; потому что мне на самом деле все равно (пока).
Результаты, достижения
Вот тесты, которые я сделал (JMH, среднее время, 1 разминка) для наивной реализации и оптимизированной:
1 << 14 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 4778,838 ± 1116,666 SpiralMatrix.optimizedFillBenchmark avgt 5 302,008 ± 27,536 n = 1 << 13 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 525,858 ± 18,257 SpiralMatrix.optimizedFillBenchmark avgt 5 68,188 ± 3,068 n = 1 << 12 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 111,950 ± 3,625 SpiralMatrix.optimizedFillBenchmark avgt 5 18,343 ± 6,507 n = 1 << 9 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 0,679 ± 0,005 SpiralMatrix.optimizedFillBenchmark avgt 5 0,277 ± 0,002 n = 1 << 8 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 0,101 ± 0,001 SpiralMatrix.optimizedFillBenchmark avgt 5 0,068 ± 0,002 n = 1 << 7 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 0,013 ± 0,001 SpiralMatrix.optimizedFillBenchmark avgt 5 0,016 ± 0,001 n = 1 << 6 (milliseconds/op) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 0,003 ± 0,001 SpiralMatrix.optimizedFillBenchmark avgt 5 0,004 ± 0,001 n = 1 << 2 (microseconds/op!) Benchmark Mode Cnt Score Error SpiralMatrix.naiveFillBenchmark avgt 5 0,024 ± 0,001 SpiralMatrix.optimizedFillBenchmark avgt 5 0,030 ± 0,001
Вы должны увидеть разницу на порядок между наивной и оптимизированной версиями для больших матриц. Разница исчезает на 1 << 7. Напомним, что мой кеш L1 составляет 1 << 15 int, так что это самый высокий случай, для которого (приблизительно) все данные попадают в кеш! Кроме того, оптимизированная версия явно превосходит наивную версию в 10 раз, что опять же ожидается из-за разницы в порядках величины между доступом к ОЗУ и кэш-памяти L1.
Выводы
Если бы меня попросили подвести итоги вышеупомянутого эксперимента, я бы сказал по меньшей мере: количество локальных переменных и локальных вычислений, которые вы выполняете в методе, не ожидается, что станет причиной того, что ваш код работает медленно.
Они кажутся обычно довольно дешевыми и полагаются на регистры (посмотрите самый последний случай 1 << 2, где разница составляет порядка наносекунды!)
Истинным узким местом вашего кода, скорее всего, будет неправильное представление об оборудовании.
Действительно, перемещение по столбцам на самом деле не является проблемой, как люди часто могут вам сказать. На самом деле проблема заключается в строках кеша и следствиях их существования.
Конечно, подобные забавные факты, скорее всего, не будут узким местом всего вашего приложения, которое, скорее всего, имеет дело с операциями ввода-вывода или сборкой мусора. Знаете ли вы, что изменение потока вызывает переключение контекста и, как ожидается, приведет к разрушению кеша? Лучшее понимание оборудования и того влияния, которое оно может оказать на код, никогда не бывает пустой тратой времени, чтобы лучше оптимизировать то, что необходимо (ввод-вывод, потоки, сборщик мусора и т. Д.), Не теряя времени на том, что не нужно.
Перед проведением этого эксперимента я бы никогда не стал ставить на то, что вторая реализация может так сильно превзойти первую, из-за того, что мне всегда говорили ... Как и во многих других областях (например, безопасность), говорить о производительности без измерений - это неуместно. абсолютно недействителен. Этот пример все доказывает. В следующий раз, когда вас об этом спросят, ответьте мудро.
И, возможно, последний вывод мог бы быть следующим: то, что мы сделали здесь для данных, концептуально справедливо и для инструкций. Помните, кэш L1 разделен на две части? Так что используйте короткие методы: так они лучше умещаются в кеш-памяти и быстрее извлекаются из того места, где они хранятся. (Здесь снова: сравните этот факт, не доверяйте слепо тому, что вы читаете на Medium!)
Ваше здоровье!
