Оптимизация тригонометрических функций
Как можно ускорить работу этих функций без потери точности результирующего значения?
Как можно ускорить работу этих функций без потери точности результирующего значения?
Разложение в ряд до заданного члена. Потеря точности - неизбежный trade-off.
Когда операции вычисления синусов и косинусов занимает 20% времени работы программы.... начинаешь об этом задумываться ;)
fsin - синус
fcos - косинус
fsincos - вычисление одновременно синуса и косинуса
fptan - тангенс
fpatan - арктангенс
fsqrt - корень квадратный
Ну или использовать общеизвестные факты о том, например, что при малых значениях аргумента синус и тангенс примерно равны аргументу...ну и все такое.
Хотя, конечно, все зависит от решаемой задачи. Если важна точность до 15 знака после запятой, то тут уже думать надо.
очевидно автор оной статьи имел в виду, что вы должны сами через разложение в ряд Тэйлора реализовать эти функции с использованием команд SSE. в принципе сие не есть уж очень геморно, но игра не стоит свеч, навряд ли прирост производительности будет ощутим, если он вообще конечно будет.
зы: кстати сейчас товарисчи из интела взялись переписывать стандартные сишные математические библиотеки под новые наборы инструкций. кому интересно можете почитать об этом в летней школе интела, адресок к сожалению не помню.:D:(
зы: кстати сейчас товарисчи из интела взялись переписывать стандартные сишные математические библиотеки под новые наборы инструкций. кому интересно можете почитать об этом в летней школе интела, адресок к сожалению не помню.:D:(
увеличение скорости расчета самих функций с потерей точности для меня не подходит
увеличение скорости расчета самих функций с потерей точности для меня не подходит
Совершенно верно.
Может гдето можно схитрить через формулы типа tg = sin/cos и т.п.
Ну и если вы оперируете с небольшим количеством углов, то может стоит сделать некий кеш значений тригонометрических функций. Хотя тут засекать нужно чтоб медленнее не получилось и с розмером кеша играться.
если вы говорите о том, что по вашей ссылки, то это полный уг, бо пляска с макросами и написание каких то оберток сишных для sse ни когда не будет работать быстрее чем сопроцессор. конечно можно надеяться на всемогущую оптимизацию сишных компиляторов, но и они не боги.
вы профилировали свой код, в смысле человеческим профайлером(к примеру аэмдешным)? возможно у вас затыки основные и не в математике.
что могу посоветовать:
Intel® Math Kernel Library - но это дело платное, есть бесплатный аналог AMD Core Math Library, сам с этими вещами не работал, но вроде как по отзывам они быстрые и крутые, может стоит поискать что то подобное.
может быть вам стоит попробовать реализовать функцию, к примеру, синус через разложение в ряд Тэйлера ручками на sse, а потом посмотреть ее производительность и точность. один мой знакомый тварил такое дело, точность у него упала не значительно(расхождение со стандартной сишной примерно 3%) и то только на больших значения угла, но вот скорость упала раза в два, но делал он это без sse, на базовых инструкциях, вдруг у вас получится лучше и быстрее, в теории это возможно. или банально заюзать сопроцессор, если вы конечно уже это не сделали. реализовывать советую на чистом асме и слинковать с вашим кодом.(использовать yasm или nasm извиняюсь за рекламу уж очень они мне нравятся:D) так же может вам стоит попробовать заюзать ваше приложение под 64 бита, там больший простор для маневров на асме(и по словам сишные компиляторы там просто звереют в оптимизации, хотя не поручусь, сам не проверял).
в общем поэкспериментируйте, результат напишите нам, лично мне будет интересно в целях расширения кругозора.
зы: постом выше я имел в виду это.
зызы: а вообще сложно так о чем то говорить, вы бы задачу свою подробней описали, показали тормозные участки кода и все такое.
если вы говорите о том, что по вашей ссылки, то это полный уг, бо пляска с макросами и написание каких то оберток сишных для sse ни когда не будет работать быстрее чем сопроцессор
Стандартные тригонометрические функции сейчас (и так было почти всегда) реализованы именно через сопроцессор.
Автору уже намекнули, что нужно произвести мемоизацию запросов. Кстати, еще можно произвести линейную аппроксимацию. Т.е. вычислить синусы и косинусы в некоторых узловых точках а для значений не являющихся узловыми вычислять промежуточные (в соответствии с прямой, проходящей между соседними узлами).
Ну это опять же недопустимая автору потеря точности.
Автор, поделитесь задачей. А возможно и критическими участками кода.
так как список закэшированных значений храниться у каждой фигуры свой, поиск по нему происходит быстро.
так как список закэшированных значений храниться у каждой фигуры свой, поиск по нему происходит быстро.
Может быть имеет смысл сделать общий кэш?
Не... фигуры вращатьются на произвольный угол с любой точностью хоть на 0,000000000000001 градуса. так что хранить все значения в таблице не реально.
а строить кэш один на все фигуры не очень красиво.... ведь в данном случае либо пользователь класса должен знать о кэше либо фигура может знать что ей не положено знать.
простите, а зачем такая точность? космические корабли проектируете? просто в подавляющем большинстве случае в задачах компьютерной графики на этом экономят, все равно пользователь не увидит, что фигура повернулось с ошибкой на несколько сотых, картинку это не испортит, а производительность повысит!!! да и к тому же разве стандартные функции считают с такой точностью???
Хм, но ведь в какой-то момент времени значения углов могут совпасть.
Согласен, что возможно такая точность и излишнее, но не хочется копить ошибки ещё и на тригонометрических функциях. а пересматривать работу алгоритмов верхнего уровня тоже времени нет)
По памяти согласен. а по скорости не совсем.
Я реализовал так, что фигура хранит расчеты по текущей позиции. То есть как фигура изменяет свое положение, угол наклона, то старые значения удаляются, а новые считаются по запросу на их получение. В итоге закэшированные значения хранятся у фигуры и доступ к ним мгновенен так как там хранятся текущие значения.
Но даже предположить если бы я реализовал это иначе, то я не понимаю как может быть доступ в общем кэше быть быстрее чем в малом? даже по аналогии с кэшем процессора самыми быстрыми являются малые кэщи.
Если кеш будет реализован с непрерывной области памяти, вероятность сбоя страницы, из-за бОльшего количества обрашений, будет меньше.
2Phodopus
Как я понял у него не кеш значений, а значения тригонометрических функций в модель додана.
2Rad87. Я прав? Вы же не держите угол - синус, а просто синусы в модель обекта приклеиваете? Так?
2Rad87. Я прав? Вы же не держите угол - синус, а просто синусы в модель обекта приклеиваете? Так?
Совершенно верно!!! Если быть точнее то не сами синусы, а результат вычислений с использованием этих синусов и косинусов.
1. Хранить кэш синусов/косинусов сравнительно больших углов (с шагом в 1').
2. Сравнительно малые углы (менее 1') с ОЧЕНЬ большой точностью равны: синус а = а, косинус а = 1. Тогда (из школьной геометрии sin(a+b) = sina*cosb + cosa*sinb) получаем формулу
sin(a+b) = a*cosb + sinb, где a - "малая" часть угла (остаток от деления на 1'), b - "большая" часть угла (целая часть деления на 1'). Например
sin (134,8776 градусов) = 0,708615746723759, а по приближённой формуле будет 134,86666... градусов и 0,656 минут (это 0,000190822665 радиан), т. е. sin (134,8 градусов) = sin (134,86666... градусов) + 0,000190822665*cos(134,8666... градусов) = 0,708750377261 - 0,000134617634 = 0,708615759627, это я ещё в расчётах использовал 12 знаков и ошибка вышла в 7-м.
Учитывая точность типа double, ошибка после всех вычислений вряд ли будет хуже 10-го знака.
Выбирая хороший шаг таблицы, можно улучшить точность.