Какова семантика ограничения C99 в отношении указателей к указателям?

Question

Я много занимаюсь матричной арифметикой и хотел бы воспользоваться restrict указателем C99.

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

int **A = malloc (ncols * sizeof(int *));
A[0] = malloc (nrows * ncols * sizof(int));
for (int i=1; i < ncols; i++) {
    A[i] = A[0] + i*nrows;
}

Теперь для функции умножения матриц

void mmultiply ( int nrows, int ncols, int **Out, int **A, int **B);

Должен ли я квалифицировать оба указателя аргументов как ограниченные? Это правильный синтаксис, но мне трудно определить, ведет себя ли int *restrict *restrict иначе, чем int **restrict.

Тогда при правильно ограниченных указателях доступ к элементам через A[0][col*nrows + row] не определен? (т.е. будет ли компилятор считать, что я только обращаюсь к матрице через A[col][row] для значений row, таких что row < nrow)? Или я должен просто оставаться последовательным?

Answer 1

Для первого вопроса «да» это будет означать что-то другое, если вы будете использовать оба спецификатора restrict, в частности, что указатели также не будут псевдонимами. Относительно того, имеет ли это какое-то значение: теоретически да, на практике это зависит от оптимизатора.

Для второго вопроса "да" будет предполагаться, что к чему-либо доступному через указатель строки можно получить доступ только через указатель строки.

Вы можете добавить туда const.

Наконец, если это gcc для -O2, -O3 или -Os, компилятор уже выполняет анализ псевдонимов на основе типов. Я уверен, что другие компиляторы делают это тоже. Это означает, что ограничение указателей по отношению к целым уже понятно, оставляя только массивы, которые могли бы хранить друг друга.

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

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

Answer 2

int **restrict только утверждает, что память, адресуемая Out, A и B, не перекрывается (за исключением того, что A и B могут перекрываться, если ваша функция не изменяет ни одну из них). Это означает массивы указателей. Он ничего не говорит о содержимом памяти, на которое указывают Out, A и B. Сноска 117 в n1124 гласит:

если идентификатор p имеет тип (int ** ограничение), тогда выражения указателя p и p + 1 основаны на обозначенный объект ограниченного указателя по р, но указатель выражений * р и p [1] не являются.

По аналогии с const, я подозреваю, что квалификация с restrict дважды будет утверждать, что вы хотите, то есть, что ни одно из значений в массиве не указывает на перекрывающуюся память. Но, читая стандарт, я не могу доказать себе, что это действительно так. Я считаю, что «Пусть D будет объявлением обычного идентификатора, который обеспечивает средство обозначения объекта P как ограниченного указателем типа T», действительно означает, что для int *restrict *restrict A, тогда A [0] и A [1 ] - объекты, обозначенные как ограниченный указателем на int. Но это довольно тяжелый легальный.

Я понятия не имею, будет ли ваш компилятор что-нибудь делать с этими знаниями, заметьте. Ясно, что это возможно, вопрос в том, реализовано ли это.

Так что я действительно не знаю, что вы получили по сравнению с обычным C 2-D массивом, где вы просто выделяете rows * cols * sizeof(int) и индексируете с помощью A[cols*row + col]. Тогда вам явно нужно только одно использование restrict, и любой компилятор, который делает что-либо с restrict, сможет переупорядочивать операции чтения из A и B через записи в Out. Без restrict, конечно, это не может, поэтому, делая то, что вы делаете, вы полагаетесь на милость вашего компилятора. Если он не может справиться с двойным ограничением, только с одним ограниченным случаем, то ваше двойное косвенное обращение обойдется вам в оптимизации.

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

имеет доступ к элементам через A [0] [col * nrows + row] undefined?

Да, если элемент изменен одним из обращений, потому что это делает A [0] псевдонимом для памяти, к которой также осуществляется доступ через A [col]. Это было бы хорошо, если бы только A и B были указателями с ограниченным ограничением, но не если A [0] и A [col].

Я предполагаю, что вы не модифицируете A в этой функции, так что на самом деле псевдоним в порядке. Если бы вы сделали то же самое с Out, поведение было бы неопределенным.

Answer 3

Внешнее (второе) ограничение сообщает компилятору, что ни один из массивов псевдонимов указателей (A, B и out). Внутреннее (первое) ограничение сообщает компилятору, что ни один из псевдонимов массивов целых (на которые указывают элементы массивов указателей).

Если вы обращаетесь к A [0] [col * nrows + row] и A [col] [row], то вы нарушаете внутреннее ограничение, поэтому все может сломаться.