Снижение производительности при расчёте малых величин.

[Mikle]

Посмотрите пример:
http://tuapse-mikle.narod.ru/fWaves.zip
Элементарная физика, распространение волн по поверхности. Кликните по форме и наблюдайте - через некоторое время fps понизится в десятки раз. Как я понимаю, это наступает тогда, когда порядок вычисляемых величин приблизится к нижней границе точности Single, видимо возникает исключение, типа "потеря точности"? Но оно не обрабатывается, не ловится на "On Error", почему тогда оно тормозит? Можно ли этого избежать?
Чтобы не ждать долго, можете уменьшить значение k1, волна будет затухать быстрее.

[jangle]

у меня фпс 390-400 сколько не кликай

[Mikle]

Ты кликни и подожди 3-5 минут, не трогай. Или уменьши k1, чтобы меньше ждать.

[jangle]

Ты кликни и подожди 3-5 минут, не трогай. Или уменьши k1, чтобы меньше ждать.

все равно 370-400, прога отбирает 50% ресурсов процессора

[Mikle]

На счёт "3-5 минут" я погорячился, дольше.
Попробуй так, поставь:

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

  k1 = 0.99
  k2 = 0.01

это снизит скорость движения волны.
Скомпилируй, запускай, подожди (не кликай) пока не установится ровный fps, потом один раз кликни, пока волна расходится, fps будет ниже, после того, как волна обойдёт всё поле, fps вернётся к первоначальной величине, и дальше уже не будет падать от новых кликов.
Я проверял на Core2 и на i5, у тебя случайно, не AMD?

[FireFenix]

Core i5: 1180 fps. Пару раз удалось добиться, что fps упало до 650-800, но после этого сколько не кликал - fps стояло на месте

[Mikle]

FireFenix
Замени процедуру MouseDown на такую:

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

Private Sub Form_MouseDown(Button As Integer, Shift As Integer, x As Single, y As Single)
  ArIn(CLng(x) + CLng(y) * 256).P = 1E-36
End Sub

FPS падает после первого клика, почти сразу.
Добавление:
Только что проверил на Athlon64 3800+ - тоже падает fps, но не так сильно, как на Intel.

[FireFenix]

Замени процедуру MouseDown на такую

VB6 не имею в наличии, можешь выложить в скомпиленом виде?

[Mikle]

Вот я сделал чистый тест без лишней графики, нажимаем:
0 - рассчёты с нулями,
1 - рассчёты с малыми величинами,
2 - рассчёты с нормальными величинами (порядка 0.5)

На Intel Core2 Quad на малых величинах падение производительности порядка 250 раз!
FireFenix
Будет интересен подобный тест на vb.net, я только вечером смогу такой сделать.

[Qwertiy]

На Си++ деление на 0 в double работает гораздо медленнее, чем при нормальных значениях. Так что, думаю так везде будет.

[Mikle]

деление на 0 в double работает гораздо медленнее

Где там деление на 0?
Где там вообще деление?

[Mikle]

На GameDev.ru подкинули ссылочку по вопросу:
http://en.wikipedia.org/wiki/Denormal_n ... nce_issues

[Qwertiy]

деление на 0 в double работает гораздо медленнее

Где там деление на 0?
Где там вообще деление?

Это я в принципе. Согласись, сходство-то есть

[FireFenix]

Вот я сделал чистый тест без лишней графики, нажимаем:
0 - рассчёты с нулями,
1 - рассчёты с малыми величинами

Core i5
По дефолту (вроде 0?) - 8500-8600fps
1 - 25-26 fps

падение в 344 раза

[FireFenix]

Посмотрел под OllyDbg, в основном больше времени проводит на этом месте


Во время выполнения этого кода в режиме 1, имеем FPU Status Register = &H3832. (а в дефолтном режиме FPU Status Register = &H3800)
Нас интересует часть с &H32, которая соответствует флагам DE, UE, PE

DE - Denormalized Operand: set if an operand of the FPU arithmetic instruction is
denormalized, or if FPU loads denormalized data from memory. This flag is sticky: once
set, it remains set until explicitly cleared;

UE - Underflow: set if the result of the arithmetic operation is less than the smallest
possible normalized value that fits into the destination. This flag is sticky: once
set, it remains set until explicitly cleared;

PE - Precision: set if the result of the arithmetic operation is not exactly
representable in the destination. For example, 1.0/3.0 will trigger precision
exception. This flag is sticky: once set, it remains set until explicitly cleared;

