Прийшов час осідлати справжнього Буцефала🏇🏻Приборкай норовливого коня разом з Newxel🏇🏻Умови на сайті
×Закрыть

Интересная задачка (С/C++)

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Есть машина (допустим, абстрактная), у которой очень медленные операции ветвления и переходов, но относительно быстрая целочисленная арифметика (скажем, один переход равен 128 арифметическим операциям по времени выполнения). Архитектурно отрицательные числа представлены в дополнительном коде (2’s complement format), как практически везде на сегодняшний день.

Есть следующий код, который вычисляет позицию внутри массива для циклического буфера. :

        delay_position = buffer_position - delay;
        if (delay_position < 0)
        {                                                                    
            delay_position = buffer_length + delay_position;         
        }  

И вот такой код, который проверяет выход за границы циклического буфера:

        if (buffer_position >= buffer_length)                                  
        {                                                                    
            buffer_position = 0;                                               
        }                       

Все переменные типа int, размер int’а неизвестен, должен вычисляться через sizeof()

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

LinkedIn

Похожие статьи

Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Я вот тут прикреплю задачку, которую я постил в другом треде, тоже 7 лет назад:

Нужно перевести цвет в формате RGB565 в RGBA8888 наиболее точно, маски битов цветовых компонент такие: RGB565 (2 байта): RRRRRGGGGGGBBBBB, RGBA8888 (4 байта): RRRRRRRRGGGGGGGGBBBBBBBBAAAAAAAA.

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

Я её использовал на собеседованиях в своём время. dou.ua/...​forums/topic/8265/#364810

В этой задачке никаких хитрых решений нету ?
Мне видится самый лекгий вариант, из серии «тупо влоб».
Где мы последовательно маскируем каждый из 3х компонентов в RGB565 , смещаем влево и по (ИЛИ) | применяем к результату.

Где мы последовательно маскируем каждый из 3х компонентов в RGB565 , смещаем влево и по (ИЛИ) | применяем к результату.

В этом и ошибка %) проверь для минимальных и максимальных значений.

Да пофиг. Никто не заметит, если не начнет рисовать распределения.

Многие мониторы используют нелинейное преобразование при отображении, что подчеркнуть глубину чёрного и HDR белость белого и когда на выходе 247 вместо 255, то отчётливо видно грязно-белый цвет.

Ну тогда возвращаемся к твоим индексным таблицам)
Кстати, общая таблица для uint16_t имеет смысл, или лучше по таблице на канал?

Ну если таблички, то как минимум две — для 5 бит и 6 бит, тоже вполне себе решение. Но идея копирования старших разрядов в младшие для стаффинга вполне справляются с этой задачей, есть ньюансы, конечно. Т.е конверсия RGB565 в RGBA8888 будет выглядеть, если брать нумерацию битов, как 43210432 для R и B каналов. Например, GPU переводит во float и потом назад. Даже «правильных» решений не одно.Вот уже три решения.

В качестве последнего вопроса какое значение нужно записать в альфа канал и почему :) Т.е. реально можно на собеседовании 45-60 минут говорить только об этой задаче. Как по мне, это лучше круглых люков и ещё лучше тестового задания.

А что, в альфе не всегда ноль на практике?

Конечно же нет. Если изображение участвует в per-pixel alpha blending, то альфа имеет значение. Но если говорить о собеседовании, то хочется услышать, что RGB565 — это полностью opaque изображение (непрозрачное), то для того, чтобы получить аналог в RGBA8888 (а мы ведь делаем конверсию из одного формата в другой), нужно записать 0xFF, чтобы сделать изображение полностью непрозрачным, как и исходный RGB565.

Кстати, общая таблица для uint16_t имеет смысл, или лучше по таблице на канал?

Проблема больших таблиц — выйдем за пределы L1 кеша, а L2 уже не такой быстрый, чтобы был очевидный прирост скорости.

val = RGB565[i];
r = (val & 0xF800);
R = (r >> 8) | (r >> 13);
g = (val & 0×07E0);
G = (g >> 5) | (g >> 9);
b = (val & 0×001F);
B = (b << 3) | (b >> 2);
result = (R << 24) | (G << 16) | (B << 8);

Да, копирование старших разрядов в младшие, как одно из решений. Есть некоторая периодическая нелинейность, но неё можно забить, но упомянуть о ней стоит:

01111011 0×7B
10000100 0×84 — разница 0×09
10001100 0×8C — разница 0×08
...

Вроде понял,
Тот же 5-байтный диапазон RRRRR (для примера).
Нужно равномерно распределить в 8 байтном результируеющем диапазоне. А не просто мапить...

Когда то очень давно я уже на эти грабли наступал.

Нужно перевести цвет в формате RGB565 в RGBA8888 наиболее точно

Надо наиболее точно, или усредненно точно (+\- 2-3 шага на канал), но быстро? :)

Это задача для собеседования «на поговорить». Понятие точности тут размыто и правильного решения нет, но есть множество решений с приближениями, т.к. мы по сути берём данные с потолка и делаем их максимально равномерными, чтобы и чёрный был чёрным и белый не был грязным.

Люблю собеседования на поговорить. Собеседовал человека один раз, на проект связанный с графикой (OpenGL). Пока подбирал вопросы, понял что лучше просто буду с ним говорить бОльшую часть времени по задачам приближенным к проекту или прямо с проекта. По итогу 15 минут опрашивал стандартно «бывает ли виртуальный конструктор», а остальные 45 минут ушли на поговорить и feel free to improvise.

посмотретъ как сделано в Qt — profit

никак. ты думал, я ломанусь сразу в кьютешный код?

кароче вот:

inline QRgb qConvertRgb16To32(uint c)
{
    return 0xff000000
        | ((((c) << 3) & 0xf8) | (((c) >> 2) & 0x7))
        | ((((c) << 5) & 0xfc00) | (((c) >> 1) & 0x300))
        | ((((c) << 8) & 0xf80000) | (((c) << 3) & 0x70000));
}

Cool. Вот только я бы за название функции яйца бы в дверях защемил %) RGBA4444 и RGB565 оба 16, как и RGBA8888 и RGBA2-10-10-10 оба 32. Называется угадай, что внутри %)

Там еще в результате байты как-то не так расположены

Ну вообще-то я думал, что ты уже смотрел.

нет, зачем? я знаю, что код там естъ, нот точнгде он не помню

gist.github.com/...​1a5b82287ef99b4facef2a55a

Набросал 5 вариантов:
1) 2 точных решения через float & double: rgb565_to_rgba8888_float_scale, rgb565_to_rgba8888_double_scale
2) точное решение через 2 таблицы на 5 бит и 6 бит: rgb565_to_rgba8888_2tables
3) приближенное решение через 1 таблицу на 6 бит: rgb565_to_rgba8888_6bit_table; 5-битовые каналы это каждый 2й элемент в 6 битовой таблице.
4) приближенное решение через сдвиг всего rgb565 цвета (по старшему разряду) и выбрасыванием что сдвинулось с других каналов: rgb565_to_rgba8888_linear_scale.

Во всех 5 вариантах — белый 255 по всем каналам. В вариантах 3 и 4 — черный 0 добиться не удалось. В варианте 3 черным является цвет rgb(4,0,4), это 1й элемент таблицы для 5 битового канала. В варианте 4 черный это rgb(7,3,7), т.к. именно этого нехватает для полноценного белого.

А вот бенчмарк удивил (g++ -O3, nice -n −20 ./uber_colors), 10000 повторений конвертации всех 65536 цветов:

2 tables : 1.090233s
6 bit table : 1.208392s
Linear scale : 0.671556s
Float scale : 2.926642s
Double scale : 3.089686s

Не ожидал что использование 1 таблицы вместо 2х — немного замедлит выполнение.

Убери | 0×1; в примере с одной таблицей и сравни скорость

Ускорилось! Работало в 1.1 раз дольше, теперь в 0.9 раз дольше по сравнених с двухтабличной версией.

Еще можно побаловаться: сделать вместо uint8_t table_6[64]; uint32_t table_6[64] или uint64_t table_6[64]; Оно будет занимать больше места, но чтение может стать быстрее. А может не стать.

Еще интересно было бы сравнить скорость с одной таблицей на 2^16, которая за одно обращение переводит uint16_t rgb565 в uint32_t rgba

Мой мир не будет прежним ) Она влезла в кеш и лидирует. Гист обновил.

i7 4770S
1 table : 0.233312s
2 tables : 0.870961s
6 bit table : 0.960064s
Linear scale : 0.527754s
Float scale : 3.853501s
Double scale : 7.437042s (что-то не дружит с даблом этот товарищ)

i7 6820hq
1 table : 0.286407s
2 tables : 1.079156s
6 bit table : 1.531276s
Linear scale : 0.864239s
Float scale : 2.922676s
Double scale : 3.102447s

Ы
Таблица на 256 килобайт получилась в разы быстрее всего остального?
ЖЕСТЬ!!!!

Да, об этом нигде не прочитаешь. Тестить и ещё раз тестить! %)

Тут сейчас выплывет, что для мультяшек быстрее работает общая таблица, а для фоток — по таблице на канал)

Какой массив входных данных? Там цвета не подряд идут?

В цикле всё подряд перебирается. Попробую сделать случайную перестановку.

Перебор подряд дает локальность обращений к таблице

Да, это были синтетические данные (но результаты порадовали даже на них). Вот по совету Майка конвертация 50мб «картинки» (из случайных пикселей). 100 конвертаций 50млн пикселей:

1 table : 5.759996s
2 tables : 8.105381s
6 bit table : 9.932783s
Linear scale : 2.274480s
Float scale : 8.746093s
Double scale : 16.253301s

std::vector<uint16_t> converted;
Лажа. Должно быть uint32_t

Спасибо, поправил, но глобально результат не изменился, пропорции те же. Его тоже поправил.

А вот теперь пускай Майк объясняет, почему дабл самый быстрый.

Нет) всё верно. Он самый медленный. То я форматированием ввёл в заблуждение. Поправил, теперь точно всё правильно. Что ещё оптимизировать можно не знаю.

Теперь самый быстрый — алгоритмический.
Добавь еще, пожалуйста, более точный алгоритмический:
dou.ua/...​orums/topic/8847/#1861666
или
dou.ua/...​orums/topic/8847/#1861503

Добавил, гист обновил. В Кутишной формуле я порядок байт не менял, не думаю что это принципиально.

1 table : 5.447952s
2 tables : 8.672480s
6 bit table : 12.029035s
Linear scale : 2.306467s
Float scale : 8.872987s
Double scale : 16.459350s
Qt : 3.177616s
Denys : 10.490398s

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

Вспомнил еще 3 варианта оптимизации:
1) Закинуть статические индексные таблицы на стек

2) Разворачивание цикла в 4 раза: вместо

 for(unsigned i = 0; i < end; ++i)
    dest[i] = trans(src[i]); 
кешируем данные в регистрах:
 for(unsigned i = 0; i < end; i += 4) {
    const uint16_t data0 = src[i];
    const uint16_t data1 = src[i + 1];
    const uint16_t data2 = src[i + 2];
    const uint16_t data3 = src[i + 3];
    const uint32_t result0 = trans(data0);
    const uint32_t result1 = trans(data1);
    const uint32_t result2 = trans(data2);
    const uint32_t result3 = trans(data3);
    dest[i] = result0;
    dest[i + 1] = result1;
    dest[i + 2] = result2;
    dest[i + 3] = result3;
} 

3) prefetch для однотабличной трансформации:

 for(unsigned next, i = 0; i < end;) {
    next = i + i;
    __builtin_prefetch(table + src[next]);
    dest[i] = table[src[i]];
    i = next;
} 

Если предел счетчика цикла известен GCC, то он сам все развернет по проц твой.

Я сам видел, как вот такое кеширование в регистры оптимизнуло как раз работу с таблицей в разы. Правда, это лет 7 назад было.

7 лет назад и сейчас всё сильно разное. Более того разные компиляторы и разные целевые платформы и многое меняется.
Так что подобные задачки интересны для разминки, но не более. На другом железе с другими компиляторами в другое время всё может в корне измениться.
Эта задачка, что дает Горчак на собеседовании ни о чем, если он не расскажет в формулах, собственно что делает эта конвертация и почему тупо нельзя забить 0-ми.
Более того форматов видео и картинок безумное море нынче и их еще плодят. Вот выше вы поразминались, но у вас картинка HWC, а многим либам предпочтительней CHW и всё, что вы выйграли здесь, проиграете в HWC->CWH.
А еще построчные матрицы или по столбцам, а еще RGB или BGR.
Вот объясни, с какого бодуна в OpenCV BGR дефолный, а не RGB.
И т.д. и подобного море. А когда добавляются батчи, то там начинается безумие из всех возможных вариантов 7 буковок N, C, W, H, R, G, B. И еще стадо форматов упаковки от RGB до YUV.
И сколько видел кода для обработки видео от 10 до 90% времени комп занимается конвертированием между форматами.

