Резьбовой код

Не путать с многопоточным программированием или переходом на потоки .

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

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

Многопоточный код наиболее известен благодаря его использованию во многих компиляторах языков программирования , таких как Forth , многих реализациях BASIC , некоторых реализациях COBOL , ранних версиях B , и другие языки для небольших миникомпьютеров и радиолюбительских спутников .

История

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

Ранние компьютеры имели относительно мало памяти. Например, большинство Data General Nova , IBM 1130 и многие первые микрокомпьютеры имели только 4 КБ оперативной памяти. Следовательно, много времени было потрачено на поиск способов уменьшить размер программы, чтобы она уместилась в доступной памяти.

Одним из решений является использование интерпретатора, который понемногу считывает символический язык и вызывает функции для выполнения действий. Поскольку исходный код обычно намного плотнее результирующего машинного кода, это может снизить общее использование памяти. Именно по этой причине Microsoft BASIC является интерпретатором: его собственный код должен был использовать 4 КБ памяти таких машин, как Altair 8800, с исходным кодом пользователя. Компилятор преобразует исходный язык в машинный код, поэтому компилятор, исходный код и выходные данные должны находиться в памяти одновременно. В интерпретаторе вывода нет.

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

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

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

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

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

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

Развитие

Чтобы сэкономить место, программисты сжимали списки вызовов подпрограмм в простые списки адресов подпрограмм и использовали небольшой цикл для вызова каждой подпрограммы по очереди. Например, следующий псевдокод использует этот метод для сложения двух чисел A и B. В этом примере список помечен как поток , а переменная ip (указатель инструкций) отслеживает наше место в списке. Другая переменная sp (указатель стека) содержит адрес в другом месте памяти, который доступен для временного хранения значения.

start:
  ip = &thread  // points to the address '&pushA', not the textual label 'thread'
top:
  jump *ip++  // follow ip to address in thread, follow that address to subroutine, advance ip
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A  // follow sp to available memory, store A there, advance sp to next 
  jump top
pushB:
  *sp++ = B
  jump top
add:
  addend1 = *--sp  // Pop the top value off the stack
  addend2 = *--sp  // Pop second value off the stack
  *sp++ = addend1 + addend2  // Add the two values together and store the result on the top of the stack
  jump top

Вызовной цикл в top настолько прост, что его можно повторять в конце каждой подпрограммы. Управление теперь переходит один раз, из конца одной подпрограммы в начало другой, вместо двойного перехода через top. Например:

start:
  ip = &thread  // ip points to &pushA (which points to the first instruction of pushA)
  jump *ip++  // send control to first instruction of pushA and advance ip to &pushB
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  *sp++ = A  // follow sp to available memory, store A there, advance sp to next 
  jump *ip++  // send control where ip says to (i.e. to pushB) and advance ip
pushB:
  *sp++ = B
  jump *ip++
add:
  addend1 = *--sp  // Pop the top value off the stack
  addend2 = *--sp  // Pop second value off the stack
  *sp++ = addend1 + addend2  // Add the two values together and store the result on top of the stack
  jump *ip++

Это называется кодом с прямой резьбой (DTC). Хотя этот метод более старый, первым широко распространенным использованием термина «поточный код», вероятно, является статья Джеймса Р. Белла 1973 года «Поточный код».

В 1970 году Чарльз Х. Мур изобрел более компактную структуру — косвенный многопоточный код (ITC) для своей виртуальной машины на Форте. Мур пришел к такой схеме, потому что миникомпьютеры Nova имели бит косвенности в каждом адресе, что делало ITC простым и быстрым. Позже он сказал, что нашел это настолько удобным, что распространил его во все более поздние разработки Форта.

Сегодня некоторые компиляторы Форта генерируют код с прямой резьбой, тогда как другие генерируют код с косвенной резьбой. Исполняемые файлы в любом случае действуют одинаково.

Модели резьбы

