Как писать на Си?

попробуй плз переписать так, чтобы минимизировать дифф

double t = 0.0

Например, это может играть роль, если компилятор не смог вывести возможность создания временной переменной.

на С как и на любом языке надо писать понятно :-) иначе код будет работать быстро, но недолго. Через полгода вам самому надо будет напрячься чтобы вспомнить что и почему, через год код становится мусором.

и в С категорически запрещено изобретать велосипеды. Матричные операции как-раз велотранспорт.

где почитать о том как писать код для наиболее эффективной оптимизации компилятором

Начни с очевидного https://en.wikipedia.org/wiki/Loop_optimization Статьи интересны не только сами по себе, но и списком литературы в ссылках.

 double *const *a, double *const *b 

Вся фишка может крыться в спецификаторах const. Уже не помню как, но есть особая магия в С, как указать компилятору, что данные в массивах константны, тогда он включает агрессивную политику кэширования данных из этих массивов, что сильно ускоряет операции с матрицами и векторами.

*(A + N * i + j)

Че за жуть то?

почему?

https://godbolt.org/z/Cvbn5O

Попробуйте, достаточно ли будет такого изменения:

+			double s = 0.0;
 			for (k = 0; k < N; ++k)
-				*C += *a++ * *t++;
+				s += *a++ * *t++;
-			++C;
+			*C++ = s;

*(A + N * i + j)

Че за жуть то?

Всего лишь A[N * i + j].

Ну вот так красивей же. Нужна ли эта обфускация с указателями?) Тем более с помощью C11 можно сделать адекватные матрицы.

Почитать про устройство современных вычислительных устройств. Я не удивлюсь, если рефернесный алгоритм ещё и на gpu ложится лучше, чем твой и прирост там будет не в разы а в разницу в количестве ядер / 2.

Ключевые слова: векторизация, simd, avx, чё там в видеокарточках - х3.

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

Ты и БПФ свое пишешь? Почему не хочешь GSL или BLAS использовать?

xaizek, bormant

Действительно с дополнительной переменной всё сильно ускорилось.

MKuznetsov, pon4ik, Eddy_Em

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

Никто в своем уме не будет на [censored] ржавчине делать математику!

Пук

Ну вот так красивей же. Нужна ли эта обфускация с указателями?)

Тут — нужно. Ибо тут специально указано, что мы обращаемся не к элементу в строке/столбце как [][], а к конкретному элементу в непрерывной памяти с одноуровневым указателем. А в транспонированной ещё и не будет запутывать за счёт смены i<->j.

Вроде многомерными массивами почти никто не пользуется всё равно. И чем это за «указано» лучше обычного [].

Вроде многомерными массивами почти никто не пользуется всё равно.

В смысле? Когда размеры константны, то многомерные скобочки - синтаксический сахар, ничем не замедляющий работу. А как только появляется необходимость чего-то прямоугольно-многомерного с неизвестными размерами предварительно, то код ТСа с malloc+calloc и работы потом с [][] как массив указателей - применяется везде и всюду.

Изучи AVX2/AVX-512 и ускоришь свой код раз в 8

-ffast-math

Код не смотрел, но это позволяет исполнять циклы с флоатами как SIMD операции.

Речь про одномерные скобочки.
А про многомерные (2-х в данном случае) — это ваша фантазия только.

*(A + N * i + j)
A[N * i + j]
(N * i + j)[A]
— все эти три варианта компилятору тождественны.

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

Так можно и на ассемблере написать, только смысла большого нет.

Речь про одномерные скобочки.
А про многомерные (2-х в данном случае) — это ваша фантазия только.

Типичный ЛОР. Не вчитываясь, броситься хамить и учить. Это ничего, что я именно ваш ответ поддержал, отвечая не вам собственно?

Двумерные скобочки тут пляшут от задачи - двумерной матрицы, но при ручной динамической реализации как одномерного указателя комилятор тут в принципе не даст ими воспользоваться.. Потому при таких тождественных записей, запись *(A + N * i + j) наиболее предпочтительная, так как другие снижают самодокументируемость, так как делают ложный намёк на одномерность.

Никаких ложных намеков, если только ничего не домысливать к синтаксису Си. Все три варианта в выражении тождественны. Или у вас есть пример либо ссылка на стандарт, когда компилятор может по разному их понимать? А все остальное — личные предпочтения суть вкусовщина.

Это ничего, что я именно ваш ответ поддержал, отвечая не вам собственно?

Ничего.

Или у вас есть пример

Есть. Вон идёте в самый верх, открываете код ТСа, и видите реализацию двумерной матрицы как массива указателей. Код рабочий, но медленней и в данном случае не нужный, так как тормоза на ровном месте.

когда компилятор может по разному их понимать?

Мозг при чтении включить слабо, перед тем как хамить? Какое слово вам непонятно во фразе: «при таких тождественных записей, запись *(A + N * i + j) наиболее предпочтительная»? Где тут написано о том, что компилятор тут сделает разное?

открываете код ТСа, и видите реализацию двумерной матрицы как массива указателей