Ты же разбираешь битовый массив, затем пихаешь разобранное в дабл, затем вынимаешь оттуда, кладешь в int8 — это для процессора громадное количество странного кода.
По сути ты делаешь все возможное, чтобы тормознуть его.

Еще можно побаловаться: заменить

const uint8_t r = static_cast<uint8_t>
на
const uint64_t r = static_cast<uint64_t>
Скорее всего, разницы не будет, но кто знает

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

1 table : 0.286407s

Сейчас придёт клиент и будет доказывать, что это невозможно %)

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

1 table      : 3938423
2 tables     : 7153231
6 bit table  : 8266133
Linear scale : 1943639
Float scale  : 6071799
Double scale : 11392550

i7-7820HQ CPU @ 2.90GHz

Завтра прийдет дядя Витя, положит это все на SSE, и порвет всех остальных)

А вот SSE я совсем не умею готовить, пробовал когда то давно интринсики вставлять, но получилось ровно ничего ) Интересно будет посмотреть на решение дяди Вити.

Я тоже не умею(

Там уметь нечего. Команды SSE и AVX прилично логичнее тех, что были в FPU. И пользоваться ими проще, но начиная с GCC8 уже почти не нужно.

GCC с 8-го уже сам это неплохо умеет, если код на С ему удобен. И циклы сами разворачивают. А смотрю чего компилер наделал здесь godbolt.org. С ключиками компилятора иногда поиграться быстрее, чем ручками солнышко закатывать.
Ну и юзаю по возможности MKL, IPP. Там у интела програмеры только подобными оптимизациями и занимаются и за очень приличные зарплаты.
И да AVX2 и AVX512 реально круты, но из процессора интеловского делают обогреватель помещения. Пришлось поставить кулер на полкило весом и 4 тепловыми трубками, чтобы тепло отводить от проца. И двумя вентиляторами и не забывать его пылесосить вовремя.

А в задачке выше нужно с битиками гемороиться.

Ну и понимаю, что Горчаку нужно на разном странном железе делать и ему за это платят приличную зарплату, а мне не платят и для моих игр мне отлично хватает интеловского проца и nvidia карточки.

В прошлый раз когда возился в AVX, GCC еще толком в него не умел.

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

Если не уверены в той memcpy, что у вас, то тупо прогоните картинку нужного вам размера через регистры AVX и получите предел, которого можете достигнуть.
И не забывайте, что данные по возможности должны быть выровненные. Кстати наиболее хорошо видно, как должно быть — это ippMalloc из IPP.

Ну и таблица, если влазит в кеш и еще влазят туда обрабатываемый данные, всегда будет быстрее. Но если таблица с обрабатываемыми не влезет хоть на 1 байт, то получите сразу приличные тормоза.
Kегко это проверить просто умножением матриц через MKL — до некоторого размера матриц будет летать, а после некоторого его увеличения будет скачек по времени — он близок к размеру кеша L1/3.

Не приду. Мне лень. Оно, конечно можно пострадать с AVX2. но зачем???
Мне вот сейчас нужно оптимизнуть ресайз маски 28×28 по баунти-боксу на размер картинки со входа.
Но про таблички напомнили мне — это хорошо.

LeetCode сайт есть. Но тема намекает на необходимость создания LeetBytes.

ps: давай ещё задачки! с интересом прочитал весь здешний топик

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

и первый и второй подход — правильные.
но мое субъективное — на «литкодах», «эйлерах» мало инженерных решений.
а в практической разработке их, инженерных решений придется применять много чаще чем теоретических

ага, а на практике рулит «ТЗ оптимизация», и стек оверфлоу.

Кстати, если брать только приведенные строчки кода, то условия не покрывают весь диапазон проверок.
Предположим, что abs(delay_position) > abs(buffer_length)

На выходе получим отрицательный

buffer_position

.

В разделе совместимости синтаксиса с С.

бритва Оками каже що ++ зайве

Два плюса говорит о том, что есть два moderatorial’а, и при получении третьего будет бан и станет C! %)

зачотний жарт )))

Пойду читать Г. Уоррен «Алгоритмические трюки для программистов ». ISBN 5-8459-0572-9 Раздел. 2.8. Трехзначная функция сравнения.

Узнал книжку только по обложке, это ж надо так перевести Hacker’s Delight — Алгоритмические трюки для программистов, а three-way comparison -> трехзначная функция сравнения. Как бы это развидеть %)

Я эту тему создавал 7 лет назад ещё до массового бума литкода и прочих соревновательных сайтов. Можно сказать, что подросло новое поколоние (пол поколения) программеров за этот срок %) На прошлой неделе всплыла ещё одна интересная, старая, как экскременты мамонта, задача — clamp значений в диапазон от 0 до 255.

Классическая имплементация на С/C++ выглядит вот так. И является типовым паттерном для оптимизации многими компиляторами — они понимают, что ты делаешь клэмпинг:

unsigned char clamp(int i)
{
    if (i<0)
        return 0;
    else if (i>255)
        return 255;
    else
        return i;
}   

Генерируемый код очень приличный. Забавно, что «литкодовцы» в своей массе начали предлагать решение полученное перегонкой из оптимизированного компилятором кода назад в С. Как пример: codereview.stackexchange.com/...​nteger-to-the-range-0-255

Для облегчения задачи можно добавить ещё одно условие — входное значение не может превышать более чем в два раза выходное. Т.е. если мы делаем на выходе 0..255, то входное значение не может быть за пределами скажем −255..+511.

Задача не высосана из пальца и абсолютно реальная, для изображения размером 1920×1080 эта функция вызывается от 60 миллионов до 120 миллионов раз согласно профайлеру и кушает 30% всего времени задачи, поэтому даже лёгкое ускорение инлайновской имплементации имеет большое значение для общей производительности. Клэмпинг в SSE делать не получится, т.к. организация данных, увы, не очень линейна по своей природе, поэтому сборка и разборка SSE регистра будет очень медленной.

P.S. Что интересно, программисты старой школы практически мгновенно выдают быстрое решение, которое является линейным кодом (может и не самое оптимальное, но быстрее того, что производит оптимизатор компилятора раза в 2-3), но тут же отбрасывают его вследствие вбитого кувалдой ограничения тех древних олдскульных времён, молодое поколение — до 30 лет этого решения не видят вообще. Как по мне такая задача гораздо интереснее насилования кандидата в особо извращённой форме литкодом.

P.P.S. Тема создана не для того, чтобы открыть ментальную паралимпиаду, просто интересное наблюдение. Кто хочет может себя проверить не читая ответы на этот пост %) Думаю, что то, олдскульное решение кто-то быстро выдаст.

Какое-то такое шаманство получилось на быструю руку. Компилить не пробовал )))

unsigned char clamp(int i)
{
int bits = sizeof(i) * 8;
int mask = 256 — (i > 255);
int sign_shift = (i >> bits — 1) << 3; //get value 8 for case i < 0, otherwise 0
return ((unsigned char)(i | mask)) << sign_shift;
}

PS: А какие теги нужны для красивого серенького блока с кодом? Потому что code уныл более чем полностью.
PPS: Посмотрел решения Fast Byte Clamp. Прикольно. И сильно пооптимальней моего будет.

PS: А какие теги нужны для красивого серенького блока с кодом? Потому что code уныл более чем полностью.

Я использовал «pre».

(i > 255)

Хотелось бы от сравнений избавиться. Потому что не только под x86/x86_64 будет код работать, а и под armv7 и aarch64.

Хотелось бы от сравнений избавиться

Якщо в якості мистецтво заради мистецтва (і тільки для 32-х бітних інтів), то можна щось таке

unsigned char clamp(int i)
{
    return (i + ((255 - i) & ((255 - i) >> 31))) & (~i >> 31);
}
Принаймні на GNU GCC v7.1.1 працює штатно.
Для цієї версії генерується щось типу
        mov     eax, 255
        sub     eax, edi
        cdq
        mov     eax, edi
        not     eax
        and     eax, edx
        add     eax, edi
        not     edi
        sar     edi, 31
        and     eax, edi
        ret
тоді як для простої
        xor     eax, eax
        test    edi, edi
        js      .L1
        cmp     edi, 255
        mov     eax, -1
        cmovle  eax, edi
Але я, чесно кажучи, без поняття як це все правильно порівнювати.

P.S. До речі, якщо написати отак:

unsigned char clamp(int i)
{
    return (255 + ((i - 255) & ((i - 255) >> 31))) & (~i >> 31);
}
то працюватиме так само, а асемблер трошки інший
        lea     eax, [rdi-255]
        cdq
        lea     eax, [rdi+1]
        not     edi
        sar     edi, 31
        and     eax, edx
        sub     eax, 1
        and     eax, edi
        ret
P.S. До речі, якщо написати отак:

С тупым кодом на С, но скомпилированный с -O3, который я привел в самом начале получается 103 ms на обработку изображения. С твоим кодом получается 107 ms. Процессоры skylake, kabylake и coffelake — соотношение приблизительно такое же. Просто когда пишешь тупым кодом, то внутри компилятора триггерится паттерн clamp, а вот с твоим кодом ничего не триггернулось и он просто разложил по операциям как написано в коде. Как по мне код красивый, но процессору не очень нравится :)

О, дуже дякую! Я не дуже вмію правильно міряти час, мені було дійсно цікаво що і на скільки швидше. Ще подумав, що в мене трохи надто загальний код вийшов, можна його ще трішки ужати:

unsigned char clamp(int i)
{
    return (i | ((255 - i) >> 31)) & (~i >> 31);
}
або, якщо дозволити собі порівняння з нулем,
unsigned char clamp(int i)
{
    return (i >= 0) * (i | ((255 - i) >> 31));
}
Я не дуже вмію правильно міряти час, мені було дійсно цікаво що і на скільки швидше.

У меня просто есть software fallback код, к аппаратному ускорителю на разных платформах, я заменяю код функции clamp() и запускаю 1000 тестов на одном ядре с приоритетом 255, чтобы никто не приэмтил выполнение кода и беру среднее. На самом деле 1000 и среднее — это излишне, т.к. результат плавает в пределах одной миллисекунды, если будет слишком быстро, можно перейти на наноизмерения, но там коды замеров по-тяжелее будут, чтобы получить необходимую точность, т.к. надо вычитать своё собственное время.

Даю маленькую подсказку идея не в оптимизации классического кода clamp, а в изменении подхода, что на выходе даст тот же clamp :)

Я чогось не розумію? Що заважає зробити отак:

unsigned char clamp(int i)
{
    return i & 255;
}

Чи тут на вході можуть бути від’ємні значення?

256 & 255 == 0
А математическая формула clamp (ТЗ) даёт верхнюю границу 255

Ну смотри. У тебя есть диапазон значений от −255 до 512. Тебе надо его обрезать до диапазона 0 — 255.
Твой код переведет −100 в +100 а должен в 0.
Твой код переведет 256 в 0 а должен в 255.

Да, для сравнения, та версия кода, которую выдали «олдскульники» выполняется за 94 ms. Хотя на первый взгляд код кажется тяжелым, но процессору виднее (причем и 32 и 64 битовым АРМам тоже). Я завтра вечером запощу код, если никто не предложит его раньше.

Хотелось бы от сравнений избавиться.

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

Спасибо, посмотрю.

Кстати, отличная книжка. Осталась в офисе на карантине ;)

я бы попробовал так: if (!! (i & (0xff<<8)))

Это сильно эффективней чем отдельновзятая операция больше, но что будет в сумме — на пробовать.

если вспоминать самую древность, то я тогда бы написал так:

unsigned char clamp(int n)
{
    if (n<0)
      return 0;
    else 
      return n-n/255*255;
}
Но это очень сильно медленнее, чем если
unsigned char clamp(int i)
{
    if (i<0)
        return 0;
    else if (i>255)
        return 255;
    else
        return i;
}   
Сравнил ради интереса здесь quick-bench.com

Самое быстрым там получается такое (codereview.stackexchange.com/...​eger-to-the-range-0-255)

unsigned char clamp(int n)
{
    int a = 255;
    a -= n;
    a >>= 31;
    a |= n;
    n >>= 31;
    n = ~n;
    n &= a;
    return n;
}

Хотя я сильно удивлен такому
Компилятор С++ разучился оптимизировать это
n-n/255*255
и заменить его подобным:
n-n>>16<<16
Тупенько и простенько влоб заменил на сдвиги и как-то сильно ускорилось (но нужно для такого вспоминать все те правила и нюансы).

От сдвигов я давно отказался и уже не помню точно правил в С++ со сдвигами знаковых и беззнаковых. Чтобы оное юзать нужно вспоминать все правила там (помню есть особенности в сравнении с асмом).
От сдвигов отказался я давно уже. Уже помню Студия 6 прекрасно заменяла эти деления и умножения на сдвиги (а потом и процессоры научились выполнять умножения и деления со скоростью сдвигов).
В общем немного удивлен.

