Оптимизация клампинга.

Программирование на Visual Basic, главный форум. Обсуждение тем программирования на VB 1—6.
Даже если вы плохо разбираетесь в VB и программировании вообще — тут вам помогут. В разумных пределах, конечно.
Правила форума
Темы, в которых будет сначала написано «что нужно сделать», а затем просьба «помогите», будут закрыты.
Читайте требования к создаваемым темам.
Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3896
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Оптимизация клампинга.

Сообщение Mikle » 13.03.2019 (Ср) 18:27

Имеется Long переменная r, может принимать значения не более +-32768, необходимо ограничить её значение до диапазона 0..255.
Наивный способ:
Код: Выделить всё
If r > 255 Then r = 255 Else If r < 0 Then r = 0

Я оптимизировал так:
Код: Выделить всё
r = r * -(r > 0) + (r > 255) * (r - 255)

Стало интересно, можно ли оптимизировать сильнее?

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16170
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Оптимизация клампинга.

Сообщение Хакер » 13.03.2019 (Ср) 23:21

Откуда информация, что второе выражение оптимальнее?
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16170
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Оптимизация клампинга.

Сообщение Хакер » 13.03.2019 (Ср) 23:31

Как и следовало ожидать:
Код: Выделить всё
Public Function ClampCond(ByVal r As Long) As Long
    If r > 255 Then r = 255 Else If r < 0 Then r = 0
    ClampCond = r
End Function


clamp_cond_disasm.png
clamp_cond_disasm.png (3.48 Кб) Просмотров: 321


Код: Выделить всё
Public Function ClampExpr(ByVal r As Long) As Long
    r = r * -(r > 0) + (r > 255) * (r - 255)
    ClampExpr = r
End Function


clamp_expr_disasm.png
clamp_expr_disasm.png (7.39 Кб) Просмотров: 321

Со всеми рискованными оптимизациями:
clamp_expr_brutal_opt.png
clamp_expr_brutal_opt.png (4.78 Кб) Просмотров: 321
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

The trick
Постоялец
Постоялец
 
Сообщения: 554
Зарегистрирован: 26.06.2010 (Сб) 23:08

Re: Оптимизация клампинга.

Сообщение The trick » 13.03.2019 (Ср) 23:48

Можно заюзать арифметику с насыщением (SIMD).
UA6527P

ALX_2002
Мега гуру
Мега гуру
 
Сообщения: 2031
Зарегистрирован: 25.11.2002 (Пн) 20:03

Re: Оптимизация клампинга.

Сообщение ALX_2002 » 14.03.2019 (Чт) 1:33

Сильно не ругайте. Просто захотелось поучаствовать. :roll: Интересно как это в асме выглядит

Код: Выделить всё
Sub main()
   MsgBox clamp(-1000, 0, 255)
End Sub

Function clamp(ByVal value As Long, min As Long, max As Long) As Long
    clamp = IIf(value <= min, min, IIf(value > max, max, value))
End Function

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16170
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Оптимизация клампинга.

Сообщение Хакер » 14.03.2019 (Чт) 1:50

ALX_2002 писал(а):Интересно как это в асме выглядит

Как вызов упаковка всех чисел в 16-байтные VARIANT-обёртке и два вызова функции rtcImmediateIf вот с такой сишной начинкой:
Код: Выделить всё
VARIANT
VBAPI   
rtcImmediateIf(
    VARIANT *pvarExpr,
    VARIANT *pvarTruePart,
    VARIANT *pvarFalsePart
)
{
    VARIANT ret;
    HRESULT hr;

    VARIANT_InitNull(&ret);

    if(fBoolFromVar(pvarExpr) == 0)
    {
        hr = VariantCopyInd(&ret, pvarTruePart);
        HrCheckAndRaiseError(hr);
        return ret;
    }   
    else
    {
        hr = VariantCopyInd(&ret, pvarFalsePart);
        HrCheckAndRaiseError(hr);
        return ret;
    }
}


fBoolFromVar — это целая клоака с обращением к TLS. Она вызывает внутри себя __vbaBoolVar, а оттуда вызывается ErrConvertVarNear, а из неё есть ещё куча вызовов. Сотни (если не тысячи) ассемблерных инструкций. Против менее чем 10, которые изначально собрались оптимизировать (вариант с обычным If).
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

ALX_2002
Мега гуру
Мега гуру
 
Сообщения: 2031
Зарегистрирован: 25.11.2002 (Пн) 20:03

