Резьбовой код - Threaded code

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

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

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

Потоковый код наиболее известен тем, что он используется во многих компиляторах языков программирования , таких как 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), для своей виртуальной машины Forth. Мур пришел к такому решению, потому что миникомпьютеры Nova имели бит косвенного обращения в каждом адресе, что делало ИТЦ простым и быстрым. Позже он сказал, что нашел это настолько удобным, что распространил его на все более поздние разработки Форта.

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

Модели с резьбой

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

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

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

Пример стековой машины может выполнять последовательность «нажать 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 обычно производят непрямый многопоточный код.

Например, если цель состоит в том, чтобы выполнить «push A, push B, add», можно использовать следующее. Здесь 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 , заявил, что «в отличие от популярных мифов, потоки подпрограмм обычно медленнее, чем прямые потоки». Однако самые последние тесты Ertl показывают, что потоки подпрограмм быстрее, чем прямые потоки, в 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 бит, в зависимости от количества поддерживаемых операций. Если ширина индекса выбрана уже, чем машинный указатель, он, естественно, будет более компактным, чем другие типы потоков, без особых усилий со стороны программиста. Обычно он составляет от половины до трех четвертей размера других потоков, которые сами по себе составляют от четверти до восьмой размера непоточного кода. Указатели таблицы могут быть косвенными или прямыми. Некоторые компиляторы Forth создают код с токен-нитями. Некоторые программисты считают « p-код », сгенерированный некоторыми компиляторами Паскаля , а также байт-коды, используемые .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, можно рассматривать как разновидность кода Хаффмана.

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

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

РПЛ

HP «s RPL , первым ввел в HP-18C калькуляторе в 1986 году, является одним из видов фирменного гибридного прямой нарезки и непрямого-резьбового резьбовой интерпретирован языка , который, в отличии от других TIL , позволяет встраивание RPL„объекты“в«runstream "т.е. Поток адресов, по которым продвигается указатель интерпретатора. «Объект» RPL можно рассматривать как особый тип данных, структура в памяти которого содержит адрес «пролога объекта» в начале объекта, а затем следуют данные или исполняемый код. Пролог объекта определяет, как тело объекта должно выполняться или обрабатываться. При использовании «внутреннего цикла RPL», который был изобретен и опубликован (и запатентован) Уильямом К. Виксом в 1986 г. и опубликован в «Средах программирования», Institute for Applied Forth Research, Inc., 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++

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

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

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

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

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

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

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

Это, пожалуй, самый простой и быстрый интерпретатор или виртуальная машина.

Смотрите также

Примечания

использованная литература

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