В общем как-то так получается быстро:

inline uint8_t _clamp2(int n)
{
     if (n<0)
       return 0;
     else 
      return n-(n>>16)<<16;
}
Но правильно-ли оно работает, я не проверял.
Теоретически проверка на < 0 не нужна, если ограничится на −255.
Но правил сдвигов я уже нихера толком не помню.

Не неправильно. Так что не знаю решения.

inline uint8_t clamp0(int val)
{
	if (val < 0)
		return 0;
	else if (val > 255)
		return 255;
	else
		return val;
}

inline uint8_t clamp1(int val)
{
	if (val < 0)
		return 0;
	else
	{
		int y = ~((val-256)>>24) | val;
		return y;
	}
}

или

inline uint8_t clamp1(int val)
{
	int y = ((~(val-256)>>24) | val) & (~(val>>31));
	return y;
}
вот такой вариант получается:
t0: 1.39983ms t1: 0.588362ms
то бишь второй вариант быстрее
с ключами компилятора -std=gnu++17 -O3 -ftree-vectorize -funroll-loops -fno-strict-aliasing

разницы между проверкой на < 0 или без нее нет.

Думаю, если поиграться с AVX, AVX2 можно еще чего выйграть (но там пару дней погемороиться придется).

З.Ы. Немного вспомнил про сдвиги с С. Наверное логические операции можно и упростить, типа минимальные диз- коньюкнивные функции повспоминать. Но без компилятора под рукой я бы не решил такую задачку. А если что-то подобное спросят на собеседовании, то сразу попрощаюсь. Код с ифами правильнее, потому как его люди читать будут. Но, как утренняя разминка задачка зашла.

если что-то подобное спросят на собеседовании, то сразу попрощаюсь.

А зря :) Обычно, если это не литкод-задротное собеседование, то на собеседовании достаточно обосновывать своё решение. Оставь оптимизацию компиляторы — как мы видим из тестов — вполне обоснованное решение, т.к. даёт наилучший результат при минимуме усилий.

Код с ифами правильнее, потому как его люди читать будут.

В какой-то мере да, но предложенное решение, которое ускорило весь код почти на 10% тоже вполне и вполне читаемое. Попробуй изменить подход — не оптимизируй исходный код, измени подход к получению обрезанных значений :)

Но, как утренняя разминка задачка зашла.

Я просто обожаю такие задачки :) Вроде бы просто как ситцевые трусы, но блин, какое поле для фантазий. Я когда-то в другом топике приводил пример перевода RGB565->RGB888, который все кандидаты делали с ошибкой, например, с этой ошибкой даже разведена энтузиастская плата Beagle Bone Black при выводе на HDMI дисплей. В простых задачках много чертей водятся %)

Вообще-то почти в 3 раза:

t0: 1.39983ms t1: 0.588362ms

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

В простых задачках много чертей водятся %)

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

Тем ни менее жду правильное решение. Интересно же.

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

В общих случаях — да, заморачиваться на оптимизацию мелочей не стоит. Но, например, я уже когда-то писал, что кастомер ради экономии двух центов покупает дешевые чипы без акселлераторов, а затем тратит миллионы на разработку. Такое сплошь и рядом. А потом говорит, я хочу получить 30 FPS и всё тут, а софтварный фолбек даёт с натягом 25 FPS. Казалось бы живи и радуйся, иди и больше не греши, но нет, хочу 30! А такая маленькая оптимизация в библиотеке, в коде, в который не заглядывали десятилетиями вдруг находится возможность путём нескольких лёгких оптимизаций улучшить код и кастомер получает уже 32 FPS.

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

Вот с тем же yolact, там постобработка питоне и pytorch.tensor и сильно питонизировано. Во всем инете нашел только пробу одного китайца запустить ту же модель на С++. Я сначала взял его код, а он еле еле шевелится. Вот пришлось в деталях разобраться с той постобработкой и переписать на с++. Вместо 60 ms кода того китайца на 1 кадр у меня получилось 3 ms. Модель выдает около 25 ms. Как бы на сейчас меня такая скорость удовлетворяет.

Я видел код питонистов, где 80% времени работы их проги занимали копирования массивов, что по RAM-RAM, что RAM-GPU.

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

Не для того щоб почати суперечку, але ІМО варто згадати що за допомогою IronPython->ngen виходить натівний код.

А для С++ є Cling — root.cern.ch/cling.

Бинарники и дефолтный сипайтон генерить может. Не без плясок с бубном но тем не менее. Водораздел не только лишь по этому признаку происходит.

Цлинга (фронт LLVM, коих много) это скорее JIT-компилятор чем интерпретатор. Ну да ладно, при большом желании можно и сапог на глобус натянуть.

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

З усім погоджуюся крім ось цього:

вылазит очередной Кулибин, переписавший часть своего (ну или китайского) питоновского кода на Си и таким образом ускоривший его в эН ра

Наскільки я розумію так якраз і рекомендовано робити і більшість відомих пакетів та фреймфорків так і написані — POC на Python, а потім переписують на C. І практично усі пакети що йдуть в «стандартному» Python написано на С.

Ви зовсім не зрозуміли іронії. Оскільки й сам дефолтний СіПайтон (несподівано) написаний на Сі, то дуже важно написати шось на Пітоні шо працювало б швидше ніж відповідний код на Сі. І навпаки: дуже дивно вихвалятися коли твій код на Сі «раптом» запрацював швидше пітоновського :)

А, мабуть дійсно не зрозумів.

Проте у попередньому коменті було правильно зазначено що

Питон никогда не претендовал на скорость

Пітон — це швидко написаний код який легко читати і супроводжувати і для якого не потрібна купа інструментарію. В цьому його сила і зручність ІМО.

Пітон — це швидко написаний код який легко читати і супроводжувати і для якого не потрібна купа інструментарію. В цьому його сила і зручність ІМО.

Саме так. Але інструментарій всеодно розростається...

Вообще-то почти в 3 раза

в 2.37919852 раза

может и не самое оптимальное, но быстрее того, что производит оптимизатор компилятора раза в 2-3

Но интересно увидеть решение Горчака.

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

Мне кажется на это больше влияет как конкретный компилятор С/С++ код разложит/оптимизирует.

Виктор, а ваш вариант точно покрывает весь диапазон для (int) ?
Я пробовал передать 1900000000 в clamp1()
На выходе получил −114 вместо 255.

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

З.Ы. Ну и мне уже давно не приходиться лезть в подобное, обычно оптимизация на уровне алгоритма эффективнее, такая нужна в предельных случаях, когда алгоритм на верхнем уровне вылизан. Мне же чаще нужно бывает, например, убрать лишнее копирование матриц больших или лишнее транспонирование и подобное — глубже не погружаюсь в оптимизации. А если тензоры, то как их правильнее решейпнуть, чтобы IPP заюзать (в стиле NHWC или NCWH и подобное).

Интересные задачки, у мня давно таких небыло.

Так я и безработный. В офис протирать штаны категорически не хочу. А бегать и рыскать в поисках заказчиков сейчас сил нет. Играюсь вот с MaskRCNN и подобным и пытаюсь его юзать на тележке с ардуинкой (для тестов).
Сейчас, нет ни одной модели для оного, чтобы хотя бы в 30 fps вложилась на приличном даже железе. Вот появилась новая YOLACT (какая-то интересная модификация MaskRCNN) — вот с ней и играюсь. Оригинальный код, как писал один китаец, что ее попробовал юзать, сильно питонизирован.
А вот последовал шагам и коду того китайца и уже его код выкинул и написал постобработку сам, так быстрее работает у меня.
Попробовал прямо на С++ из питона переносить, не получилось. Понял в деталях, написал на матлабе понятно для себя, затем сходу на С++ перенес.
Сейчас буду вот пытаться ту модель под openvino перенести (понятно обученную уже).
YOLACT на 1080 прекрасно в 30 fps влазит.
Но уже там есть недоделка — часть аналогичная FasterRCNN там хуже, чем я ожидал, почему, я пока не знаю еще.

А с работой, хрюшки стукаются, но с какой-то безумной мутью.

Компилятор С++ разучился оптимизировать это

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

и заменить его подобным:
n-n>>16<<16

Для этого нужно 256, а не 255 :)

Ну, по тупому набросал и не проверил. Я сейчас выход модели yolact делаю обработку и там мне уже не до опускания в такие глубины — хватает гемора на более верхних уровнях (причем хочется писать так, чтобы я или кто другой смог прочитать написанное через полгода, посему кручусь в cv::Mat).
И стараюсь в такие оптимизации не лезть. Почти всегда находятся оптимизации на более высоких уровнях (переделкой алгоритма), что дают результат лучше.
Но как задачка для разминки мозгов, то, что ты кинул сюда, интересно.

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

Чуть интересная тема и из 90% местных тут говно тоннами полилось. Интересно, у вас фишка такая — гадить везде, где только можно и нельзя?

Я ж не виноват что вы именно так и воспринимаете любую справедливую критику в свой адрес.
Особенно когда крыть по сути нечем.
Но это сугубо ваши интимные проблемы, и вам с этим жить.

Там C/C++ в WebAsm скорее всего компилируется или что-то вроде того с непонятными опциями оптимизации, третий «полуасемблер» хорошо ложится на V8 или что у них там для песочницы. После того как вторым вариантом займётся скажем gcc то код будет оптимален для текущего CPU и к тому же хорошо читаем программистом. Ну и там если свести к безнаковому вообще минуса хватит и одной проверки.

Там C/C++ в WebAsm скорее всего компилируется или что-то вроде того

с какого перепугу?

uint32_t clamp(uint32_t N) {
    // 
    uint32_t clamp_0 = N & (((N >> 31) & 1) - 1);
    uint32_t clamp_255 = (clamp_0 | ((((clamp_0 - 256) >> 31) & 1) - 1)) & 0xFF;
    return clamp_255;
}
(clamp_0 |

а вот оператор OR разве условный переход не порождает?

а где конст

clamp_0

и нафига нужен

clamp_255

?

а где конст

clamp_0

Первая строчка клампит до 0

uint32_t clamp_0 = N & (((N >> 31) & 1) - 1);

Вторая дополнительно клампит до 255

uint32_t clamp_255 = (clamp_0 | ((((clamp_0 - 256) >> 31) & 1) - 1)) & 0xFF;

Все в коде.

и нафига нужен

clamp_255

Хочется :)

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

Но если так уж хотите получить решение этой своей синтетической задачи, то это несложно.
На ассемблере клампинг 32 битного int в 0..255 без условных переходов и прочих ветвлений будет выглядеть так (используем fastcall соглашение о вызовах):

cdq
not edx
and eax, edx
and eax, 0FFh
retn
Ну попробуйте написать чтонибудь быстрее :)
В современных процессорах еще с прошлого столетия присутствует блок предсказания переходов, на секундочку.

Я же попросил не устраивать спец-олимпиаду. Давай не будем вдаваться в детали, т.к. если мы говорим о x86/x86_64, то это уже давно не так, там на перёд выполняется код, если успевает для положительного и отрицательного сравнения. Если сравнений много, то конвеер уменьшается до неприличного размера, что косвенно существенно всё равно влияет на скорость. Если ты сделаешь замер просто своего кода — он будет быстрый, если ты вставишь свой код в другой, как в моём примере, то общее замедление будет очевидным. Также мы говорим не только о x86.

Ну попробуйте написать чтонибудь быстрее :)

Не скомпилилось под AARCH64. На С, пожалуйста.

На С, пожалуйста.

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

если ты вставишь свой код в другой

а если нет.

Не скомпилилось под AARCH64

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

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

Ты не перегрелся случайно?

Но если так уж хотите получить решение этой своей синтетической задачи, то это несложно.

Это не синтетическа задача, а часть IDCT трансформации и YUV->RGB преобразований.

А почему бы её не сформулировать тогда целиком изначально?
Или это слишком сложно для вас и вы решили провести декомпозицию?
В таком случае спешу вас немножечко разочаровать: в комплексе оптимальное по скорости выполнения решение данной задачи может выглядеть кардинально иначе, чем по частям.

А почему бы её не сформулировать тогда целиком изначально?

Потому что алгоритм доведён до оптимальности.

Или это слишком сложно для вас и вы решили провести декомпозицию?

От чего такой батхёрт?

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

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

Это в детском саде учат.

видимо недостаточно хорошо учат.

Я не просил трогать алгоритм весь, только его кирпичики. Это так сложно принять?

совсем несложно.
слушайте, а почему бы вам не выступить со своей задачкой на стаковерфлов?
данная платформа как то больше предназначена для подобных задач, или вы так не считаете?

данная платформа как то больше предназначена для подобных задач, или вы так не считаете?

Зачем? Я ещё раз акцентирую внимание, что я не хочу устраивать спец-олимпиаду тут или там. Если попадается интересная задача, очень простая на первый взгляд, то почему бы и не запостить её тут. Цель другая.

