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

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

safocl писал(а):

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

Пожалуйста, добавляем в загрузку 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 я так и делал, иначе компилятор мою функцию сворачивал до константы.

safocl писал(а):

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

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

Реклама

Эиком - электронные компоненты и радиодетали

safocl

Adrift писал(а):

Я своплю значения регистров.

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

Реклама

Adrift

safocl писал(а):

каких регистров? кто тебе про такое гарантировал бы?

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

safocl писал(а):

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

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

Реклама

safocl

Adrift писал(а):

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

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

Adrift

safocl писал(а):

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

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

safocl

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

Реклама

ПростоНуб

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

Добавлено after 2 minutes 45 seconds:

Adrift писал(а):

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

Вообще-то, ключевое слово "очевидно", делает процитированную фразу уже образцом демагогии )))
https://ru.wikipedia.org/wiki/%D0%94%D0 ... 1%82%D1%8C

Adrift

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

safocl

ПростоНуб писал(а):

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

можно указть на мой код, где массив по указателю передается?

Добавлено after 1 minute 50 seconds:

ПростоНуб писал(а):

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

а чем мой std::array не локальный? он же стековый и вполне себе может оказать напрямую на регистрах -- кто запрещает компилятору так сделать?

ПростоНуб

Adrift писал(а):

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

Для Вас embedded system заканчивается на STM32, а у моего клиента на заводе есть embedded system даже на Epyc. У многих дома - на одноплатниках под Linux и HA. Впрочем даже у Вас наверняка есть embeded ARM с SIMD в смартфоне.
Почитайте внимательней, что не для Вас, а для большинства, считается embedded system: https://en.wikipedia.org/wiki/Embedded_system

Добавлено after 12 minutes:

safocl писал(а):

ПростоНуб писал(а):

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

можно указть на мой код, где массив по указателю передается?

Сами же ответили:

safocl писал(а):

std::array

Если при компиляции целиком это и может быть заинлайнено или как-то оптимизировано, то в случае библиотечной функции, С++ ABI не позволяет передать массив, иначе, чем по указателю.
Впрочем меня опять тут начнут укорять, что я методологии профессиональной разработки пытаюсь применять к пет-проектам, где никто изоляцией кода между модулями проекта не заморачивается, так как разработчик всегда один и только один.

safocl

ПростоНуб писал(а):

Сами же ответили:

да в общем то нет -- не ответил -- с чего взято, что std::array это какая то нестековая память и что он не является POD типом и агрегатом?

Adrift

ПростоНуб писал(а):

Для Вас embedded system заканчивается на STM32, а у моего клиента на заводе есть embedded system даже на Epyc. У многих дома - на одноплатниках под Linux и HA. Впрочем даже у Вас наверняка есть embeded ARM с SIMD в смартфоне.

Здорово, только это раздел микроконтроллеров и ПЛИС, не одноплатников, соответственно понятие embedded тут уточненное ) Вы же прекрасно понимаете, что шла бы речь про Epic и одноплатники на Linux никто бы к вашему SIMD не цеплялся, но речь про микроконтроллеры где этот SIMD присутствует в виде очень редкого исключения. С другой стороны важно ведь не само наличие SIMD, а его влияние на производительность, правильно? Например, STM32H7 на 550MHz, выполняющие 2 инструкции за такт, даже без нормального SIMD должны быть существенно быстрее вашего Xtensa с SIMD. И что прикажете делать? Какой из этих двух мк устарел? )

ПростоНуб

safocl писал(а):

ПростоНуб писал(а):

Сами же ответили:

да в общем то нет -- не ответил -- с чего взято, что std::array это какая то нестековая память и что он не является POD типом и агрегатом?

Какая разница, стековая или не стековая? В данном случае, раз T POD и никаких собственных конструктора, операторов или деструктора добавлено не было, это как раз POD тип. С точки зрения С++ ABI, POD массив передается всегда, как указатель.
Если очень интересно, можете погрузиться в спецификацию Itanium C++ ABI.

safocl

ПростоНуб писал(а):

С точки зрения С++ ABI, POD массив передается всегда, как указатель.

непонятно откуда такая инфа -- возможно ты путаешь аргумент в виде (int arr[]) -- но std::array в аргументе не превращается в такое -- но в первом случае просто правило языка C++ действует, которое делает decoy int[] к int* в аргументе функций -- тут ничего общего с моим случаем.

ПростоНуб

Adrift писал(а):

Здорово, только это раздел микроконтроллеров и ПЛИС, не одноплатников, соответственно понятие embedded тут уточненное

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

Adrift писал(а):

Например, STM32H7 на 550MHz, выполняющие 2 инструкции за такт, даже без нормального SIMD должны быть существенно быстрее вашего Xtensa с SIMD. И что прикажете делать?

Могу посмеяться над голословным утверждением. Без данных тестирования, которое можно повторить и проверить, говорить об этом смысла не имеет. Возможны любые результаты. Например, в том же ffmpeg переход на SSSE3 дал прирост производительности некоторых функций в 40 раз, а на AVX-512 - в 94 раза. Так что имея почти двукратный выигрыш в CoreMark, STM32H7 вполне может проиграть.

safocl

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

ПростоНуб

safocl писал(а):

ПростоНуб писал(а):

С точки зрения С++ ABI, POD массив передается всегда, как указатель.

непонятно откуда такая инфа

Например, отсюда https://stackoverflow.com/questions/367 ... f-t-is-pod