Практически весь исполняемый многопоточный код использует тот или иной из этих методов для вызова подпрограмм (каждый метод называется «потоковой моделью»).

Прямая резьба

Адреса в потоке — это адреса машинного языка. Эта форма проста, но может иметь накладные расходы, поскольку поток состоит только из адресов машин, поэтому все дальнейшие параметры должны загружаться косвенно из памяти. Некоторые системы Форта создают код с прямой резьбой. На многих машинах прямая обработка резьбы выполняется быстрее, чем подпрограммная обработка (см. ссылку ниже).

Пример стековой машины может выполнять последовательность «нажать A, нажать B, добавить». Это можно перевести в следующий поток и процедуры, где ip инициализируется по адресу, обозначенному thread (т.е. адрес, по которому &pushA хранится).

#define PUSH(x) (*sp++ = (x))
#define POP() (*--sp)
start:
  ip = &thread  // ip points to &pushA (which points to the first instruction of pushA)
  jump *ip++  // send control to first instruction of pushA and advance ip to &pushB
thread:
  &pushA
  &pushB
  &add
  ...
pushA:
  PUSH(A)
  jump *ip++ // send control where ip says to (i.e. to pushB) and advance ip
pushB:
  PUSH(B)
  jump *ip++
add:
  result = POP() + POP()
  PUSH(result)
  jump *ip++

Альтернативно, в поток могут быть включены операнды. Это может устранить некоторую косвенность, необходимую выше, но увеличит поток:

#define PUSH(x) (*sp++ = (x))
#define POP() (*--sp)
start:
  ip = &thread
  jump *ip++
thread:
  &push
  &A  // address where A is stored, not literal A
  &push
  &B
  &add
  ...
push:
  variable_address = *ip++ // must move ip past operand address, since it is not a subroutine address
  PUSH(*variable_address) // Read value from variable and push on stack
  jump *ip++
add:
  result = POP() + POP()
  PUSH(result)
  jump *ip++

Косвенная резьба

Косвенная обработка потоков использует указатели на места, которые, в свою очередь, указывают на машинный код. За косвенным указателем могут следовать операнды, которые сохраняются в косвенном «блоке», а не сохраняются повторно в потоке. Таким образом, косвенный код часто более компактен, чем код с прямой резьбой. Косвенность обычно делает его медленнее, хотя обычно все же быстрее, чем интерпретаторы байт-кода. Если операнды-обработчики включают в себя как значения, так и типы, экономия места по сравнению с кодом с прямой резьбой может быть значительной. Старые системы FORTH обычно создают код с косвенной резьбой.

Например, если цель состоит в том, чтобы выполнить «нажми A, нажми B, добавь», можно использовать следующее. Здесь, ip инициализируется по адресу &thread, каждый фрагмент кода ( push, add) находится путем двойного перенаправления через ip и косвенный блок; и все операнды фрагмента находятся в косвенном блоке, следующем за адресом фрагмента. Для этого необходимо сохранить текущую подпрограмму в ip, в отличие от всех предыдущих примеров, где он содержал следующую вызываемую подпрограмму.

start:
  ip = &thread  // points to '&i_pushA'
  jump *(*ip)  // follow pointers to 1st instruction of 'push', DO NOT advance ip yet
thread:
  &i_pushA
  &i_pushB
  &i_add
  ...
i_pushA:
  &push
  &A
i_pushB:
  &push
  &B
i_add:
  &add
push:
  *sp++ = *(*ip + 1)  // look 1 past start of indirect block for operand address
  jump *(*++ip)  // advance ip in thread, jump through next indirect block to next subroutine
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  jump *(*++ip)

Потоки подпрограммы