А кто сказал что исполнятся будет это все на центральном процессоре? В описании к задаче явно другое программируемое устройство.

Походу асик, акселератор

Ну вообще-то на CPU, просто на целом зоопарке кортекс ядер и x86.

походу не угадали.

В общем, не прошло и полгода как ошибочка была таки замечена.
Реально рабочий и самый быстрый код выглядит так:

        cdq
        not     edx
        shr     edx, 18h
        cmp     eax, 0FFh
        cmova   eax, edx
        ret 
Версия для 64 бит:
cqo
not     rdx
xor     rdx, rdx
dec     dl
cmp     rax, 0FFh
cmova   rax, rdx
ret
входное значение не может быть за пределами скажем —255..+511

То може таблицю фуйнути просто?

return ptable[i];//ptable is a pointer to 256th element of the table, so negatives should be fine.

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

Прикольное решение. Но у олдов памяти было всегда мало и на подобные таблички разменивались только там, где ее было достаточно. Ну и я как примат, таблички не любил, это уже больше чисто эмбедерские фишки. И таблички — это больше с расчетам трансцендентных функций — вот такая у меня установка.
Ну и я надеялся на что-то сильно более красивое ;(.

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

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

У x86 была такая команда как XLAT, которая по входному байту доставала из памяти из таблички значение и возвращала его. В те дремучие годы 8086 и 80286 многие её использовали где могли даже для таких операций как перевод ASCII символов в верхний или нижний регистр, одна команда процессора и табличка и всё.

Ну и я надеялся на что-то сильно более красивое ;(.

Главное, что оказалось серьёзно быстрее чем любые битхаки.

Если честно, то спасибо за напоминание о таком трюке. Уже и совсем забыл его.

Ну трюк живий. У кріпті/хешах він ніколи не помирав, є у ембеді різному. Я дивився відео, де казали, що ви там у вашому ML додовбились вже чи не до байтів і юзают таблицю, щоб сігмоїди чи шо там ваше рахувати. Тут ще збиває, шо функція проста.

Все просто. Вот ты юзаешь эту 1/(1+e^{-x}). А какие x на входе ты просто не знаешь.
И тут либо анализировать их, дискретизировать вход и после юзать и это долго. Или тупо и быстро функцию дернуть.
И если ты начнешь так тонко всё оптимизировать, то собственно задачу решишь лет через 100, когда она уже никому не нужна будет.
Вот сколько времени ты на базе опенсурсного будешь тонко оптимизировать какой кодек?
Задачка выше — это микроскопическая часть от него.

Но, если посмотришь на движки, что int8 умеют, то там это внутри скорее всего сделано уже.

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

Вон минская IBA хвасталась продуктом по подсчету товаров на полках. Это задаче уже лет 7 и громадное количество пыталось ее решать на дохлом железе (в том числе и смартфоны) и всегда получалась у всех фигня. IBA тупо шлет картинку на свои сервера с теслами (или в какое облако), там ее распознает и обратно уже шлет результат. По нескольким рекламным картинкам распознается неплохо у них.
Но могу сказать, что их решение у них покупать не будут. Сетям нужно, чтобы стояли дешевые камеры и сообщали персоналу магазина, что вот там на полке пусто и бегом товар выставлять. И стоила такая хрень не дороже 200 баксов, лучше 100.

Вот стартап в котором я 2 года поработал. Его инвесторы свернули. дело в том, что наше решение работало, но стоило в 5-7 раз дороже, чем крупные сети готовы были заплатить. Ему нужны были хотя бы 1080 с полноценным компом, а крупные сети готовы были только на хрени за 150-200 баксов и не дороже.
Теоретически можно было бы нанять еще сишников дорогих и за 2 года оптимизировать раза в 3, но инвестор на такое не готов был, причем с фиксами движка нейронки под себя. такое реально могут тянуть только монстры типа мордокниги, гугла, интела.
АМД вон не тянет — они до сих пор не сделали аналога CUDA и cuDNN. Только не напоминай про ОpenCL — это что-то вечно полурабочее. Вот та же NVDIA заморочалась и сделала полный аналог IPP, называется NPP.

Вон у Горчака такие задачки не частые, а если взять всю их контору, то не удивлюсь если подобным там занимаются 2.5 человека максимум.

На самом деле такие «красивые задачки» как золотые самородки, всплывают редко. В основном скукота, месяца на 2, например, есть многопоточный драйвер, в котором 27 потоков попеременно просыпаются и засыпают. Иногда могут проснуться все и т.п. 4 активных ядра для обработки потоков. Сидишь вот в этой байде: www.eclipse.org/...​pass/img/shots/kernel.png (Это наш opensource продукт на базе eclipse для всех ОС, кто может генерировать трейсы, платная версия под QNX может с наносекундной точностью раскладывать все процессы и их взаимодействие в системе). Так вот сидишь в этой байде и скурпулёзно смотришь, какого хрена скедьюлер ядра тупил 35 микросекунд, прежде чем начать выполнение потока. Или почему поток за 20мс 400 раз захватил и отпустил мьютекс. И всё в таком же духе, никакой романтики. Зато потом, конечно, приятно наблюдать, когда один и тот же код в ядре линукса работает на 25-30% медленее, чем этот же код, но как код процесса под QNX.

:)
Сразу подумалось об этом решении. Не публиковал здесь по простой причине — хотелось посмотреть что предложат молодые и амбициозные.

Я лично реализовывал табличный синус на 8086. Потому что вычислялся он дольше, а память могли себе позволить. Возможно, на Ильичевской БРЛС до сих пор это используется. Черноморское морское пароходство не устраивало быстродействие, когда одновременно рассчитывалось движение судов на рейде. Поэтому когда Майк предложил задачу, это решение мне пришло в голову первым.

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

У американских олдов памяти было поболе.

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

Победителей не судят, пока это самое быстрое решение.

обращение по индексу это всегда медленно. Всегда существуют более быстрые решения.

обращение по индексу это всегда медленно.

Почему? По тестам получается самое быстрое решение и этому есть объяснение.

По тестам получается самое быстрое решение и этому есть объяснение.

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

Если будет частое дергание этого массива, то он , как минимум в кэш попадет.
Это, конечно не регистры , то довольно таки живенько будет.

Потому что еще в детском садике учат что обращение к памяти по индексу работает медленее чем к значению в регистре, Карл! Это настолько очевидно и 100500 раз перепроверено что как бы даже нифига не смешно получается когда вы заявляете

пока это самое быстрое решение.

Уныло, но не смешно. В случае с синусами да : там выигрыш (ОБЩИЙ!) был поскольку плавающая точка, умножения/деления/округления и ряды тейлора, ну и сопроцессор сильно тупил раньше. Похоже вы совсем не поняли моей предыдущей иронии и продолжаете с самым серьезным видом пороть полнейшую чушь.

Попробуйте написать собственную реализацию? Лучшее что у меня получилось — 4-ре инструкции на операцию, но переплюнуть заоптимизированное обращение к таблице у меня не получилось, пока-что непонятно почему.

Дык написал еще вчера. Только это языческий ассемблер и в ортодоксально православных сях сие не компилируется (ну по крайней мере у Горчака не вышло).

Горит как газовый факел на нефтескважине!

сочувствую, но ничем помочь не могу (бензин самому нужен).

Вот, кстати, тебе libjpeg, www.ijg.org/files — об этом продукте врядли кто-то не слышал. Несколько лет назад они переделали clamp() на вычитку из таблички и не только — они везде где только можно использует теперь таблички, если не веришь можешь поискать в коде range_limit, а если тебе всё-таки захочется поизмерять скорость, можешь взять jdcolor.c — там YUV -> RGB преобразования с клемпингом, но будь осторожен! Там даже перемножение вектора на матрицу сделано через таблички!

Там даже перемножение вектора на матрицу сделано через таблички!

Дайте угадаю... через таблички умножения?
Хм, неожиданно ))))

Потому что еще в детском садике учат что обращение к памяти по индексу работает медленее чем к значению в регистре, Карл! Это настолько очевидно и 100500 раз перепроверено что как бы даже нифига не смешно получается когда вы заявляете

У многих людей есть склонность к закостенелым мозгам, когда они выучились и с тех пор думают, что мир неизменен. Вот это реально несмешно жить представлениями 80386 в сегодняшнем мире. Просто одним, которые, работают в банке, это простительно, им эти знания и их обновления — не нужны по жизни, хватает и старого багажа, а другие этим зарабатывают на жизнь и комментарии от первых просто воспринимают как в той рекламе: «А потім маленьке звірятко загортає шоколад у фольгу...»

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

А что мешает тебе, кроме ЧСВ и знаний 20 летней давности провести тесты? Или в банке нет современной техники для тестов?

ага, вижу, не горит, а даже полыхает...

и с тех пор думают, что мир неизменен

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

Просто одним, которые, работают в банке, это простительно

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

А что мешает тебе, кроме ЧСВ и знаний 20 летней давности провести тесты?

Зачем мне тестировать очевидные вещи? Кроме того Интел не делал чтото в последнее время революционных заявлений, мол регистровая память стала работать на порядок медленнее.

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

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

Зачем мне тестировать очевидные вещи?

Я ж говорю — закостенелось мозгов. Возьми и попробуй. Корона не упадёт.

Я ж говорю — закостенелось мозгов. Возьми и попробуй.

Огласите пожалуйста весь список того что мне нужно будет проделать чтобы не дай бог не показаться закостенелым в ваших глазах.
(пальцы в розетку совать надо будет?).

просто нужно по-меньше доказывать, что земля плоская

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

Корона не упадёт.

Точно? Вы проверяли?

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

Держи:

Потому что еще в детском садике учат что обращение к памяти по индексу работает медленее чем к значению в регистре, Карл! Это настолько очевидно и 100500 раз перепроверено что как бы даже нифига не смешно получается когда вы заявляете

Но и здравомыслящий Августин не мог допустить, что люди живут вниз головой. Оно и понятно: ведь признай Августин антиподов, получится, что на свете живут существа, ведущие свой род не от Адама и не затронутые искупительной жертвой © Умберто Эко

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

так-с, давайте ка уточним: регистры процессора — это по-вашему какой вид памяти?

не вижу связи.

Тесты запусти и потом доказывай что белое — это чёрное сколько тебе угодно, но факты упрямая вещь. Они существует независимо от того хочешь ты или нет.

скорее это если бы сила тяжести вдруг перестала работать потому что обращение к памяти (да еще и с индексом) у вас стало работать быстрее чем к регистрам.

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

так-с, давайте ка уточним: регистры процессора — это по-вашему какой вид памяти?

Какие регистры, архитектурные или физические? Архитектурных там будет под две сотни в процессоре, некоторые во время работы переименовываются в физические с именами, причём до четырёх переименований регистров за один такт.

Like the front-end, the Reorder Buffer has been increased to 224 entries, 32 entries more than Broadwell. Since each ROB entry holds complete µOPs, in practice 224 entries might be equivalent to as much as 350 µOPs depending on the code being executed (e.g. fused load/stores).

....

Skylake’s memory subsystem is in charge of the loads and store requests and ordering. Since Haswell, it’s possible to sustain two memory reads (on ports 2 and 3) and one memory write (on port 4) each cycle. Each memory operation can be of any register size up to 256 bits. Skylake memory subsystem has been improved. The store buffer has been increased by 42 entries from Broadwell to 56 for a total of 128 simultaneous memory operations in-flight or roughly 60% of all µOPs.

А причём тут регистры

При том что там черным по белому опкоды операций с регистрами а не с памятью. одно от другого отличить не можете?

никакой параллельности

шито? ))))

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

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

Какие регистры, архитектурные или физические?

квадратно-гнездовые!!!

я не знаю как вам еще объяснить что 2+2 будет 4 а не 1.
походу ваша крыша уехала и вернуться не обещала.

Ну ладно, последняя попытка.
Допустим вы адресуетесь косвенно к своему инту в памяти.
Что для этого нужно?
1) базовый сегментный регистр: ss/ds/es/fs/gs
2) регистр смещения начала вашей таблицы в памяти
3) смещение элемента в таблице
т.е. это будет косвенная адресация со смещением, например
es:[edi + ebx]
И что же мы здесь видим? Целых три регистра процессора для доступа к одному элементу массива в памяти! А между двумя этими регистрами еще и арифметическая операция (выполняется под капотом камня).
Можно было бы уже на этом закончить этот театр абсурда,
НО ЭТО ЕЩЕ НЕ ВСЁ!!!
Вы собрались клэмпить Int.
Возьмем для простоты 32-битный инт, потому что если от будет 64 битный то вам как бы памяти мало не покажется.
Итого вам потребуется 4 гигабайта памяти для хранения вашей таблички. Т.е. уже на этом этапе вам потребуется сделать преклэмпинг индекса чтобы хоть както ужаться. А это на секундочку математическая операция (и не одна).
И после всего этого вы еще имеете наглость заявляеть что 4 элементарных инструкции что оперируют только лишь значениями в регистрах без обращений к памяти будут работать медленнее?
Так что вам будет быстрее, сбегать в магазин за прекешированной бутылкой водки (или что вы там такое регулярно употребляете) или сходить на кухню к холодильнику? Л — логика, как бы, да.
У меня на этом всё. Удачи.

