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

[Mikle]

Имеется 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)

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

[Хакер]

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

[Хакер]

Как и следовало ожидать:

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

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 (3.48 Кб) Просмотров: 2585

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

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 (7.39 Кб) Просмотров: 2585

Со всеми рискованными оптимизациями:

clamp_expr_brutal_opt.png (4.78 Кб) Просмотров: 2585

[The trick]

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

[ALX_2002]

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

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

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


[Хакер]

Интересно как это в асме выглядит

Как вызов упаковка всех чисел в 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).

[ALX_2002]

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

[Mikle]

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

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

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

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

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

Попробовал такой вариант математики:

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

r = (r And (r > 0)) - ((r - 255) And (r > 255))

На удивление - почти никаких изменений, на AMD чуть-чуть ускорилось, на Интел так же чуть-чуть замедлилось.

[alibek]

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

[Mikle]

А что такое клампинг?

То, что выходит за границы, должно быть им приравнено.

r and 255 чтобы обрезать по 8 битам.

Тогда 256 станет нулём, а должно быть 255.

что-то вроде +255*not(r and &hfffffff0) чтобы присвоить 255 при переполнении 8 бит.

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

[Mikle]

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

[Хакер]

Исходный тест:

If: 0.0629
Math: 0.032456
Logic: 0.034268

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

If: 0.026896

Код подправлен в дизассемблере:

clamp_cmov.png (3.01 Кб) Просмотров: 2518

[Хакер]

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

Clamp_ext.zip

(1.39 Кб) Скачиваний: 123

И вариант с CMOV:

Clamp_ext_mod.zip

(8.6 Кб) Скачиваний: 126

clamp_cmov_ext.png (13.03 Кб) Просмотров: 2515

[Mikle]

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

Да, вычитаем накладные расходы на вызов функции.

И вариант с CMOV

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