TL: DR: абстрактная машина C ++ представляет собой тип PRAM (параллельная машина произвольного доступа) .
из языков фон Неймана Википедиястатья, на которую вы ссылаетесь:
Многие широко используемые языки программирования, такие как C, C ++ и Java, перестали быть строго фон Неймана, добавив поддержку параллельной обработки в виде потоков.
Прекращение описывает переход от бытия к небытию. Так что да, до того, как C ++ 11 добавил потоки, C ++ был строго языком фон Неймана согласно Википедии. (И после того, как это все еще в основном язык VN; наличие нескольких потоков, совместно использующих одно и то же адресное пространство, принципиально не меняет работу C ++.)
В этом контексте интересны аспекты архитектуры Von Neumann. :
- Имея вообще адресуемую оперативную память, обеспечивая эффективный доступ (кеширование / подкачка по модулю) к любому объекту в любое время
- Хранение программы в оперативной памяти: возможны указатели функцийи эффективный, не требующий интерпретатора
- Наличие счетчика программы, который выполняет инструкции в хранимой программе: Естественная модель - это императивный язык программирования, который выполняет одну вещь за один раз . Это настолько фундаментально, что легко забыть, что это не единственная модель! (по сравнению с FPGA или ASIC или чем-то, где все шлюзы потенциально выполняют что-то параллельно каждый тактовый цикл. Или MIMD GPU, где вычислительное «ядро», которое вы пишете, выполняется над всеми данными, потенциально параллельными, без неявной последовательности каждого порядка. элемент обрабатывается в. Или Вычислительная память : поместите ALU в микросхемы памяти, чтобы обойти узкое место фон Неймана)
IDK, хотя в статье в вики упоминается самоизменяющийся код;Как и большинство языков, ISO C ++ не стандартизирует это и полностью совместимо с опережающей компиляцией для архитектуры Гарварда с разделенной шиной и разделенным адресом 1039 *. (Нет eval или что-либо еще, что потребовало бы интерпретатора или JIT.) Или на обычном процессоре ( Von Neumann ), строгой защите памяти W ^ X и никогда не используя mprotect для изменения прав доступа к странице свозможность записи в исполняемый файл.
Конечно, большинство реальных реализаций C ++ do предоставляют четко определенные способы записи машинного кода в буфер и приведения к указателю на функцию в качестве расширений. (например, GNU C / C ++ __builtin___clear_cache(start, end) назван для синхронизации I-кеша, но определен с точки зрения обеспечения безопасного вызова данных как функции, в том числе и для оптимизации устранения мертвых хранилищ, поэтому код может обойтись без негодаже на x86, который имеет когерентный I-кэш.) Таким образом, реализации могут расширить ISO C ++, чтобы воспользоваться преимуществами этой архитектуры Von Neumann ;ISO C ++ намеренно ограничен в объеме, чтобы учесть различия между операционными системами и тому подобным.
Обратите внимание, что, будучи фон Нейманом, не строго подразумевает поддержку косвенных режимов адресации. Некоторые ранние процессоры этого не делали, и для модификации вещей, для которых мы сейчас используем косвенное обращение, был необходим самоизменяющийся код (для перезаписи адреса, жестко закодированного в инструкции).
Также обратите внимание, что Джон ФонНейман был действительно известным парнем, его имя было связано с множеством фундаментальных вещей . Некоторые из коннотаций архитектуры фон Неймана (в отличие от Гарварда) не очень актуальны во всех контекстах. например, термин «язык фон Неймана» не очень заботит фон Неймана против Гарварда;Он заботится о сохраненной программе со счетчиком программ и чем-то вроде Cellular Automata или машины Тьюринга (с реальной лентой) . Получение дополнительной полосы пропускания с использованием отдельной шины (или просто разделенных кэшей) для извлечения инструкций (Гарвард) - это просто оптимизация производительности, а не фундаментальное изменение.
Что такое модель / модель вычисления абстрактной машиныв любом случае?
Прежде всего, существуют модели вычислений , которые на слабее , чем машины Тьюринга, например Машины конечного состояния . Существуют также непоследовательные модели вычислений, например, Сотовые автоматы (Игра жизни Конвея) , где несколько вещей происходят параллельно на каждом "шаге".
Тьюрингmachine - самая широко известная (и математически простая) последовательная абстрактная машина , настолько же «сильная», насколько мы знаем, как ее создать. Без какой-либо абсолютной адресации памяти, просто относительного перемещения на ленте, она, естественно, обеспечивает бесконечное хранение. Это важно и делает некоторые другие виды абстрактных машин в некоторых отношениях очень непохожими на реальные процессоры. Помните, что эти модели вычислений используются для теоретической информатики, а не инженерии. Такие проблемы, как ограниченный объем памяти или производительность, не имеют отношения к тому, что вычисляется в теории , только на практике.
Если вы можете что-то вычислить на машине Тьюринга, вы можете вычислить ее на любомдругая модель вычислений, полная по Тьюрингу (по определению), возможно, с гораздо более простой программой или, возможно, нет. Машины Тьюринга не очень хороши в программировании или, по крайней мере, сильно отличаются от языка ассемблера для любого реального процессора. В частности, память не случайного доступа. И они не могут легко моделировать параллельные вычисления / алгоритмы. (Если вы хотите доказать что-то об алгоритме в абстрактном виде, иметь его реализацию для некоторой абстрактной машины, вероятно, хорошо.)
Также потенциально интересно доказать, что представляет собой абстрактная машинадолжен иметь, чтобы был завершен по Тьюрингу, так что это еще один мотив для разработки большего количества из них.
Есть много других, которые эквивалентны с точки зрения вычислимости. Модель машины RAM больше всего похожа на реальные процессоры с массивом памяти. Но будучи простой абстрактной машиной, она не беспокоится о регистрах. Фактически, просто чтобы запутать вещи, он называет свои ячейки памяти массивом регистров . Машина с ОЗУ поддерживает косвенную адресацию, поэтому правильная аналогия с реальными процессорами - это память, а не регистры процессора. (И существует неограниченное количество регистров, каждый из которых имеет неограниченный размер. Адреса продолжают работать вечно, и каждый «регистр» должен иметь возможность хранить указатель.) Машина ОЗУ может быть гарвардской: программа хранится в отдельной части конечного состояниямашина. Думайте об этом, как о машине с режимами адресации косвенной памяти, так что вы можете хранить «переменные» в известных местах и использовать некоторые из них в качестве указателей на структуры данных неограниченного размера.
Программа дляабстрактный RAM RAM выглядит как ассемблер, с загрузкой / добавлением / jnz и любым другим набором инструкций, которые вы хотите иметь. Операнды могут быть непосредственными или регистрировать номера (что обычные люди называют абсолютными адресами). Или, если модель имеет аккумулятор, то у вас есть машина загрузки / хранения с аккумулятором, намного больше похожая на реальный процессор.
Если вы когда-нибудь задумывались, почему так называлась «трехадресная» машина, такая как MIPS,вместо 3-х операндов это, вероятно, 1. потому что для кодирования инструкций требуется пропускная способность помещения / I-выборки через узкое место фон Неймана для 3 явных местоположений операндов (номер регистра) и 2. потому что в абстрактной машине ОЗУ, операнды - это адреса памяти = номера регистров.
C ++ не может быть завершен по Тьюрингу: указатели имеют конечный размер.
Конечно, C ++ имеет огромные отличия от модели абстрактной машины CS: C ++ требует, чтобы каждый тип имел постоянную времени компиляции sizeof, поэтому C ++ может 't быть завершенным по Тьюрингу, если вы включите требование бесконечного хранения . Все, что в Является ли C на самом деле полным по Тьюрингу? в cs.SE также применимо и к C ++: требование, чтобы типы имели фиксированную ширину, являлось демонстрационным шагом для бесконечного хранения. См. Также https://en.wikipedia.org/wiki/Random-access_machine#Finite_vs_unbounded
Итак, абстрактные машины информатики глупы, а как насчет абстрактной машины C ++?
У них, конечно, есть свои цели, но есть гораздо более интересные вещи, которые мыМожно сказать о C ++ и о том, какую машину он принимает, если мы получим менее абстрактную , а также поговорим о том, что машина может сделать эффективно . Как только мы говорим о машинах с конечными машинами и производительности, эти различия становятся важными.
Во-первых, чтобы вообще запустить C ++, и во-вторых, чтобы работать без огромных и / или недопустимых накладных расходов на производительность. (Например, HW должен будет поддерживать указатели довольно напрямую, вероятно, не с самоизменяющимся кодом, который сохраняет значение указателя в каждой инструкции загрузки / хранения, которая его использует. И это не сработает в C ++ 11, где многопоточность является частьюязык: один и тот же код может работать с двумя разными указателями одновременно.)
Мы можем более подробно рассмотреть модель вычисления, принятую в стандарте ISO C ++, которая описывает, как язык работает в терминахчто происходит на абстрактной машине. Реальные реализации требуются для запуска кода на реальном оборудовании, которое работает «как будто», если абстрактная машина выполняла исходный код C ++, воспроизводя любое / все наблюдаемое поведение (наблюдаемое другими частями программы без вызова UB).
C / C ++ имеет память и указатели, поэтому это определенно тип машины с ОЗУ.
Или в наши дни a Параллельная машина с произвольным доступом , добавляющая общую памятьк модели оперативной памяти, и давая каждому потоку свой собственный счетчик программ. Учитывая, что std::atomic<> release-последовательности делают все предыдущие операции видимыми для других потоков, модель синхронизации «установление отношения до того» основана на связной общей памяти. Эмуляция его поверх чего-то, что требовало ручного запуска синхронизации / очистки, было бы ужасно для производительности. (Очень умные оптимизации могут доказать, когда это может быть отложено, поэтому не каждый релиз-хранилище должен страдать, но 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 для получения дополнительной истории; C выросла из B на PDP-7 Unix . (Первый Unix был написан на PDP-7 asm). Я не знаю много о PDP-7, но, очевидно, BCPL и B также используют указатели, которые являются просто целыми числами, а массивы основаны на арифметике указателей.
PDP-7 - это18-битное адресуемое слово ISA . Вероятно, поэтому B не имеет типа char. Но его регистры достаточно широки, чтобы содержать указатели, поэтому он, естественно, поддерживает модель указателей B и C (что указатели на самом деле не являются специальными, вы можете копировать их и разыменовывать, и вы можете взять адрес чего угодно). Такая плоская модель памяти, никакой «особой» области памяти, как на сегментированных машинах или некоторых 8-битных микросхемах с нулевой страницей.
Такие вещи, как C99 VLA (и локальные переменные неограниченного размера) и неограниченный повторный вход и рекурсия, подразумевают стек вызовов или другой механизм выделения для контекста локальной переменной функции (так называемые кадры стека на обычном компьютере, который использует указатель стека.)