Человек выдумывает целую нереальную вселенную, чтобы не дай бох не запустить тест. Бывает. Человек не верит, что ещё два десятка продуктов использует этот подход для клемпинга, потому что он быстрее. Тоже бывает. Проще прятаться от реальности, иначе она может убить.

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

Ты на верном жизненном пути. В конце тебя ждёт успех.

так запускали или нет? я что то не расслышал.

Что запускал? А ты сделал что запускать? У меня три платформы, x86 среди них нет, есть только x86_64. Я должен отключать компиляцию на других платформах в билд системе, вот нафига мне такая радость? Сделаешь нормально — я запущу. Хотя даже без запуска видно лажу в коде, ты его и сам не запускал.

Во-вторых я не могу заинлайнить ассемблерные вставки — это удар по яйцам для комплятора, когда ассемблерная вставка использует фиксированные регистры, заставляя компилятор генерировать неоптимальный окружающий эту вставку код.

               EAX=0x00000100
CDQ:           EAX=0x00000100, EDX=0x00000000;
NOT EDX:       EAX=0x00000100, EDX=0xFFFFFFFF;
AND EAX, EDX:  EAX=0x00000100, EDX=0xFFFFFFFF;
AND EAX, 0FFh: EAX=0x00000000

Т.е. при значении 256 мы получим 0. Как у той секретарши, 1000 знаков в минуту, только такая херня получается.

Ну и человек, который не может конвертнуть в С элементарный код, который компилятором разложиться именно в тот же ассемблерный код, врядли далеко ушёл по развитию.

unsigned char clamp_from_freak(int i)
{
    int sign_ext = ~(i>>31);

    return (i & sign_ext) & 0x0FF;
}

Ну вот это уже другой разговор.

Т.е. при значении 256 мы получим 0.

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

        cdq
        not     edx
        shr     edx, 18h
        cmp     eax, 0FFh
        cmova   eax, edx
        ret 
Это самый шустрый вариант. Здесь нет условных переходов, а инструкция CMP на самом деле есть ни что иное как неразрушающий SUB и кэш ни грамма не портится.
Однако если нужен вариант без сравнений то вот, без проблем:
        cdq
        not     edx
        shr     edx, 18h
        mov     ecx, eax
        shr     ecx, 8
        cmovnz  eax, edx
        ret 
Во-вторых я не могу заинлайнить ассемблерные вставки — это удар по яйцам для комплятора

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

Ну и человек, который не может конвертнуть в С элементарный код

См. выше.

врядли далеко ушёл по развитию.

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

Бгг. Ну наконец то, я уж думал никто так и не заметит.

Знаешь анекдот про неуловимого Джо?

Рабочий вариант на самом деле не сложнее

И ничем не отличается от продукта компиляции.

Здесь нет условных переходов,

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

Даже самый прошаренный компилятор не сравнится никогда с грамотным программистом. Так что такие критические вещи отдавать ему на откуп совсем не стоит.

Это последние лет 10 не так. Компилятор генерирует более оптимальный код, особенно при инлайнинге. Руками ты никак не напишешь для параллелизации выполнения до 4 команд одновременно, а компилятор может.

А вот компилятор конвертнуть в ассемблер далеко не всегда оптимально может. Или вы придерживаетесь иного мнения?

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

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

Почему же тогда вариант с CMP на практике самый быстрый, а? Ведь в вашей вымышленной вселенной это должно бы было быть совсем не так. А вот почему: процессор не видит условного перехода и поэтому ничего не генерит. Ваша гипотеза не подтвердается, увы.

Руками ты никак не напишешь для параллелизации выполнения до 4 команд одновременно

Легко.

аблички быстрее и я уже 100500 раз объяснил почему.

Продолжаем упорно жрать кактус?
Что ж, я промерял твои таблички. Проигрыш 4 раза на 1 килобайтной табличке, которая уж точно поместится в кэш. При этом я даже упростил код, подавая на вход только лишь значения 0..1023. Что как бы было очевидно с самого начала, но почему то не только лишь всем. Мозги как бы включать надо, а не полагаться на хваленый компилятор и свои розовые фантазии.

есть только x86_64

Да не вопрос, можно и в 64 бита, можно и 128битными SSE2 инструкциями pmaxsd/pminsd даже пакетами несколько интов за раз, если это реально надо. Или 256 битными AVX. Но на одиночных интах выигрыша от этого никакого не будет. Самый быстрый вариант это первый выше. Или он же немного измененный на 64 битах:

cqo
not     rdx
xor     rdx, rdx
dec     dl
cmp     rax, 0FFh
cmova   rax, rdx
ret

Вот тебе пример, который короче твоего примера, причём это код в лоб:

unsigned char clamp(int x)
{
  __asm__ (
      "\tcmpl %3,%1\n"
      "\tcmovl %3,%1\n"
      "\tcmpl %2,%1\n".
      "\tcmovg %2,%1\n"
      : "=r"(x)
      : "0"(x), "r" (0xff), "r" (0)
      );
  return x;
}

Данный пример даже оперирует абстракциями, а не какими-то жёсткими регистрами, конечно компилятор может сгенерировать несуществующий код типа OR EDX, EDX для сравнения на ноль, но мы это опустим.

А вот инлайнинг оказывается совсем небесплатным и превращается в:

        movl    %edi, %eax
        movl    $255, %edx
        xorl    %ecx, %ecx
        cmpl    %ecx,%eax
        cmovl    %ecx,%eax
        cmpl    %edx,%eax
        cmovg    %edx,%eax

Тоже случается и с твоим кодом на асме. Нужно продолжать, что асм вреден сейчас?

а не какими-то жёсткими регистрами

регистры имеют значение.
опкод операций с rax/eax/ax на байт короче например, что дает пускай и небольшую но прибавку в скорости. нужно продолжать?

Тоже случается и с твоим кодом на асме

чтото я не пойму: то ли у вас сильно «умный» компилятор, то ли вы...

Нужно продолжать, что асм вреден сейчас?

ой как всё запущено...
например вот здесь habr.com/ru/post/326900 человек ломает голову как бы еще ускорить обработку изображений и изучает новые инструкции процессора SSE4.2 для того чтобы прикрутить к Питону, а вы тем временем порете чушь и не только по этому вопросу. наверное у вас хобби такое: чушь пороть. ну что ж, каждому своё.
Кстати почитайте, там примеры на вашем любимом Си и достаточно подробно описано как работать с процессором напрямую.

регистры имеют значение.
опкод операций с rax/eax/ax на байт короче например, что дает пускай и небольшую но прибавку в скорости. нужно продолжать?

Меня твои пещерные знания уже утомили. Давай конкретно, какую прибавку они дают, тесты в студию.

чтото я не пойму: то ли у вас сильно «умный» компилятор, то ли вы...

Оба.

например вот здесь habr.com/ru/post/326900 человек ломает голову как бы еще ускорить обработку изображений и изучает новые инструкции процессора SSE4.2 для того чтобы прикрутить к Питону

lh3.googleusercontent.com/...​v3u-C0YgcG4JQhFd__HWyzYC9

Обнять и плакать, если честно, дело ведь не в скорости обработки конечного этапа. Чел, наверное просто не знает что ещё до распаковки JPEG можно рисайзнуть и даже повернуть практически за нулевую стоимость. Ведь он всё равно JPEGи распаковывает, чтобы получить сырую картинку, им на сайт не bmp заливают. Ну а вообще это не моё дело, каждый страдает как умеет.

а вы тем временем порете чушь и не только по этому вопросу. наверное у вас хобби такое: чушь пороть. ну что ж, каждому своё.

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

Кстати почитайте, там примеры на вашем любимом Си и достаточно подробно описано как работать с процессором напрямую.

Детка, я в индустрии 1.5 раза больше времени, чем ты. И работаю постоянно в этой сфере. Свои пещерные взгляды можешь вайтишникам втирать, ты даже код на работоспособность проверить не можешь, я конечно, притворился что поверил, будто ты это специально, но мы оба знаем, что это враньё.

Меня твои пещерные знания уже утомили.

Эти «пещерные» знания вообще то называются фундаментальными. И я уже давно понял что у вас на этом месте большая зияющая дыра (не путать с отверстием). Но это еще полбеды.

тесты в студию.

А еще что? Спеть? Сплясать? Это азы, деточка, перепроверенные к тому же овер 100500. А ежели для вас это божье откровение то и проверяйте, я и так убил на развенчивание ваших бредней более чем достаточно времени.

Я этим зарабатываю деньги и платят мне за результат,

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

Детка, я в индустрии 1.5 раза больше времени, чем ты.

не больше, а меньше.
вы еще и врать напропалую не гнушаетесь.
глупо, ведь это всё достаточно легко проверяется.
на что вы вообще рассчитывали, что опять проканает?

Обнять и плакать, если честно

ну это бла-бла-бла мы пропустим ибо очередное нарезание ненужных понтов и мимо кассы. вам про Фому как бы...

но мы оба знаем, что это враньё.

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

Эти «пещерные» знания вообще то называются фундаментальными.

Увы, они как раз пещерные. Ибо в здравом уме никто не будет аргументировать знаниями из 1990 в 2020 году.

А еще что? Спеть? Сплясать?

С этим в ЕПАМ. Ко мне с тестами. Нет тестов — с вещами на выход.

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

Ну попробуй, поелозь, если не слабо!

не больше, а меньше.
вы еще и врать напропалую не гнушаетесь.

Докажи. Я программирую на ассемблере с 11 лет, сейчас мне 42.

Докажи. Я программирую на ассемблере с 11 лет, сейчас мне 42.
Детка, я в индустрии 1.5 раза больше времени, чем ты.

С 11 лет в индустрии? Нуну ))))))

Речь, на секундочку, о коммерческом опыте, который вы сможете хоть чемто подтвердить, а не ваши очередные россказни. Программировали бы реально на ассемблере хоть чтото более-менее серьезное вообще в своей жизни, то не пороли бы подобную чушь.

Ну попробуй, поелозь, если не слабо!

Ну так уже. Или не заметили? :

Проигрыш 4 раза на 1 килобайтной табличке, которая уж точно поместится в кэш. При этом я даже упростил код, подавая на вход только лишь значения 0..1023.

Вобщем я так понимаю продолжать этот балаган далее смысла не имеет. За сим откланиваюсь.

Проигрыш 4 раза на 1 килобайтной табличке, которая уж точно поместится в кэш. При этом я даже упростил код, подавая на вход только лишь значения 0..1023.

Тест где? Одному мышевозителю известно что ты там написал. Такое же как и супер быстрый клемпинг, который не работает?

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

В общем предлагаю поступить так. Если у кого то другого кроме вас и вашей (назовём её так) группы поддержки здесь на форуме вдруг закрадутся обоснованные подозрения в истинности моих слов — я тут же предоставлю полный текст программы и ссылку на общедоступную платформу в Интернете, где её можно скомпилировать, запустить и проверить, в их полное распоряжение. А разжевывать именно для вас, уж простите, нет совершенно никакого желания.

Кто не входит в группу поддержки?

Той кого цікавить в першу чергу істина, а не особистість що її висловила. Ви ж підтримуєте Майка попри все (в цій темі а також і в інших) виходячи очевидно з міркувань особистої лояльності та солідарності. І тому я обґрунтовано вважаю що на істину вам начхати.

В цій темі вище вже були контрінтуїтивні результати бенчмарків. І є правило, що оптимізувати перформанс потрібно за результатами бенчмарків на цільовому залізі. Бо інакше можна, навпаки, сповільнити програму. Тому я за цифри, котрі покажуть, хто правий.

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

А с чего тебе верить на слово? Наоборот, от того что ты тут написал нужно перепроверять от и до.

Равно как и представить свои собственные выкладки в легко воспроизводимом виде.

Открой, например, исходники libjpeg и наслаждайся тем же самым подходом с лукап табличками, потому что они тоже протестировали и нашли его самым быстрым способом. Можешь взять базовые исходники tinyjpeg и переделать свой код клампа, который ты там можешь найти через look-up table и посмотреть разницу.

Но продолжать кушать кактус упорствовать вопреки всей очевидности истины — это сколько угодно.

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

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

Удачи в своей дремучести.

от того что ты тут написал нужно перепроверять от и до.

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

Открой, например, исходники libjpeg

