Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

Введение

• Подход к реализации
• Выделение памяти для массивов с «динамическими» границами
• Обработка констант
• Объекты программы, зависящие от размеров границ массивов
• Синтаксис массивов с изменяемыми границами
• Ссылка на массивы с изменяемыми границами
• Пример использования «динамических» массивов как параметров
• Заключение

Введение

            В свете все возрастающего потока англоязычных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо «модификация исполняемого кода» написать что-нибудь вроде «run-time reflection». Суть от этого не меняется. Речь о способе реализации в языке программирования такого непростого объекта, как массив с заранее неизвестными границами. Типичный пример использования подобных объектов – это операции (в математическом смысле) с матрицами разных размеров. А в данном случае имеется в виду еще более сложный (так сказать, «настоящий») многомерный массив, который занимает непрерывный участок памяти и у которого нижние границы не обязательно начинаются с нуля. Реализация обращения к таким массивам гораздо сложнее случая, когда границы размерностей константы и известны при компиляции. Из сложности реализации таких массивов следует неприятное следствие: обращение к массивам с «динамическими» границами выполняется существенно медленнее, чем к массивам с границами-константами. Желательно было бы соединить мощь и удобство работы с массивами с задаваемыми при исполнении кода границами с быстротой доступа к массивам с границами-константами, когда часть вычислений адресов элементов может производиться уже на этапе компиляции программы.

            Далее все рассуждения приводятся на примере конкретной реализации компилятора PL/1-K с языка PL/1 для Win64 (см. «К вопросу о совершенствовании языка программирования»).

Подход к реализации

            Самый простой подход к решению данной задачи, который первым приходит в голову – заменить значения границ-констант массивов на новые значения и перетранслировать программу. Разумеется, во многих случаях такой подход неприемлем. Но рассмотрим, чем будет отличаться выполняемый код? Например, такому обращению к элементу массива:

dcl x(100,100) float(53);
dcl (i,j)      fixed(63);
...
x(i,j)=12345e0;

соответствует такой исполняемый код x86-64:

48693DB838010020030000   imul q rdi,I,800
48A1C038010000000000     mov  q rax,J
488DBCC710FDFFFF         lea    rdi,X+0FFFFFCD8h[rdi+rax*8]
BE30000000               mov  q rsi,offset @00000030h
48A5                     movsq

            Видно, что при разных значениях границ-констант массива исполняемый код будет отличаться лишь разными значениями операндов-констант в некоторых командах. В данном случае это значение третьего операнда-константы операции IMUL и константа-«смещение» в операции LEA. Следовательно, если в выполняемом модуле сохранить информацию об адресах таких команд, а также информацию, каким образом получены такие операнды-константы, то можно создать служебную подпрограмму, которая при вызове во время исполнения программы заменит все нужные операнды-константы на новые значения, соответствующие новым требуемым значениям границ массивов. После этого, исполнение кода пойдет так, как если бы при трансляции были заданы такие новые границы-константы. В результате получаются массивы как бы с «динамическими» границами, т.е. изменяемыми при выполнении программы, но обращение к которым идет точно так же, как и к массивам со «статическими» границами.

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

Выделение памяти для массивов с «динамическими» границами

            Если границы массивов, а, значит, и объем занимаемой памяти, меняются во время исполнения программы, то в общем случае такие массивы не могут размещаться в «статической» памяти. Конечно, там можно заранее разместить массив с заведомо наибольшими значениями границ, а затем в процессе исполнения только «динамически» уменьшать их, но такой подход ограничен и неудобен. Поэтому память для массивов с «динамическими» границами должен явно выделять программист из «кучи» оператором ALLOCATE и освобождать оператором FREE. В языке PL/1 такие объекты считаются объектами с «управляемой» (CONTROLLED) памятью (см. «О размещении переменных в стеке»).

            Следовательно, новые значения границ должны быть определены до собственно создания массива, т.е. до выполнения соответствующего оператора ALLOCATE. Поэтому и обращение к служебной подпрограмме замены констант для данного массива должно быть тоже прежде оператора ALLOCATE, так как объем выделяемой для массива памяти – это также операнд-константа в одной из команд перед вызовом ALLOCATE, зависящий от размеров границ.

Обработка констант

            Константы, которые вычисляются из границ-констант массива и которые, в конечном итоге, становятся частью операндов-констант команд исполняемого кода, формируются на этапе анализа исходного текста программы. Компилятор PL/1-KT переводит текст программы в промежуточную обратную польскую запись, где каждая константа – это отдельная «операция», имеющая единственный операнд – само значение константы (4 байта). Для реализации «динамических» массивов вводится новая операция «модифицированная константа», которая имеет операнд-ссылку на таблицу компилятора. По ссылке располагается само значение константы, а также вся необходимая информация, позволяющая определить, как получилось данное значение, и, следовательно, позволяющая рассчитать новое значение при новых границах. После окончания трансляции эти ссылки сохраняются и в выполняемом модуле, причем к ним добавляются адреса команд, в код которых «замешивается» данная константа, а также адрес служебного (создаваемого компилятором) указателя на выделенную «динамическому» массиву память.

            Служебная подпрограмма рассматривает только те ссылки, у которых указатель совпадает с её входным параметром. Для этих ссылок определяется место в команде, где записана константа, формируется новая константа из новых значений границ, к ней добавляется часть исходной константы, которая не зависит от границ. Новая константа заменяет в команде старую, и подпрограмма ищет следующую ссылку для заданного массива.

            Исправляемые таким образом команды текстуально могут находиться и «выше» и «ниже» вызова служебной подпрограммы. Но, разумеется, если начать выполнять еще не приведенный к правильным границам код, поведение программы станет непредсказуемым.

Объекты программы, зависящие от размеров границ массивов

Таких объектов в программе на языке PL/1 оказалось восемь:
• встроенные функции языка LBOUND/HBOUND/DIMENSION, выдающие значения нижней/верхней границы или числа элементов для заданной размерности;
• оператор ALLOCATE, неявно имеющий входным параметром число выделяемых массиву байт, зависящее от его границ;
• «индекс», т.е. собственно команды вычисляющие часть адреса по очередному индексу-переменной при обращении к элементу массива;
• «последний индекс», появляется только в случае режима компиляции с контролем выхода индекса за границы массива. Для данного элемента корректировать константу в команде не требуется, например, это случай одномерного массива, где вычисление адреса по единственному индексу не зависит от значения границ, но где-то далее имеются команды контроля выхода индекса за границы и их-то и необходимо скорректировать.
• «смещение» массива, это последняя из команд вычисления адреса элемента массива. К этому моменту уже вычислены составляющие адреса от индексов-переменных и в этой команде для x86-64 обычно реализуется базово-индексный режим адресации, причем имеется и постоянное «смещение», которое как раз и зависит от значений границ и должно быть скорректировано. Смещение возникает, так как нижние границы не обязательно нулевые, некоторые индексы могут быть константами, а элемент, адрес которого вычисляется, сам может быть элементом «структуры» (агрегата разнотипных элементов), имеющим свое постоянное «смещение» внутри каждого элемента этой структуры;
• «участок памяти» - при обращении к части массива или к массиву целиком как к непрерывному участку памяти необходимо скорректировать число обрабатываемых байт, так как оно также зависит от текущих значений границ.

            Наиболее громоздким для обработки является корректировка константы в команде элемента «смещение», поскольку в константу команды-«смещение» входят и части от индексов-констант. Служебной подпрограмме необходимо повторить весь расчет адресной части заново, причем, если были индексы-константы, еще необходимо тут же проверить их на выход за пределы новых значений границ.

