Каким должен быть язык программирования? Анализ и критика Описание языка Компилятор
Отечественные разработки Cтатьи на компьютерные темы Компьютерный юмор Новости и прочее

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

Введение

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

                В свете все возрастающего потока англоязычных терминов в области программирования и следуя за модой, в названии статьи можно было бы вместо «модификация исполняемого кода» написать что-нибудь вроде «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, задающая границы при исполнении программы. Однако в этих случаях «динамически» меняются все же данные в программе, а не операнды команд ее исполняемого кода.

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

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

    Опубликовано: 2019.09.12, последняя правка: 2019.09.12    18:51

    Оцените

    Отзывы

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

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

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

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

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

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

         2019/09/13 14:07, kt          # 

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

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

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

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

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

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

         2019/09/13 18:16, MihalNik          # 

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


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

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

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

         2019/09/13 18:18, MihalNik          # 

    Второй абзац выше излишне зацитирован, следует читать как ответ на пред. цитату.

         2019/09/13 22:15, kt          # 

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

    Так возьмите любой язык, где есть и такие и такие массивы и сделайте тест многократных обращений к элементу массивов, например, по двум индексам и для динамических и для статических границ.
    Для 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)

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

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

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

Авторизация

Регистрация

Выслать пароль

Карта сайта


Каким должен быть язык программирования?

Анализ и критика

Описание языка

Компилятор

Отечественные разработки

Cтатьи на компьютерные темы

Двадцать тысяч строк кода, которые потрясут мир?

Почему владение/заимствование в Rust такое сложное?

Масштабируемые архитектуры программ

Почему Хаскелл так мало используется в отрасли?

Программирование исчезнет. Будет дрессировка нейронных сетей

Бесплатный софт в мышеловке

Исповедь правового нигилиста

Русской операционной системой должна стать ReactOS

Почему обречён язык Форт

Программирование без программистов — это медицина без врачей

Электроника без электронщиков

Программисты-профессионалы и программирующие инженеры

Статьи Дмитрия Караваева

●  Идеальный транслятор

●  В защиту PL/1

●  К вопросу о совершенствовании языка программирования

●  О реализации метода оптимизации при компиляции

●  О реализации метода распределения регистров при компиляции

●  О распределении памяти при выполнении теста Кнута

●  Опыты со стеком или «чемпионат по выполнению теста Кнута»

●  О размещении переменных в стеке

●  Сколько проходов должно быть у транслятора?

●  Чтение лексем

●  Экстракоды при синтезе программ

●  Об исключенных командах или за что «списали» инструкцию INTO?

●  Типы в инженерных задачах

●  Непрерывное компилирование

●  Об одной реализации специализированных операторов ввода-вывода

●  Особенности реализации структурной обработки исключений в Win64

●  О русском языке в программировании

●  Формула расчета точности для умножения

●  Права доступа к переменным

●  Заметки о выходе из функции без значения и зеркальности get и put

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

●  Ошибка при отсутствии выполняемых действий

●  Скорость в попугаях

●  Крах операции «Инкогнито»

●  Предопределённый результат

Компьютерный юмор

Новости и прочее

Последние комментарии

2019/09/15 21:18 ••• Александр Коновалов aka Маздайщик
Признаки устаревшего языка

2019/09/15 14:53 ••• Александр Коновалов aka Маздайщик
Некошерный «goto»

2019/09/13 16:38 ••• Автор сайта
Программирование исчезнет. Будет дрессировка нейронных сетей

2019/09/13 16:35 ••• Автор сайта
Модификация исполняемого кода как способ реализации массивов с изменяемыми границами

2019/09/12 20:40 ••• Александр Коновалов aka Маздайщик
Циклы

2019/08/30 07:57 ••• Noname
Почему обречён язык Форт

2019/08/29 09:07 ••• рст256
Устарел ли текст как форма представления программы

2019/08/19 19:19 ••• Автор сайта
Шестнадцатиричные и двоичные константы

2019/08/05 19:22 ••• Геннадий Тышов
Программирование без программистов — это медицина без врачей

2019/07/30 14:06 ••• Александр Коновалов aka Маздайщик
К вопросу о совершенствовании языка программирования

2019/07/21 20:30 ••• Автор сайта
Деньги = работа / знание

2019/07/20 19:42 ••• Александр Коновалов aka Маздайщик
Права доступа к переменным