Анализ производительности циклов I-K-J и K-I-J в языках Delphi и Pascal: почему row-ориентированные циклы могут ускорить ваш код?

Delphi , Синтаксис , Массивы

Оптимизация умножения матриц в Delphi и Pascal: анализ производительности циклов I-K-J и K-I-J

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

Проблема классического подхода

Рассмотрим стандартный алгоритм умножения матриц (ijk-порядок):

type
  TMatrix = array of array of Double;

procedure MatrixMultiply_IJK(const A, B: TMatrix; var C: TMatrix);
var
  i, j, k: Integer;
begin
  for i := 0 to High(A) do
    for j := 0 to High(B[0]) do
      for k := 0 to High(B) do
        C[i,j] := C[i,j] + A[i,k] * B[k,j];
end;

Такой код работает медленно из-за неоптимального доступа к памяти. При обращении к B[k,j] мы "прыгаем" по разным строкам матрицы B, что вызывает частые промахи кэша.

Оптимизированный подход (ikj-порядок)

Более эффективная версия выглядит так:

procedure MatrixMultiply_IKJ(const A, B: TMatrix; var C: TMatrix);
var
  i, k, j: Integer;
  temp: Double;
begin
  for i := 0 to High(A) do
    for k := 0 to High(B) do
    begin
      temp := A[i,k];
      for j := 0 to High(B[0]) do
        C[i,j] := C[i,j] + temp * B[k,j];
    end;
end;

Почему это быстрее? 1. Мы читаем элементы матрицы B последовательно (по строкам) 2. Переменная temp исключает повторное чтение A[i,k] 3. Лучшая локализация данных в кэше процессора

Тестирование производительности

Для матриц 1000×1000 на Intel i7-2670QM результаты могут быть такими:

Дальнейшая оптимизация

1. Использование указателей:

procedure FastMatrixMultiply(const A, B: TMatrix; var C: TMatrix);
var
  i, k, j: Integer;
  pA, pB, pC: PDouble;
begin
  for i := 0 to High(A) do
  begin
    pC := @C[i,0];
    for k := 0 to High(B) do
    begin
      pA := @A[i,k];
      pB := @B[k,0];
      for j := 0 to High(B[0]) do
      begin
        pC^ := pC^ + pA^ * pB^;
        Inc(pB);
        Inc(pC);
      end;
    end;
  end;
end;

1. Разворот циклов (loop unrolling):

for j := 0 to High(B[0]) div 4 do
begin
  // Обработка 4 элементов за итерацию
  pC[0] := pC[0] + pA^ * pB[0];
  pC[1] := pC[1] + pA^ * pB[1];
  pC[2] := pC[2] + pA^ * pB[2];
  pC[3] := pC[3] + pA^ * pB[3];
  Inc(pB, 4);
  Inc(pC, 4);
end;

Когда использовать каждый подход?

1. IJK-порядок - только для обучения, не для production-кода
2. IKJ-порядок - хороший баланс между читаемостью и производительностью
3. Указатели + разворот циклов - когда критична максимальная производительность

Заключение

Оптимизация доступа к памяти часто даёт больший выигрыш, чем микрооптимизации кода. Для матричных операций в Delphi/Pascal:

1. Всегда используйте row-major порядок (IKJ вместо IJK)
2. Применяйте указатели для исключения лишних проверок границ
3. Рассмотрите разворот циклов для дополнительного ускорения
4. Для максимальной производительности используйте специализированные библиотеки (OpenBLAS, MKL)

Эти принципы применимы не только к умножению матриц, но и к другим операциям с большими массивами данных в Delphi и Pascal.

Создано по материалам из источника по ссылке.

Анализ оптимизации умножения матриц в Delphi и Pascal через изменение порядка циклов для улучшения использования кэш-памяти и повышения производительности.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Массивы ::