Comments.blogs

Интересный глюк в std::sort

2 мар 2007 09:31
0
(Текст записи скрыт. Показать...)
Недавно напоролись.
Дано:
Предикат сравнения для сортировки
// sort visibles by dist to camera
struct VisiblesCamDistSort
{
VisiblesCamDistSort( const Vector3& cPos ) : camPos( cPos ) {}
bool operator()( Scene::Visible* a, Scene::Visible* b ) const
{
float dist1Sq=(a->getBoundCenter()-camPos).SquaredLength();
float dist2Sq=(b->getBoundCenter()-camPos ).SquaredLength();
return dist1Sq > dist2Sq;
}
const Vector3 camPos;
};
И вызов сортировки:
std::sort(it, itEnd, VisiblesCamDistSort(cam.GetEyePos()));

Результат:
В конфигурациях без оптимизации - всё работает.
При включении оптимизаций начинает падать внутри сортировки в разных ситуациях (но при большом числе сортируемых объектов).

Интересно, кто-нибудь еще с таким сталкивался?
Решение есть, но хочется других послушать :)
Отправлено 02.03.2007 в 14:29
Отвечает на сообщение 183998
0
Есть мнение, что дело не в сортировке.
А где именно падает то и почему?
Отправлено 02.03.2007 в 14:43
Отвечает на сообщение 183999
0
Alexey Kryazhev wrote:
>
> Есть мнение, что дело не в сортировке.
> А где именно падает то и почему?


Дело было именно в алгоритме сортировки.
Падает внутри operator(). Значения переменных не посмотреть, тк оптимизации включены
Отправлено 02.03.2007 в 14:46
Отвечает на сообщение 184012
0
Ну если в твоём операторе падает, то при чём тут std::sort?
Oleg Fedorov  02.03.2007 14:57
Артём Пальвелев  02.03.2007 15:37
Артём Пальвелев  02.03.2007 15:38
В ветке ещё 7 сообщений
Антон Шеховцов  02.03.2007 22:33
Oleg Fedorov  05.03.2007 10:30
Отправлено 02.03.2007 в 15:09
Отвечает на сообщение 183998
0
Oleg Fedorov wrote:
>
> Результат:
> В конфигурациях без оптимизации - всё работает.
> При включении оптимизаций начинает падать внутри
> сортировки в разных ситуациях (но при большом
> числе сортируемых объектов).

ИМХО, дело не в вкл/выкл оптимизации, а просто нарушение инварианта самого предиката, т.е. если он greater то он должен возвращать true только когда a > b, во всех остальных случаях false. А вылет похоже инициирован ошибкой в Vector3::operator >(...).
Отправлено 02.03.2007 в 15:31
Отвечает на сообщение 184027
0
Михаил Ястребцов wrote:
>
> ИМХО, дело не в вкл/выкл оптимизации, а просто
> нарушение инварианта самого предиката, т.е. если
> он greater то он должен возвращать true только
> когда a > b, во всех остальных случаях false. А
> вылет похоже инициирован ошибкой в
> Vector3::operator >(...).


a и b - это указатели. А сравнивается дистанция до камеры.
Но при a==b дистанция от a до камеры не равна дистанции от b до камеры :). Парадокс вычислений float.
Лечится принудительной проверкой, на a==b.
Отправлено 04.03.2007 в 00:17
Отвечает на сообщение 184036
0
Oleg Fedorov wrote:
> a и b - это указатели. А сравнивается дистанция
> до камеры.
> Но при a==b дистанция от a до камеры не равна
> дистанции от b до камеры :). Парадокс вычислений
> float.
> Лечится принудительной проверкой, на a==b.

Это понятно, собственно и есть ошибка в предикате, это не парадокс вычислений float, а вполне определенное поведение чисел с пл. точкой, на них вообще не работает правильно операция == (правильно с точки зрения ожидаемого поведения). К примеру, пакет decimal(IBM alphaworks если память не изменяет) не даст таких проблем. Иначе не делали бы спец. типов для денежных вычислений.

Можно воспользоваться дельтой, доп. сравнение указателей это все же "хак". :)
Oleg Fedorov  05.03.2007 10:28
Отправлено 04.03.2007 в 12:28
Отвечает на сообщение 184036
0
Oleg Fedorov wrote:
> a и b - это указатели. А сравнивается дистанция
> до камеры.
> Но при a==b дистанция от a до камеры не равна
> дистанции от b до камеры :).


А может просто у вам там нечисла завелись?
Oleg Fedorov  05.03.2007 10:28
Отправлено 02.03.2007 в 16:19
Отвечает на сообщение 183998
0
Недавно напарывался что std::sort "раз на миллион вызовов" зацикливается.
Оператор сравнения элементарный, вся последовательность из корректных чисел.
Что там стряслось - выяснять не стал, поменял на обычный quicksort.
Отправлено 02.03.2007 в 16:21
Отвечает на сообщение 184084
0
Антон Шеховцов wrote:
>
> Недавно напарывался что std::sort "раз на миллион
> вызовов" зацикливается.
> Оператор сравнения элементарный, вся
> последовательность из корректных чисел.
> Что там стряслось - выяснять не стал, поменял на
> обычный quicksort.


Возможно глюк был именно в этом. Float suxx
Отправлено 02.03.2007 в 17:16
Отвечает на сообщение 184084
0
Антон Шеховцов wrote:
> Недавно напарывался что std::sort "раз на миллион
> вызовов" зацикливается.


ух. а какая реализация STL?

> Оператор сравнения элементарный, вся
> последовательность из корректных чисел.


есть repro?
Отправлено 02.03.2007 в 22:25
Отвечает на сообщение 184118
0
Andrew Aksyonoff wrote:
>
> Антон Шеховцов wrote:
> > Недавно напарывался что std::sort "раз на
> миллион
> > вызовов" зацикливается.
>
> ух. а какая реализация STL?


vc6 :)
repro нет. кажется понял: sort состоит из нескольких частей, и если оператор сравнения что-то считает, оно могло заинлайниться в разной степени в разные места, и получать разные результаты сравнения одних и тех же элементов...
Comments.blogs
Списки доступа
  • Подписчики [789]
Права доступа
У обсуждений в этой группе различные ограничения доступа.
Пользователи имеют персональные права доступа к обсуждениям.

Copyright © 2021 ООО "ДТФ.РУ". Все права защищены.

Воспроизведение материалов или их частей в любом виде и форме без письменного согласия запрещено.

Замечания и предложения отправляйте через форму обратной связи.

Пользовательское соглашение