Хитрые, необычные алгоритмы и код

[safocl]

https://godbolt.org/z/7zdGn5hqT -- сделал еще два варианта -- VAR_V в 3 и 4 думаю достойны...

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

[Adrift]

safocl, на мк тестировали, почему бы не потестить на ПК )

Спойлер

Код: Выделить всё

#include <algorithm>
#include <print>
#include <chrono>
#include <array>
using namespace std::chrono;

int median5_adrift(const int* arr)
{
	int a = arr[0], b = arr[1], c = arr[2], d = arr[3], e = arr[4];

	if (a > b) std::swap(a, b);
	if (b > c) std::swap(b, c);
	if (c > d) std::swap(c, d);
	if (a > b) std::swap(a, b);
	if (b > c) std::swap(b, c);
	if (c > e) std::swap(c, e);
	if (a > b) std::swap(a, b);
	return (b > c) ? b : c;
}

int median5_adrift2(int* arr)
{
	if (arr[0] > arr[1]) std::swap(arr[0], arr[1]);
	if (arr[1] > arr[2]) std::swap(arr[1], arr[2]);
	if (arr[2] > arr[3]) std::swap(arr[2], arr[3]);
	if (arr[0] > arr[1]) std::swap(arr[0], arr[1]);
	if (arr[1] > arr[2]) std::swap(arr[1], arr[2]);
	if (arr[2] > arr[4]) std::swap(arr[2], arr[4]);
	if (arr[0] > arr[1]) std::swap(arr[0], arr[1]);
	return (arr[1] > arr[2]) ? arr[1] : arr[2];
}

int median5_safocl(std::array<int, 5> values)
{
	std::ranges::nth_element(values, values.begin() + 2);
	return values[2];
}

int median5_safocl2(std::array<int, 5>& values)
{
	std::ranges::nth_element(values, values.begin() + 2);
	return values[2];
}

std::array arr{ 30, 10, 50, 70, 20 };

int main()
{
	auto time = steady_clock::now();

    for (int i = 0; i < 100'000'000; i++)
    {
		volatile auto v = median5_adrift(arr.data()); // 0.24s
		//volatile auto v = median5_adrift2(arr.data()); // 0.19s
		//volatile auto v = median5_safocl(arr); // 0.38s
		//volatile auto v = median5_safocl2(arr); // 0.25s
    }

	auto elapsedTime = duration_cast<duration<double>>(steady_clock::now() - time).count();
	std::println("{}", elapsedTime);
}

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

[safocl]

а ты прими извне данные -- а не из известных наперед (в компайл тайме) значений памяти...

Добавлено after 1 minute 14 seconds:
Adrift, ты даже заблуждаешься что ты ничего не меняешь -- при этом свапая все значения)))

[Adrift]

[uquote="safocl",url="/forum/viewtopic.php?p=4656821#p4656821"]а ты прими извне данные -- а не из известных наперед (в компайл тайме) значений памяти...[/uquote]
Пожалуйста, добавляем в загрузку volatile:

Код: Выделить всё

int a = (volatile int&)arr[0], b = (volatile int&)arr[1], c = (volatile int&)arr[2], d = (volatile int&)arr[3], e = (volatile int&)arr[4];

Было 0.24s, стало 0.26s, по-прежнему быстрее, чем 0.38s ) На самом деле для STM32H5 и gcc я так и делал, иначе компилятор мою функцию сворачивал до константы.

Adrift, ты даже заблуждаешься что ты ничего не меняешь -- при этом свапая все значения)))

Я своплю значения регистров. Второй вариант действительно свопит в памяти, но он там для сравнения, ведь тебе я тоже добавил функцию передающую array по ссылке, что можно считать заменой передачей со span, которую ты назвал достойным вариантом )

[safocl]

[uquote="Adrift",url="/forum/viewtopic.php?p=4656855#p4656855"]Я своплю значения регистров.[/uquote]
каких регистров? кто тебе про такое гарантировал бы? и чем по твоему массив на стеке отличается от такого же количества простых переменных на стеке?

[Adrift]

[uquote="safocl",url="/forum/viewtopic.php?p=4656856#p4656856"]каких регистров? кто тебе про такое гарантировал бы?[/uquote]
Переменных, в смысле ) А в переменных хранятся копии значений из массива, это я специально для тебя уточняю )

и чем по твоему массив на стеке отличается от такого же количества простых переменных на стеке?