1) Это ваш эталон и последнее слово в индустрии?
2) Вы уверены что правильно всё поняли? Прегенерированные таблички иногда используются, и даже в некоторых случаях это дает выигрыш в производительности, о чем упоминал в том числе и я (хотя бы вот здесь: dou.ua/...​ign=reply-comment#1859048). Но это совсем не тот случай :)

Ты явно чего-то не понимаешь фундаментального

Удивительно, но процессор (и не один) со мной согласен и показывает проигрыш в 4-6 раз (на разных платформах) в даже самых примитивных табличках по сравнению с элементарными математическими вычислениями в регистровой (не путать с registered) памяти. С пониманием принципов работы ветвлений (аналогично, постигаются с первых же шагов в ассемблере) у вас также, как видно, сплошное огорчение.

я бы его взял и сказал, что он самый быстрый, но это не так

Как в теме с павутиною-web (см. dou.ua/...​ign=reply-comment#1890074) вопреки всей очевидности даже собственных цитат? Очень смешно ))))))

А вот ты в своей упоротости спорить с очевидными вещами просто поражаешь.

Плохо вы освоили хуцпу (впрочем, как и все прочее). Откровенно не дотягиваете. Тренируйтесь еще.

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

То есть люди в фейсбуке и гугле оптимизирующие код по результатам микро-бенчей и макро-бенчей (профайлинг продакшена) — занимаются фигнёй?

Добрий вечір, хлібороби. Вирішили вклинитись в розмову, невловивши її зміст?

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

Ну наконец-то ты признал, что после изучения ты уже не следил за развитием процессоров. Это именно то, что я говорю, тебя заморозили лет на 20-25.

Удивительно, но процессор (и не один) со мной согласен и показывает проигрыш в 4-6 раз (на разных платформах)

Бла-бла-бла, тесты где, Склифосовский?

Ну наконец-то ты признал,

Продовжуємо балуватись на очі?

Выше в теме вчерашние результаты тестов.

Потому что еще в детском садике учат что обращение к памяти по индексу работает медленее чем к значению в регистре, Карл! Это настолько очевидно и 100500 раз перепроверено что как бы даже нифига не смешно получается когда вы заявляете

В процессоре есть такая штука, как кеш. Если к каким-то адресам памяти недавно было обращение, они с большой вероятностью будет в кеше процессора и последующие обращения к ним будут идти в кеш, что намного быстрее «честного» обращения в память.

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

Вот тут говорится, что в Skylake 32КБ кеш памяти (чего достаточно для хранения всей таблицы), также что обращение к L1 кешу занимает всего 4-5 тактов, что может быть быстрее битовой и арифметической магии на регистрах.

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

Всё правильно, но есть такой ньюанс — современные интеловские процессоры как и ARM используют многоступенчатое пред-выполнение кода. Например, если чтение из памяти — это единственная команда чтения на 3-4 остальные команды в коде, то к моменту выполнения команды чтения данные будут уже загружены из кеша, что будет 1 или 0.5 такта. Если же тупо долбить чтением, то производительность просядет. Запись в память организована по другому принципу, сразу во временный кешлайн, что будет около 1 такта. Вот и получается, что даже для такого кода:

       r = (y + add_r) >> SCALEBITS;
       *p++ = clamp(r);
       g = (y + add_g) >> SCALEBITS;
       *p++ = clamp(g);
       b = (y + add_b) >> SCALEBITS;
       *p++ = clamp(b);

Операций между вызовами (инлайнами) clamp() будет достаточно, чтобы эта операция была условно-бесплатной. А вот если задействовать битовую магию, то в идеальном случае 1 такт на команду. И даже 4 команды будут в 4 раза медленее выборки из памяти, причём, т.к. все команды работают в одном ALU домене с одними регистрами, то это убьёт любое распараллеливание.

Например, если чтение из памяти — это единственная команда чтения на 3-4 остальные команды в коде, то к моменту выполнения команды чтения данные будут уже загружены из кеша, что будет 1 или 0.5 такта.

Я понимаю что доступ к кешу быстр, но не могу понять как он может быть настолько быстр, при косвенной адресации. Как это может быть при прямой — это очевидно.

Так адреса уже вычислены заранее. Интел говорит, что любая операция загруки регистра из памяти стоит одинаково с точки зрения микрокода. Это справедливо для всех процессоров на базе Nehalem архитектуры, начиная с 2008 года. Чем ближе к сегодняшнему дню, тем быстрее работа с памятью, но принципы работы процессора одинаковые, отличаются только размеры внутренних блоков и параллелизация.

Какие материалы можешь посоветовать, чтоб понять как это все работает? Интересует что-то что написано более мене понятным доступным языком для простых смертных

Интересует что-то что написано более мене понятным доступным языком для простых смертных

Тогда я бы посоветовал только Playboy, Hustler, Penthouse — там мало текста и много веселых картинок.

Этого добра у меня есть в избытки. Хотелось бы больше подробностей о работе CPU, чем можно почерпнуть из вышеуказанных источников.

Тогда забудь о доступном языке. Начни с wikichip’а, например по skylake: en.wikichip.org/...​tectures/skylake_(client

Они реально информацию по крупицам стаскивают в одно место, внизу есть списки источников, вот с ними и работать.

Ну вот ... придётся ехать в библиотеку...

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

Майк в своих экспериментах тупо запретил вытиснение

Дело не в экспериментах. Если мы боремся за скорость и хотим видеть максимальную производительность, когда надо, то логично предположить, что приложение будет запущено на отдельном ядре с высоким приоритетом.

В процессоре есть такая штука, как кеш

Да вы что? Надо же, никогда не слышал...

Если к каким-то адресам памяти недавно было обращение, они с большой вероятностью будет в кеше процессора и последующие обращения к ним будут идти в кеш, что намного быстрее «честного» обращения в память.

Регистры работают как бы немножечько быстрее чем даже кеш. Или для вас это тоже новость?

что может быть быстрее битовой и арифметической магии на регистрах.

Неужели?

Регистры работают как бы немножечько быстрее чем даже кеш.

для спецов в Turbo Pascal 5, проспавших лет 15.

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

внеочередное исполнение;
переименование регистров;
объединение нескольких команд в одну.

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

предсказатель переходов;
кэш;
конвейер (используется во всех современных суперскалярах);
одновременая многопоточность (SMT) — одновременное исполнение инструкций нескольких независимых потоков в каждом такте на одновременно работающих конвейерах суперскалярного процессора.
...
Пе́нтиум — торговая марка нескольких поколений микропроцессоров архитектуры x86, выпускаемых корпорацией Intel с 22 марта 1993 года.
Основные отличия от процессора 486
Суперскалярная архитектура....

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

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

Та же самая таблица сложения — зачем думать в двоичной системе, когда можно думать в 256-ричной? Это та же двоичная, но поддержанная таблицей значений. Мало того, обращение к ней даже не потребует переключения транзисторов, часто используемые таблицы можно прошить намертво. А ещё существенно сократит площадь элемента на кристалле, настолько, что этими таблицами можно сотни графических ядер накормить. Больше скажу — поскольку значения прошиты намертво, можно пережигать путь к дефектным строкам, и раскрывать вместо них путь к резервным — и всё в автоматическом режиме, прямо во время тестирования. Разрешение иметь дефекты с определённой вероятностью снова снижает площадь элемента на кристалле, без каких-либо дополнительных затрат.

PS. Я совсем не прогер на низком уровне. Но часть моего образования включает древнее железо. И когда я учился, актуальной была задача ускорения АЦП-ЦАП преобразований. Так вот, по сей день дешевле всего обходятся таблицы и им подобные элементы банальнейшего распараллеливания.

Простой пример: как дёшево и быстро взять аналоговое значение с точностью до 32 бит? Неправильный ответ — построить таблицу на 32 бита, то есть 4млрд аналоговых значений. Правильный ответ — построить 4 таблицы на 8 бит. Сначала делается огрубление сигнала по шкале от 0 до 255, оно, умноженное на заданную величину (в аналоге), СРАЗУ подаётся на узел сравнения (на точных устройствах таких узлов вдвое больше, чтобы снизить погрешность не теряя скорости), и аналоговая разница уже поступает на следующий компаратор.
Применение — поначалу звуковые устройства, потом и более быстрые волны стали таким образом анализировать.
Дополнительное ускорение, если нужно, берут с упрощения усилителя. Сделать аналоговый усилитель, который имеет линейную характеристику в узком диапазоне, достаточно просто даже на одном транзисторе. А настройку точности делает программный код — в момент инициализации (который происходит раз в какое-то время), на устройство приходит поверяющий сигнал уже с точного источника опорного напряжения — оцифровывается разница, и ей управляется сдвиг.

За счёт чего ускорение без потери точности: за счёт того, что устройство регулярно поверяется более медленным, но точным узлом измерения. А уже за интервал между поверками (и поправками) устройство делает триллионы измерений.
Если нужно максимальное удешевление, делают даже 1-битные измерители. Но тогда всё же точность и скорость падают (незначительно, в сравнении с удешевлением). Обычно компромис останавливается на 4-битных.

PPS. Сорри если моё знание мат.части малость устарело, я давно не вникал в тему. Но думаю мало что меняется в этой теме, и через 10 лет проблема удешевления будет актуальной.

Потому я очень удивлён отсутствию в современных процах железно реализованных таблиц умножения.

А может, они и есть, откуда ты знаешь?
Но в большинстве случаев сейчас самый дорогой по вентилям, но быстрый вариант — матрица AND-вентилей с деревом сумматоров над ними. Например, в случае умножения 32*32 это будет 1024 AND’ов и дерево из 63 сумматоров, которые постепенно сходятся в одну сумму (6 каскадов сложений, выполняемых параллельно), складывая числа:

(a[0][31]) << 31
(a[1][31], 0, a[0][30]) << 30
(a[2][31], 0, a[1][30], 0, a[0][29]) << 29
...
(a[30][31], 0, a[29][30], 0, ..., a[1][2], 0, a[0][1]) << 1
(a[31][31], 0, a[30][30], 0, ..., a[1][1], 0, a[0][0])
(a[31][30], 0, a[30][29], 0, ..., a[2][1], 0, a[1][0]) << 1
...
(a[31][1], 0, a[30][0]) << 30
(a[31][0]) << 31

то есть каждое входное число для сумматора набирается по диагонали выходной матрицы. Можешь нарисовать сам: возьми матрицу с row и col от 0 до 31, на ней все диагонали, перпендикулярные направлениям, на которых row+col=const — получишь 63 диагонали (крайние — по 1 элементу), на которых будут собираться данные.
За счёт того, что сумматоры тоже параллелятся, и каждый из них работает ну где-то треть-половину такта — получаем 2-3 такта на всё умножение — достаточно близкий результат к тому, что показано для x86.

И по элементам это влезет в сотню тысяч — нестрашное на сейчас число — а если бы это делали на чистой матрице 32*32, было бы этак 250 миллиардов — сейчас такое ещё не осиливают; если 4 штуки 16*16 — 10 миллионов — тоже много. То есть сразу за таким подходом — сумматоры по диагоналям — начинается неоправданный рост по мощности.

А ещё существенно сократит площадь элемента на кристалле, настолько, что этими таблицами можно сотни графических ядер накормить.

Нет, полная матрица не экономит — будет чудовищная затрата на объём ПЗУ.

Правильный ответ — построить 4 таблицы на 8 бит.

Или 8 по 4, или 7 по 5, вариантов много... но в принципе, да, где-то так и делают, насколько я понимаю.

Проблема в том, что это вентиля. Вентиль греется в момент переключения, и распределённым по кристаллу ты его не сделаешь.

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

Кстати, с кеш-памятью вероятно стоит поступить так же. По крайней мере Интел доказала, что L3 кеш вполне даже ценная штука. А вот что можно в буквальном смысле вывести решение простой арифметики за пределы проца, заставляя выполниться прямо на кеше — такого ещё не делали, и вероятно за таким подходом будущее. Просто уже потому, что разделение на составляющие даёт удешевление и экономию, за счёт раннего тестирования и более дешёвого производства: что в таблицах что в кеше, допустимо делать резервирование строчек памяти ради компенсации брака, и если строчка показала сбой — вместо неё прямо на тестировочном оборудовании переназначить соседнюю. В картах памяти давно уж так и поступают — удешевление легко заметить.

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

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

ты не там смотрел. По моей информации целочисленное умножение таблицами 8×8 и 16×16 — норма. В ЦСП АД об этом тупо в даташитах написано. В других процессорах тоже используется но подробностей не помню.

мдя, а я не отважился, смотрел на эти танцы с битами, «на кой?», но морочится с битами — это ж вроде как признак крутизны :)

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

давно то было... «в детском саду», в котором меня учили что никаких таких обращений по индексу массива не существует. как и самих массивов :)

кто уже помнит классику
как быстро проиницализировать массив одинаковыми элементами?...

как быстро проиницализировать массив одинаковыми элементами?...

В моё время изпользовали floating point регистры (double), которые были 64 бита, когда всё остальное было 16 и 32. 0 и 0.0, если мне не изменяет долговременная оперативная память, имели одинаковую репрезентацию в памяти, т.е. все нули.

для Z80 рассказывали, и помнится что и для x86 годится:
устанавливаем стековый регистр на конец «массива»
и pushим.
переключаемся ессно потом назад.

как-то так.

погуглил:
...Ещё POP <все регистры>; PUSH <все регистры> и так в цикле (только SP переставляли)
все обсуждение caxapa.ru/456050

для Z80 рассказывали, и помнится что и для x86 годится:
устанавливаем стековый регистр на конец «массива»
и pushим.
переключаемся ессно потом назад.

Много слышал, но ни разу не приходилось так делать :)