Re: Оптимизация клампинга.

Сообщение ALX_2002 » 14.03.2019 (Чт) 1:53

Хакер, ох ё... А я и не обратил внимания, что у IIF параметры Variant ! (
Пасиб, что ткнул носом )

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3896
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Оптимизация клампинга.

Сообщение Mikle » 14.03.2019 (Чт) 9:24

Хакер писал(а):Откуда информация, что второе выражение оптимальнее?

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

The trick писал(а):Можно заюзать арифметику с насыщением (SIMD).

Само собой, а шейдеры ещё лучше. Вопрос именно про VB код. Впрочем, код на C++, если он без асм-вставок и интринсиков, ведёт себя подобным образом.

Я немного изменил код второго варианта, избавился от унарного минуса, но на быстродействие это не повлияло.
Прилагаю тест, компилировалось со всеми опциями оптимизации скорости.
На AMD FX-6300 получаю 88-90%.
На Intel i7-3740QM получаю 66-67%.

Попробовал такой вариант математики:
Код: Выделить всё
r = (r And (r > 0)) - ((r - 255) And (r > 255))

На удивление - почти никаких изменений, на AMD чуть-чуть ускорилось, на Интел так же чуть-чуть замедлилось.
Вложения
Clamp.zip
(4.82 Кб) Скачиваний: 9
Последний раз редактировалось Mikle 14.03.2019 (Чт) 15:59, всего редактировалось 2 раз(а).

alibek
Большой Человек
Большой Человек
 
Сообщения: 14137
Зарегистрирован: 19.04.2002 (Пт) 11:40
Откуда: Russia

Re: Оптимизация клампинга.

Сообщение alibek » 14.03.2019 (Чт) 12:30

А что такое клампинг? Условные границы, за пределы которых не выходит значение?
А то ведь можно просто битовые операции использовать.
r and 255 чтобы обрезать по 8 битам.
И что-то вроде +255*not(r and &hfffffff0) чтобы присвоить 255 при переполнении 8 бит.
Lasciate ogni speranza, voi ch'entrate.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3896
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Оптимизация клампинга.

Сообщение Mikle » 14.03.2019 (Чт) 12:42

alibek писал(а):А что такое клампинг?

То, что выходит за границы, должно быть им приравнено.
alibek писал(а):r and 255 чтобы обрезать по 8 битам.

Тогда 256 станет нулём, а должно быть 255.
alibek писал(а):что-то вроде +255*not(r and &hfffffff0) чтобы присвоить 255 при переполнении 8 бит.

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

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3896
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Оптимизация клампинга.

Сообщение Mikle » 14.03.2019 (Чт) 16:05

У меня был вариант на Subах, переписал на Function, как у Хакера, стало быстрее, и теперь If на Интеле отстаёт более, чем вдвое, на AMD несколько меньше.
Перезалил закачку в тот же пост.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16170
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Оптимизация клампинга.

Сообщение Хакер » 14.03.2019 (Чт) 17:34

Исходный тест:
If: 0.0629
Math: 0.032456
Logic: 0.034268


Но я не удержался от искушения (хоть это и против правил) и сделал так:
If: 0.026896


Код подправлен в дизассемблере:
clamp_cmov.png
clamp_cmov.png (3.01 Кб) Просмотров: 254
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16170
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Оптимизация клампинга.

Сообщение Хакер » 14.03.2019 (Чт) 18:28

Более объективный способ замера:
Clamp_ext.zip
(1.39 Кб) Скачиваний: 5


И вариант с CMOV:
Clamp_ext_mod.zip
(8.6 Кб) Скачиваний: 9

clamp_cmov_ext.png
clamp_cmov_ext.png (13.03 Кб) Просмотров: 251
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Mikle
Изобретатель велосипедов
Изобретатель велосипедов
Аватара пользователя
 
Сообщения: 3896
Зарегистрирован: 25.03.2003 (Вт) 14:02
Откуда: Туапсе

Re: Оптимизация клампинга.

Сообщение Mikle » 14.03.2019 (Чт) 21:13

Хакер писал(а):Более объективный способ замера:

Да, вычитаем накладные расходы на вызов функции.
Хакер писал(а):И вариант с CMOV

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


Вернуться в Visual Basic 1–6

Кто сейчас на конференции

Сейчас этот форум просматривают: Google-бот, Yandex-бот и гости: 3

    TopList