Так называемый «код с нитями подпрограмм» (также «код с нитями вызовов») состоит из серии инструкций «вызова» на машинном языке (или адресов функций для «вызова», в отличие от прямого использования потоков в «переходе»). ). Ранние компиляторы для ALGOL , Fortran, Cobol и некоторых систем Forth часто создавали многопоточный код подпрограмм. Код во многих из этих систем работал со стеком операндов «последним пришел — первым обслужен» (LIFO), для которого теория компиляторов была хорошо развита. Большинство современных процессоров имеют специальную аппаратную поддержку инструкций «вызова» и «возврата» подпрограмм, поэтому затраты на одну дополнительную машинную инструкцию на каждую отправку несколько уменьшаются.

Антон Эртл, Gforth , заявил, что «в отличие от популярных мифов, обработка подпрограмм обычно медленнее, чем прямая обработка». соавтор компилятора Однако последние тесты Эртла показывают, что обработка подпрограмм выполняется быстрее, чем прямая обработка потоков, в 15 из 25 тестовых случаев. В частности, он обнаружил, что прямая обработка потоков является самой быстрой моделью потоковой обработки на процессорах Xeon, Opteron и Athlon, непрямая обработка потоков является самой быстрой на процессорах Pentium M, а обработка подпрограмм является самой быстрой на процессорах Pentium 4, Pentium III и PPC.

В качестве примера потоковой обработки вызовов для «push A, push B, add»:

thread:
  call pushA
  call pushB
  call add
  ret
pushA:
  *sp++ = A
  ret
pushB:
  *sp++ = B
  ret
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  ret

Обмен токенами

Код с токенами реализует поток как список индексов в таблице операций; ширина индекса, естественно, выбирается как можно меньшей из соображений плотности и эффективности. 1 байт/8 бит — естественный выбор для простоты программирования, но можно использовать меньшие размеры, например 4 бита, или большие, например 12 или 16 бит, в зависимости от количества поддерживаемых операций. Пока ширина индекса выбрана уже, чем машинный указатель, он, естественно, будет более компактным, чем другие типы резьбы, без особых усилий со стороны программиста. Обычно он составляет от половины до трех четвертей размера других потоков, которые сами по себе составляют от четверти до восьмой размера беспоточного кода. Указатели таблицы могут быть косвенными или прямыми. Некоторые компиляторы Форта создают код с токенной резьбой. Некоторые программисты считают « p-код », генерируемый некоторыми компиляторами Pascal , а также байт-коды, используемые .NET , Java , BASIC и некоторыми компиляторами C , потоками токенов.

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

start:
  vpc = &thread
dispatch:
  addr = decode(&vpc) // Convert the next bytecode operation to a pointer to machine code that implements it
  // Any inter-instruction operations are performed here (e.g. updating global state, event processing, etc)
  jump addr
CODE_PTR decode(BYTE_CODE **p) {
  // In a more complex encoding, there may be multiple tables to choose between or control/mode flags
  return table[*(*p)++];
}
thread:  /* Contains bytecode, not machine addresses.  Hence it is more compact. */
  1 /*pushA*/
  2 /*pushB*/
  0 /*add*/
table:
  &add    /* table[0] = address of machine code that implements bytecode 0 */
  &pushA  /* table[1] ... */
  &pushB  /* table[2] ... */
pushA:
  *sp++ = A
  jump dispatch
pushB:
  *sp++ = B
  jump dispatch
add:
  addend1 = *--sp
  addend2 = *--sp
  *sp++ = addend1 + addend2
  jump dispatch

Если виртуальная машина использует только инструкции размером в байт, decode() это просто выборка из thread, но часто используются широко используемые 1-байтовые инструкции плюс некоторые менее распространенные многобайтовые инструкции (см. компьютер со сложным набором команд ), и в этом случае decode() является более сложным. Декодирование однобайтовых кодов операций может быть очень просто и эффективно выполнено с помощью таблицы ветвей, использующей код операции непосредственно в качестве индекса.

Для инструкций, в которых отдельные операции просты, таких как «push» и «add», накладные расходы , связанные с принятием решения о том, что выполнять, превышают затраты на фактическое выполнение, поэтому такие интерпретаторы часто работают намного медленнее, чем машинный код. Однако для более сложных («составных») инструкций процент накладных расходов пропорционально менее значителен.

