Означает ли это, что два или более указателя, переданных функции, не перекрываются?
Что еще это значит?
Ответ 1
В своей статье "Оптимизация памяти", Christer Ericson говорит, что пока restrict еще не является частью стандарта С++, он поддерживается многими компиляторами, и он рекомендует использовать его при наличии:
ограничить ключевое слово
! Новый стандарт ANSI/ISO C 1999 года
! Совсем не в стандарте С++, но поддерживается многими компиляторами С++
! Только подсказка, поэтому ничего не может поделать и по-прежнему соответствовать
Указатель с ограничениями (или ссылка)...
!... в основном пообещать компилятору, что для область действия указателя, цель указателя будет только доступ через этот указатель (и указатели скопированы от него).
В компиляторах С++, которые его поддерживают, он должен, вероятно, вести себя так же, как в C.
Подробнее см. в этом сообщении SO: Реалистичное использование ключевого слова C99 для ограничения?
Возьмите полчаса, чтобы пропустить через Эриксон бумагу, это интересно и стоит времени.
Edit
Я также обнаружил, что IBM AIX C/С++ компилятор поддерживает ключевое слово __restrict__.
g++ также, похоже, поддерживает это, поскольку следующая программа компилируется на g++:
#include <stdio.h>
int foo(int * __restrict__ a, int * __restrict__ b) {
return *a + *b;
}
int main(void) {
int a = 1, b = 1, c;
c = foo(&a, &b);
printf("c == %d\n", c);
return 0;
}
Я также нашел хорошую статью об использовании restrict:
Демистификация ограничивающего ключевого слова
Edit2
Я просмотрел статью, в которой конкретно обсуждается использование ограничений в программах на С++:
Load-hit-stores и ключевое слово __restrict
Кроме того, Microsoft Visual С++ также поддерживает ключевое слово __restrict.
Ответ 2
Как и другие сказали, если ничего не значит, как в С++ 14, так что давайте рассмотрим __restrict__ расширение GCC, который делает то же самое, как C99 restrict.
C99
restrict говорит, что два указателя не могут указывать на перекрывающиеся области памяти. Наиболее распространенное использование для аргументов функции.
Это ограничивает возможность вызова функции, но позволяет оптимизировать компиляцию.
Если вызывающий абонент не выполняет restrict контракт, неопределенное поведение.
Проект C99 N1256 6.7.3/7 "Типовые квалификаторы" говорит:
Предполагаемое использование ограничителя (например, класс хранения регистров) заключается в продвижении оптимизации, а удаление всех экземпляров квалификатора из всех блоков перевода, составляющих соответствующую программу, не меняет своего значения (т.е. Наблюдаемого поведения).
и 6.7.3.1 "Формальное определение ограничения" дает подробные сведения.
Возможная оптимизация
Пример Википедии очень освещается.
Он ясно показывает, как это позволяет сохранить одну инструкцию сборки.
Без ограничений:
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 a may be equal to x.
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
load R2 ← *b
add R2 += R1
set R2 → *b
Действительно ли GCC это делает?
g++ 4.8 Linux x86-64:
g++ -g -std=gnu++98 -O0 -c main.cpp
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 был еще более ясным, чем статья wiki: 4 инструкции и 3 инструкции.
Массивы
До сих пор у нас есть одна экономия на инструкциях, но если указатель представляет собой массивы, которые должны быть зациклированы, общий прецедент, тогда куча инструкций может быть сохранена, как упомянуто supercat и michael.
Рассмотрим, например:
void f(char *restrict p1, char *restrict p2, size_t size) {
for (size_t i = 0; i < size; i++) {
p1[i] = 4;
p2[i] = 9;
}
}
Из-за restrict интеллектуальный компилятор (или человек) мог бы оптимизировать это:
memset(p1, 4, size);
memset(p2, 9, size);
Что потенциально намного более эффективно, так как это может быть сборка оптимизирована на достойной реализации libc (например, glibc). Лучше ли использовать std :: memcpy() или std :: copy() в терминах производительности? , возможно с инструкциями SIMD.
Без, ограничить, эта оптимизация не может быть выполнена, например, рассмотрим:
char p1[4];
char *p2 = &p1[1];
f(p1, p2, 3);
Затем for версии:
p1 == {4, 4, 4, 9}
в то время как версия memset делает:
p1 == {4, 9, 9, 9}
Действительно ли 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, только разворачивание цикла с шестью итерациями, которое я не собираюсь воспроизводить здесь :-)
У меня не было терпения сравнивать их, но я считаю, что ограниченная версия будет быстрее.
Строгое правило сглаживания
Ключевое слово restrict влияет только на указатели совместимых типов (например, на два int*), потому что правила строгих правил псевдонимов говорят о том, что по умолчанию несовместимые типы псевдонимов являются неопределенным поведением, поэтому компиляторы могут предположить, что этого не происходит и не оптимизируется.
См.: Что такое строгое правило псевдонимов?
Он работает для ссылок?
Согласно документам GCC он делает: https://gcc.gnu.org/onlinedocs/gcc-5.1.0/gcc/Restricted-Pointers.html с синтаксисом:
int &__restrict__ rref
Существует даже версия для this функции-члена:
void T::fn () __restrict__