Синтаксис массивов с изменяемыми границами

            В стандарте языка PL/1 изменяемые границы массивов просто задаются выражениями, например:

dcl  n      fixed(31),
     x(0:n) float ctl;
get list(n);
allocate x;
...

            Для описываемой реализации такая запись бессмысленна, поскольку границы будут меняться другим способом, поэтому в описании вместо границ используется знак «*», этот пример эквивалентен предыдущему:

dcl  n      fixed(31),
     x(*)   float ctl;
get list(n);
?index(1,1)=0; ?index(1,2)=n; // устанавливаем новые границы
call ?ret(addr(x));           // меняем константы для массива x
allocate x;
...

Для изменения границ в компилятор PL/1-KT введены служебные элементы в виде встроенного двумерного массива новых значений нижних и верхних границ:

dcl ?index(15,2) fixed(31) external;

Первая размерность этого массива 1:15, поскольку это максимально допустимое число размерностей массива в компиляторе PL/1-KT. А также введена служебная подпрограмма «перетрансляции», т.е. корректировки констант в командах, использующая текущие значения массива ?index:

dcl ?ret entry(ptr) external;

            Служебный массив ?index и подпрограмма ?ret предопределены в компиляторе PL/1-KT. При запуске программы все значения границ в массиве ?index по умолчанию заданы единичными.

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

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

            Компилятор PL/1-KT отмечает в своей таблице признак изменяемой границы у данного массива, а сам значок «*» просто заменяет на некоторые «некруглые» значения границ. Это сделано для того, чтобы далее в процессе компиляции создавались обычные команды, как для массивов с границами-константами. А «некруглые» значения не позволяют оптимизатору применять более короткие формы команд, поскольку тогда невозможно скорректировать их другими, например, большими значениями.

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

dcl // структура-массив с изменяемыми границами
1 s(*,*)       ctl,
 2 x1          char(100) var,
 2 y1 (-1:25)  float,
 2 z1 (100)    fixed(31);

Ссылка на массивы с изменяемыми границами

            Для передачи в подпрограммы массивов с изменяемыми границами как параметров, учитывается тот факт, что такие массивы всегда неявно используют указатели. Но поскольку это служебные указатели, создаваемые компилятором, напрямую использовать их имена нельзя. Обращение к указателю без явного использования его имени возможно в языке PL/1 в случае применения встроенной функции ADDR, например:

dcl x(100) float based(p1),
   (p1,p2) ptr;
p2=addr(x);     //это эквивалентно p2=p1;

            Таким образом, если нужно передавать как параметры массивы с «динамическими» границами, достаточно передать указатели на них с помощью ADDR, без явного использования имен служебных указателей:

call умножение_матриц(addr(a),addr(b),addr(c),m,n,q);

и тогда описание параметров таких подпрограмм становится единообразным, не зависящим от самих массивов:

dcl умножение_матриц entry(ptr,ptr,ptr,fixed(31),fixed(31),fixed(31));

            Этот прием позволяет передавать «динамические» массивы в подпрограммы, но не позволяет «принимать» их внутри подпрограмм, поскольку тогда нужно присваивать указатели-параметры объектам класса «управляемой» памяти. Поэтому в компиляторе PL/1-KT дополнительно разрешено использовать и в левой части присваивания встроенную функцию ADDR:

dcl x(*) float ctl,
    p1   ptr;
addr(x)=p1; //эквивалентно оператору <служебный указатель на x>=p1;

            И тогда, наконец, использование массивов-параметров становится возможным через неявную передачу указателей на них с помощью встроенной функции ADDR.

Пример использования «динамических» массивов как параметров

            В данном примере применена описанная выше технология корректировки констант для выполнения универсального умножения матриц заданного размера. «Динамические» массивы-матрицы создаются оператором ALLOCATE и передаются (неявно указателями) в универсальную процедуру умножения матриц. Корректировка констант в исполняемом коде производится как для фактических параметров A1, B1,C1, так и для формальных A, B, C. Кроме этого, формальным параметрам присваиваются фактические значения с помощью разрешения использовать функцию ADDR в левой части присваивания. Процедура «УМНОЖЕНИЕ_МАТРИЦ» может находиться в отдельном модуле и транслироваться автономно.

TEST:PROC MAIN;

DCL (A1,B1,C1)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦЫ
DCL (M1,N1,Q1)      FIXED(31); // ЗАДАВАЕМЫЕ ГРАНИЦЫ
DCL (I,J)           FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЫЕ ЗНАЧЕНИЯ ГРАНИЦ ----

M1=5; N1=4; Q1=3;

//---- КОРРЕКТИРУЕМ КОНСТАНТЫ A1(M1,N1), B1(N1,Q1), C1(M1,Q1) ----

?INDEX(1,2)=M1; ?INDEX(2,2)=N1;
?RET(ADDR(A1));                   // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ A1
?INDEX(1,2)=N1; ?INDEX(2,2)=Q1;
?RET(ADDR(B1));                   // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ B1
?INDEX(1,2)=M1;
?RET(ADDR(C1));                   // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ C1

//---- СОЗДАЕМ МАТРИЦЫ A1(M1,N1), B1(N1,Q1) И C1(M1,Q1) ----

ALLOCATE A1,B1,C1;

//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦЫ НЕКОТОРЫМИ ЗНАЧЕНИЯМИ ----

DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;
DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;

//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----

УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);

//---- ВЫДАЕМ ПОЛУЧЕННЫЙ РЕЗУЛЬТАТ ----

PUT SKIP DATA(C1);

FREE A1,B1,C1;

//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========

УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);

//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----

DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦЫ
DCL (M,N,Q)      FIXED(31); // ЗАДАННЫЕ ГРАНИЦЫ
DCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦЫ
DCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- НОВЫЕ ОПЕРАТОРЫ ПРИСВАИВАНИЯ УКАЗАТЕЛЕЙ ----

ADDR(A)=P1;     // АДРЕС ДЛЯ МАССИВА A
ADDR(B)=P2;     // АДРЕС ДЛЯ МАССИВА B
ADDR(C)=P3;     // АДРЕС ДЛЯ МАССИВА C

//---- КОРРЕКТИРУЕМ КОНСТАНТЫ МАТРИЦ A(M,N), B(N,Q), C(M,Q) ----

?INDEX(1,2)=M; ?INDEX(2,2)=N;
?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ A
?INDEX(1,2)=N; ?INDEX(2,2)=Q;
?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ B
?INDEX(1,2)=M;
?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ C

//---- УМНОЖЕНИЕ МАТРИЦ ----

DO I=1 TO M;
   DO J=1 TO Q;
          C(I,J)=0;
          DO K=1 TO N;
                 C(I,J)+=A(I,K)*B(K,J);
          END K;
   END J;
END I;
END УМНОЖЕНИЕ_МАТРИЦ;
END TEST;

Эта тестовая программа эквивалентна приведенной ниже программе с границами-константами у матриц.

TEST:PROC MAIN;

