Войти
В информатике, поточный код - это метод программирования, в котором код имеет форма, которая по существу полностью состоит из вызовов подпрограмм. Он часто используется в компиляторах, которые могут генерировать код в этой форме или быть реализованы в этой форме сами. Код может быть обработан интерпретатором или это может быть просто последовательность команд машинного кода вызова.
Потоковый код имеет лучшую плотность, чем код, сгенерированный альтернативными методами генерации и альтернативными соглашениями о вызовах. В кэшированных архитектурах он может выполняться немного медленнее. Однако программа, которая достаточно мала, чтобы поместиться в кэш компьютерного процессора, может работать быстрее, чем более крупная программа, у которой много промахов в кэше. Небольшие программы также могут быстрее переключаться между потоками, когда другие программы заполнили кэш.
Многопоточный код наиболее известен тем, что он используется во многих компиляторах языков программирования, таких как Forth, многих реализациях BASIC, некоторых реализациях COBOL, ранних версий B и других языков для небольших миникомпьютеров и для любительских радиоспутников.
Обычный способ make компьютерные программы должны использовать компилятор для перевода исходного кода (написанного на каком-то символьном языке ) в машинный код. Результирующий исполняемый файл обычно работает быстро, но, поскольку он специфичен для аппаратной платформы, он не переносится. Другой подход заключается в создании инструкций для виртуальной машины и использовании интерпретатора на каждой аппаратной платформе. Интерпретатор создает экземпляр среды виртуальной машины и выполняет инструкции. Таким образом, нужно компилировать только интерпретатор.
Ранние компьютеры имели относительно мало памяти. Например, в большинстве Data General Nova, IBM 1130 и во многих первых микрокомпьютерах было установлено всего 4 КБ ОЗУ. Следовательно, много времени было потрачено на то, чтобы найти способы уменьшить размер программы, чтобы она уместилась в доступной памяти.
Одно из решений - использовать интерпретатор, который читает символический язык по частям и вызывает функции для выполнения действий. Поскольку исходный код обычно намного плотнее, чем полученный машинный код, это может снизить общее использование памяти. Это было причиной того, что Microsoft BASIC является интерпретатором: его собственный код должен был совместно использовать 4 КБ памяти таких машин, как Altair 8800, с исходным кодом пользователя. Компилятор выполняет перевод с исходного языка в машинный код, поэтому компилятор, исходный код и вывод должны находиться в памяти одновременно. В интерпретаторе нет вывода. Код создается построчно, выполняется, а затем отбрасывается.
Потоковый код - это стиль форматирования для скомпилированного кода, который минимизирует использование памяти. Вместо того, чтобы записывать каждый шаг операции при каждом его появлении в программе, как это было обычно, например, в макросборщиках , компилятор записывает каждый общий бит кода в подпрограмму. Таким образом, каждый бит существует только в одном месте в памяти (см. «Не повторяйся »). Приложение верхнего уровня в этих программах может состоять только из вызовов подпрограмм. Многие из этих подпрограмм, в свою очередь, также состоят только из вызовов подпрограмм нижнего уровня. Этот метод - рефакторинг кода - по-прежнему широко используется сегодня, хотя и по другим причинам.
Мэйнфреймы и некоторые ранние микропроцессоры, такие как RCA 1802, требовали нескольких инструкций для вызова подпрограммы. В приложении верхнего уровня и во многих подпрограммах эта последовательность постоянно повторяется, и только адрес подпрограммы изменяется от одного вызова к другому. Это означает, что программа, состоящая из множества вызовов функций, также может иметь значительное количество повторяющегося кода.
Чтобы решить эту проблему, системы с многопоточным кодом использовали псевдокод для представления вызовов функций в одном операторе. Во время выполнения крошечный «интерпретатор» просматривает код верхнего уровня, извлекает адрес подпрограммы в памяти и вызывает ее. В других системах эта же базовая концепция реализована в виде таблицы ветвей, таблицы диспетчеризации или таблицы виртуальных методов, каждая из которых состоит из таблицы подпрограмм. адреса.
В 1970-е годы разработчики аппаратного обеспечения приложили значительные усилия, чтобы сделать вызов подпрограмм более быстрым и простым. В улучшенных конструкциях для вызова подпрограммы используется только одна инструкция, поэтому использование псевдо-инструкции не экономит места. Кроме того, выполнение этих вызовов практически не требует дополнительных затрат. Сегодня, хотя почти все языки программирования сосредоточены на изоляции кода на подпрограммы, они делают это для ясности кода и удобства обслуживания, а не для экономии места.
Системы с многопоточным кодом экономят место, заменяя тот список вызовов функций, в котором от одного вызова к другому изменяется только адрес подпрограммы, списком токенов выполнения, которые по сути являются вызовами функций с кодом операции вызова (s), оставив после себя только список адресов.
За прошедшие годы программисты создали множество вариаций этого «интерпретатора» или «небольшого селектора». Конкретный адрес в списке адресов может быть извлечен с использованием индекса, регистра общего назначения или указателя. Адреса могут быть прямыми или косвенными, смежными или несмежными (связаны указателями), относительными или абсолютными, разрешенными во время компиляции или динамически построенными. Ни один вариант не является «лучшим» для всех ситуаций.
Чтобы сэкономить место, программисты сжали списки вызовов подпрограмм в простые списки адресов подпрограмм и использовали небольшой цикл для вызова каждой подпрограммы по очереди. Например, следующий псевдокод использует эту технику для сложения двух чисел A и B. В этом примере список помечен thread, а переменная ip (указатель инструкции) отслеживает наше место внутри список. Другая переменная sp (указатель стека) содержит адрес в другом месте памяти, доступный для временного хранения значения.
start: ip = thread // указывает на адрес 'pushA', а не на текстовую метку 'thread' top: jump * ip ++ // следуйте за ip по адресу в потоке, следуйте за этим адресом до подпрограммы, продвигайте ip thread: pushA pushB add... pushA: * sp ++ = A // следовать sp до доступной памяти, сохранять A там, продвигать sp к следующему началу перехода pushB: * sp ++ = B jump top add: addend = * - sp // указывать sp на последнее значение, сохраненное в стеке, следуйте за ним, чтобы скопировать это значение из стека * sp ++ = * - sp + addend // копировать другое значение из стека, складывать, копировать сумму в стек скачок вверх
. Цикл вызова в вершиненастолько прост, что его можно повторять в конце каждой подпрограммы. Теперь управление перескакивает один раз, с конца одной подпрограммы на начало другой, вместо двойного перехода через top. Например:
start: ip = thread // ip указывает на pushA (который указывает на первую инструкцию pushA) jump * ip ++ // отправляет управление первой инструкции pushA и продвигает ip к потоку pushB: pushA pushB add... pushA: * sp ++ = A // следуйте sp до доступной памяти, сохраните там A, продвиньте sp к следующему переходу * ip ++ // отправьте управление, где ip говорит (т.е. pushB) и продвиньте ip pushB: * sp ++ = B jump * ip ++ add: addend = * - sp // укажите sp на последнее значение, сохраненное в стеке, следуйте за ним, чтобы скопировать это значение * sp ++ = * - sp + addend // скопируйте другое значение из стека, сложите, скопируйте сумму переход в стек * ip ++
Это называется прямым многопоточным кодом (DTC). Хотя этот метод и старше, первым широко распространенным использованием термина «многопоточный код», вероятно, является статья Джеймса Р. Белла 1973 года «Потоковый код».
В 1970 году Чарльз Х. Мур изобрел более компактную структуру, непрямой многопоточный код (ITC), для своей виртуальной машины Forth. Мур пришел к такой договоренности, потому что миникомпьютеры Nova имели бит косвенного обращения в каждом адресе, что сделало ИТК простым и быстрым. Позже он сказал, что нашел это настолько удобным, что распространил его на все более поздние разработки Forth.
Сегодня некоторые компиляторы Forth генерируют код с прямым потоком, а другие генерируют код с косвенным потоком. Исполняемые файлы в любом случае действуют одинаково.
Практически весь исполняемый многопоточный код использует тот или иной из этих методов для вызова подпрограмм (каждый метод называется «потоковой моделью»).
Адреса в потоке - это адреса машинного языка. Эта форма проста, но может иметь накладные расходы, поскольку поток состоит только из машинных адресов, поэтому все дополнительные параметры должны загружаться косвенно из памяти. Некоторые системы Forth создают код с прямыми потоками. На многих машинах прямое выполнение потоков выполняется быстрее, чем выполнение подпрограмм (см. Ссылку ниже).
Пример стековой машины может выполнять последовательность «нажать A, нажать B, добавить». Это может быть преобразовано в следующий поток и подпрограммы, где ipинициализируется адресом, помеченным thread(то есть адресом, где хранится pushA).
start: ip = thread // ip указывает на pushA (который указывает на первую инструкцию pushA) jump * ip ++ // отправляет управление первой инструкции pushA и продвигает ip к потоку pushB: pushA pushB add... pushA : * sp ++ = A jump * ip ++ // отправляем элемент управления, где ip указывает (т.е. pushB) и продвигает ip pushB: * sp ++ = B jump * ip ++ add: addend = * - sp * sp ++ = * - sp + addend jump * ip ++
В качестве альтернативы в поток могут быть включены операнды. Это может удалить некоторую косвенность, необходимую выше, но увеличивает поток:
start: ip = thread jump * ip ++ thread: push A // адрес, где хранится A, а не буквальный A push B add... push: * sp ++ = * ip ++ // должен переместить ip за адрес операнда, так как это не переход по адресу подпрограммы * ip ++ add: addend = * - sp * sp ++ = * - sp + addend jump * ip ++
Непрямая многопоточность использует указатели на местоположения, которые, в свою очередь, указывают на машинный код. За косвенным указателем могут следовать операнды, которые хранятся в косвенном «блоке», а не повторяются в потоке. Таким образом, косвенный код часто более компактен, чем код с прямым потоком. Косвенное обращение обычно делает его медленнее, хотя обычно все же быстрее, чем интерпретаторы байт-кода. Если операнды обработчика включают как значения, так и типы, экономия места по сравнению с кодом с прямым потоком может быть значительной. Старые системы FORTH обычно производят непрямый многопоточный код.
Например, если цель состоит в том, чтобы выполнить «нажмите A, нажмите B, добавьте», можно использовать следующее. Здесь ipинициализируется адресом и thread, каждый фрагмент кода (push, add) обнаруживается двойным косвенным обращением через ipи косвенный блок; и любые операнды фрагмента находятся в косвенном блоке, следующем за адресом фрагмента. Для этого требуется сохранить текущую подпрограмму в ip, в отличие от всех предыдущих примеров, где она содержала следующую вызываемую подпрограмму.
start: ip = thread // указывает на 'i_pushA' jump * (* ip) // следуйте указателям на 1-ю инструкцию 'push', НЕ продвигайте ip пока thread: i_pushA i_pushB i_add... i_pushA: push A i_pushB: push B i_add: add push: * sp ++ = * (* ip + 1) // смотреть на 1 после начала косвенного блока для перехода по адресу операнда * (* ++ ip) // продвигать ip в потоке, переходить через следующий косвенный блок к следующей подпрограмме add: addend = * - sp * sp ++ = * - sp + addend 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 : addend = * - sp * sp ++ = * - sp + addend ret
Потоковый код токенов использует списки 8- или 12-битных индексов для таблицы указателей. Он очень компактен, не требует особых усилий со стороны программиста. Обычно он составляет от половины до трех четвертей размера других потоков, которые сами по себе составляют от четверти до восьмой размера непоточного кода. Указатели таблицы могут быть косвенными или прямыми. Некоторые компиляторы Forth создают код с токен-нитями. Некоторые программисты рассматривают «p-code », сгенерированный некоторыми компиляторами Pascal, а также байт-коды , используемые .NET, Компиляторы Java, BASIC и некоторые C для потоковой передачи токенов.
Традиционно распространенным подходом является байт-код, в котором используются 8-битные коды операций и, часто, виртуальная машина на основе стека. Типичный интерпретатор известен как "" и имеет форму:
start: vpc = thread top: i = decode (vpc ++) / * может быть реализовано просто как: return * vpc * / addr = table [i] jump * addr thread: / * Содержит байт-код, а не машинные адреса. Следовательно, он более компактный. * / 1 / * pushA * / 2 / * pushB * / 0 / * add * / table: add / * table [0] = адрес машинного кода, реализующего байт-код 0 * / pushA / * table [1]... * / pushB / * table [2]... * / pushA: * sp ++ = A jump top pushB: * sp ++ = B jump top add: addend = * - sp * sp ++ = * - sp + addend jump top
Если виртуальная машина использует только инструкции байтового размера, decode ()- это просто выборка из потока, но часто встречаются обычно используемые 1-байтовые инструкции плюс некоторые менее распространенные многобайтовые инструкции (см. компьютер со сложным набором команд ), в этом случае decode ()более сложен. Декодирование однобайтовых кодов операций может быть очень просто и эффективно обработано таблицей переходов, использующей код операции непосредственно в качестве индекса.
Для инструкций, в которых отдельные операции просты, такие как «push» и «add», накладные расходы, связанные с принятием решения о том, что выполнять, больше, чем затраты на фактическое выполнение, поэтому такие интерпретаторы часто намного медленнее, чем машинный код. Однако для более сложных («составных») инструкций процент служебных данных пропорционально менее значим.
Как ни странно, код с токен-нитями иногда может работать быстрее, чем эквивалентный машинный код - когда машинный код слишком велик для размещения в кеше, но более высокая плотность кода многопоточности код, особенно код с токенами, позволяет ему полностью поместиться в высокоскоростной кэш.
Потоковый код Хаффмана состоит из списков токенов, хранящихся как коды Хаффмана. Код Хаффмана - это строка битов переменной длины, которая идентифицирует уникальный токен. Потоковый интерпретатор Хаффмана находит подпрограммы с помощью индексной таблицы или дерева указателей, по которым можно перемещаться с помощью кода Хаффмана. Многопоточный код Хаффмана - одно из самых компактных представлений компьютерных программ. Индекс и коды выбираются путем измерения частоты вызовов каждой подпрограммы в коде. При частых звонках даются кратчайшие коды. Операции с примерно равными частотами задаются кодами с примерно равной битовой длиной. Большинство потоковых систем Хаффмана были реализованы как Forth-системы с прямыми потоками и использовались для упаковки больших объемов медленно работающего кода в небольшие дешевые микроконтроллеры. Чаще всего опубликовано использование смарт-карт, игрушек, калькуляторов и часов. Бит-ориентированный токенизированный код, используемый в PBASIC, можно рассматривать как разновидность многопоточного кода Хаффмана.
Примером является потоковая передача строк, в которой операции идентифицируются строками, обычно просматриваемыми с помощью хеш-таблицы. Это использовалось в самых ранних реализациях Forth Чарльза Х. Мура и в экспериментальном компьютерном языке с аппаратной интерпретацией Университета Иллинойса. Он также используется в.
HP RPL, впервые представленный в калькуляторе HP-18C в 1986 году, представляет собой тип запатентованного гибридного прямого и непрямого потокового язык с потоковой интерпретацией, который, в отличие от других TIL, позволяет встраивать «объекты» RPL в «поток выполнения», т.е. Поток адресов, по которым продвигается указатель интерпретатора. «Объект» RPL можно рассматривать как особый тип данных, структура которого в памяти содержит адрес «пролога объекта» в начале объекта, а затем следуют данные или исполняемый код. Пролог объекта определяет, как тело объекта должно выполняться или обрабатываться. При использовании «внутреннего цикла RPL», который был изобретен и опубликован (и запатентован) Уильямом К. Виксом в 1986 г. и опубликован в «Средах программирования» Института прикладных исследований Forth, Inc., 1988 г., выполнение выглядит следующим образом:
Это может более точно:
O = [I] I = I + Δ PC = [O] + Δ
Где выше, O - текущий указатель объекта, I - указатель интерпретатора, Δ - длина одного адресного слова, а оператор «» означает «разыменование».
Когда управление передается указателю объекта или встроенному объекту, выполнение продолжается следующим образом:
PROLOG ->PROLOG (Адрес пролога в начале кода пролога указывает на себя) IF O + Δ = / = PC THEN GOTO INDIRECT (тест на прямое выполнение) O = I - Δ (исправьте O, чтобы указать на начало встроенного объекта) I = I + α (исправьте I, чтобы указать после встроенного объекта, где α - длина объекта) INDIRECT (остальная часть пролога)
На микропроцессорах HP Saturn, использующих RPL, существует третий уровень косвенного обращения, который стал возможен с помощью архитектурного / программного трюка, который обеспечивает более быстрое выполнение.
Во всех интерпретаторах ветвь просто изменяет указатель потока (ipвыше). Условная ветвь для перехода, если значение вершины стека равно нулю, может быть закодировано следующим образом. Обратите внимание, что thread [123]- это место для перехода, а не адрес обработчика. Таким образом, его необходимо пропустить (ip ++) независимо от того, была ли ветка взята.
поток:... brz thread [123]... brz: tmp = ip ++ if (* sp ++ == 0) ip = tmp jump * ip ++
Разделение данных и возврат стеков в машине устраняет большую часть кода управления стеком, существенно уменьшая размер многопоточного кода. Принцип двойного стека возник трижды независимо: для больших систем Burroughs, Forth и PostScript. Он используется в некоторых виртуальных машинах Java.
Три регистра часто присутствуют в многопоточной виртуальной машине. Другой существует для передачи данных между подпрограммами («слова»). Это:
Часто многопоточные виртуальные машины, такие как реализации Forth, в основе своей имеют простую виртуальную машину, состоящую из трех примитивов. Это:
В виртуальной машине с косвенными потоками, приведенной здесь, операции являются:
next: * ip ++ ->w jump ** w ++ nest: ip ->* rp ++ w ->ip next unnest: * - rp ->ip next
Это, пожалуй, самый простой и быстрый интерпретатор или виртуальная машина.
Портал компьютерного программирования ipпараметром функции