В информатике многопоточный код — это метод программирования, при котором код имеет форму, которая по существу полностью состоит из вызовов подпрограмм . Он часто используется в компиляторах , которые могут генерировать код в этой форме или сами реализовываться в этой форме. Код может обрабатываться интерпретатором или представлять собой просто последовательность инструкций вызова машинного кода .
Поточный код имеет лучшую плотность , чем код, созданный альтернативными методами генерации и альтернативными соглашениями о вызовах . В кэшированных архитектурах он может выполняться немного медленнее. [ Необходима цитация ] Однако программа, которая достаточно мала, чтобы поместиться в кэше процессора компьютера , может работать быстрее, чем более крупная программа, которая имеет много промахов в кэше . [1] Небольшие программы также могут быстрее переключаться между потоками , когда другие программы заполнили кэш.
Многопоточный код наиболее известен благодаря использованию во многих компиляторах языков программирования , таких как Forth , многих реализациях BASIC , некоторых реализациях COBOL , ранних версиях B , [2] и других языках для небольших миникомпьютеров и для любительских радиоспутников . [ нужна цитата ]
Обычным способом создания компьютерных программ является использование компилятора для перевода исходного кода (написанного на некотором символьном языке ) в машинный код . Получаемый в результате исполняемый файл обычно работает быстро, но, поскольку он специфичен для аппаратной платформы, он непереносим. Другой подход заключается в создании инструкций для виртуальной машины и использовании интерпретатора на каждой аппаратной платформе. Интерпретатор создает экземпляр среды виртуальной машины и выполняет инструкции. Таким образом, необходимо скомпилировать только интерпретатор.
Ранние компьютеры имели относительно мало памяти. Например, большинство Data General Nova , IBM 1130 и многие первые микрокомпьютеры имели только 4 КБ оперативной памяти. Следовательно, много времени было потрачено на поиск способов уменьшить размер программы, чтобы она уместилась в доступной памяти.
Одним из решений является использование интерпретатора, который понемногу считывает символический язык и вызывает функции для выполнения действий. Поскольку исходный код обычно намного плотнее результирующего машинного кода, это может снизить общее использование памяти. Именно по этой причине Microsoft BASIC является интерпретатором: [а] его собственный код должен был использовать 4 КБ памяти таких машин, как Altair 8800, с исходным кодом пользователя. Компилятор преобразует исходный язык в машинный код, поэтому компилятор, исходный код и выходные данные должны находиться в памяти одновременно. В интерпретаторе вывода нет.
Поточный код — это стиль форматирования скомпилированного кода, который минимизирует использование памяти. Вместо того, чтобы записывать каждый шаг операции при каждом ее появлении в программе, как это было принято, например, в ассемблерах макросов , компилятор записывает каждый общий бит кода в подпрограмму. Таким образом, каждый бит существует только в одном месте памяти (см. « Не повторяйтесь »). Приложение верхнего уровня в этих программах может состоять только из вызовов подпрограмм. Многие из этих подпрограмм, в свою очередь, также состоят из вызовов подпрограмм более низкого уровня.
Мейнфреймам и некоторым ранним микропроцессорам, таким как RCA 1802, требовалось несколько инструкций для вызова подпрограммы. В приложении верхнего уровня и во многих подпрограммах эта последовательность постоянно повторяется, при этом от одного вызова к другому меняется только адрес подпрограммы. Это означает, что программа, состоящая из множества вызовов функций, также может содержать значительное количество повторяющегося кода.
Чтобы решить эту проблему, системы с многопоточным кодом использовали псевдокод для представления вызовов функций в одном операторе. Во время выполнения крошечный «интерпретатор» просматривал код верхнего уровня, извлекал адрес подпрограммы в памяти и вызывал ее. В других системах эта же базовая концепция реализована в виде таблицы ветвей , таблицы диспетчеризации или таблицы виртуальных методов , каждая из которых состоит из таблицы адресов подпрограмм.
В 1970-е годы разработчики аппаратного обеспечения приложили значительные усилия, чтобы сделать вызовы подпрограмм более быстрыми и простыми. В улучшенных конструкциях для вызова подпрограммы затрачивается только одна инструкция, поэтому использование псевдоинструкции не экономит места. [ нужна цитата ] Кроме того, производительность этих вызовов практически не требует дополнительных накладных расходов. Сегодня, хотя почти все языки программирования сосредоточены на изоляции кода в подпрограммах, они делают это для ясности кода и удобства сопровождения, а не для экономии места.
Системы с резьбовым кодом экономят место, заменяя этот список вызовов функций, в котором от одного вызова к другому меняется только адрес подпрограммы, списком токенов выполнения, которые по сути представляют собой вызовы функций с удаленными кодами операций вызова, оставляя после себя только список адресов. [3] [4] [5] [6] [7]
За прошедшие годы программисты создали множество вариаций этого «интерпретатора» или «маленького селектора». Конкретный адрес в списке адресов можно извлечь с помощью индекса, регистра общего назначения или указателя . Адреса могут быть прямыми или косвенными, смежными или несмежными (связанными указателями), относительными или абсолютными, разрешаемыми во время компиляции или динамически создаваемыми. Ни один вариант не является «лучшим» для всех ситуаций.
Чтобы сэкономить место, программисты сжимали списки вызовов подпрограмм в простые списки адресов подпрограмм и использовали небольшой цикл для вызова каждой подпрограммы по очереди. Например, следующий псевдокод использует этот метод для сложения двух чисел A и B. В этом примере список помечен как поток , а переменная ip (указатель инструкций) отслеживает наше место в списке. Другая переменная sp (указатель стека) содержит адрес в другом месте памяти, который доступен для временного хранения значения.
start : ip = & thread // указывает на адрес '&pushA', а не на текстовую метку 'thread' top : jump * ip ++ // следуем по ip до адреса в потоке, следуем по этому адресу до подпрограммы, продвигаем ip thread : & pushA & pushB & add ... pushA : * sp ++ = A // следуем sp до доступной памяти, сохраняем там A, переходим к следующей вершине перехода pushB : * sp ++ = B jump top add : addend1 = * - - sp // Извлекаем верхнее значение из стека addend2 = *-- sp // Извлекаем второе значение из стека * sp ++ = addend1 + addend2 // Складываем два значения вместе и сохраняем результат на вершине стека прыгать сверху
Вызов цикла at topнастолько прост, что его можно повторять в конце каждой подпрограммы. Управление теперь переходит один раз, из конца одной подпрограммы в начало другой, вместо двойного перехода через top. Например:
start : ip = & thread // ip указывает на &pushA (который указывает на первую инструкцию pushA) jump * ip ++ // отправляем управление на первую инструкцию pushA и перемещаем ip на &pushB thread : & pushA & pushB & add . .. pushA : * sp ++ = A // следуем sp до доступной памяти, сохраняем там A, переходим к следующему переходу * ip ++ // отправляем управление туда, куда говорит ip (т.е. в pushB) и продвигаем ip pushB : * sp ++ = B jump * ip ++ add : addend1 = *-- sp // Извлекаем верхнее значение из стека addend2 = *-- sp // Извлекаем второе значение из стека * sp ++ = addend1 + addend2 / / Складываем два значения и сохраняем результат поверх стека jump * ip ++ Это называется кодом с прямой резьбой (DTC). Хотя этот метод более старый, первым широко распространенным использованием термина «поточный код», вероятно, является статья Джеймса Р. Белла 1973 года «Потоковый код». [8]
В 1970 году Чарльз Х. Мур изобрел более компактную структуру — косвенный многопоточный код (ITC) для своей виртуальной машины на Форте. Мур пришел к такой схеме, потому что миникомпьютеры Nova имели бит косвенности в каждом адресе, что делало ITC простым и быстрым. Позже он сказал, что нашел это настолько удобным, что распространил его во все более поздние проекты Форта. [9]
Сегодня некоторые компиляторы Форта генерируют код с прямой резьбой, тогда как другие генерируют код с косвенной резьбой. Исполняемые файлы в любом случае действуют одинаково.
Практически весь исполняемый многопоточный код использует тот или иной из этих методов для вызова подпрограмм (каждый метод называется «потоковой моделью»).
Адреса в потоке — это адреса машинного языка. Эта форма проста, но может иметь накладные расходы, поскольку поток состоит только из адресов машин, поэтому все дальнейшие параметры должны загружаться косвенно из памяти. Некоторые системы Форта создают код с прямой резьбой. На многих машинах прямая обработка резьбы выполняется быстрее, чем подпрограммная обработка (см. ссылку ниже).
Пример стековой машины может выполнять последовательность «нажать A, нажать B, добавить». Это может быть преобразовано в следующий поток и процедуры, где ipинициализируется помеченный адрес thread(т. е. адрес, где &pushAхранится).
#define PUSH(x) (*sp++ = (x)) #define POP() (*--sp) start : ip = & thread // ip указывает на &pushA (который указывает на первую инструкцию pushA) jump * ip ++ // отправляем управление первой инструкции pushA и передаем ip в поток &pushB : & pushA & pushB & add ... pushA : PUSH ( A ) jump * ip ++ // отправляем управление туда, куда говорит ip (т.е. в pushB ) и вперед 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 // адрес, где хранится A, не литерал A & push & B & add ... push : variable_address = * ip ++ // необходимо переместить ip за адрес операнда, так как это не адрес подпрограммы PUSH ( * variable_address ) // Считать значение из переменной и нажать дальше стек jump * ip ++ add : result = POP () + POP () PUSH ( result ) 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 : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 jump * ( *++ ip ) Так называемый «код с нитями подпрограмм» (также «код с нитями вызовов») состоит из серии инструкций «вызова» на машинном языке (или адресов функций для «вызова», в отличие от прямого использования потоков в «переходе»). ). Ранние компиляторы для ALGOL , Fortran, Cobol и некоторых систем Forth часто создавали многопоточный код подпрограмм. Код во многих из этих систем работал со стеком операндов «последним пришел — первым обслужен» (LIFO), для которого теория компиляторов была хорошо развита. Большинство современных процессоров имеют специальную аппаратную поддержку инструкций «вызова» и «возврата» подпрограмм, поэтому затраты на одну дополнительную машинную инструкцию на каждую отправку несколько уменьшаются.
Антон Эртл, соавтор компилятора Gforth , заявил, что «в отличие от популярных мифов, обработка подпрограмм обычно медленнее, чем прямая обработка потоков». [10] Однако последние тесты Ertl [1] показывают, что обработка подпрограмм выполняется быстрее, чем прямая обработка потоков, в 15 из 25 тестовых случаев. В частности, он обнаружил, что прямая обработка потоков является самой быстрой моделью потоковой обработки на процессорах Xeon, Opteron и Athlon, непрямая обработка потоков является самой быстрой на процессорах Pentium M, а обработка подпрограмм является самой быстрой на процессорах Pentium 4, Pentium III и PPC.
В качестве примера потоковой обработки вызовов для «push A, push B, add»:
поток : вызов pushA вызов pushB вызов 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 = & диспетчеризация потоков : addr = decode ( & vpc ) // Преобразование следующей операции с байт-кодом в указатель на машинный код, который ее реализует // Здесь выполняются любые операции между командами (например, обновление глобального состояния, обработка событий, и т. д.) jump addr CODE_PTR decode ( BYTE_CODE ** p ) { // В более сложной кодировке может быть несколько таблиц для выбора или флаги управления/режима return table [ * ( * p ) ++ ]; } thread : /* Содержит байт-код, а не адреса компьютеров. Следовательно, он более компактен. */ 1 /*pushA*/ 2 /*pushB*/ 0 /*add*/ table : & add /* table[0] = адрес машинного кода, реализующего байт-код 0 */ & pushA /* table[1] . .. */ & pushB /* table[2] ... */ pushA : * sp ++ = диспетчеризация перехода A pushB : * sp ++ = диспетчеризация перехода B add : addend1 = *-- sp addend2 = *-- sp * sp ++ = addend1 + addend2 диспетчеризация перехода Если виртуальная машина использует только инструкции размером в байт, decode()это просто выборка из thread, но часто используются обычно используемые 1-байтовые инструкции плюс некоторые менее распространенные многобайтовые инструкции (см. компьютер с комплексным набором команд ), и в этом случае decode()ситуация более сложная. Декодирование однобайтовых кодов операций может быть очень просто и эффективно выполнено с помощью таблицы ветвей, использующей код операции непосредственно в качестве индекса.
Для инструкций, в которых отдельные операции просты, таких как «push» и «add», накладные расходы , связанные с принятием решения о том, что выполнять, превышают затраты на фактическое выполнение, поэтому такие интерпретаторы часто работают намного медленнее, чем машинный код. Однако для более сложных («составных») инструкций процент накладных расходов пропорционально менее значителен.
Бывают случаи, когда код с токенной резьбой иногда может работать быстрее, чем эквивалентный машинный код, когда этот машинный код оказывается слишком большим, чтобы поместиться в кэше инструкций L1 физического процессора. Более высокая плотность кода многопоточного кода, особенно кода с токенами, может позволить ему полностью поместиться в кэше L1, когда в противном случае это было бы невозможно, тем самым избегая перегрузки кэша. Однако многопоточный код использует как кеш инструкций (для реализации каждой операции), так и кеш данных (для байт-кода и таблиц), в отличие от машинного кода, который использует только кеш инструкций; это означает, что многопоточный код будет расходовать бюджет объема данных, который может храниться для обработки ЦП в любой момент времени. В любом случае, если решаемая задача предполагает применение большого количества операций к небольшому объему данных, то использование многопоточного кода может быть идеальной оптимизацией. [4]
Потоковый код Хаффмана состоит из списков токенов, хранящихся как коды Хаффмана . Код Хаффмана — это строка битов переменной длины, которая идентифицирует уникальный токен. Интерпретатор с потоками Хаффмана находит подпрограммы с помощью индексной таблицы или дерева указателей, по которым можно перемещаться с помощью кода Хаффмана. Код Хаффмана — одно из наиболее компактных представлений компьютерных программ. Индекс и коды выбираются путем измерения частоты вызовов каждой подпрограммы в коде. Частым звонкам присваиваются самые короткие коды. Операциям с примерно одинаковой частотой присваиваются коды почти одинаковой длины в битах. Большинство систем с потоками Хаффмана были реализованы как системы Forth с прямым потоком и использовались для упаковки больших объемов медленно выполняемого кода в маленькие и дешевые микроконтроллеры . Большинство опубликованных [11] применений относятся к смарт-картам, игрушкам, калькуляторам и часам. Бит-ориентированный токенизированный код, используемый в PBASIC, можно рассматривать как своего рода код с резьбой Хаффмана.
Примером является потоковая обработка строк, при которой операции идентифицируются строками, которые обычно просматриваются по хеш-таблице. Это использовалось в самых ранних реализациях Форта Чарльза Х. Мура и в экспериментальном аппаратно интерпретируемом компьютерном языке Университета Иллинойса . Он также используется в Башфорте.
RPL компании HP , впервые представленный в калькуляторе HP-18C в 1986 году, представляет собой тип проприетарного гибридного (с прямой и косвенной резьбой) многопоточного языка интерпретации (TIL) [12] , который, в отличие от других TIL, позволяет встраивать RPL. «объекты» в «поток выполнения», т. е. поток адресов, по которому перемещается указатель интерпретатора. «Объект» RPL можно рассматривать как специальный тип данных, структура которого в памяти содержит адрес «пролога объекта» в начале объекта, за которым следуют данные или исполняемый код. Пролог объекта определяет, как должно выполняться или обрабатываться тело объекта. Используя «внутренний цикл RPL», [13] который был изобретен и запатентован [14] Уильямом К. Уиксом в 1986 году и опубликован в 1988 году, выполнение происходит следующим образом: [15]
Более точно это можно представить следующим образом:
О = [Я] Я = Я + Δ ПК = [О] + Δ
Здесь O — указатель текущего объекта, I — указатель интерпретатора, Δ — длина одного адресного слова, а оператор «[]» означает «разыменование».
Когда управление передается указателю объекта или внедренному объекту, выполнение продолжается следующим образом:
ПРОЛОГ -> ПРОЛОГ (адрес пролога в начале кода пролога указывает на себя) ЕСЛИ O + Δ =/= PC THEN GOTO INDIRECT (проверка прямого выполнения) O = I - Δ (Исправьте O, чтобы указать начало внедренного объекта) I = I + α (Исправьте I, чтобы указать точку после встроенного объекта, где α — длина объекта) INDIRECT (остальная часть пролога)
В микропроцессорах HP Saturn , использующих RPL, существует третий уровень косвенности, ставший возможным благодаря архитектурному/программному трюку, который обеспечивает более быстрое выполнение. [13]
Во всех интерпретаторах ветвь просто меняет указатель потока ( ip) на другой адрес в потоке. Условная ветвь перехода, если ноль, которая переходит только в том случае, если значение вершины стека равно нулю, может быть реализовано, как показано ниже. В этом примере используется версия прямой резьбы со встроенными параметрами, поэтому линия &thread[123]является местом назначения перехода, если условие истинно, поэтому ее необходимо пропустить ( ip++), если ветвь не выбрана.
thread : ... & brz & thread [ 123 ] ... brz : When_true_ip = * ip ++ // Получаем адрес назначения для ветки if ( *-- sp == 0 ) // Извлечение/потребление вершины стека и проверка если ноль ip = When_true_ip jump * ip ++ Разделение стеков данных и возвратов на машине устраняет большую часть кода управления стеком, существенно уменьшая размер многопоточного кода. Принцип двойного стека возник трижды независимо: для больших систем Берроуза , Forth и PostScript . Он используется в некоторых виртуальных машинах Java .
В многопоточной виртуальной машине часто присутствуют три регистра . Другой существует для передачи данных между подпрограммами («словами»). Это:
Часто многопоточные виртуальные машины , такие как реализации Форта, имеют в основе простую виртуальную машину, состоящую из трёх примитивов . Это:
В виртуальной машине с непрямой резьбой, приведенной здесь, выполняются следующие операции:
следующий : * ip ++ -> w jump ** w ++ гнездо : ip -> * rp ++ w -> ip next unnest : *-- rp -> ip next 
ipпараметром функции.