Почему производительность этих матричных умножений настолько различна?

Я написал два класса матриц в Java, чтобы сравнить производительность их матричных умножений. В одном классе (Mat1) хранится член double[][] A, где строка i матрицы A[i]. Другой класс (Mat2) хранит A и T, где T является транспонированием A.

Скажем, мы имеем квадратную матрицу M и хотим получить произведение M.mult(M). Вызовите продукт P.

Когда M является экземпляром Mat1, используемый алгоритм был простым:

P[i][j] += M.A[i][k] * M.A[k][j]
    for k in range(0, M.A.length)

В случае, когда M является Mat2, я использовал:

P[i][j] += M.A[i][k] * M.T[j][k]

который является тем же самым алгоритмом, поскольку T[j][k]==A[k][j]. На матрицах 1000x1000 второй алгоритм занимает около 1,2 секунды на моей машине, а первый занимает не менее 25 секунд. Я ожидал, что второй будет быстрее, но не этим. Вопрос в том, почему это происходит намного быстрее?

Моя единственная догадка заключается в том, что второй лучше использует кэширование CPU, поскольку данные втягиваются в кеши в кусках более одного слова, а второй алгоритм извлекает выгоду из этого путем перемещения только строк, в то время как первый игнорирует данные, вложенные в кеши, сразу переходя к строке ниже (что составляет ~ 1000 слов в памяти, поскольку массивы хранятся в основном порядке строки), ни один из данных, для которых кешируется.

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

Итак, что это? Или есть еще одна причина для разницы в производительности?

Ответ 1

Это из-за локальности ваших данных.

В ОЗУ матрица, хотя и двумерная с вашей точки зрения, она, естественно, хранится как непрерывный массив байтов. Единственное отличие от массива 1D заключается в том, что смещение рассчитывается путем интерполяции обоих используемых вами индексов.

Это означает, что если вы получите доступ к элементу в позиции x,y, он рассчитает x*row_length + y, и это будет смещение, используемое для ссылки на элемент в указанной позиции.

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

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

(я скорее упростил все объяснение, а просто дал вам основную идею вокруг этой проблемы)

В любом случае я не думаю, что это вызвано JVM самостоятельно. Возможно, это связано с тем, как ваша ОС управляет памятью процесса Java.

Ответ 2

Кэш и гипотезы TLB являются разумными, но я хотел бы видеть полный код вашего теста... не только фрагменты псевдокода.

Другая возможность заключается в том, что разница в производительности - результат вашего приложения, на 50% больше памяти для массивов данных в версии с транспозицией. Если размер кучи JVM мал, возможно, это приводит к тому, что GC работает слишком часто. Это может быть результатом использования размера кучи по умолчанию. (Три лота байтов 1000 x 1000 x 8 ~ 24 Мб)

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

Ответ 3

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

Не нужно догадываться. Два метода могут дать вам ответ - однократное и случайное паузы.

Если вы используете один шаг медленного кода, вы можете обнаружить, что он делает много вещей, о которых вы никогда не мечтали. Например, спросите вы? Попробуйте и узнайте. То, что вы должны видеть, что это делает, на уровне машинного языка, эффективно проходит через внутренний цикл без движения отходов.

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

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

Ответ 4

Вы можете попробовать сравнить производительность между JDK6 и OpenJDK7, учитывая этот набор результатов...