Почему бы просто не признать, что не прав и мой вариант работает быстрее? )

[safocl]

[uquote="Adrift",url="/forum/viewtopic.php?p=4656860#p4656860"]Переменных, в смысле ) А в переменных хранятся копии значений из массива, это я специально для тебя уточняю )[/uquote]
а переменные то где хранятся? и почему у них должно это как то отличаться от массива?

[Adrift]

[uquote="safocl",url="/forum/viewtopic.php?p=4656870#p4656870"]а переменные то где хранятся? и почему у них должно это как то отличаться от массива?[/uquote]
Все ясно, очередной ПростоНуб который будет грузить меня демагогией и до последнего отстаивать свои очевидно ошибочные убеждения. Не интересно )

[safocl]

так ты же сам даже не понимаешь где хранятся данные "переменных" ))

[ПростоНуб]

Массив передается в функцию по указателю, поэтому просто обязан быть в памяти. А локальным переменным функции ничто не мешает быть регистровыми, что и использует компилятор.
Вполне здравая и эффективная идея Adrift заключается в том, что компилятор видит, что из переставляемых значений используется в итоге лишь одно, да и то возвращается в регистре, как результат функции. Поэтому реальную перестановку ему даже не обязательно производить.
Другой вопрос, что при наличии SIMD инструкций, перестановки ими не оптимизируются. Но в связи с тем, Adrift отказывается мыслить шире, чем в рамках используемой им сейчас архитектуры, обсуждение этого ранее зашло в тупик.

Добавлено after 2 minutes 45 seconds:
[uquote="Adrift",url="/forum/viewtopic.php?p=4656872#p4656872"]ПростоНуб который будет грузить меня демагогией и до последнего отстаивать свои очевидно ошибочные убеждения. Не интересно )[/uquote]
Вообще-то, ключевое слово "очевидно", делает процитированную фразу уже образцом демагогии )))
https://ru.wikipedia.org/wiki/%D0%94%D0 ... 1%82%D1%8C

[Adrift]

ПростоНуб, тут как раз в CubeMX добавили STM32N6, который выйдет в следующем году и будет иметь нормальный SIMD, так вот самый мелкий корпус там vfbga142 - это к вопросу об их массовом использовании в эмбедде )

[safocl]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656881#p4656881"]Массив передается в функцию по указателю, поэтому просто обязан быть в памяти.[/uquote]
можно указть на мой код, где массив по указателю передается?

Добавлено after 1 minute 50 seconds:
[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656881#p4656881"]А локальным переменным функции ничто не мешает быть регистровыми, что и использует компилятор.[/uquote]
а чем мой std::array не локальный? он же стековый и вполне себе может оказать напрямую на регистрах -- кто запрещает компилятору так сделать?

[ПростоНуб]

[uquote="Adrift",url="/forum/viewtopic.php?p=4656889#p4656889"]ПростоНуб, тут как раз в CubeMX добавили STM32N6, который выйдет в следующем году и будет иметь нормальный SIMD, так вот самый мелкий корпус там vfbga142 - это к вопросу об их массовом использовании в эмбедде )[/uquote]
Для Вас embedded system заканчивается на STM32, а у моего клиента на заводе есть embedded system даже на Epyc. У многих дома - на одноплатниках под Linux и HA. Впрочем даже у Вас наверняка есть embeded ARM с SIMD в смартфоне.
Почитайте внимательней, что не для Вас, а для большинства, считается embedded system: https://en.wikipedia.org/wiki/Embedded_system

