Pull to refresh

История одной оптимизации

Java *


Аннотация


Статья раскрывает особенности высокоуровневых оптимизаций вычислительных алгоритмов на Java на примере кубического алгоритма перемножения матриц.

Шаг 0. Установи точку отсчета!


Определимся с окружением:
  • Hardware: 1-socket/2-cores Intel Core 2 Duo T7300 2GHz, 2Gb ram;
  • Java: HotSpot(TM) Client VM (build 17.0-b17, mixed mode, sharing);


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

for (int i = 0; i < A.rows(); i++) {
	for (int j = 0; j < A.columns(); j++) {
		double summand = 0.0;
		for (int k = 0; k < B.columns(); k++) {
			summand += A[i][k] * B[k][j];
		}
		C[i][j] = summand;
	}
}


В качестве workload`а возьмем две плотных квадратных матрицы N x N двойной точности (double precision), где N = 1000.

В таком случае, время работы простого кубического алгоритма: 18.921 s. Будем считать это число точкой отсчета (baseline) для последующих оптимизаций.

Шаг 1. Знай правило 20/80!


Известно, что 80% времени работает 20% кода. Задача разработчика — вычислить эти самые 20% из всего объема кода. В нашем случае все очевидно — искомые 20% сосредоточены во внутреннем вычислительном цикле. С точки зрения JVM, этот код — наиболее вероятный кандидат на just-in-time компиляцию. Проверить компилируется ли байт-код в нативный можно с помощью опций — XX:+PrintCompilation -XX:+CITime.

$ java -XX:+PrintCompilation la4j.Demo
  1       java.lang.String::hashCode (64 bytes)
  2       java.lang.String::charAt (33 bytes)
  3       java.lang.String::indexOf (151 bytes)
  4       java.lang.String::indexOf (166 bytes)
  5       java.util.Random::next (47 bytes)
  6       java.util.concurrent.atomic.AtomicLong::get (5 bytes)
  7       java.util.concurrent.atomic.AtomicLong::compareAndSet (13 bytes)
  8       java.util.Random::nextDouble (24 bytes)
  9       la4j.matrix.DenseMatrix::set (10 bytes)
  1%      la4j.matrix.MatrixFactory::createRandomDenseMatrix @ 30 (68 bytes)
  10      la4j.matrix.MatrixFactory::createRandomDenseMatrix (68 bytes)
  2%      la4j.matrix.DenseMatrix::multiply @ 81 (152 bytes)


Из листинга видно, что метод перемножения матриц (la4j.matrix.DenseMatrix::multiply) был успешно скомпилирован. Это дает нам определенный простор для дальнейших действий. Во-первых, поробуем воспользоваться преимуществами final переменных. Известно, что при компиляции в нативный код они транслируются непосредственно в значения. Теоретически, замена границ матриц на final значения сократит обращения к памяти на 1000x1000x1000 раз. Вместо этого, значения будут подставлены непосредственно. Проверим теорию.

final int aColumns = A.columns();
final int aRows = A.rows();
final int bColumns = B.columns();
final int bRows = B.rows();
				
for (int i = 0; i < aRows; i++) {
	for (int j = 0; j < aColumns; j++) {
		double summand = 0.0;
		for (int k = 0; k < bColumns; k++) {
			summand += A[i][k] * B[k][j];
		}
		C[i][j] = summand;
	}
}

Время работы алгоритма: 16.996 s ;
Прирост производительности: ~11%;

Шаг 2. Помни о Кеше!


На самом деле, такая реализация будет работать всегда медленно. Итерация по “k”, обращается к элементам матрицы B по столбцам. Такое чтение очень дорогое, потому что процессору приходится каждый раз подкачивать (prefetch) данные из памяти, вместо того, чтобы брать их готовыми из кеша.

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

На рассматриваемой платформе размер кеш линии (cache line size) первого уровня (L1) — 64 байта — это самая дешевая память для процессора. В нашем случае, 64 байта почти бесплатной памяти дают потенциал для получения целых 8 ячеек матрицы (sizeof(double) = 8) в место одной сопровождаемой еще и оверхедом от префетчинга.

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

Попробуем исправить это и реализовать последовательный доступ к элементам матриц, чтобы получить максимальную выгоду от кеша. Для этого просто транспонируем матрицу B и будем обращаться к ее элементам по строкам.
final int aColumns = A.columns();
final int aRows = A.rows();
final int bColumns = B.columns();
final int bRows = B.rows();

double BT[][] = new double[bColumns][bRows];
for (int i = 0; i < bRows; i++) {
	for (int j = 0; j < bColumns; j++) {
		BT[j][i] = B[i][j];
	}
}

for (int i = 0; i < aRows; i++) {
	for (int j = 0; j < aColumns; j++) {
		double summand = 0.0;
		for (int k = 0; k < bColumns; k++) {
			summand += A[i][k] * BT[j][k];
		}
		C[i][j] = summand;
	}
}

Время работы алгоритма: 7.334 s;
Прирост производительности: ~232%;

Шаг 3. Думай!


Кода стало больше, однако время работы сократилось почти в 2.5 раза. Неплохо. Однако, при просмотре кода бросаются в глаза очевидные недостатки. Главный из которых — много циклов. Попробуем сократить объем кода и сделать его изящнее, объединив операции транспонирования и умножения в один вычислительный цикл. При этом, транспонирование будет осуществляться не для целой матрицы а по-столбцам, по мере их надобности.

final int aColumns = A.columns();
final int aRows = A.rows();
final int bColumns = B.columns();
final int bRows = B.rows();

double thatColumn[] = new double[bRows];

for (int j = 0; j < bColumns; j++) {
	for (int k = 0; k < aColumns; k++) {
		thatColumn[k] = B[k][j];
	}

	for (int i = 0; i < aRows; i++) {
		double thisRow[] = A[i];
		double summand = 0;
		for (int k = 0; k < aColumns; k++) {
			summand += thisRow[k] * thatColumn[k];
		}
		C[i][j] = summand;
	}
}

Время работы алгоритма: 3.976 s;
Прирост производительности: ~190%;

Шаг 4. Выбрасывай!


Воспользуемся еще одним преимуществом Java — исключениями. Попытаемся заменить проверку на выход за границы матрицы на блок try {} catch {}. Это сократит количество сравнений на 1000 в нашем случае. Действительно, зачем 1000 раз сравнивать то, что всегда будет возвращать false и на 1001 раз вернет true.

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

final int aColumns = A.columns();
final int aRows = A.rows();
final int bColumns = B.columns();
final int bRows = B.rows();

double thatColumn[] = new double[bRows];

try {
	for (int j = 0; ; j++) {
		for (int k = 0; k < aColumns; k++) {
			thatColumn[k] = B[k][j];
		}

		for (int i = 0; i < aRows; i++) {
			double thisRow[] = A[i];
			double summand = 0;
			for (int k = 0; k < aColumns; k++) {
				summand += thisRow[k] * thatColumn[k];
			}
			C[i][j] = summand;
		}
	}
} catch (IndexOutOfBoundsException ignored) { }

Время работы алгоритма: 3.594 s;
Прирост производительности: ~10%;

Шаг 5. Не останавливайся!


На этом этапе я пока остановился, потому что достиг желаемой цели. Моя цель была обогнать самую популярную сейчас библиотеку по работе с матрицами — JAMA (первая строчка в гугле по запросу “java matrix”). Сейчас моя реализация работает примерно на 30% быстрее чем JAMA. Кроме того, относительно небольшие оптимизации привели к приросту почти в 600%, относительно начальной версии.

Вместо заключения (это не реклама)


Рассмотренный код является частью open-source проекта laj4. Это библиотека для решения задач линейной алгебры на Java. Над проектом я начал работать на 4-ом курсе в процессе изучения курса вычислительной математики. Сейчас la4j показывает отличную производительность и работает в несколько раз быстрее чем аналоги на многих задачах.

Если кто-то заинтересовался и хочет подобным образом проводить вечера — пишите в личку :)
Tags:
Hubs:
Total votes 96: ↑87 and ↓9 +78
Views 17K
Comments 84
Comments Comments 84

Posts