В коде ТСа такой реализации нет. Такая реализация есть в коде третьей стороны, с которой ТС сравнивает свою реализацию, в которой выделяет память единым куском.
В реализации 3 стороны транспонирование дает выиигрыш в том числе за счет устранения лишней косвенной адресации при проходе по столбцам. А вот ТС мог бы попробовать ходить по столбцам при помощи i+=N, которое до определенных пределов N оставалось бы столь же быстрым, как и ++i для транспонированной матрицы.

Какое слово вам непонятно во фразе: «при таких тождественных записей, запись *(A + N * i + j) наиболее предпочтительная»?

«наиболее предпочтительная»
Если, конечно, речь не идет об исключительно личных предпочтениях.

Мозг при чтении включить слабо

Извините, не имею ни возможности, ни желания включать либо выключать ваш мозг, как-нибудь сами пожалуйста.

Такая реализация есть в коде третьей стороны,

Да. Это и имелось в виду, что код представленный для примера ТСом.

Если, конечно, речь не идет об исключительно личных предпочтениях.

Напоминаю, что был вопрос, почему автор выбрал запись *(A+offset), а не A[offset]. Я уже три раза, как об стенку горох, пытался донести, непонятно почему именно вам, что первая запись при реализации через одномерную непрерывную память при тождественном конечном результате предпочтительнее, так как это самодокументируемость кода, указывающая на особенность реализации. Так как вторая предпочтительна для самодокументируемоcти при работе с одномерным массивом (строкой при двумерных входных данных). При чём тут личные предпочтения?!

Извините,

Вот и следите за собой.

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

Автор один, а вас много.

Владимир

Не мой пост.

Владимир

Вы кто такие? Я вас не звал!

Владимир

в числодробилках на современном си обычно оптимизирут кешмиссы

Ты опять, всё-таки, выходишь на связь, подлец?

Владимир

И почему же? Потому что Эдичка так считает, более вменяемого аргумента не ждать?

-ffast-math на расте не работает прост.

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

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

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

вопрос «ЗАЧЕМ?» можно задавать почти на каждый первый топик форума. С гарантией что автор не знает ответа :-)

Но на C её тоже писать больно. Приятно делать её на C#, Python и чём-то более высокоуровневые, ну или взять старый Фортран, в котором всё уже есть давным-давно.

Да нормально все на С, если правильные библиотеки использовать!

Си-диез — некошерная ванузоидность, на ней люди ничего не пишут. А пхытон — это ж вообще для наркоманов!!!

и в С категорически запрещено изобретать велосипеды.

На русском языке тоже не рекомендуется писать глупости, но кое-кого это не останавливает. Ты действительно не понимаешь зачем человек возится с матрицами на Си?

Поправил. Без транспонирования медленно. Но удалось убрать неочивидную переменную благодаря restrict. Получилось даже в 2 раза быстрее, чем в варианте, с которым сравнивал. Нужные оптимизации активируются при включении флагов -O3 и -ffast-math.

Спасибо всем за ответы.

+

а также зачем используют вместо CPU не только многоGPU, но еще и вместо Си вставки машинного кода для СPU и GPU …

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

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

Вот жесть то... Читать такое без подготовки очень неприятно.

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

Поправил

Полагаю, ошибочка закралась:

-				*(C + N*i + j) += *(A + N*i + k) * *(T + N*i + k);
+				*(C + N*i + j) += *(A + N*i + k) * *(T + N*j + k);

+				C[N*i + j] = A[N*i + k] * T[N*j + k];

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

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

При чём тут личные предпочтения?!

Стандарт языка Си говорит нам

6.5.2.1 Array subscripting
Constraints
1 One of the expressions shall have type “pointer to complete object type”, the other expression shall
have integer type, and the result has type “type”.
Semantics
2 A postfix expression followed by an expression in square brackets [] is a subscripted designation of
an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical
to (*((E1)+(E2))). Because of the conversion rules that apply to the binary+ operator, if E1 is an
array object (equivalently, a pointer to the initial element of an array object) and E2 is an integer,
E1[E2] designates the E2 -th element of E1 (counting from zero).

E1[E2] is identical to (*((E1)+(E2)))

Идентичны они, так говорит нам стандарт.

Именно поэтому выбор одной (краткой) или другой (длинной) записи является только и исключительно предметом личных предпочтений.

Надеюсь, мне на этот раз удалось донести мысль?


PS. Доводы про упоминание array object тут не работают, ибо а) случай с указателем упомянут явно, б) для арифметики указателей применяются те же самые ограничения, иначе UB ;)

Ведь транспонирование специально выполняется для того чтобы по колонкам не бегать.

Без транспонирования вы умножали i-ю строку A на j-й столбец B.
После транспонирования (замены j-го столбца B j-й строкой T) нужно умножать i-ю строку A на j-ю строку T.
Разве нет?

Без транспонирования было бы:

-				*(C + N*i + j) += *(A + N*i + k) * *(T + N*i + k);
+				*(C + N*i + j) += *(A + N*i + k) * *(T + N*k + j);
// или
+				C[N*i + j] = A[N*i + k] * T[N*k + j];