Добавлено after 12 minutes:
[uquote="safocl",url="/forum/viewtopic.php?p=4656894#p4656894"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656881#p4656881"]Массив передается в функцию по указателю, поэтому просто обязан быть в памяти.[/uquote]
можно указть на мой код, где массив по указателю передается?[/uquote]
Сами же ответили:

[uquote="safocl",url="/forum/viewtopic.php?p=4656894#p4656894"]std::array[/uquote]
Если при компиляции целиком это и может быть заинлайнено или как-то оптимизировано, то в случае библиотечной функции, С++ ABI не позволяет передать массив, иначе, чем по указателю.
Впрочем меня опять тут начнут укорять, что я методологии профессиональной разработки пытаюсь применять к пет-проектам, где никто изоляцией кода между модулями проекта не заморачивается, так как разработчик всегда один и только один.

[safocl]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656905#p4656905"]Сами же ответили:[/uquote]
да в общем то нет -- не ответил -- с чего взято, что std::array это какая то нестековая память и что он не является POD типом и агрегатом?

[Adrift]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656905#p4656905"]Для Вас embedded system заканчивается на STM32, а у моего клиента на заводе есть embedded system даже на Epyc. У многих дома - на одноплатниках под Linux и HA. Впрочем даже у Вас наверняка есть embeded ARM с SIMD в смартфоне.[/uquote]
Здорово, только это раздел микроконтроллеров и ПЛИС, не одноплатников, соответственно понятие embedded тут уточненное ) Вы же прекрасно понимаете, что шла бы речь про Epic и одноплатники на Linux никто бы к вашему SIMD не цеплялся, но речь про микроконтроллеры где этот SIMD присутствует в виде очень редкого исключения. С другой стороны важно ведь не само наличие SIMD, а его влияние на производительность, правильно? Например, STM32H7 на 550MHz, выполняющие 2 инструкции за такт, даже без нормального SIMD должны быть существенно быстрее вашего Xtensa с SIMD. И что прикажете делать? Какой из этих двух мк устарел? )

[ПростоНуб]

[uquote="safocl",url="/forum/viewtopic.php?p=4656936#p4656936"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656905#p4656905"]Сами же ответили:[/uquote]
да в общем то нет -- не ответил -- с чего взято, что std::array это какая то нестековая память и что он не является POD типом и агрегатом?[/uquote]
Какая разница, стековая или не стековая? В данном случае, раз T POD и никаких собственных конструктора, операторов или деструктора добавлено не было, это как раз POD тип. С точки зрения С++ ABI, POD массив передается всегда, как указатель.
Если очень интересно, можете погрузиться в спецификацию Itanium C++ ABI.

[safocl]

[uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656946#p4656946"]С точки зрения С++ ABI, POD массив передается всегда, как указатель.[/uquote]
непонятно откуда такая инфа -- возможно ты путаешь аргумент в виде (int arr[]) -- но std::array в аргументе не превращается в такое -- но в первом случае просто правило языка C++ действует, которое делает decoy int[] к int* в аргументе функций -- тут ничего общего с моим случаем.

[ПростоНуб]

[uquote="Adrift",url="/forum/viewtopic.php?p=4656943#p4656943"]Здорово, только это раздел микроконтроллеров и ПЛИС, не одноплатников, соответственно понятие embedded тут уточненное[/uquote]
Я же уже писал, хотите себя ограничивать и для каждой архитектуры, для которой ведете разработку, переписывать библиотечные функции заново - Ваши проблемы.
Я имею все основания утверждать, что в профессиональной разработке предпочитительно иметь, по возможности, один и тот же код для всех платформ. Но доказывать Вам выгоды такого решения уже утомился. Так что делайте как хотите. Мне от этого хуже не будет )

[uquote="Adrift",url="/forum/viewtopic.php?p=4656943#p4656943"]Например, STM32H7 на 550MHz, выполняющие 2 инструкции за такт, даже без нормального SIMD должны быть существенно быстрее вашего Xtensa с SIMD. И что прикажете делать?[/uquote]
Могу посмеяться над голословным утверждением. Без данных тестирования, которое можно повторить и проверить, говорить об этом смысла не имеет. Возможны любые результаты. Например, в том же ffmpeg переход на SSSE3 дал прирост производительности некоторых функций в 40 раз, а на AVX-512 - в 94 раза. Так что имея почти двукратный выигрыш в CoreMark, STM32H7 вполне может проиграть.

[safocl]

причина более худшего в тестировании с std::array моем варианте скорости сокрыта не в нем, а как оказалось в почему то грустно работающем std::sort и nth_element -- они обязаны за O(n) и O(n*log(n)) работать соответственно применяя компаратор, но почему то получается в этих реализациях бибилиотек c++ дополнительные накладные расходы предоставляют...

[ПростоНуб]

[uquote="safocl",url="/forum/viewtopic.php?p=4656950#p4656950"][uquote="ПростоНуб",url="/forum/viewtopic.php?p=4656946#p4656946"]С точки зрения С++ ABI, POD массив передается всегда, как указатель.[/uquote]
непонятно откуда такая инфа[/uquote]
Например, отсюда https://stackoverflow.com/questions/367 ... f-t-is-pod