Сглаживание (вычисления) - Aliasing (computing)

Относительно терминов, используемых в обработке сигналов и компьютерной графике, см. Сглаживание.
Чтобы узнать, как заменить имена команд в оболочке компьютера, см. Псевдоним (команда).

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

Примеры

Переполнение буфера

Например, большинство реализаций Язык программирования C не выполнять проверка границ массива. Затем можно использовать реализацию языка программирования компилятором и архитектурой компьютера. язык ассемблера соглашений, чтобы добиться эффекта сглаживания путем записи вне массива (тип переполнение буфера ). Это вызывает неопределенное поведение согласно спецификации языка C; однако многие реализации C демонстрируют описанные здесь эффекты наложения имен.

Если массив создается на стек, с переменной, расположенной в памяти непосредственно рядом с этим массив, можно индексировать за пределами массива и напрямую изменять переменную, изменяя соответствующий элемент массива. Например, если есть int массив размером 2 (для этого примера называя его обр), рядом с другим int переменная (назовите это я), обр [2] (т.е. 3-й элемент) будет называться я если они смежны в памяти.

# включить int основной(){  int обр[2] = { 1, 2 };  int я=10;  / * Записываем после окончания обр. Неопределенное поведение в стандартном C будет записывать в i в некоторых реализациях. * /  обр[2] = 20;  printf("элемент 0:% d  т", обр[0]); // выводит 1  printf("элемент 1:% d  т", обр[1]); // выводит 2  printf("элемент 2:% d  т", обр[2]); // выводит 20, если произошло алиасинг  printf("мне бы  т  т", я); // может также вывести 20, а не 10, из-за наложения имен, но компилятор может сохранить i в регистре и вывести 10  / * размер arr по-прежнему равен 2. * /  printf("размер arr:% d  п", (размер(обр) / размер(int)));}

Это возможно в некоторых реализациях C, потому что массив является блоком непрерывной памяти, а ссылки на элементы массива просто смещены от адреса начала этого блока, умноженного на размер одного элемента. Поскольку в C нет проверки границ, возможна индексация и адресация вне массива. Обратите внимание, что вышеупомянутое поведение псевдонима неопределенное поведение. Некоторые реализации могут оставлять пространство между массивами и переменными в стеке, например, для выравнивания переменных по ячейкам памяти, которые являются кратными собственному архитектурам. размер слова. Стандарт C обычно не определяет, как данные должны быть размещены в памяти. (ИСО / МЭК 9899: 1999, раздел 6.2.6.1).

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

Указатели с псевдонимом

Смотрите также: Смещение указателя

Другая разновидность псевдонимов может иметь место на любом языке, который может относиться к одному месту в памяти с более чем одним именем (например, с указатели ). См. C пример алгоритма обмена XOR, который является функцией; он предполагает, что два переданных ему указателя различны, но если они фактически равны (или являются псевдонимами друг друга), функция завершается ошибкой. Это обычная проблема с функциями, которые принимают аргументы-указатели, и их допуск (или отсутствие такового) к сглаживанию должен быть тщательно задокументирован, особенно для функций, которые выполняют сложные манипуляции с переданными им областями памяти.

Указанный псевдоним

В некоторых случаях может быть желательно контролируемое поведение псевдонимов (то есть, поведение псевдонимов, которое указано, в отличие от того, что разрешено макетом памяти в C). Это обычная практика в Фортран. В Perl язык программирования определяет в некоторых конструкциях поведение псевдонима, например, в для каждого петли. Это позволяет изменять определенные структуры данных напрямую с меньшим количеством кода. Например,