DCL (P1,P2,P3)      PTR;             // УКАЗАТЕЛИ НА МАТРИЦЫ
DCL A1(5,4)         FLOAT BASED(P1), // СТАТИЧЕСКАЯ МАТРИЦА А1
    B1(4,3)         FLOAT BASED(P2), // СТАТИЧЕСКАЯ МАТРИЦА B1
    C1(5,3)         FLOAT BASED(P3); // СТАТИЧЕСКАЯ МАТРИЦА C1
DCL (M1,N1,Q1)      FIXED(31);       // ЗАДАВАЕМЫЕ ГРАНИЦЫ
DCL (I,J)           FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- ДЛЯ ТЕСТА ЗАДАЕМ НЕКОТОРЫЕ ЗНАЧЕНИЯ ГРАНИЦ ----

M1=5; N1=4; Q1=3;

//---- СОЗДАЕМ МАТРИЦЫ A1(M1,N1), B1(N1,Q1) C1(M1,Q1) ----

ALLOCATE A1,B1,C1;

//---- ДЛЯ ТЕСТА ЗАПОЛНЯЕМ МАТРИЦЫ НЕКОТОРЫМИ ЗНАЧЕНИЯМИ ----

DO I=1 TO M1; DO J=1 TO N1; A1(I,J)=I+J; END J; END I;
DO I=1 TO N1; DO J=1 TO Q1; B1(I,J)=I-J; END J; END I;

//---- УМНОЖЕНИЕ МАТРИЦ A1 И B1, РЕЗУЛЬТАТ - МАТРИЦА C1 ----

УМНОЖЕНИЕ_МАТРИЦ(ADDR(A1),ADDR(B1),ADDR(C1),M1,N1,Q1);

//---- ВЫДАЕМ ПОЛУЧЕННЫЙ РЕЗУЛЬТАТ ----

PUT SKIP DATA(C1);

FREE A1,B1,C1;

//========== УМНОЖЕНИЕ МАТРИЦ ЗАДАННОГО РАЗМЕРА ==========

УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);

//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ - МАТРИЦА C(M,Q) ----

DCL (P1,P2,P3)   PTR;             // УКАЗАТЕЛИ НА МАТРИЦЫ
DCL (M,N,Q)      FIXED(31);       // ЗАДАННЫЕ ГРАНИЦЫ
DCL A(5,4)       FLOAT BASED(P1), // СТАТИЧЕСКИЕ МАТРИЦЫ
    B(4,3)       FLOAT BASED(P2),
    C(5,3)       FLOAT BASED(P3);
DCL (I,J,K)      FIXED(31);       // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- УМНОЖЕНИЕ МАТРИЦ ----

DO I=1 TO M;
   DO J=1 TO Q;
          C(I,J)=0;
          DO K=1 TO N;
                 C(I,J)+=A(I,K)*B(K,J);
          END K;
   END J;
END I;
END УМНОЖЕНИЕ_МАТРИЦ;
END TEST;

Обе программы дают идентичный результат:

C1(1,1)=  2.600000E+01 C1(1,2)=  1.200000E+01 C1(1,3)= -2.000000E+00
C1(2,1)=  3.200000E+01 C1(2,2)=  1.400000E+01 C1(2,3)= -4.000000E+00
C1(3,1)=  3.800000E+01 C1(3,2)=  1.600000E+01 C1(3,3)= -6.000000E+00
C1(4,1)=  4.400000E+01 C1(4,2)=  1.800000E+01 C1(4,3)= -8.000000E+00
C1(5,1)=  5.000000E+01 C1(5,2)=  2.000000E+01 C1(5,3)= -1.000000E+01

Заключение

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

            Схожие подходы изменения границ специальной операцией применялись и ранее, например, в языке Visual Basic имеется операция reDim, задающая границы при исполнении программы. Однако в этих случаях «динамически» меняются все же данные в программе, а не операнды команд ее исполняемого кода.

            Изменение же части кода при реализации многомерных массивов с изменяемыми во время исполнения границами, требует дополнительных действий для своеобразной «подготовки» выполняемого кода перед созданием очередного массива. Однако после такой корректировки кода программы, ее выполнение идет так, словно границы массивов были изначально заданы нужными значениями. Это позволяет сократить операции вычисления адресов элементов массивов и в целом ускорить программу, поскольку часто требуется корректировка лишь нескольких команд, а обращения к массивам могут быть затем многократными.

            И при этом, поскольку в компиляторе генерация кода доступа к массивам остается прежней, потребовались более простые доработки, чем, если бы создавался полный механизм «динамических» границ, предусматривающий постоянное хранение их значений в памяти и использование при каждом обращении к массиву.

Автор: Д.Ю.Караваев. 15.10.2019

Опубликовано: 2019.09.12, последняя правка: 2019.11.25    20:31

Оцените	Оценки посетителей
Нравится	███████████████ 5 (35.7%)
Неплохо	█████████ 3 (21.4%)
Так себе	██████ 2 (14.2%)
Не нравится	████████████ 4 (28.5%)




Отзывы

✅  2019/09/13 13:59, Автор сайта          #0 

Если границы массивов, а, значит, и объем занимаемой памяти, меняются во время исполнения программы, то в общем случае такие массивы не могут размещаться в «статической» памяти.

Это правильный вывод.

Поэтому память для массивов с «динамическими» границами должен явно выделять программист из «кучи» оператором ALLOCATE и освобождать оператором FREE.

А этот вывод не всегда правильный. Объекты переменной длины (а массив с динамическими границами — как раз такой объект) можно так же размещать в стеке при условии, что таких стеков два, а используются они по очереди. Подробнее — «Размещение объектов переменной длины с использованием двух стеков» и «Реализация двухстековой модели размещения данных». Поскольку оператор ALLOCATE работает значительно медленнее, чем вычитание значения из регистра RSP, то это даст ещё и прибавку в скорости.

Вот только любопытно: границы массива меняются уже после его создания? Или после создания границы массива «затвердевают»?

✅  2019/09/13 14:07, kt          #1 

Наверное, можно размещать и в стеке. Но для долгоживущих объектов, да еще, не дай бог, при параллельных процессах... Уж лучше (пока) на испытанной «куче».

границы массива меняются уже после его создания? Или после создания границы массива «затвердевают»?

Разумеется, границы должны быть изменены ДО создания. Т.е. до allocate и потом они остаются неизменными до соответствующего free.
При данной реализации, правда, есть нюанс — если границы уменьшаются по сравнению с предыдущими, можно не делать free/allocate и оставаться внутри уже раз выделенной памяти. Конечно, если не жалко, что часть области при этом становится бесполезной.

✅  2019/09/13 16:35, Автор сайта          #2 

Разумеется, границы должны быть изменены ДО создания.

Ну тогда двухстековая система это точно выдержит.

✅  2019/09/13 18:16, MihalNik          #3 

Ну тогда двухстековая система это точно выдержит.


Так free никуда не денется. Реальные массивы данных надо загружать/выгружать в произвольной очередности, стековая, когда функция получила данные, переработала и освободила память — подходит не всегда. Никто же, например, не закрывает вкладки в читалке/редакторе/браузере строго в обратном порядке.