помнится, но смутно,
я такую очистку памяти у своего аллокатора памяти делал.

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

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

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

Для облегчения задачи можно добавить ещё одно условие — входное значение не может превышать более чем в два раза выходное. Т.е. если мы делаем на выходе 0..255, то входное значение не может быть за пределами скажем —255..+511.

Кажется я нашел идеальное решение:

switch(i) {
case -255: return 0;
....
case 511: return 255;
}

согласно моему опыту портянку выше gcc должен просто нереально заоптимизировать.

Буду раз узнать результаты бенч-марка.

Дай полный код :), мне лень генерить 768 строчек %) Кстати, раньше Борланд С/C++ понимал последовательные case в свиче и делал сам табличку в памяти, если мне не изменяет память от 16 элементов.

Сейчас на другой машине, поэтому другие числа, не те, что были в другом посте, переделал все тесты по-новой:

87 ms — lookup table
96 ms — dumb if-else-if
126 ms — mega switch

Что забавно, когда эта функция инлайновская, то скорость компиляции модуля упал с 0.01 секунды до 8 секунд! Компилятору от мегасвича стало очень плохо.

Когда я вынул посмотреть что сделал оптимизатор без инлайна, gcc с -O3 лажанулся капитально — он создал таки табличку, но табличку переходов вместо данных и сделал 768 функций, каждая из который возвращает только одно значение :)

leaq    .L4(%rip), %rdx
movslq  (%rdx,%rdi,4), %rax
addq    %rdx, %rax
jmp     *%rax

...

.L259:
    movl $-1, %eax
   ret
.L260:
    movl $2, %eax
    ret
.L7:
    movl $3, %eax
    ret
.L5:
    movl $1, %eax
    ret
.L3:
    xorl %eax, %eax
    ret
gcc с -O3 лажанулся капитально — он создал таки табличку, но табличку переходов вместо данных

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

Кстати я протупил и попросил тебя генерить ту ленту кода, ведь можно использовать gcc трюк с switch/case ranges:

unsigned char clamp(int i)
{
        switch(i) {
             case -255 ... -1: return 0;
             case 0 ... 255: return i;
             case 256 ... 511: return 255;
        };
}

Но gcc оптимизатор сгенерил код как под кальку с тупого if-else-if, только на ассемблере:

clamp:
.LFB23:
        .cfi_startproc
        cmpl    $255, %edi
        jg      .L3
        testl   %edi, %edi
        movl    %edi, %eax
        jns     .L1
        xorl    %eax, %eax
        cmpl    $-255, %edi
        jl      .L2
.L1:
        rep ret
        .p2align 4,,10
        .p2align 3
.L2:
        rep ret
        .p2align 4,,10
        .p2align 3
.L3:
        cmpl    $511, %edi
        jg      .L2
        movl    $-1, %eax
        ret
        .cfi_endproc

Т.е. оптимизатор switch/case у gcc по-ходу отбит наглухо. gcc -v:

gcc version 7.4.0 (Ubuntu 7.4.0-1ubuntu1~18.04.1)

Тоесть по скорости теже 96 ms?

Т.е. оптимизатор switch/case у gcc по-ходу отбит наглухо. gcc -v:

Так и есть

Тоесть по скорости теже 96 ms?

98 ms, чуть хуже, потому как исходный if-else-if gcc компилирует с использованием conditional move инструкций. Те же яйца, только в профиль, в общем.

я тут вычитал что такая вещь как __builtin_unreachable() влияет на то как компилятор оптимизирует switch(). Насколько я понял поддерживается как гцц так и шлангом. Насколько я понял то ее нужно добавить в ветку default в обсуждаемом свиче.

йокарный балет! вам что, как индусам за код построчно платят? )))

Кстати, раньше Борланд С/C++ понимал последовательные case в свиче и делал сам табличку в памяти, если мне не изменяет память от 16 элементов.

Последние лет 10 это дает обратный эффект, и поэтому гцц использует радикально другие оптимизации.

Так и есть.

12 лет прошло с тех пор, может что-то уже совсем зафакапили нафиксили.

Я тут пораскинул мыслями и у меня получилось нечто весьма интересное:

#define clamp(x) ({ \
	typeof(x) val = (x); \
	unsigned char c = (val < 0 ) ? 0 : val; \
	(val > 255 ) ? 255 : с; })


unsigned char clamp2(int i)
{
	return clamp(i);
}

ассемблерный листинг:

unsigned char clamp2(int i)
{
    return clamp(i);
   0:   81 ff ff 00 00 00       cmp    $0xff,%edi
   6:   b8 ff ff ff ff          mov    $0xffffffff,%eax
   b:   7f 0a                   jg     17 <clamp2+0x17>
   d:   85 ff                   test   %edi,%edi
   f:   b8 00 00 00 00          mov    $0x0,%eax
  14:   0f 49 c7                cmovns %edi,%eax
}
  17:   f3 c3                   repz retq

Сделай, плиз, бенчмарк именно с макросом clamp(x) ?

96 ms, как и в случае с if-else-if.

Ок, а что ты думаешь на тему вот такой немного грязноватой оптимизации?

Суть в том что предыдущий код компилился в 6 инструкций, одна из которых условный переход. Этот имеет шансы скомпилится в 4-ре, причем без ветвлений.

#define clamp(x) \
do { \
    x = ( x < 0 ) ? 0 : x; \
    x = ( x > 255 ) ? 255 : x; \
} while(0)


unsigned char clamp2(int val)
{
    clamp(val);

    return val;
}

А на другой чаше весов просто выборка байта из памяти:

leaq    arraycl(%rip), %rax
movzbl    (%rax,%rdi), %eax

Причём первая команда процессора во время инлайна уходит во вспомогательный регистр с номером и хранится там до скончания веков, эээ, выполнения функции. Остаётся одна movzbl.

Смотрим по скайлейку, например, и видим, что:

Reciprocal throughput: The average number of core clock cycles per instruction for a series of independent instructions of the same kind in the same thread — 0.5.
Latency: от нуля до какого-то значения.

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

Если рассматривать самый «лёгкий код» выше:

cdq - latency 1
not edx - latency 1
and eax, edx - latency 1 
and eax, 0FFh - latency 1

Итого выборка из памяти будет в 2-4 раза быстрее в среднем по палате. У AARCH64 latency для выборки будет 4, для логических операций 1-2. Код выше на AARCH64 будет из 5 команд. Т.е. всё равно быстрее, если даже конвеер забит. А если свободен, то загрузка значения из памяти начнётся за 4 такта до её выполнения и будет выполнена за 1 такт, когда придёт время, при условии что остальной код память не долбит, а это именно так.

Для упрощенного варианта (

—255..+511.

) вот такая билеберда вышла —

int result = !(initial >> (sizeof(int) * 8 — 1)) * (((initial >> 8) * 255) | (initial & 255));

Обновил свой вариант решения, теперь поддерживается весь интовый диапазон.

int clamp255(int initVal)
{
    auto getMaxBit = [](int value) {return (value >> (sizeof(int) * 8 - 1)) & 1; };

    int result = ((initVal >> 8) & 0xFFFFFF) * -1;
    result = getMaxBit(result) * 0xFF;
    result |= ((initVal << 1) >> 1) & 0xFF;
    result *= getMaxBit(initVal) ^ 1;

    return result;
}

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

но тут же отбрасывают его вследствие вбитого кувалдой ограничения тех древних олдскульных времён

Да, похожий эффект.

Подсмотрел, если все переменные типа int, то без фунции, обычный оператор деления:
delay_position = buffer_position — delay;
delay_position = delay_position — (delay_position / buffer_length) * buffer_length;

Исправлю себя, оказывается целочисленное деление для отрицательных чисел работает не так, как я ожидал:
delay_position = buffer_position + buffer_length — delay;
delay_position = delay_position — (delay_position / buffer_length) * buffer_length;

выше был код для первого примера, а вот для второго:
buffer_position = buffer_position — (buffer_position / buffer_length) * buffer_position;

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

delay_position = buffer_position — delay;
delay_position = delay_position — INT(delay_position / buffer_length) * buffer_length;
Давно с Си не работал
INT() - целая часть числа, может функция не совсем так называется

delay_position = buffer_position — delay;
if (delay_position < 0)
{
delay_position = buffer_length + delay_position;
}
В голову почему-то сразу типа такого приходит (ассемблерное прошлое с поправкой на С++ дает знать):
delay_position+=(delay_position&(-INT_MAX-1))/(-INT_MAX-1)*buffer_length;
Проверить не могу — под рукой нет студии %), но смысл идеи понятен (надеюсь %).
Вообще смахивает на задачки преподавателя студентам.
Вообще смахивает на задачки преподавателя студентам.
Как я уже объяснял, мне нужен был красивый и читабельный код вместо моего нечитабельного. Я это и получил.
В голову почему-то сразу типа такого приходит (ассемблерное прошлое с поправкой на С++ дает знать):
-INT_MAX-1
К, сожалению, будет равно 0×80000000.

Только почему «к сожалению»?
Да, и где тут читабельный код? Пролистал все комментарии, но такого не нашел :) Может его сразу в главное сообщение, чтоб всем было видно?

Только почему «к сожалению»?
Это писалось для вашего старого кода до модификации :) теперь неактуально.

Понятно. Хотят там пару минут прошло между редакциями всего:) — забыл привести к 1-це.
ПС: на ассемблере проще всё это делается как-то — %))), вообще без делений-умножений.

Да, и где тут читабельный код? Пролистал все комментарии, но такого не нашел :) Может его сразу в главное сообщение, чтоб всем было видно?
Вот
dou.ua/...-comment#406039
dou.ua/...-comment#406026

Я так понял, ссылки переставлены?
dou.ua/...-comment#406039
Мина. О ней там же и написано. Но от нее достаточно просто избавиться.

dou.ua/...-comment#406026
В плане циклического буфера да (и даже правильней). И читабельность сохраняется. Но в плане эквивалентности приведенному в топике коду — нет. Эквивалентность была бы, если вместо if было бы while. И то при соблюдении некоторых начальных условий.

Нет, этот результат зависит от железа. Отрицательные числа, в отличие от беззнаковых, имеют сильно разное двоичное представление.

2’s complement — standard de facto. en.wikipedia.org/wiki/Two’s_complement

Сейчас мало кто в здравом уме рискнёт реализовать что-то другое.

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

Обратный код умер совсем. Были несколько лет ещё эмуляции каких-то древних процессоров от CDC, но и они уже неактуальны.
Фактически единственное, что от него осталось в мире — контрольные суммы IPv4/TCP/UDP.

Прямой код очень активно используется, но в плавучке и длинной целочисленной арифметике. Например, в GMP — MPN слой работает с целыми без знака (от 0), а поверх него MPZ строит знаковые значения. Там это потому, что со знаками в длинной арифметике слишком задалбываешься — на каждом лимбе надо рассматривать до 4 вариантов поведения вместо одного.

С одиночными же значениями — дополнительный код всех победил, живых альтернатив не осталось.

%), но смысл идеи понятен (надеюсь %
Необычный формат строки

1) Может так, хоть не хочется думать о переполнениях

delay_position = (buffer_length + delay_position — delay) % buffer_length;

2) Навскидку согласно логике, не проверял реально ))

buffer_position = (~(buffer_position/buffer_length)/~0)*buffer_position;

buffer_position = min(buffer_position, buffer_length) % buffer_length

min без бранчинга можно сделать так:
min(x,y) = y ^ ((x ^ y) & -(x < y));

(x < y)
Это и есть бранчинг. Ну можно min() реализовать и без сравнения. Но там будет около 8-9 операций.

его можно сделать через (x — y) >> (sizeof(int) * kBitsInByte) — 1
если х < y знак вычитания будет равен 1 который в результате сдвига станет 0 либо 1.
граничные условия не проверял

А куда делся delay ?

Второй вопрос, наверное, так бы решал:

template < typename _TType >
void reset_if_limit(_TType& val, _TType& limit)
{
val &= val — limit >> std::numeric_limits<_TType>::digits;
}
...
reset_if_limit(buffer_position, buffer_length);

limit >> std::numeric_limits<_TType>::digits;
Очень неочевидно. Если брать GNU libstdc++, то на сколько я помню, то оно содержит inline max() который реализован через ternary conditional operator, что является сравнением и соответственно бранчем.