мой @array = (1, 2, 3);для каждого мой $ element (@array) {    # Увеличить $ element автоматически    # изменение @array, поскольку $ element имеет псевдоним    # по очереди к каждому из элементов @ массива.    $ element++;}Распечатать "@ массив  n";

в результате распечатает «2 3 4». Если кто-то хочет обойти эффекты сглаживания, можно скопировать содержимое индексной переменной в другую и изменить копию.

Конфликты с оптимизацией

Оптимизаторы часто приходится делать консервативные предположения о переменных, когда возможно сглаживание. Например, зная значение переменной (такой как Икс равно 5) обычно допускает определенные оптимизации (например, постоянное распространение ). Однако компилятор не может использовать эту информацию после присвоения другой переменной (например, в C, * у = 10) потому что могло быть так * у это псевдоним Икс. Это могло произойти после такого задания, как у = & х. В результате этого присвоения * у, значение x также будет изменено, таким образом распространяя информацию, Икс равно 5 к следующим утверждениям * у = 10 было бы потенциально неправильно (если * у это действительно псевдоним Икс). Однако, если есть информация об указателях, процесс распространения константы может сделать запрос типа: может Икс быть псевдонимом * у? Тогда, если ответ отрицательный, х = 5 можно безопасно размножать.

Еще одна оптимизация, на которую влияет наложение псевдонимов, - это изменение порядка кода. Если компилятор решит, что Икс не имеет псевдонима * у, затем код, который использует или изменяет значение Икс можно переместить перед назначением * у = 10, если это улучшит планирование или включить больше оптимизация цикла будет осуществляться.

Чтобы обеспечить такую ​​оптимизацию предсказуемым образом, стандарт ISO для Язык программирования C (включая его более новые C99 редакция, см. раздел 6.5, параграф 7) указывает, что незаконно (за некоторыми исключениями) обращаться к одному и тому же участку памяти с использованием указателей разных типов. Поэтому компилятор может предположить, что такие указатели не являются псевдонимами. Это правило, известное как строгое правило алиасинга, иногда позволяет добиться впечатляющего увеличения производительности,[1] но известно, что он нарушает какой-то в остальном действительный код. Некоторые программные проекты намеренно нарушают эту часть стандарта C99. Например, Python 2.x сделал это, чтобы реализовать подсчет ссылок,[2] и потребовалось внести изменения в основные структуры объектов в Python 3, чтобы включить эту оптимизацию. В Ядро Linux делает это потому, что строгое алиасинг вызывает проблемы с оптимизацией встроенного кода.[3] В таких случаях при компиляции с gcc, опция -fno-strict-aliasing вызывается для предотвращения нежелательной оптимизации, которая может привести к непредвиденному коду.

Аппаратный псевдоним

Период, термин сглаживание также используется для описания ситуации, когда из-за выбора конструкции оборудования или отказа оборудования один или несколько доступных битов адреса не используются в процессе выбора памяти.[4] Это может быть конструктивным решением, если доступно больше адресных битов, чем необходимо для поддержки установленных устройств памяти. В случае сбоя один или несколько битов адреса могут быть закорочены вместе или могут быть вынуждены земля (логический 0) или напряжение питания (логическая 1).

пример

В этом примере, предполагая структуру памяти с 8 ячейками, требующую только 3 адресных строк (или биты ) поскольку 23 = 8). Биты адреса (с именами от A2 до A0) декодируются для выбора уникальных ячеек памяти следующим образом в стандартном двоичный счетчик мода:

A2A1A0Место в памяти
0000
0011
0102
0113
1004
1015
1106
1117

В приведенной выше таблице каждая из 8 уникальных комбинаций адресных битов выбирает разные ячейки памяти. Однако, если бы один бит адреса (скажем, A2) был закорочен на землю, таблица была бы изменена следующим образом:

A2A1A0Место в памяти
0000
0011
0102
0113
0000
0011
0102
0113

В этом случае, когда A2 всегда равен нулю, первые четыре ячейки памяти дублируются и снова появляются как вторые четыре. Ячейки памяти с 4 по 7 стали недоступны.

Если бы это изменение произошло с другим адресным битом, результаты декодирования были бы другими, но в целом эффект был бы таким же: потеря одного адресного бита сокращает доступное пространство памяти наполовину, что приводит к дублированию (псевдониму) оставшееся место.

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

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

  1. ^ Майк Эктон (01.06.2006). "Понимание строгого псевдонима".
  2. ^ Нил Шеменауэр (17 июля 2003 г.). "Строгий псевдоним ANSI и Python".
  3. ^ Линус Торвальдс (26 февраля 2003 г.). "Re: недопустимая компиляция без -fno-strict-aliasing".
  4. ^ Майкл Барр (27 июля 2012 г.). «Программное тестирование памяти».

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