Реалистичное использование ключевого слова C99 «Restrict»?

183

Я просматривал некоторую документацию и вопросы / ответы и видел упомянутое. Я прочитал краткое описание, в котором говорится, что программист обещает, что указатель не будет использоваться для указания другого места.

Может ли кто-нибудь предложить некоторые реалистичные случаи, когда на самом деле стоит использовать это?

user90052
источник
4
memcpyпротив memmoveодин канонический пример.
Александр С.
@AlexandreC .: Я не думаю, что это особенно применимо, так как отсутствие квалификатора «restrict» не означает, что логика программы будет работать с перегрузкой источника и назначения, а также наличие такого классификатора не будет препятствовать вызываемому методу определение, перекрываются ли источник и назначение, и, если это так, замена dest на src + (dest-src), который, поскольку он является производным от src, может получить псевдоним.
суперкат
@supercat: Вот почему я поставил это как комментарий. Тем не менее, 1) restrictквалифицирующие аргументы, memcpyпозволяющие в принципе агрессивно оптимизировать наивную реализацию, и 2) простой вызов memcpyпозволяет компилятору предполагать, что переданные ему аргументы не являются псевдонимами, что может позволить некоторую оптимизацию вокруг memcpyвызова.
Александр С.
@AlexandreC .: Компилятору на большинстве платформ было бы очень трудно оптимизировать наивный memcpy - даже с «restrict» - быть настолько эффективным, насколько версия адаптирована к цели. Оптимизация на стороне вызова не потребует ключевого слова restrict, и в некоторых случаях усилия по их упрощению могут быть непродуктивными. Например, многие реализации тетсру могли бы, при нулевой дополнительных затрат, в отношении memcpy(anything, anything, 0);как не-оп, и гарантировать , что если pэто указатель на по крайней мере , nзаписываемые байт memcpy(p,p,n); не будет иметь побочных эффектов. Такие случаи могут возникнуть ...
суперкат
... естественно, в определенных видах кода приложения (например, подпрограмма сортировки, заменяющая элемент на себя) и в реализациях, где они не имеют неблагоприятных побочных эффектов, разрешение обработки этих случаев с помощью кода общего случая может быть более эффективным, чем использование добавить специальные тесты. К сожалению, некоторые авторы компиляторов, кажется, считают, что лучше, чтобы программисты добавляли код, который компилятор, возможно, не сможет оптимизировать, чтобы упростить «возможности оптимизации», которые компиляторы очень редко использовали бы в любом случае.
суперкат

Ответы:

182

restrictговорит, что указатель - единственная вещь, которая обращается к базовому объекту. Это исключает возможность наложения указателей, обеспечивая лучшую оптимизацию компилятором.

Например, предположим, у меня есть машина со специализированными инструкциями, которая может умножать векторы чисел в памяти, и у меня есть следующий код:

void MultiplyArrays(int* dest, int* src1, int* src2, int n)
{
    for(int i = 0; i < n; i++)
    {
        dest[i] = src1[i]*src2[i];
    }
}

Потребности компилятор правильно обращаться , если dest, src1и src2перекрытия, а это означает , что необходимо выполнить одно умножение в то время, от начала до конца. Имея restrict, компилятор может оптимизировать этот код с помощью векторных инструкций.

В Википедии есть запись restrict, с другим примером, здесь .

Майкл
источник
3
@ Майкл - Если я не ошибаюсь, тогда проблема будет только в том случае, если destперекрывается любой из исходных векторов. С чего бы возникли проблемы, если src1и src2перекрываются?
2015 г.
1
ограничение обычно действует только при указании на объект, который изменяется, и в этом случае он утверждает, что скрытые побочные эффекты не должны приниматься во внимание. Большинство компиляторов используют его для облегчения векторизации. Msvc использует проверку времени выполнения для перекрытия данных для этой цели.
tim18
Добавление ключевого слова register к переменной цикла for также ускоряет его, в дополнение к добавлению restrict.
2
На самом деле, ключевое слово в реестре носит рекомендательный характер. А в компиляторах, начиная примерно с 2000 года, i (и n для сравнения) в этом примере будут оптимизированы в регистр независимо от того, используете ли вы ключевое слово register.
Марк Фишлер
154

Пример Википедии является очень осветительным.

Это ясно показывает, как это позволяет сохранить одну инструкцию по сборке .

Без ограничений:

void f(int *a, int *b, int *x) {
  *a += *x;
  *b += *x;
}

Псевдо сборка:

load R1  *x    ; Load the value of x pointer
load R2  *a    ; Load the value of a pointer
add R2 += R1    ; Perform Addition
set R2  *a     ; Update the value of a pointer
; Similarly for b, note that x is loaded twice,
; because x may point to a (a aliased by x) thus 
; the value of x will change when the value of a
; changes.
load R1  *x
load R2  *b
add R2 += R1
set R2  *b

С ограничением:

void fr(int *restrict a, int *restrict b, int *restrict x);

Псевдо сборка:

load R1  *x
load R2  *a
add R2 += R1
set R2  *a
; Note that x is not reloaded,
; because the compiler knows it is unchanged
; "load R1 ← *x" is no longer needed.
load R2  *b
add R2 += R1
set R2  *b

GCC действительно делает это?

GCC 4.8 Linux x86-64:

gcc -g -std=c99 -O0 -c main.c
objdump -S main.o

С участием -O0 они одинаковы.

С -O3:

void f(int *a, int *b, int *x) {
    *a += *x;
   0:   8b 02                   mov    (%rdx),%eax
   2:   01 07                   add    %eax,(%rdi)
    *b += *x;
   4:   8b 02                   mov    (%rdx),%eax
   6:   01 06                   add    %eax,(%rsi)  

void fr(int *restrict a, int *restrict b, int *restrict x) {
    *a += *x;
  10:   8b 02                   mov    (%rdx),%eax
  12:   01 07                   add    %eax,(%rdi)
    *b += *x;
  14:   01 06                   add    %eax,(%rsi) 

Для непосвященных соглашение о вызовах :

  • rdi = первый параметр
  • rsi = второй параметр
  • rdx = третий параметр

Вывод GCC был даже более ясным, чем статья в вики: 4 инструкции против 3 инструкций.

Массивы

Пока у нас есть единственная экономия команд, но если указатель представляет массивы, которые должны быть зациклены, это обычный случай использования, тогда может быть сохранен набор команд, как упомянуто суперкатом .

Рассмотрим для примера:

void f(char *restrict p1, char *restrict p2) {
    for (int i = 0; i < 50; i++) {
        p1[i] = 4;
        p2[i] = 9;
    }
}

Из-за restrictэтого умный компилятор (или человек) может оптимизировать это так:

memset(p1, 4, 50);
memset(p2, 9, 50);

который потенциально гораздо более эффективен, так как может быть оптимизирован для сборки при достойной реализации libc (например, glibc): лучше ли использовать std :: memcpy () или std :: copy () с точки зрения производительности?

GCC действительно делает это?

GCC 5.2.1. Linux x86-64 Ubuntu 15.10:

gcc -g -std=c99 -O0 -c main.c
objdump -dr main.o

С участием -O0 , оба одинаковы.

С -O3:

  • с ограничением:

    3f0:   48 85 d2                test   %rdx,%rdx
    3f3:   74 33                   je     428 <fr+0x38>
    3f5:   55                      push   %rbp
    3f6:   53                      push   %rbx
    3f7:   48 89 f5                mov    %rsi,%rbp
    3fa:   be 04 00 00 00          mov    $0x4,%esi
    3ff:   48 89 d3                mov    %rdx,%rbx
    402:   48 83 ec 08             sub    $0x8,%rsp
    406:   e8 00 00 00 00          callq  40b <fr+0x1b>
                            407: R_X86_64_PC32      memset-0x4
    40b:   48 83 c4 08             add    $0x8,%rsp
    40f:   48 89 da                mov    %rbx,%rdx
    412:   48 89 ef                mov    %rbp,%rdi
    415:   5b                      pop    %rbx
    416:   5d                      pop    %rbp
    417:   be 09 00 00 00          mov    $0x9,%esi
    41c:   e9 00 00 00 00          jmpq   421 <fr+0x31>
                            41d: R_X86_64_PC32      memset-0x4
    421:   0f 1f 80 00 00 00 00    nopl   0x0(%rax)
    428:   f3 c3                   repz retq

    Два memsetзвонка, как и ожидалось.

  • без ограничений: никаких вызовов stdlib, просто развертывание цикла в 16 итераций, которое я не собираюсь воспроизводить здесь :-)

У меня не хватило терпения их тестировать, но я считаю, что ограниченная версия будет быстрее.

C99

Давайте посмотрим на стандарт для полноты.

restrictговорит, что два указателя не могут указывать на перекрывающиеся области памяти. Наиболее распространенное использование для аргументов функции.

Это ограничивает способ вызова функции, но позволяет оптимизировать время компиляции.

Если вызывающая сторона не выполняет restrictдоговор, неопределенное поведение.

Проект C99 N1256 6.7.3 / 7 « Классификаторы типов» гласит:

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

и 6.7.3.1 «Формальное определение ограничения» дает кровные детали.

Строгое правило алиасинга

restrictКлючевое слово влияет только указатели совместимых типов (например , два int*) , поскольку строгие правила наложения спектров говорят , что сглаживание несовместимых типов не определенно поведение по умолчанию, и поэтому компиляторы могут предположить , что это не произойдет и оптимизирует прочь.

Смотрите: что такое строгое правило наложения имен?

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

Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
источник
9
Определитель «restrict» может реально позволить значительно большую экономию. Например, учитывая void zap(char *restrict p1, char *restrict p2) { for (int i=0; i<50; i++) { p1[i] = 4; p2[i] = 9; } }, что ограничивающие квалификаторы позволят компилятору переписать код как «memset (p1,4,50); memset (p2,9,50);». Restrict значительно превосходит псевдонимы на основе типов; Обидно, компиляторы больше ориентируются на последнее.
Суперкат
@supercat отличный пример, добавлен в ответ.
Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
2
@ tim18: Ключевое слово "restrict" может включить много оптимизаций, которые не может даже агрессивная оптимизация на основе типов. Кроме того, существование «restrict» в языке - в отличие от агрессивного псевдонима на основе типов - никогда не делает невозможным выполнение задач настолько эффективно, насколько это возможно при их отсутствии (поскольку код, который будет нарушен «restrict», может просто не используйте его, в то время как код, который нарушается агрессивным TBAA, должен часто переписываться менее эффективным способом).
суперкат
2
@ tim18: окружающие вещи, содержащие двойные подчеркивания в чертах, как в __restrict. В противном случае двойные подчеркивания могут быть неверно истолкованы как указание на то, что вы кричите.
суперкат
1
Более важно, чем не кричать, что подчеркивание имеет значение, непосредственно относящееся к тому, что вы пытаетесь подчеркнуть.
рециклы