Изменение же части кода при реализации многомерных массивов с изменяемыми во время исполнения границами, требует дополнительных действий для своеобразной «подготовки» выполняемого кода перед созданием очередного массива. Однако после такой корректировки кода программы, её выполнение идет так, словно границы массивов были изначально заданы нужными значениями. Это позволяет сократить операции вычисления адресов элементов массивов и в целом ускорить программу, поскольку часто требуется корректировка лишь нескольких команд, а обращения к массивам могут быть затем многократными. Тут хотелось бы каких-то замеров.

✅  2019/09/13 22:15, kt          #4 

Тут хотелось бы каких-то замеров.

Так возьмите любой язык, где есть и такие и такие массивы и сделайте тест многократных обращений к элементу массивов, например, по двум индексам и для динамических и для статических границ.
Для PL/1-KT такой замер сделать невозможно: у него отродясь не было динамических границ, только статические :)
Но исходя из общих соображений, вот такие команды для индексов I и J, как в начале статьи для динамических невозможны. Принимается, что адрес массива x(100,100) float(53) находится в указателе P:
Для статических:

mov  q rdi,P
imul q rax,I,800
add  q rdi,rax
mov  q rax,J
lea    rdi,0FFFFFCD8h[rdi+rax*8] ; начало X(I,J) 

Для динамических, если «паспорт» со значениями границ располагается перед началом массива, то как-нибудь так:

mov  q rdi,P
mov rax,[rdi]-16   ;верхняя граница 2
sub rax,[rdi]-8    ;нижняя граница 2
add rax,1
add rax,J          ;младший индекс
shl rax,3          ;умножаем число элементов на 8 байт
mov rbx,[rdi]-32   ;верхняя граница 1
sub rbx,[rdi]-24   ;нижняя граница 1
add rbx,1
add rbx,I          ;старший индекс
imul rbx           ;умножаем число элементов на размерность
lea rdi,[rdi+rbx]  ;начало X(I,J)


Раза так в полтора побыстрее

✅  2019/10/10 20:52, kt          #5 

Послал эту заметку в редакцию, сегодня получил ответ;

Уважаемый автор!
Ваша статья не была рекомендована нашими рецензентами для публикации в журнале "Программирование". Вот общий комментарий, поступивший от них:
Статья описывает механизм генерации кода для динамически изменяемых границ массива для языка PL/I. Механизм динамического изменения кода многократно
обкатан в JIT-компиляторах и системах исправления ошибок на лету (dynamic patching), там это обычно применяется для обеспечения безопасности. Неясна новизна статьи: сам по себе подход известен, а его детали в PL/I не будут интересны читателям журнала из-за низкой актуальности использования этого языка.
С уважением,
ответственный секретарь редакционной коллегии журнала "Программирование"
д.т.н. Л. Е. Карпов

Со своей стороны они правы: науки здесь ноль целых, хрен десятых. Не хватает журнала типа почившего RSDN magazine, где были уместны статьи, посвященные практике, а не только теории. В конце концов, программирование — это и практическая деятельность, а в журнале с таким названием полно заумных статей, которые нужны лишь для зачета публикаций авторам.
А вот насчет JIT-компиляторов, пожалуй, они не правы. Он работает не так потому, что ему не требуется исправлять операнды готовых команд, он сами эти команды генерирует.
В предлагаемой же схеме не требуется анализ кода, а лишь примитивный пересчет операндов.
Хотя по скорости трансляции PL/1-KT похож на JIT-компилятор :)

✅  2019/10/11 07:31, utkin          #6 

Всё это здорово конечно. Но есть замечания.
• Первое — есть концепция разрежённого массива, которая решает данную задачу в общем виде (то есть там нет ориентации на скорость, есть класс задач, который может быть решен эффективно). Пример разрежённого массива — это бесконечная таблица в Экселе. В общем виде разрежённые массивы могут расти в обе стороны. Реализация строго куча, никаких стеков.
• Второе — что значит затвердевание границы? Я снова обращаюсь к живому примеру — электронной таблице. Как бы Вы построили программу с использованием предлагаемой технологии?
• Третье — массивы создавались для того, чтобы избавиться от указателей, а не для того, чтобы ещё больше использовать их.

✅  2019/10/11 13:55, Автор сайта          #7 

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

Да уж, журнал «Программирование» сразу же после своего создания был превращён в отстойник для диссертантов. Это мне говорили люди, заставшие этот момент.

Неясна новизна статьи

Ну так новизна может быть не только научной, но и инженерной.

utkin
концепция разрежённого массива ... решает данную задачу в общем виде.

Решение задачи в общем виде менее эффективно, чем частный конкретный случай, когда границы массива «затвердевают». Т.е. границы являются аргументами конструктора массива, а после создания являются неизменными.

Разрежённые же массивы реализуются либо ассоциативным массивом, либо связным списком. Разные виды массивов хороши по-своему: обычные массивы эффективнее с точки зрения железа, а разрежённые удобны при решении задач «в общем виде»; электронные таблицы — подходящий «клиент» для разрежённых массивов. А вот для решения многих задач СУБД вполне подходят обычные массивы, границы которых «затвердевают» после создания.

✅  2019/10/11 12:59, kt          #8 

Здесь всё-таки подразумеваются задачи совсем другого класса, типа решения стационарного уравнения теплопроводности методом Либмана (которое обсуждалось в ветке «Идеальный транслятор»). Там главная возможность — использование массивов с заранее неизвестными границами как параметров подпрограмм. Самый простой пример, как в статье — возможность универсальной подпрограммы умножение матриц. Разреженные массивы в данном случае не годятся, они только замедлят работу и увеличат объем требуемой памяти.

А у меня стояла задача — ввести в маленький транслятор PL/1-KT«динамические» массивы не переделывая транслятор. И выход нашелся в корректировке операндов сгенерированного кода. И с приятным бонусом — вычисление адресов по индексам идет быстрее, чем в случае «настоящих» динамических массивов, где требуется больше умножений и сложений.

Я в RSDN кинул ссылку на эту ветку, там некто с ником IID обещал сравнить быстродействие. Но что-то молчит. Придется VIT1972 c theriodont просить, чтобы они сравнили быстродействие с компилятором IBM.

✅  2019/10/11 13:36, kt          #9 

забыл написать саму ссылку на RSDN:

http://rsdn.org/forum/flame.comp/7559764.1

✅  2019/10/12 16:11, Comdiv          #10 

Дмитрий. Кроме PL/I Вы знаете ещё языки? Можете изложить ту тестовую программу на RSDN более понятным образом для непричастных. Например, на Паскале? Вы писали, что это делается за минуты.

✅  2019/10/12 18:47, kt          #11 

Да очень простой пример — всего лишь подпрограмма умножения двух матриц заранее неизвестного размера MxN и NxQ, ответ — матрица размера MxQ.
Алгоритм умножения матриц приводится во многих местах, обычно на Си. Значение M N Q — 2000, 1500 и 1000. На моем ноутбуке расчет идет 30 секунд, при этом оптимизации у меня практически нет.

✅  2019/10/12 20:43, Comdiv          #12 

Да сам алгоритм вопросов не вызывает, а вот обвязка неясна. Она не имеет большого значения?

✅  2019/10/12 21:48, kt          #13 