По последнему стандарту там всё хорошо: static constexpr int digits;
(т.е. всё будет во время компиляции вроде как)

Правда для unsigned типов мое решение не работает.

Сорри, ошибся, невнимательно посмотрел на код. Для int: std::numeric_limits<int>::digits будет содержать 31 на 32ух битовой платформе. То вызов:

reset_if_limit(13, 27); будет выглядеть как:

val&=13 — 27>>31; Ну а val&=13 не приведёт к результату.

val&=13 — 27>>31; Ну а val&=13 не приведёт к результату.
по-идее же сначала выполнится subtraction, потом right shift. А потом val&=1, что равно val.
по-идее же сначала выполнится subtraction, потом right shift.
en.cppreference.com/...ator_precedence
Да, опять ошибся, bitwise shift — седьмое место, addition and subtraction — шестое. Чего-то запамятовал именно эту очередность.
А потом val&=1, что равно val.
Там будет −1, а val&=-1 то же самое, что и val.

Майк, а ежели так

int buffer_position = ((unsigned(buffer_position — buffer_length)) >> 31) * buffer_position;

на стандартной 32-битке делает что ты хочешь :)

на стандартной 32-битке делает что ты хочешь :)
размер int’а неизвестен

никто не мешает делать «правильно» — (sizeof(int) * CHAR_BIT — 1). Я показал идею, а уж как 31 заменить на «чтобы всегда работало» он догадается.

Так я так и делал :)
delay_position+ = ((delay_position & ~(((ALuint)-1) >> 1))>>(sizeof(ALuint)*8-1)) * buffer_length;

Просто захотелось более читабельного кода :) Заодно и более оптимального.

Заодно и более оптимального.
А в абстрактной машине сдвиг сильно быстрее умножения и деления?

Да, но это вторично в данной задаче. Там просто по соседству ведутся дикие вычисления с плавающией запятой и любая целочисленная операция кажется однотактовой по сравнению с теми операциями. Т.е. грубо говоря 1234567 тактов против 1234560 тактов не принципиально :)

таки можно без умножения/деления, только +,-,сдвиги, логика
buffer_position = buffer_position >> (((((unsigned)(buffer_position — buffer_length)) >> (sizeof(int) * CHAR_BIT — 1))) + UINT_MAX)
как-то так, но так нечитаемо — и не уверен что правильно)

Может стоит выкинуть вычисления с float и использовать fixed point (местами с удвоенной точностью) ?

Для музыки, тем более, судя по параметрам (44.1kHz, 8 каналов), музыки для широких масс, — более чем достаточно. А половину (а то и больше) тактов точно уберете :).

Может стоит выкинуть вычисления с float и использовать fixed point (местами с удвоенной точностью) ?
А смысл? Например, умножение на FP быстрее, чем для integer. И т.д., то есть выигрышь не всегда однозначен. Ну и всё хранится в float формате и данные живут от начала и до конца во float. От fixed point компиляторам часто срывает башню на счёт оптимизации, особенно, если использовать не 16:16 (32:32), а 8:24, 16:48 и т.п.

Да, для Интел все-таки легче/лучше с float. Это я поторопился с высказыванием :).

Про CHAR_BIT вы правы, спасибо. Забыла, что на некоторых DSP CHAR_BIT может быть 16 или 32 вообще. Экзотика, конечно:)

На DEC Alpha было 24. Но это было давно. Просто решил что раз сделали замечание, то следует раскрыть его со всеми подводными камнями :)

На DEC Alpha было 24.

Может, таки 64? До введения BWX extensions в массы.

Хм, походу да, ошибся. Но я точно помню, что был какой-то проц, который ходил в конкурентах раннего Pentium-а, а потом здох и было у него 24 битная арифметика. А может мозг чего скомпоновал :)

(((unsigned)(buffer_position+1-buffer_length))>>???)*buffer_position
//зависит от наличия команд; (sizeof(int) * 8 — 1) добавляет дополнительные действия

(sizeof(int) * 8 — 1) — вычисляется на этапе компиляции, это constant expression. Так что не добавляет.

О, рад тебя видеть! :)

Взаимно. Полагаю удалось уложиться в 3 операции ;) gcc выдает что нужно, полагаю твоя GPU штуковина имеет обычный набор ALU и сделает тоже самое :)

Не, это hobby project :) Обработка звука, мейнтейнер попросил не коммитить код, который содержит бранчи в main loop. То, что я закоммитил имело плохую читаемость и я каждый раз проходя мимо хотел это переписать. Ну а уходить в Новый Год с незавершенными делами не хотелось :)

что-то мне приведённые здесь примеры совсем не кажутся удобочитаемыми...Или Вы под «плохой читаемостью» подразумеваете наличие условий в коде?..

Посмотрите постановку задачи. Не должно быть сравнений на определённом участке кода, который повторяется десятки миллионов раз в секунду. То, что получилось без сравнений, должно иметь удобоваримый вид. Оба предложенных решения для первого варианта — Sviatoslav Yakymiv, для второго — John Doe имеют гораздо более читабельный вид, чем мой код. А это именно то, ради чего я создал эту тему.

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

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

А имеются какие-нибудь допустимые границы значений вводных данных? Потому что например:

int main()
{
int buffer_position = 1;
int delay = 103;
int buffer_length = 30;

int delay_position = buffer_position — delay;
if (delay_position < 0) {
delay_position = buffer_length + delay_position;
}
std::cout << delay_position << std::endl;
}

выведет совсем не то, что:

int main()
{
int buffer_position = 1;
int delay = 103;
int buffer_length = 30;

int delay_position = (buffer_position — delay + buffer_length) % buffer_length;

std::cout << delay_position << std::endl;
}

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

:D Привет. А вот ты так уж точно «внезапно» — в теме про плюсы, к которым у тебя стойкое отвращение :)

Мне интересно, о чем Майк пишет =)

Друга частина за 5 операцій: buffer_position = buffer_position * !!!(buffer_position / buffer_length)

Я не люблю логические операции вплетать в арифметические, при использовании !!! мы всего лишь приведём к логическому отрицанию в той форме, в какой её видит компилятор согласно стандарту. Ну а если добавить +1 к buffer_position, то будет уже 6 операций.

!!! поверне нам 0 або 1, яка використовується як множник для позиції.
Не зовсім розумію для чого додавати 1.

Не зовсім розумію для чого додавати 1.
Ну для примера, размер буффера 32, а последняя валидная позиция 31.

Для bufer_position == 31
buffer_position = 31 * !!!(31 / 32) = 31

Для bufer_position >= 32
buffer_position = 32 * !!!(32 / 32) = 0

Мені здається, що все правильно. Але я вже дали кращу відповідь за 3 операції.


Для bufer_position >= 32
buffer_position = 32 * !!!(32 / 32) = 0
buffer_position не будет больше 31.
buffer_position не будет больше 31.
тоді для чого ця перевірка?
if (buffer_position >= buffer_length)

Моя вина. Перед этим идёт buffer_position++; Т.е. 32 оно будет иметь только до проверки.

Тоді погоджуюсь. 6 операцій.

Якщо ви впевнені в тому що buffer_position >= 0 && buffer_position < buffer_length і тільки в одному випадку buffer_position == buffer_length, то можна зробити все за 1 операцію (+ операція інкремент).

Вторую часть так еще можно попробовать...

buffer_position = -buffer_position * ((buffer_position — buffer_length)>>(sizeof(int)*8 — 1));

вторая часть

int pos_m, pos_d;
        
pos_m = pos % len;
pos_d = pos / len;
pos -= pos_d * len + pos_m * (!!pos_d);

Першу частину коду можна переписати наступним чином: delay_position = (buffer_position — delay + buffer_length) % buffer_length;

Круто! Просто нет слов, три арифметические операции!

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

(buffer_position — delay) & (buffer_length — 1)

можно еще изначально делать buffer_length = 2^n — 1 )

смысл? Или это был юмор?
Или −1 к формуле не относится?

Изначально так и было, но, к примеру 44100Hz * 2.0f периода * 0.4f секунды = 35280 -> next power of two -> 65536.

Итого мы выкидываем 65536 — 35280 = 30256 * sizeof(float) * 8 каналов = 968192 байт впустую только на одном эффекте.

И как я уже говорил ниже, когда идут большие вычисления с floating point, то одиночный & или % для целых чисел уже не играет особой роли.

А чтобы скорость стала действительно космической — нужно оперировать данными не больше размера cacheline за раз, но это уже другая тема :)

Следующим вопросом пойдет специфика архитектуры, наборы команд, величина кешей))) — только тему придется в ASM переименовать)

На некоторых архитектурах % по времени выполнения стоит значительно дороже ветвлений
А ещё по-идее и значительно(может даже на порядок) дороже простых операций сложения, и битовых операций.

Можно ещё так сделать чтобы на буфер не закладываться:

int delay_position = buffer_position — delay;
delay_position += delay_position >>
std::numeric_limits<decltype(delay_position)>::digits & buffer_length;

А ещё по-идее и значительно(может даже на порядок) дороже простых операций сложения, и битовых операций.
Если взять core в среднем — 40 тиков, nehalem — 26 тиков на деление против 1-3 такта на and/not/xor/or. Но фишка в том, что в суперскалярных архитектурах на ветвлениях идёт основная потеря производительности. Так как перед переходом все микроперации должны быть завершены. и после перехода всё начинается заново. Даже в новейших процессорах с fast recovery after branch misprediction это ударит по out-of-order execution. А это будет больше по времени, чем операция деления, поэтому, среднее время в 40 тиков на деление не имеет большого значения в данном коде. Ведь цель стоит не заоптимизировать код по максимуму, а в том, чтобы он работал быстро, но оставался читабельным.

В конце концов modulo % можно заменить на тривиальное умножение и сдвиг, используя reciprocal multiplication, предварительно подготовив коэффициенты. Тут вообще даже потерей тиков может не быть на современном железе вообще.

Но ваш способ тоже отличный :)

Если взять core в среднем — 40 тиков, nehalem — 26 тиков на деление против 1-3 такта на and/not/xor/or.
Если говорить о последних процессорах, и тем более процессорах Intel то тут, боюсь, смысла в ручной оптимизации такого миниатюрного кода нет. Компилятор все сделает сам, причем может даже в лоб и без ветвлений (например, см. Conditional move instructions).

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

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

Дело как раз не в хитрости инструкций, они все известны, и не в приёмах их использования, они тоже известны. Просто он лучше может контроллировать загрузку процессора. Ведь уже давно всё выполняют микрокоманды, а не команды. Микрокоманды могут использовать блоки ALU напрямую, например, целочисленный умножитель, которых может быть несколько и т.д. Про по-командный параллелизм уже и речи нет.

Например, movq rax, rcx; imulq rbx; sarq 45, r2 могут параллелиться пока есть свободные юниты ALU для их выполнения. А дело компилятора об этом позаботиться.

Если говорить о последних процессорах, и тем более процессорах Intel то тут, боюсь, смысла в ручной оптимизации такого миниатюрного кода нет. Компилятор все сделает сам, причем может даже в лоб и без ветвлений (например, см. Conditional move instructions).
Вот и я о том же. Компилятор лучше знает свою работу, ручная оптимизация слишком дорога. Но на счёт ветвлений — они в коде появляются достаточно часто, поэтому компилятору нужно помогать.

У меня изначально получилось четыре операции: &, ~, >>, *.

Совершенно не знаком с Сями и плюсами. Но по ходу, если есть возможность привести «тру» в 1, а «фолс» в 0, то второй кусок кода можно записать как
int buffer_position = (int) !(buffer_position >= buffer_length)
Правда, это совсем печально будет если позиция меньше длины :)

(buffer_position >= buffer_length)
К сожалению, в коде это будет выглядеть как операция сравнения. Для первого кода у меня получилось четыре арифметические операции, а для второго шесть, но мне кажется, что я всё-равно что-то упускаю.

buffer_position/buffer_length будет 0 или целое

buffer_position *= (int)(1-(bool)(buffer_position / buffer_length))
//true или таки 1 ?)

boolean я бы не использовал вообще, ибо оно построено на операциях !0, а не ноль может быть любым. Итого:

buffer_position*=1-(buffer_position+1)/buffer_length;

Если гарантировать, что buffer_position не будет слишком больше buffer_length, то тогда получаем четыре операции, превосходно! :)

Если не надо делать всяческие «защиты от дурака», то да.

Тогда скорее (buffer_position+1)/buffer_length, да вы правы будет или 0 или 1. Вот только 1 будет только в том случае, когда надо присвоить 0.

buffer_position=((~((buffer_position+1)/buffer_length)) & 1)*buffer_position;

Пять операций: ~, +, /, &, *
У меня шесть операций: +, -, &, ~, >>, *

Да, именно так, лишь читабельность бы чуть улучшить — но это вопрос вкуса и внутренних стандартов, у каждого свои)

Подписаться на комментарии