Бывают случаи, когда код с токенной резьбой иногда может работать быстрее, чем эквивалентный машинный код, когда этот машинный код оказывается слишком большим, чтобы поместиться в кэше инструкций L1 физического процессора. Более высокая плотность кода многопоточного кода, особенно кода с токенами, может позволить ему полностью поместиться в кэше L1, когда в противном случае это было бы невозможно, тем самым избегая перегрузки кэша. Однако многопоточный код использует как кеш инструкций (для реализации каждой операции), так и кеш данных (для байт-кода и таблиц), в отличие от машинного кода, который использует только кеш инструкций; это означает, что многопоточный код будет расходовать бюджет объема данных, который может храниться для обработки ЦП в любой момент времени. В любом случае, если вычисляемая задача предполагает применение большого количества операций к небольшому объему данных, то использование многопоточного кода может быть идеальной оптимизацией.

Нарезка Хаффмана

Потоковый код Хаффмана состоит из списков токенов, хранящихся как коды Хаффмана . Код Хаффмана — это строка битов переменной длины, которая идентифицирует уникальный токен. Интерпретатор с потоками Хаффмана находит подпрограммы, используя индексную таблицу или дерево указателей, по которым можно перемещаться с помощью кода Хаффмана. Код Хаффмана — одно из наиболее компактных представлений компьютерных программ. Индекс и коды выбираются путем измерения частоты вызовов каждой подпрограммы в коде. Частым звонкам присваиваются самые короткие коды. Операциям с примерно одинаковой частотой присваиваются коды почти одинаковой длины в битах. Большинство систем с потоками Хаффмана были реализованы как системы Forth с прямым потоком и использовались для упаковки больших объемов медленно выполняемого кода в маленькие и дешевые микроконтроллеры . Наиболее опубликованные их использовали в смарт-картах, игрушках, калькуляторах и часах. Бит-ориентированный токенизированный код, используемый в PBASIC, можно рассматривать как своего рода код с нитями Хаффмана.

Менее используемая резьба

Примером является потоковая обработка строк, при которой операции идентифицируются по строкам, которые обычно просматриваются по хеш-таблице. Это использовалось в самых ранних реализациях Форта Чарльза Х. Мура и в Университета Иллинойса экспериментальном аппаратно интерпретируемом компьютерном языке . Он также используется в Bashforth .

РПЛ

HP компании RPL , впервые представленный в калькуляторе HP-18C в 1986 году, представляет собой тип проприетарного гибридного (с прямой и косвенной резьбой) многопоточного интерпретационного языка (TIL). это, в отличие от других TIL, позволяет встраивать «объекты» RPL в «поток выполнения», то есть поток адресов, по которым перемещается указатель интерпретатора. «Объект» RPL можно рассматривать как специальный тип данных, структура которого в памяти содержит адрес «пролога объекта» в начале объекта, за которым следуют данные или исполняемый код. Пролог объекта определяет, как должно выполняться или обрабатываться тело объекта. Используя «внутренний цикл RPL», который был изобретен и запатентован Уильямом К. Уиксом в 1986 году и опубликованным в 1988 году, казнь выглядит следующим образом:

1. Разыменуйте IP (указатель инструкции) и сохраните его в O (указатель текущего объекта).
2. Увеличьте IP-адрес на длину одного указателя адреса.
3. Разыменовать O и сохранить его адрес в O_1 (это второй уровень косвенности)
4. Передача управления следующему указателю или встроенному объекту путем установки ПК (счетчика программ) на O_1 плюс один указатель адреса.
5. Вернитесь к шагу 1

Более точно это можно представить следующим образом:

    O  = [I]
    I  = I + Δ
    PC = [O] + Δ

Здесь O — указатель текущего объекта, I — указатель интерпретатора, Δ — длина одного адресного слова, а оператор «[]» означает «разыменование».

Когда управление передается указателю объекта или внедренному объекту, выполнение продолжается следующим образом:

PROLOG -> PROLOG (The prolog address at the start of the prolog code points to itself)
    IF O + Δ =/= PC
    THEN GOTO INDIRECT (Test for direct execution)
        O = I - Δ (Correct O to point to start of embedded object)
        I = I + α (Correct I to point after embedded object where α is the length of the object)
    INDIRECT (Rest of prolog)

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

Филиалы

Во всех интерпретаторах ветвь просто меняет указатель потока ( ip) на другой адрес в теме. Условная ветвь перехода, если ноль, которая переходит только в том случае, если значение вершины стека равно нулю, может быть реализовано, как показано ниже. В этом примере используется версия прямой резьбы со встроенными параметрами, поэтому &thread[123] строка — это пункт назначения, куда можно перейти, если условие истинно, поэтому ее необходимо пропустить ( ip++) закончится, если ветка не будет занята.

thread:
  ...
  &brz
  &thread[123]
  ...
brz:
  when_true_ip = *ip++ // Get destination address for branch
  if (*--sp == 0)      // Pop/Consume top of stack and check if it's zero
    ip = when_true_ip
  jump *ip++

Общие удобства

Разделение стеков данных и возвратов на машине устраняет большую часть кода управления стеком, существенно уменьшая размер многопоточного кода. Принцип двойного стека возник трижды независимо: для больших систем Берроуза , Forth и PostScript . Он используется в некоторых виртуальных машинах Java .

три регистра В многопоточной виртуальной машине часто присутствуют . Другой существует для передачи данных между подпрограммами («словами»). Это:

• ip или i ( указатель инструкции ) виртуальной машины (не путать со счетчиком программ базового оборудования, реализующего виртуальную машину)
• w (рабочий указатель)
• rp или r (возврат стека ) указатель
• sp или s ( указатель стека параметров для передачи параметров между словами)

Зачастую многопоточные виртуальные машины , такие как реализации Форта, имеют в основе простую виртуальную машину, состоящую из трёх примитивов . Это:

1. гнездо , также называемое доколом
2. unnest или semi_s (;s)
3. следующий

В виртуальной машине с непрямой резьбой, представленной здесь, выполняются следующие операции:

 next:
   *ip++ -> w
   jump **w++
 nest:
   ip -> *rp++
   w -> ip
   next
 unnest:
   *--rp -> ip
   next

См. также

• Стиль передачи продолжения , который заменяет глобальную переменную ip с параметром функции
• Компиляция точно в срок
• Возвратно-ориентированное программирование : повторное обнаружение многопоточного кода для использования удаленных уязвимых систем.
• Хвостовой вызов
• История процессоров общего назначения

Дальнейшее чтение

• Разработка языка C, заархивированная 28 марта 2015 г. в Wayback Machine Деннисом М. Ричи, описывает B (предшественник C) как реализованный с использованием «поточного кода».
• Хорн, Джозеф К. «Что такое РПЛ?» . Архивировано из оригинала 17 сентября 2017 г. Проверено 17 сентября 2017 г. (Примечание. Краткий обзор связанных языков, системного и пользовательского RPL, используемых в калькуляторах HP, таких как HP 48. )

Внешние ссылки

• Пояснительная страница Антона Эртла Что такое резьбовой код? описывает различные методы обработки потоков и предоставляет дополнительные ссылки.
• Проект Thinking Forth включает в себя плодотворную (но вышедшую из печати) книгу Лео Броди Thinking Forth, заархивированную 13 ноября 2005 г. в Wayback Machine, опубликованную в 1984 году.
• Интернет-версия Starting FORTH книги Лео Броди Starting FORTH. Архивировано 13 ноября 2005 г. в Wayback Machine, опубликованной в 1981 году.
• В книге Брэда Родригеса « Двигаясь вперед: Часть 1: Проектные решения в ядре Forth» подробно рассматриваются методы многопоточности.
• Расширения GCC. Ярлыки как ценности