Как ты и говорил - FPU впадает в депрессию при работе с числами близкими к 0.
Обычным поиском на сайте интела нашёл доку, в которой говориться

Denormal Numbers

A normalized number is a number for which both the exponent (including offset) and the most significant bit of the mantissa are non-zero. For such numbers, all the bits of the mantissa contribute to the precision of the representation.

The smallest normalized single precision floating-point number greater than zero is about 1.1754943-38. Smaller numbers are possible, but those numbers must be represented with a zero exponent and a mantissa whose leading bit(s) are zero, which leads to a loss of precision. These numbers are called denormalized numbers; denormals (newer specifications refer to these as subnormal numbers).
Denormal computations use both hardware or operating system resources to handle them, which can cost hundreds of clock cycles.

• Denormal computations take much longer to calculate on IA-32 and Intel® 64 processors than normal computations.
• Denormals are computed in software on processors based on the IA-64 architecture, and the computation usually requires hundreds of clock cycles, which results in excessive kernel time.

There are several ways to handle denormals and increase the performance of your application:
• Scale the values into the normalized range.
• Use a higher precision data type with a larger dynamic range.
• Flush denormals to zero.

В ходе трассировки OllyDbg не падает в обработчик исключения, а продолжает выполнять цикл, что вроде как исключает падение производительности на обработчиках. Тогда приходим к тому, что пишет Intel - Denormal computations take much longer to calculate on IA-32 and Intel® 64 processors than normal computations и the computation usually requires hundreds of clock cycles

как-то так

[Mikle]

Flush denormals to zero.

Вопрос как? Проверять "If Value < MinValue Then Value = 0!"? Так тут мы всё равно по крайней мере два раза работаем с денормализованным значением. Кроме того, на современных процессорах ветвление - тоже очень догорая штука.
Мне кажется, я вижу недоделку в архитектуре процессоров - можно было предусмотреть флаги:
1. Просто считать все денормализованные числа нулями.
2. Все тормоза происходят от того, что денормализованные числа для вычислений нормализуются - все расчёты на FPU всё равно идут на 80-ти разрядных числах, любое 32-х разрядное float денормализованное число в 80-ти разрядном представлении можно представить нормальным числом. Можно было бы предусмотреть флаг отказа от нормализации, это тоже потеря точности, но меньшая, чем в первом варианте.

[FireFenix]

Если использовать не FPU (скорее все и для него, пока ещё глубоко не вникал в подробности), а SSE, то есть контрольный регистр MXCSR, в котором можно указать Denormals-Are-Zeros.
А вот как это реализовать на VB6, думаю нужно спросить у Хакера, ну может есть штатные средства

[Хакер]

А вот как это реализовать на VB6, думаю нужно спросить у Хакера, ну может есть штатные средства

Я, как обычно, вижу не один, а большое множество вариантов, как это можно реализовать.

[ger_kar]

Я, как обычно, вижу не один, а большое множество вариантов, как это можно реализовать.

А можно и нам увидеть эти варианты, или хотя-бы один из них, через призму твоего видения этого дела? Очень интересно

[Хакер]

Смотря с какой стороны подходить.
Людей, боящихся чего-то необычного наверное устроит вариант, когда всё пишется как обычно, обычной встроенной в язык арифметикой, но потом некоторая «невидимая магия» заменяет FPU-вычисления на SSE-вычисления.

Мне самому такой вариант не нравится.

Я бы сделал что-то вроде объектно-основанного подхода, где в центре стоял бы объект «выражения». К выражению можно было бы применить действие «вычислить». Где выражения можно было бы комбинировать, и менеджер выражений автоматически разруливал композиции, выдавая объекты-композиты.

Например, мы взяли сперва создали объект-выражение a*x*4.95. Потом создали выражения g*a*(f+c*y). Каждое объект-выражение можно «вычислить», но ещё у нас есть возможность выполнить композицию.

Например, например выражение композит по типу exp1 / exp2. Менеджер выражений создаст новый объект-выражение 4.95*x/(g*(f+c*y)), сократив множетель «а».

[Mikle]

некоторая «невидимая магия» заменяет FPU-вычисления на SSE-вычисления

Это решит проблему падения производительности на денормализованных числах.

что-то вроде объектно-основанного подхода, где в центре стоял бы объект «выражения». К выражению можно было бы применить действие «вычислить». Где выражения можно было бы комбинировать, и менеджер выражений автоматически разруливал композиции, выдавая объекты-композиты

А это как поможет? То есть это всё хорошо, но не вижу связи с конкретной проблемой.

[Хакер]

