Я написал два класса матриц на 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 секунд. Я ожидал, что второй будет быстрее, но не настолько. Вопрос в том, почему это намного быстрее?
Мое единственное предположение состоит в том, что второй алгоритм лучше использует кеши ЦП, поскольку данные втягиваются в кеши кусками, превышающими 1 слово, и второй алгоритм извлекает выгоду из этого, проходя только строки, в то время как первый игнорирует данные, загруженные в кэширует, сразу переходя к строке ниже (которая составляет ~ 1000 слов в памяти, потому что массивы хранятся в основном порядке строк), ни одна из данных для которой не кэшируется.
Я спросил кого-то, и он подумал, что это из-за более дружелюбных шаблонов доступа к памяти (то есть, что вторая версия приведет к меньшему количеству программных ошибок TLB). Я вообще не думал об этом, но я могу видеть, как это приводит к меньшему количеству ошибок TLB.
Итак, что это такое? Или есть какая-то другая причина разницы в производительности?
