Считается ли C++ языком программирования фон Неймана?
Термин " языки фон Неймана" применяется к языкам программирования, вычислительная модель которых основана на компьютерной архитектуре фон Неймана.
- Считается ли C++ языком фон Неймана, или, если это не так (например, из-за асинхронного выполнения с появлением потоков), он когда-либо считался языком фон Неймана?
- Существует ли архитектура, на которой основана вычислительная модель / абстрактная машина C++ и, таким образом, может быть классифицирована как язык этой архитектуры?
3 ответа
TL:DR: Абстрактная машина C++ - это тип PRAM (параллельная машина произвольного доступа).
Из статьи в Википедии VonNeumann Languages, которую вы связали:
Многие широко используемые языки программирования, такие как C, C++ и Java, перестали быть строго фон Нейманом, добавив поддержку параллельной обработки в форме потоков.
Прекращение описывает переход от бытия к небытию. Итак, да, до того, как C++11 добавил потоки, C++ был строго языком фон Неймана согласно Википедии. (И после того, как это все еще в основном язык VN; наличие нескольких потоков, совместно использующих одно и то же адресное пространство, принципиально не меняет принцип работы C++.)
Интересные моменты в архитектуре фон Неймана в этом контексте:
- Наличие адресуемой оперативной памяти, обеспечивающей эффективный доступ (по модулю кеширования / подкачки) к любому объекту в любое время
- Хранение программы в ОЗУ: указатели функций возможны и эффективны, не требуя интерпретатора
- Наличие программного счетчика, который выполняет инструкции в сохраненной программе: естественная модель - это императивный язык программирования, который выполняет одно действие за раз. Это настолько фундаментально, что легко забыть, что это не единственная модель! (по сравнению с FPGA или ASIC или чем-то еще, где все ворота потенциально делают что-то параллельно каждый тактовый цикл. Или MIMD GPU, где вычислительное "ядро", которое вы пишете, запускается над всеми данными потенциально параллельно, без неявной последовательности каждого из них элемент обрабатывается. Или вычислительная ОЗУ: поместите ALU в микросхемы памяти, чтобы обойти узкое место фон Неймана)
IDK, почему в вики-статье упоминается самомодифицирующийся код; как и большинство языков, ISO C++ не стандартизирует это и полностью совместим с опережающей компиляцией для гарвардской архитектуры с разделенной шиной / разделенным адресным пространством. (Нетevalили что-нибудь еще, что потребует интерпретатора или JIT.) Или на обычном процессоре ( фон Неймана), строгая защита памяти W^X и никогда не использоватьmprotect чтобы изменить права доступа к странице с записываемых на исполняемые.
Конечно, большинство реальных реализаций C++ действительно предоставляют четко определенные способы записи машинного кода в буфер и преобразования его в указатель функции в качестве расширений. (например, GNU C/C++__builtin___clear_cache(start, end)назван в честь синхронизации I-кеша, но определен с точки зрения обеспечения безопасного вызова данных как функции wrt. Оптимизация исключения мертвого хранилища также возможна, так что код может сломаться без этого даже на x86, который имеет согласованные I-кеши.) Таким образом, реализации могут расширять ISO C++, чтобы использовать преимущества этой функции архитектур фон Неймана; Объем ISO C++ намеренно ограничен, чтобы учесть различия между операционными системами и тому подобным.
Обратите внимание, что, будучи Нейману вовсе не строго означает, поддерживая косвенные режимы адресации. Некоторые ранние процессоры этого не сделали, и самомодифицирующийся код (для перезаписи адреса, жестко закодированного в инструкции) был необходим для реализации вещей, для которых мы сейчас используем косвенное обращение.
Также обратите внимание, что Джон фон Нейман был действительно известным парнем, с его именем было связано множество фундаментальных вещей. Некоторые коннотации архитектуры фон Неймана (в отличие от Гарварда) на самом деле актуальны не во всех контекстах. например, термин "язык фон Неймана" не так сильно заботится о противостоянии фон Неймана и Гарварда; Он заботится о сохраненной программе со счетчиком программ по сравнению с чем-то вроде Cellular Automata или машины Тьюринга (с настоящей лентой). Получение дополнительной пропускной способности за счет использования отдельной шины (или просто разделенных кешей) для выборки инструкций (Гарвард) - это просто оптимизация производительности, а не фундаментальное изменение.
Что такое абстрактная машинная модель / модель вычислений?
Прежде всего, есть некоторые модели вычислений, которые слабее машин Тьюринга, например, конечные автоматы. Существуют также непоследовательные модели вычислений, например Cellular Automata (Игра жизни Конвея), в которых несколько вещей происходят параллельно на каждом "шаге".
Машина Тьюринга - наиболее широко известная (и математически простая) последовательная абстрактная машина, которая настолько "сильна", насколько мы знаем, как ее создать. Без какой-либо абсолютной адресации памяти, только относительное движение на ленте, естественно, обеспечивает бесконечное хранилище. Это важно и отличает все другие виды абстрактных машин в некотором роде от настоящих ЦП. Помните, что эти модели вычислений используются в теоретической информатике, а не в инженерии. Такие проблемы, как конечный объем памяти или производительность, не имеют отношения к тому, что вычислимо в теории, только на практике.
Если вы можете вычислить что-то на машине Тьюринга, вы можете вычислить это на любой другой полной по Тьюрингу модели вычислений (по определению), возможно, с помощью гораздо более простой программы, а возможно, и нет. Машины Тьюринга не очень хорошо программировать или, по крайней мере, сильно отличаются от языка ассемблера для любого реального процессора. В частности, память не является произвольной. И они не могут легко моделировать параллельные вычисления / алгоритмы. (Если вы хотите доказать что-то об алгоритме абстрактно, то, вероятно, неплохо было бы иметь его реализацию для какой-либо абстрактной машины.)
Также потенциально интересно доказать, какие функции должна иметь абстрактная машина, чтобы быть полной по Тьюрингу, так что это еще одна мотивация для разработки большего количества из них.
Есть много других, эквивалентных с точки зрения вычислимости. Модель RAM-машины больше всего похожа на реальные процессоры, у которых есть массив памяти. Но будучи простой абстрактной машиной, она не заботится о регистрах. Фактически, чтобы еще больше запутать, он называет свои ячейки памяти массивом регистров.. Машина RAM поддерживает косвенную адресацию, поэтому правильная аналогия с реальными процессорами определенно связана с памятью, а не с регистрами процессора. (И существует неограниченное количество регистров, каждый из которых имеет неограниченный размер. Адреса сохраняются вечно, и каждый "регистр" должен содержать указатель.) RAM-машина может быть Гарвардской: программа хранится в отдельной части конечного состояния. машина. Думайте об этом как о машине с режимами косвенной адресации памяти, чтобы вы могли хранить "переменные" в известных местах и использовать некоторые из них как указатели на структуры данных неограниченного размера.
Программа для абстрактной RAM-машины выглядит как язык ассемблера, с load/add/jnz и любым другим набором инструкций, который вы хотите, чтобы он имел. Операнды могут быть непосредственными или регистровыми числами (то, что нормальные люди называют абсолютными адресами). Или, если в модели есть аккумулятор, тогда у вас есть машина загрузки / хранения с аккумулятором, больше похожая на настоящий ЦП.
Если вы когда-нибудь задумывались, почему так называлась "3-адресная" машина, такая как MIPS, вместо 3-операнда, вероятно, 1. потому что для кодирования инструкций требуется пропускная способность места / I-выборки через узкое место фон Неймана для трех явных расположений операндов (регистр number) и 2. потому что в абстрактной машине RAM операнды - это адреса памяти = номера регистров.
C++ не может быть полным по Тьюрингу: указатели имеют конечный размер.
Конечно, C++ имеет огромные отличия от модели абстрактной машины CS: C++ требует, чтобы каждый тип имел конечную константу времени компиляции.sizeof, поэтому C++ не может быть полным по Тьюрингу, если вы включите требование бесконечного хранилища. Всё в C действительно ли Тьюринг-полным? в cs.SE применимо и к C++: требование, чтобы типы имели фиксированную ширину, является препятствием для бесконечного хранения. См. Также https://en.wikipedia.org/wiki/Random-access_machine
Итак, абстрактные машины по информатике глупы, а как насчет абстрактной машины C++?
У них, конечно, есть свои цели, но мы можем сказать гораздо больше интересного о C++ и о том, какую машину он предполагает, если мы станем немного менее абстрактными, а также поговорим о том, что машина может делать эффективно. Когда мы говорим о машинах с конечным автоматом и производительности, эти различия становятся актуальными.
Во-первых, чтобы запустить C++ вообще, а во-вторых, чтобы он работал без огромных и / или недопустимых накладных расходов на производительность. (например, HW необходимо будет поддерживать указатели напрямую, вероятно, не с помощью самомодифицирующегося кода, который сохраняет значение указателя в каждой инструкции загрузки / сохранения, которая его использует. И это не будет работать в C++11, где потоки являются частью язык: один и тот же код может работать с двумя разными указателями одновременно.)
Мы можем более подробно рассмотреть модель вычислений, принятую в стандарте ISO C++, который описывает, как работает язык с точки зрения того, что происходит на абстрактной машине. Реальные реализации требуются для запуска кода на реальном оборудовании, которое работает "как если бы" абстрактная машина выполняла исходный код C++, воспроизводя любое / все наблюдаемое поведение (наблюдаемое другими частями программы без вызова UB).
В C / C++ есть память и указатели, так что это определенно тип RAM-машины.
Или в эти дни, Параллельная машина с произвольным доступом, добавление разделяемой памяти в модели RAM, и дает каждому потоку свой собственный программный счетчик. При условии std::atomic<>Release-sequence делают все предыдущие операции видимыми для других потоков, модель синхронизации "установление связи происходит до" основана на согласованной разделяемой памяти. Эмуляция его поверх чего-то, что требует ручного запуска синхронизации / очистки, будет ужасно для производительности. (Очень умная оптимизация может оказаться отложенной, поэтому не каждое хранилище релизов должно пострадать, но seq-cst, вероятно, будет ужасным. Seq-cst должен установить глобальный порядок операций, с которым согласны все потоки; это сложно, если магазин становится видимым для всех других потоков одновременно.)
Но обратите внимание, что в C++ фактический одновременный доступ - это UB, если вы не сделаете это с atomic<T>. Это позволяет оптимизатору свободно использовать регистры ЦП для локальных, временных и даже глобальных переменных, не раскрывая регистры как функцию языка. UB допускает оптимизацию в целом; вот почему современные реализации C / C++ не являются переносимым языком ассемблера.
Исторический registerКлючевое слово в C / C++ означает, что адрес переменной не может быть взят, поэтому даже неоптимизирующий компилятор может сохранить его в регистре ЦП, а не в памяти. Мы говорим о регистрах ЦП, а не о машинном ОЗУ "регистр = адресуемая область памяти". (Подобноrax..rsp/r8..r15 на x86 или r0..r31на MIPS). Современные компиляторы избегают анализа и, естественно, обычно хранят локальные переменные в регистрах, если им не нужно их проливать. Возможны и другие типы регистров ЦП, например регистровый стек, такой как регистры x87 FP. Во всяком случае,registerключевое слово существует для оптимизации для этого типа машин. Но это не исключает работы на машине без регистров, только инструкции память-память.
C++ разработан для хорошей работы на машине фон Неймана с регистрами ЦП, но абстрактная машина C++ (которую стандарт использует для определения языка) не позволяет выполнять данные в виде кода или ничего не говорить о регистрах. Тем не менее, каждый поток C++ имеет свой собственный контекст выполнения, и он моделирует потоки / ядра PRAM, каждый из которых имеет свой собственный счетчик программ и стек вызовов (или что-то еще, что реализация использует для автоматического хранения и для определения того, куда вернуться). На реальной машине. с регистрами ЦП они принадлежат каждому потоку.
Все реальные ЦП являются машинами с произвольным доступом и имеют регистры ЦП отдельно от адресуемой / индексируемой ОЗУ. Даже процессоры, которые могут выполнять вычисления только с одним регистром накопителя, обычно имеют по крайней мере один указатель или индексный регистр, который по крайней мере допускает некоторую ограниченную индексацию массива. По крайней мере, все процессоры, которые хорошо работают как цели компилятора C.
Без регистров для кодирования каждой машинной инструкции потребовались бы абсолютные адреса памяти для всех операндов. (Может быть, как 6502, где "нулевая страница", младшие 256 байтов памяти, были особенными, и есть режимы адресации, которые используют слово с нулевой страницы в качестве индекса или указателя, чтобы разрешить 16-битные указатели без каких-либо 16-битные архитектурные регистры или что-то в этом роде.) См. Почему компиляторы от C до Z80 создают плохой код? на RetroComputing.SE для некоторых интересных вещей о реальных 8-битных процессорах, где полностью совместимая реализация C (поддерживающая рекурсию и повторный вход) довольно дорога в реализации. Большая часть медлительности заключалась в том, что системы 6502 / Z80 были слишком малы для размещения оптимизирующего компилятора. Но даже гипотетический современный оптимизирующий кросс-компилятор (например, серверная часть gcc или LLVM) столкнется с трудностями с некоторыми вещами. См. Также недавний ответ о том, что такое неиспользуемый адрес памяти? для хорошего объяснения режима индексированной адресации нулевой страницы 6502: 16-битный указатель из абсолютного 8-битного адреса в памяти + 8-битный регистр.
Машина без косвенной адресации вообще не может легко поддерживать индексирование массивов, связанные списки и определенно не переменные-указатели в качестве объектов первого класса. (В любом случае неэффективно)
Что эффективно на реальных машинах -> какие идиомы естественны
Большая часть ранней истории C была связана с PDP-11, который представляет собой обычную машину с памятью и регистрами, где любой регистр может работать как указатель. Автоматическое хранилище сопоставляется с регистрами или с пространством в стеке вызовов, когда их нужно пролить. Память - это плоский массив байтов (или фрагментыchar), без сегментации.
Индексирование массивов просто определяется в терминах арифметики указателей, а не само по себе, возможно, потому, что PDP-11 может делать это эффективно: любой регистр может содержать адрес и разыменовываться. (по сравнению с некоторыми машинами только с парой специальных регистров ширины указателя, а остальные уже. Это было обычным явлением на 8-битных машинах, но ранние 16-битные машины, такие как PDP-11, имели мало ОЗУ, чтобы один 16-битный регистр хватило на адрес).
См. Статью Денниса Ричи " Развитие языка Си" для получения дополнительной информации; C вырос из B на PDP-7 Unix. (Первый Unix был написан на PDP-7 asm). Я мало что знаю о PDP-7, но, очевидно, BCPL и B также используют указатели, которые являются просто целыми числами, а массивы основаны на арифметике указателей.
PDP-7 - это 18-битный ISA с адресацией по словам. Наверное, поэтому у B нетcharтип. Но его регистры достаточно широки, чтобы содержать указатели, поэтому он, естественно, поддерживает модель указателя B и C (указатели на самом деле не являются особенными, вы можете копировать их и разыскивать, и вы можете взять адрес чего угодно). Итак, плоская модель памяти, никакой "особой" области памяти, как на сегментированных машинах или каких-то 8-битных микросхемах с нулевой страницей.
Такие вещи, как C99 VLA (и локальные переменные неограниченного размера), неограниченная повторная входимость и рекурсия, подразумевают стек вызовов или другой механизм распределения для контекста локальной переменной функции (он же фреймы стека на обычной машине, которая использует указатель стека).
Я думаю, что попытка привязать C++ (или большинство других языков) к единой модели архитектуры в лучшем случае сложно. Рассмотрим C++ 98/03. Как говорится в вопросе, они соответствуют модели фон Неймана. Но подождите - они также примерно одинаково (если не лучше) подходят гарвардской архитектуре.
В этом отношении Гарвардская архитектура - это скорее семейство моделей, чем отдельная модель. В частности, обычно считается, что ЦП использует Гарвардскую архитектуру, если у него есть отдельные кеши для кода и данных - даже если это что-то вроде x86, где оборудование делает все возможное, чтобы скрыть это разделение от кода (например, вы можете напишите самомодифицирующийся код, и после того, как вы изменили код, то, что вы выполняете, будет новым кодом - хотя это может быть значительным штрафом, потому что кеш инструкций не оптимизирован для обработки изменений).
Но "Гарвардская архитектура" также может использоваться для описания таких вещей, как некоторые DSP, которые имеют две (или три) полностью отдельные шины памяти, подключенные к физически отдельной памяти:
Языковые правила для этого на самом деле довольно тонкие - до такой степени, что, если вы не искали их, было бы легко их полностью пропустить. Например, C и C++ определяют указатель на функцию как отдельную вещь от указателя на данные. Они также очень осторожны, чтобы не давать никаких гарантий относительно сопоставимости таких вещей, как адреса, за исключением довольно ограниченных обстоятельств (например, в C++ вам ничего не гарантируется относительно сравнения адреса функции с адресом данных).
Однако, начиная со стандарта C++11, это немного изменилось. В то время как основной язык сохраняет базовый характер наличия некоторого потока инструкций, выполняемых в указанном порядке, библиотека добавляет возможность создавать несколько потоков, которые могут выполняться параллельно. Им разрешено связываться через общую память, но вы должны использовать атомарную переменную или забор памяти, чтобы гарантировать любую степень успеха. Это позволяет реализовать на машинах где угодно - от чрезвычайно сильно связанных до довольно слабосвязанных, где (например) связь, которая выглядит как разделяемая память, может фактически включать отправку данных через что-то вроде сетевого соединения с отправкой сигнала, чтобы сообщить дальнему концу, когда передача завершена.
Итак, опять же, спецификация языка на самом деле не привязана к тому, что обычно рассматривается как единая архитектура на аппаратном уровне. Скорее наоборот, хотя он, вероятно, работает лучше для того, что обычно считается довольно сильно связанными машинами, я считаю, что он может быть реализован на довольно слабосвязанных машинах, таких как кластер полностью отдельных, разрозненных машин. Обычно вам нужно (или, по крайней мере, хотеть) изменить способ написания кода, но, по крайней мере, теоретически вы могли бы написать переносимый код C++, который работал бы на любом из них.
C++ - это спецификация, написанная на английском языке в виде стандарта. См. N3337 - поздний черновик C++11.
Как объясняют Джерри Коффин и Питер Кордес, официальная модель - это параллельная случайная машина.
Но обычно вы пишете код на C++ с помощью компилятора и запускаете свою программу (если вы не кодируете встроенные системы) в какой-либо операционной системе (например, Windows или Linux; прочтите также это). Многие ОС предоставляют средства динамической загрузки (например, dlopen(3) в Linux), и большинство компьютеров могут иметь компиляторы C++.
Тогда вы практически можете сгенерировать код C++ во время выполнения, выполнить компиляцию этого сгенерированного кода C++ как плагин, а затемdlopenэтот сгенерированный плагин. А в Linux вы можете делать это много раз (например, иметь десятки тысяч таких сгенерированных плагинов, см. Мои программы bismon и manydl.c).
Вы также можете найти несколько JIT-компилирующих библиотек C++, таких как libgccjit или LLVM.
Фактически, программы на C++ могут генерировать код во время выполнения, а затем использовать его (даже если это выходит за рамки стандарта C++). И это характерно для машин фон Неймана.