"Обвязка" совершенно неважна. Это всего лишь некоторое заполнение матриц, чтобы они были не нулевые. И замер времени выполнения. Соль теста — определить выигрыш, который дает (или не дает или компенсируется оптимизацией) использование статических массивов вместо динамических. Обращение к элементам динамических массивов более громоздкое (и долгое), чем к массивам, границы которые известны при компиляции. Приведенный в статье механизм дает одинаковую скорость за счет корректировки операндов команд перед использованием массивов. Интересно сравнить с PL/1 IBM или с Фортраном: у них развитая оптимизация.

✅  2019/10/12 23:42, Comdiv          #14 

У меня получилась такая версия на C:

#include <stdlib.h>
#include <stdio.h>

#if !defined(CONST_BOUNDS)
#   define CONST_BOUNDS (0>1)
#endif

#if defined(M) && defined(N) && defined(Q)
//  здесь три точки без пробелов, но это сочетание приводит к проблемам отображения на этом сайте
#   define BOUNDS(...)
#else
#   define BOUNDS(...) __VA_ARGS__
#endif

static void mul(BOUNDS(int M, int N, int Q,)
                float const a[M][N], float const b[N][Q],
                float c[M][Q])
{
    for (int i = 0; i < M; i += 1) {
        for (int j = 0; j < Q; j += 1) {
            c[i][j] = 0.0;
            for (int k = 0; k < N; k += 1) {
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
}

static void init(BOUNDS(int M, int N, int Q,)
                 float a[M][N], float b[N][Q])
{
    for (int i = 0; i < M; i += 1) {
        for (int j = 0; j < N; j += 1) {
            a[i][j] = i + j + 2;
        }
    }
    for (int i = 0; i < N; i += 1) {
        for (int j = 0; j < Q; j += 1) {
            b[i][j] = i — j;
        }
    }
}

static void printMatrix(BOUNDS(int M, int Q,) float c[M][Q]) {
    for (int i = 0; i < M; i += 1) {
        for (int j = 0; j < Q; j += 1) {
            printf("%g ", c[i][j]);
        }
        printf("\n");
    }
}

static float sumAll(BOUNDS(int M, int Q,) float c[M][Q]) {
    float sum;
    sum = 0;
    for (int i = 0; i < M; i += 1) {
        for (int j = 0; j < Q; j += 1) {
            sum += c[i][j];
        }
    }
    return sum;
}

static void run(BOUNDS(int M, int N, int Q)) {
    float (*a)[M][N], (*b)[N][Q], (*c)[M][Q];
    a = malloc(sizeof(*a));
    b = malloc(sizeof(*b));
    c = malloc(sizeof(*c));
    init(BOUNDS(M, N, Q,) *a, *b);
    mul(BOUNDS(M, N, Q,) *a, *b, *c);
    if (M * Q < 65) {
        printMatrix(BOUNDS(M, Q,) *c);
    } else {
        printf("%g\n", sumAll(BOUNDS(M, Q,) *c));
    }
    free(a);
    free(b);
    free(c);
}

int main(int argc, char *argv[]) {
    run(BOUNDS(atoi(argv[1]), atoi(argv[2]), atoi(argv[3])));
    return 0;
}

23:34:09 matrix: # динамические границы
23:34:27 matrix: gcc mulma.c -o mulma -O1
23:34:38 matrix: time ./mulma 2000 1500 1000
1.87575e+15

real	0m19,363s
23:35:14 matrix: # динамические границы с контролем границ массива
23:35:32 matrix: gcc mulma.c -o mulma -O1 -fsanitize=undefined -fsanitize-undefined-trap-on-error
23:35:43 matrix: time ./mulma 2000 1500 1000
1.87575e+15

real	0m20,990s
23:36:06 matrix: # статические границы
23:36:23 matrix: gcc mulma.c -o mulma -DM=2000 -DN=1500 -DQ=1000 -O1
23:36:44 matrix: time ./mulma
1.87575e+15

real	0m19,410s
23:37:13 matrix: gcc mulma.c -o mulma -DM=2000 -DN=1500 -DQ=1000 -O3
23:37:18 matrix: time ./mulma
1.87575e+15

real	0m5,146s
23:37:28 matrix: gcc mulma.c -o mulma -O3
23:37:59 matrix: time ./mulma 2000 1500 1000
1.87575e+15

real	0m19,298s

Ваш исполняемый файл из-под WINE падает, наверно, из-за динамических правок кода

✅  2019/10/13 10:39, kt          #15 

Спасибо за исчерпывающий тест. Похоже, кроме одного режима оптимизации, "статичность" границ вообще не учитывается.

из-под WINE падает, наверно, из-за динамических правок кода

"это вряд ли" (с) т. Сухов

Надеюсь, таблицу адресов А5.ТХТ не забыли скачать и переименовать?
Если можно, запустите файл в режиме отладчика командой: "A5.EXE ??"
После этого команда "G" и должна быть хоть какая-то диагностика

✅  2019/10/13 18:23, Comdiv          #16 

Надеюсь, таблицу адресов А5.ТХТ не забыли скачать и переименовать?

Забыл, как же без этого

START=  9.71444508209000E+008
?STIME=  9.71444533775000E+008 ?STIME-START=  2.55659999847412E+001

Похоже, кроме одного режима оптимизации, "статичность" границ вообще не учитывается.

Почему в кавычках и почему не учитывается? Просто компилятор хорошо оптимизирует. Как Вы понимаете, во многих случаях не все действия по вычислению адреса нужно выполнять каждый раз.
Вот результаты выполнения с минимальным уровнем оптимизации (ниже некуда)

18:00:06 matrix: gcc mulma.c -o mulma
18:00:50 matrix: time ./mulma 2000 1500 1000
1.87575e+15

real	0m24,745s
18:01:19 matrix: gcc mulma.c -o mulma -DM=2000 -DN=1500 -DQ=1000
18:01:29 matrix: time ./mulma
1.87575e+15

real	0m23,191s

С результатами трансляции можно ознакомиться здесь — https://godbolt.org/z/in4jji

Также я задал Ваш вопрос в телеграмм-канале, где находится множество практикующих компиляторщиков (не "рассадник диссертантов"). Если кратко резюмировать их ответы, то несмотря на то, что они отметили изменение машинного кода как целесообразное решение и применяемое ими на практике, конкретно для массивов они не знают случаев такого применения и скептически отнеслись к нему и предположили, что полезность такого подхода вызвана применением простенького самописного компилятора. Оптимизирующие компиляторы используют более общие механизмы, например https://en.wikipedia.org/wiki/Loop-invariant_code_motion

✅  2019/10/13 19:02, kt          #17 

Спасибо за доделанную до конца работу. Только обратите внимание, что данный пример был простейший (и хорошо оптимизируемый). В больших программах не все сводится к тройным непрерывным циклам, что и дает здесь глубокую оптимизацию.
Статические границы в общем случае объективно быстрее считаются, хотя бы потому, что для них возможна команда умножения для индекса I типа:

imul rdi,I,800

Динамические границы не позволяют поместить константу 800 прямо в команду, поскольку она заранее неизвестна. Из-за этого собственно и выигрыш.
И еще. Данный способ вполне может использоваться совместно с другой оптимизацией, а не вместо нее. И тогда выигрыш был бы ещё больше.

✅  2019/10/13 20:16, Comdiv          #18 

Только обратите внимание, что данный пример был простейший(и хорошо оптимизируемый)

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

Данный способ вполне может использоваться совместно с другой оптимизацией, а не вместо нее. И тогда выигрыш был бы ещё больше.

Не совсем. Слишком частные случаи погоды не сделают. Для того, чтобы применить такую оптимизацию для более общего случая необходимо, на мой взгляд, существенно усложнить транслятор. Время всегда дефицитное и если тратить время на решения, которые по принципу Парето требуют 80% усилий для достижения 20% результата, то решение окажется неверным.

Кстати, какой выигрыш в этом примере получился на Вашем трансляторе?

✅  2019/10/13 21:34, kt          #19 

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

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

Кстати, какой выигрыш в этом примере получился на Вашем трансляторе?

Никакого. Не с чем сравнивать, поскольку в PL/1-KT не было динамических границ и я как раз и ввел их корректировкой статических. Именно для того, чтобы не менять (усложнять) транслятор.

✅  2019/10/13 21:44, Comdiv          #20 

Нет, транслятор практически не усложняется

Тогда интересно узнать, как транслятор работает с подпрограммой, в которую передаётся массив с открытыми границами? Тело подпрограммы переписывается каждый раз при вызове? Все другие случаи использования тоже обрабатываются?

✅  2019/10/13 22:00, Comdiv          #21 

Посмотрел внимательно на программу. Похоже что каждый раз. Это означает, что в некоторых случаях это будет приводить наоборот, к замедлению. Ну и решение на PL/1, в целом, выглядит хардкорно, многословно и небезопасно. Как я вижу, открытых массивов нет — это просто указатели, которые на честном слове приводятся к нужным массивам. Как будет вести себя программа со списком массивов, к примеру?
Честных именованных констант тоже нет? Ведь иначе не было бы нужно задавать массив с константными границами через числа напрямую. Или это недочёт конкретного примера?

✅  2019/10/13 22:56, kt          #22 

Тело подпрограммы переписывается каждый раз при вызове?

Каждый раз не переписывается, а внутри несколько констант-операндов меняется.

Это означает, что в некоторых случаях это будет приводить наоборот, к замедлению.


В примере меняется десяток констант, а затем идут миллионы обращений к массивам. Потери на корректировку малы. А если и размерность массивов мала — общие затраты времени невелики.

Как будет вести себя программа со списком массивов, к примеру?

Не понял. В примере было 6 массивов — 3 формальных и 3 фактических параметра. Ну, было бы их не 6, а 1006, какая разница? Технология одна на всех.

Честных именованных констант тоже нет?

Не имеет отношения к теме. В PL/1-KT есть оператор %replace. Зачем затенять пример посторонними вещами?

И я, например, увидел, что никакого реального контроля выхода индексов за границы в проведенных тестах нет. Возможно, и переменные индексов не созданы. Для данного простого примера с непрерывными циклами для массивов это возможно. В большинстве реальных алгоритмов — нет. Попробуйте добавить в тесты печать индексов I,J,K (например, при ошибке) и посмотрите на время выполнения.

✅  2019/10/14 00:26, Comdiv          #23 

Попробуйте добавить в тесты печать индексов I,J,K (например, при ошибке) и посмотрите на время выполнения.

Я уже приводил результаты тестов с проверкой

gcc mulma.c -o mulma -O1 -fsanitize=undefined -fsanitize-undefined-trap-on-error

Не поленитесь, соберите и всё увидите. Сможете попробовать и с более сложными случаями. Си — это не тот язык, который упирается самострелу, но даже в нём в его современной форме контроль выглядит более полным в данном случае.

В PL/1-KT есть оператор %replace. Зачем затенять пример посторонними вещами?

Нормальные константы ничего не затеняют. Это как DECLARE, только CONST, то есть, это не потребовало бы никаких добавлений в код.

В примере меняется десяток констант, а затем идут миллионы обращений к массивам. Потери на корректировку малы.

Я потому и писал про общий случай, а не частные. Уточню — что будет, когда потребуется обработать связный список/массив динамических массивов, что является достаточно рядовой ситуацией. Массивы могут оказаться невелики, а сам список — наоборот.
Хотя, пожалуй, представить себе работу с массивом динамических массивов, для нынешней реализации довольно проблематично.
Как будет выглядеть код, подобный этому утрированному примеру?

PROCEDURE Do(a: ARRAY OF POINTER TO ARRAY *,* OF INTEGER; y,j,k: INTEGER): INTEGER;
RETURN a[y][j][k]
END Do;

✅  2019/10/14 10:05, kt          #24 

Я имел ввиду, что в простых случаях оптимизатор не вставляет реальные команды контроля индексов. Но если есть операторы вывода индексов — их придется заполнять и время увеличится. Мы это разбирали в ветке «Идеальный транслятор». Оптимизатор IBM даже не заводил переменных, если их не выводить.

В свете предлагаемой технологии пример выглядел бы как-то так (x,x1,x2 — границы массивов, здесь их надо задавать явно):

Do:PROCEDURE (p,x,y,j,k) RETURNS(FIXED(*));
DCL 
p           PTR,
(x,y,j,k)   FIXED(*),
1 a(*), 
 2 a1       PTR CTL,
 2 x1,x2)   FIXED(*),
b(*,*)      FIXED(*) CTL;

ADDR(a)=p;
?INDEX(1,1)=1;     ?INDEX(1,2)=x;    ?RET(ADDR(a));
ADDR(b)=a1(y);
?INDEX(1,1)=x1(y); ?INDEX(1,2)=x2(y);?RET(ADDR(b));
RETURN (b(j,k));
END Do;

✅  2019/10/14 12:56, Comdiv          #25 

Я имел ввиду, что в простых случаях оптимизатор не вставляет реальные команды контроля индексов. Но если есть операторы вывода индексов — их придется заполнять и время увеличится.

Верно, но в типичном случае при произвольном доступе не будет и многих обращений к массиву за раз. В любом случае, не хотите продолжить тестирование технологии? Можете предложить реалистичный алгоритм для тестирования, где требуется произвольный доступ? Например, при работе с ассоциативным массивом. И не хотите провести сравнение для обхода массива небольших динамических массивов?

✅  2019/10/14 13:41, kt          #26 

А зачем? Я, наверное, привел неудачный пример для сравнения производительности. Умножение массивов — это в данном случае слишком примитивно.
Все равно команды для расчета адресов для границ-констант принципиально короче, чем для динамических. Кроме того, не факт, что статические и динамические границы всегда реализовались по-разному в тестах этим транслятором. А, может, когда действительно по-разному, то и результат — в 4 раза быстрее по Вашим же данным.

Предлагаемая мною технология применима во всех случаях как ещё один «слой» оптимизации. А для действительного сравнения тестов нужно анализировать сгенерированные команды. Иначе может получиться неправомерное сравнение.

✅  2019/10/14 18:52, Comdiv          #27 

А зачем?

Чтобы лучше понять настоящие, а не гипотетические возможности технологии. Выявить сильные и слабые стороны и скорректировать транслятор по практическим данным.

А, может, когда действительно по-разному, то и результат — в 4 раза быстрее по Вашим же данным.

Судя по выводу кода, транслятор при сильной оптимизации векторизовал вычисления — по 4 float за раз, что идеально согласуется со временем. С double закономерно считает в 2-а раза медленней. Теоретически, транслятор мог бы векторизовать и с динамическими границами, но не шмог. Границы здесь влияют очень опосредованно. Полагаю, что трансляторы Fortran, для которых это родная стихия, будут векторизовать в любых случаях.

✅  2019/10/14 22:08, kt          #28 

Так и не нужно строить гипотезы. Нужны распечатки подпрограммы самого умножения, хотя бы в виде псевдоассемблера. Тогда и будет ясно, почему такие времена исполнения, например, вот код псевдоассемблера PL/1-KT (оптимизация фактически отсутствует):

//---- САМО УМНОЖЕНИЕ ----
DO I=1 TO M;
48C7051802000001000000      mov  q I,1
488B3D00020000              mov  q rdi,M
486307                      movsxq rax,[rdi]
48A36002000000000000        mov  q @00000260h,rax
                        @18:
48A16002000000000000        mov  q rax,@00000260h
48390518020000              cmp  q I,rax
0F8F00000000                jg     @19
   DO J=1 TO Q;
48C7052002000001000000      mov  q J,1
488B3D10020000              mov  q rdi,Q
486307                      movsxq rax,[rdi]
48A36802000000000000        mov  q @00000268h,rax
                        @20:
48A16802000000000000        mov  q rax,@00000268h
48390520020000              cmp  q J,rax
0F8F00000000                jg     @21
      C(I,J)=0;
488B3DB0000000              mov  q rdi,?P0006
48690518020000E4030000      imul q rax,I,996
4803F8                      add  q rdi,rax
48A12002000000000000        mov  q rax,J
488DBC87D8DCFFFF            lea    rdi,0FFFFDCD8h[rdi+rax*4]
BE10010000                  mov  q rsi,offset @00000110h
A5                          movs
      DO K=1 TO N;
48C7052802000001000000      mov  q K,1
488B1D08020000              mov  q rbx,N
486303                      movsxq rax,[rbx]
48A37002000000000000        mov  q @00000270h,rax
                        @22:
48A17002000000000000        mov  q rax,@00000270h
48390528020000              cmp  q K,rax
0F8FC0000000                jg     @23
         C(I,J)+=A(I,K)*B(K,J);
488B3DC0000000              mov  q rdi,?P0004
48690518020000E4030000      imul q rax,I,996
4803F8                      add  q rdi,rax
48A12802000000000000        mov  q rax,K
48C1E002                    shl  q rax,2
4803F8                      add  q rdi,rax
488B35B8000000              mov  q rsi,?P0005
48690528020000E4030000      imul q rax,K,996
4803F0                      add  q rsi,rax
48A12002000000000000        mov  q rax,J
488D9C86D8DCFFFF            lea    rbx,0FFFFDCD8h[rsi+rax*4]
488D97D8DCFFFF              lea    rdx,0FFFFDCD8h[rdi]
F8                          clc
D903                        FLD32  [RBX]
53                          PUSH   RBX
D80A                        FMUL32 [RDX]
D91C24                      FST32P [RSP]
488B3DB0000000              mov  q rdi,?P0006
48690518020000E4030000      imul q rax,I,996
4803F8                      add  q rdi,rax
48A12002000000000000        mov  q rax,J
488D9C87D8DCFFFF            lea    rbx,0FFFFDCD8h[rdi+rax*4]
F8                          clc
D90424                      FLD32  [RSP]
D803                        FADD32 [RBX]
58                          POP    RAX
488B3DB0000000              mov  q rdi,?P0006
48690518020000E4030000      imul q rax,I,996
4803F8                      add  q rdi,rax
48A12002000000000000        mov  q rax,J
488DBC87D8DCFFFF            lea    rdi,0FFFFDCD8h[rdi+rax*4]
D91F                        fst32p [rdi]
48FF0528020000              inc  q K
E929FFFFFF                  jmp    @22
                        @23:
48FF0520020000              inc  q J
E9BAFEFFFF                  jmp    @20
                        @21:
48FF0518020000              inc  q I
E978FEFFFF                  jmp    @18
                        @19:
C3                          ret

✅  2019/10/15 10:51, Comdiv          #29 

Мне следовало выразиться ясней — судя по ассемблерному коду, выведенному транслятором, он провёл векторизацию. Если Вы всё-таки сходите по ссылке на godbolt, то увидите в удобной интерактивной форме этот код — https://godbolt.org/z/OetsT3

✅  2019/10/15 12:30, kt          #30 

Ну да, вот интересующий нас кусочек собственно умножения матриц с помощью SSE:

.L17:
xor      r8d, r8d
.L16:
Pxor     xmm1, xmm1
lea      rax, [rbx+r8]
lea      rcx, [r10+r8]
mov      rdx, rdi
.L15:
movss    xmm0, DWORD PTR [rdx]
add      rax, 4000
add      rdx, 4
shufps   xmm0, xmm0, 0
movups   xmm6, XMMWORD PTR [rax-4000]
cmp      rcx, rax
mulps    xmm0, xmm6
addps    xmm1, xmm0
jne .    L15
movups   XMMWORD PTR [r9+r8], xmm1
add      r8, 16
cmp      r8, 4000
jne      .L16
add      rdi, 6000
add      r9, 4000
cmp      r11, rdi
jne      .L17

Так по предлагаемой технологии достаточно на лету менять операнды-константы 4000 и 6000 и этот же код будет действовать для динамических границ с той же 4-х кратной скоростью.

✅  2019/10/15 13:05, Александр Коновалов aka Маздайщик          #31 

А я выскажусь вот о чём. Не о производительности примера, а об эргономике для программиста.

Очень некрасиво, что для того, чтобы создать динамический массив, приходится делать два присваивания, вызов процедуры и оператор allocate. Имеют ли смысл присваивания элементам массива ?index без вызова ?ret и allocate? Имеет ли смысл allocate без присваиваний и вызова процедуры? Осмысленно ли вызывать процедуру ?ret без присваиваний и allocate?

В большинстве случаев — нет. Конечно, если аллоцируются несколько массивов одинакового размера, можно один раз присвоить значения элементам ?index и после этого массивы аллоцировать. Но в остальном разделять эти операции бессмысленно.

Поэтому я бы при проектировании таких динамических массивов добавил синтаксический сахар для типичного случая:

dcl  n      fixed(31),
     x(*)   float ctl;
get list(n);
allocate x(0:n);

Вызов allocate arr(a:b, c:d…) автоматически присваивает значения ?index, вызывает ?ret и после этого аллоцирует массив.


И ещё одно соображение: если подпрограмма использует динамические массивы и динамически корректирует свой код, то она не должна быть рекурсивной. Я не помню, Ваш PL/1 поддерживает рекурсию или нет?

✅  2019/10/15 13:20, Александр Коновалов aka Маздайщик          #32 

Дополняю предыдущий комментарий.

Операцию allocate вызывать без ?index и ?ret бессмысленно. Но наоборот — осмысленно, для процедур, принимающих динамические массивы.

Передача динамических массивов в подпрограммы — вещь довольно типичная, для неё тоже имело бы смысл ввести синтаксический сахар. Вернее, он введён, но очень скромно: addr(A) = p. А красиво было бы сделать так:

УМНОЖЕНИЕ_МАТРИЦ:PROC(P1,P2,P3,M,N,Q);

//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ — МАТРИЦА C(M,Q) ----

DCL (P1,P2,P3)   PTR;       // УКАЗАТЕЛИ НА МАТРИЦЫ
DCL (M,N,Q)      FIXED(31); // ЗАДАННЫЕ ГРАНИЦЫ
DCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦЫ
DCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- ВОССТАНАВЛИВАЕМ ДИНАМИЧЕСКИЕ МАССИВЫ ----

ALLOCATE A(M,N)=P1;
ALLOCATE B(N,Q)=P2;
ALLOCATE C(M,Q)=P3;

//---- УМНОЖЕНИЕ МАТРИЦ ----

DO I=1 TO M;
   DO J=1 TO Q;
          C(I,J)=0;
          DO K=1 TO N;
                 C(I,J)+=A(I,K)*B(K,J);
          END K;
   END J;
END I;
END УМНОЖЕНИЕ_МАТРИЦ;

Синтаксис

allocate arr(a:b, …)=p;

означал бы инициализацию динамического массива без реальной аллокации памяти — за основу брался бы указатель p.

В Си++ тоже есть «размещающее new», которое не выделяет память, а только вызывает конструктор для объекта по данному указателю.

char buffer[sizeof(std::string)];
std::string *p = new (buffer) std::string;

Теперь указатель p содержит адрес массива buffer, а сам buffer инициализирован объектом std::string.

✅  2019/10/15 13:31, kt          #33 

Спасибо. Я как-то не обращал внимания и сразу вспомнился анекдот, как отец с сыном сами надстроили в доме второй этаж. Пригласили всех знакомых отметить, торжественно снесли леса. Но когда запоздавший гость хотел посмотреть построенное, оказалось, что забыли спроектировать лестницу на 2 этаж, а сами за это время так привыкли взбираться по лесам, что не обращали внимания на её отсутствие. С allocate красиво. Вы правы, подумать стоит и сахар здесь уместен.

Рекурсия и параллельность в PL/1-KT допустимы, и, да, в данном случае автоматической защиты от повторной коррекции кода нет.

✅  2019/10/15 15:06, Comdiv          #34 

Так по предлагаемой технологии достаточно на лету менять операнды-константы 4000 и 6000 и этот же код будет действовать для динамических границ с той же 4-х кратной скоростью.

Суть в том, что векторизация будет работать и для динамических границ, просто капризный оптимизатор отказался это делать. Его вообще легко "отговорить" от векторизации даже для константных границ, к примеру, достаточно функцию сделать extern вместо static. То есть, здесь основная оптимизация лежит совершенно в другой области. Если константные границы позволяют на адресации сэкономить в лучшем случае 10%, векторизация позволяет 75%. Ещё одна серьёзная оптимизация может быть в играх с кэшем процессора, но для этого надо преобразовать одну из матриц, что для оптимизатора слишком сложно и неочевидно.

✅  2019/10/15 15:07, Александр Коновалов aka Маздайщик          #35 

В руководствах по хорошему стилю программирования рекомендуют избегать временных зависимостей между функциями (например, Роберт Мартин «Чистый код», параграф G31, стр. 342). Например, если класс или библиотека требует, чтобы последовательно вызывались функции f() и g(), при этом именно в таком порядке, то здесь что-то не так с интерфейсом. Или надо ввести библиотечную функцию f_and_g(), или сделать зависимость явной зависимостью по данным: x = f(); g(x);.

Причина такой рекомендации очевидна: в случае временной зависимости программист может перепутать порядок вызовов или забыть вызвать одну из функций f() и g(). И такую ошибку иногда может быть сложно отладить. Поэтому хороший стиль — проектировать интерфейсы так, чтобы снизить вероятность ошибки.

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

Да и не только безопаснее, но и удобнее. В том же примере на умножение матриц текст

?INDEX(1,2)=M; ?INDEX(2,2)=N;
?RET(ADDR(A));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ A
?INDEX(1,2)=N; ?INDEX(2,2)=Q;
?RET(ADDR(B));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ B
?INDEX(1,2)=M;
?RET(ADDR(C));                    // ИЗМЕНЯЕМ КОМАНДЫ ДЛЯ C

требует 6 строк, в то время как само перемножение матриц — 8 строк. Слишком много текста уходит на служебные операции, потому что они слишком низкоуровневые. Действительно, как по лесам карабкаться. Нужно повышать уровень языка.

✅  2019/10/15 15:22, Александр Коновалов aka Маздайщик          #36 

А вообще, самый компактный синтаксис — синтаксис которого нет.

УМНОЖЕНИЕ_МАТРИЦ:PROC(A,B,C);

//---- ВХОД A(M,N) И B(N,Q), ОТВЕТ — МАТРИЦА C(M,Q) ----

DCL (A,B,C)(*,*) FLOAT CTL; // ДИНАМИЧЕСКИЕ МАТРИЦЫ
DCL (I,J,K)      FIXED(31); // РАБОЧИЕ ПЕРЕМЕННЫЕ

//---- УМНОЖЕНИЕ МАТРИЦ ----

DO I=1 TO HBOUND(A,1);
   DO J=1 TO HBOUND(B,2);
          C(I,J)=0;
          DO K=1 TO HBOUND(A,2);
                 C(I,J)+=A(I,K)*B(K,J);
          END K;
   END J;
END I;
END УМНОЖЕНИЕ_МАТРИЦ;

Если среди параметров есть массивы с динамическими границами, то коррекция кода происходит неявно.

Но для этого каждый массив, включая статические, должен иметь свой паспорт. Подпрограмма, принимающая массив, смотрит в паспорт и корректирует свой код.

✅  2019/10/15 15:38, Александр Коновалов aka Маздайщик          #37 

Как можно решить проблему с параллельностью и рекурсией. Если подпрограмма модифицирует свой код (содержит динамические массивы), то для неё можно генерировать подпрограмму-переходник. Переходник выделяет на стеке буфер размером с основную подпрограмму, копирует её в буфер и вызывает подпрограмму, лежащую на стеке. Недостаток: расходы на копирование. Преимущество: реентерантность.

✅  2019/10/15 16:32, kt          #38 

Нужно повышать уровень языка.

Да я не спорю. Сначала думалось передавать границы как параметры в ?RET, но поскольку размерностей (число пар) может быть до 15, а переменное число аргументов в PL/1-KT не реализовано, то пришлось по быстрому ввести глобальные переменные ?INDEX, что не очень красиво. Да и все силы ушли на реализацию, на интерфейс уже не хватило.

А вообще, самый компактный синтаксис — синтаксис которого нет.

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

Это известно ещё со времен БЭСМ-Алгола, но у меня стояла главная задача ввести динамические массивы, не переделывая транслятор, что в общем-то и удалось.

для неё можно генерировать подпрограмму-переходник

С параллельностью мы вообще часто поступали по «рабоче-крестьянски»: тело подпрограммы писали в отдельный файл и создавали множество подпрограмм для разных потоков:

Program_a:proc %include'f1.pl1';
Program_b:proc %include'f1.pl1';
Program_c:proc %include'f1.pl1';

Затем в каждом потоке использовалась только одна подпрограмма с номером потока, например, с помощью массива ENTRY-VARIABLE:

Program(1)=Program_a;
Program(2)=Program_b;
Program(3)=Program_c;

call program(i)(a,b,c,); // параллельный вызов для потока i 

В общем, как говорил Скуперфильд из «Незнайки на Луне»: «и пусть бесплатно убираются к лешему!»

Добавить свой отзыв

Написать автору можно на электронную почту
mail(аt)compiler.su