Первый вариант работает так: невидимая магия ищет в коде FPU-фрагменты, дизассемблирует их, конвертирует в аналогичный SSE-код, патчит оригинальный бинарник. Это чёрная магия. Она абсолютно незаметна программисту (который её использует, а не который её создал), но она не очень красива сама по себе. Попахивает костылями.

А второй вариант, это когда SSE-код динамически генерируется на основе информации об объектах, репрезентирующих математические выражения.


Первый вариант позволит расчитать сумму двух чисел так:

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

c = a + b

А второй как-то так:

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

Set oExpr = new CExpressionObject ' где-то в начале, при инициализации программы.
oExpr.InitalizeFromNormalString "a + b" ' Где-то в начале, при инициализации программы

...

oExpr.IntroduceVar "a", f_var_A
oExpr.IntroduceVar "b", f_var_B

...

f_var_C = oExpr.Compute() ' Когда надо вычислить



[Хакер]

Mikle, ты даже как-то не отписался совсем. Как тебе варианты?

[FireFenix]

Я бы кое что хотел прояснить...

Регистр MXCSR имеет отношение только к SSE?

В регистре FPU Control World 10 и 11 бит - Rounding Control, так же 12 бит IC

RC - Rounding control: controls the rounding of the imprecise results of the
floating-point operations:

+----+------------------------------+
| 00 | Round to the nearest |
+----+------------------------------+
| 01 | Round down (towards -INF) |
+----+------------------------------+
| 10 | Round up (towards +INF) |
+----+------------------------------+
| 11 | Round towards zero |
+----+------------------------------+

IC - Infinity control: dummy flag, provided for the compatibility with the 80287
coprocessor.

Я не сильно понимаю, как они работают с imprecise results и provided for the compatibility with the 80287, но нельзя ли с помощью них добиться нормализации?

Второй вариант предполагает (используя только средства VB):
- выделение памяти
- подстановка значений в заготовленные шаблоны инструкций sse
- передача управления по указателю к созданной выше инструкции? (в частности средствами FNDLL или его новым/будущим аналогом)
Такие действия?

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

[Mikle]

Как тебе варианты?

1. Практически нереально сделать (дизассемблировать готовый EXE, заменить FPU на SSE, не нарушая логики), не спасает при отладке, при отладке и в рантайме результаты могут разойтись.
2. То есть программа будет компилироваться дважды, один раз - когда мы компилим в среде, второй раз - когда мы запускаем EXE докомпилируются объекты CExpressionObject? А каким компилятором они будут компилироваться? Своим? В принципе - написать компилятор для математических выражений, это более реально, чем для полных программ, мысль очень интересная.

Менеджер выражений создаст новый объект-выражение 4.95*x/(g*(f+c*y)), сократив множетель «а».

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

[Хакер]

1. Практически нереально сделать (дизассемблировать готовый EXE, заменить FPU на SSE, не нарушая логики), не спасает при отладке, при отладке и в рантайме результаты могут разойтись.

Я в своём многопоточном кирпиче, который мне никак нет времени доделать, сделал дизассемблер, который дизассемблирует, и заменяет обращения к глобальным переменным на обращения к TLS-переменным. Это заняло 600 строк кода на Си, а если убрать комментарии, то все 400.

2. То есть программа будет компилироваться дважды, один раз - когда мы компилим в среде, второй раз - когда мы запускаем EXE докомпилируются объекты CExpressionObject?

Когда мы компилируем в среде, мы компилируем наш код. Когда программа работает, CExpressionObject динамически генериует код для SSE-вычислений на основе информации о выражении.

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

Да. Это не только реально, а ещё и достаточно просто. Сначала выражение конвертируется в RPN. Затем элементам RPN-записи практически один в один сопоставляются инструкции SSE. По крайней мере, так обстояли дела с FPU.

[Mikle]

Затем элементам RPN-записи практически один в один сопоставляются инструкции SSE. По крайней мере, так обстояли дела с FPU.

Особая "фишка" SSE в том, что вычисления можно распараллеливать на четыре "потока" (я написал в кавычках, не придирайтесь). Но заставить компилятор самому находить зависимости и использовать параллельные вычисления - сложная задача, тот же VS C++ этого не делает. Тут у меня есть мысль - облегчить работу компилятору, используя в качестве аргументов специальную структуру - 4 сингла. Потому, что программисту самому найти (или создать) зависимость гораздо проще.

[Хакер]

Я знаю.
Ты описываешь выражения с помощью объектов CExpressionObject. И пусть членами таких выражений будут 4 элементные сущности.