ООП: А мой identity – больше твоего.

Наткнулся на незабавный класс багов. Использование указателей объектов как ключей в хеш-таблице/бинарном дереве поиска.
Адреса которые выдаёт менеджер памяти – зависят от всего, включая на каком компьютере запускаем, от порядка предыдущих выделений/освобождений памяти, в многопоточной программе – от того что делают другие потоки и шедулера OS.
Соответственно, порядок объектов при итерации по таблице – тоже от всего этого зависит.

На конкретный экземпляр этого класса багов – наткнулся в библиотеке GTS, которая хранит точки/вершины/ребра в динамической памяти. От настроения менеджера памяти – зависит в каком порядке он будет делить doublы.
То есть, на одном компьютере есть деление на ноль, на другом нет. При первых ста запусках – всё хорошо, на сто первом – привет, вырожденный треугольник, эффект бабочки.

Так же это легко продемонстрировать на примере скриптовых языков, где по умолчанию для сравнения объектов используется их id, взятый как сишный указатель из внутренностей интерпретатора.


class MyClass:
    def __init__(self, i):
        self.i = i

    def __repr__(self):
        return str(self.i)

#выдаёт разные списки. 
print set([MyClass(i) for i in range(10)])
print set([MyClass(i) for i in range(10)])

#выдаёт как False, так и True. 
print ([MyClass(1) < MyClass(2) for i in range(10)])

Лечить наверное буду при помощи VirtualAlloc и перебрасыванием gmalloc на свой менеджер памяти, что бы выделялось всё всегда детерменировано при одинаковых данных на входе. Если не выбросим этот GTS нафиг вообще, он постоянно падает даже на синтетических цилиндрах, страшно подумать про графику от моделлеров.

http://en.wikipedia.org/wiki/Identity_(object-oriented_programming)

  • http://aruslan.livejournal.com/ aruslan

    Лечить надо по-другому – чтобы результат от порядка обхода не зависел.
    В отладочной версии – специально рандомизировать порядок обхода.

    Это касается всех систем типа подписчиков на события и т.п.
    Ну а джедайкая сила – в том, чтобы не зависящий от порядка обхода результат вычислялся таки эффективно.

  • alll

    [из-под стола, жалобно] зачем нужно что-то искать “в хеш-таблице/бинарном дереве поиска”, когда уже есть указатель?

  • http://aruslan.livejournal.com/ aruslan

    > [из-под стола, жалобно] зачем нужно что-то искать “в хеш-таблице/бинарном дереве поиска”, когда уже есть указатель?

    ну, видимо, надо как раз пройтись по указателям которые уже есть! :)
    динамизм, понимаш.

  • http://-winnie.livejournal.com _winnie

    alll:
    Оно используется для проверки «есть ли», быстрой вставки, быстрого удаления. Так же, засовывать нужные атрибуты прямо в структуру вершины – им не всегда удобно так как вершины произвольно шарятся между фейсами разных поверхностей.
    Наверное, можно избавится от такого пришивания атрибутов сбоку, но это сложнее чем кого-то вытащить из-под стола.

  • http://max630.net/ max630

    ещё из-под стола – что существенное может зависеть от порядка обхода ассоциативного массива?

  • http://max630.net/ max630

    кстати, про boost::multi_index в курсе?

  • IronPeter

    >ещё из-под стола – что существенное может зависеть от порядка обхода ассоциативного массива

    Есть интерфейс ITimer, у которого Tick. И vector > Тикают одновременно

    1.) Лифт, в котором мы стоим
    2.) Персонажи ( требуют тика лифта )
    3.) Эффект молнии между руками персонажа и головой второго ( требует просчитанной анимации для персонажей ).

    Было бы интереснее узнать, как такое может не зависеть от порядка обхода.

  • IronPeter

    Он съел мой код! там был

    [code]
    vector >
    [/code]

  • http://-winnie.livejournal.com _winnie

    >max630:
    >ещё из-под стола – что существенное может зависеть от порядка обхода ассоциативного массива?
    ЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫЫ.
    Задание: просуммируй ряд чисел 1/1, 1/2, 1/3, …. 1/100000.
    Затем просумммируй тот же ряд чисел задом наперёд.

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

    >>> n = 10*1000*1000
    >>> r = range(n)

    >>> a = sum((1.0 / i for i in r))
    >>> b = sum((1.0 / i for i in reversed(r)))
    >>> a
    16.695311265857271
    >>> b
    16.695311265859964

    >>> a = sum((pow(0.9, i) for i in r))
    >>> a
    8.9999999999999929
    >>> b = sum((pow(0.9, i) for i in reversed(r)))
    >>> b
    9.0000000000000036

  • Sergei_am

    IronPeter:
    >Было бы интереснее узнать, как такое может не зависеть от порядка обхода.
    Зачем их тогда держать в контейнере, где порядок не сохраняется?

    Winnie:
    Ето не баг имхо из-за того, что тъ написал, ето баг в GTS в принципе.
    Там что, разнъй порядок в разнъх пассах процессинга или просто разнъй порядок обработки входнъх даннъх в зависимости от менажера памяти? Если второе, то очевидно я могу в том же порядке подать даннъе и на первом менажере памяти и оно опять сбажит. Или я не понял?

  • http://-winnie.livejournal.com _winnie

    Разнъй порядок обработки входнъх даннъх в зависимости от менажера памяти.
    Да. Менеджер памяти – выдаёт разные адреса при последовательных вызовах функции на одних и тех же данных.
    И там использовано ещё много неприятного (например static-переменные которые инициализируются при первом вызове), что бы это было ещё сложней вылечить.

  • http://-winnie.livejournal.com _winnie

    > Если второе, то очевидно я могу в том же порядке подать даннъе и на первом менажере памяти и оно опять сбажит
    Да. Если такое в экспорте – это мега-неприятно, что игра глючит по разному в зависимости от компа на был экспорт. Если оно падает – пусть падает всегда одинаково, дизайнер вершинку подвинет, перестанет падать (ахтунг конечно, но в сочетании когда оно то падает, то нет…)

  • http://max630.net/ max630

    > _winnie:

    > 16.695311265857271
    > 16.695311265859964

    > 8.9999999999999929
    > 9.0000000000000036

    Это не “существенно”

    На самом деле много что может быть существенно, но тогда почему нет явного слежения за порядком?

  • http://-winnie.livejournal.com _winnie

    > Это не “существенно”
    Эффект бабочки. У любого дискретного события есть чаша терпения, и одна капля может её переполнить.

    >На самом деле много что может быть существенно, но тогда почему нет явного слежения за порядком?
    Потому что козлы.

  • http://max630.net/ max630

    > У любого дискретного события есть чаша терпения, и одна капля может её переполнить.

    “Бутылку водки и, эта, спрайт, а то нас от кока-колы уже тошнит”

  • Earwin

    > Наткнулся на забавный класс багов. Использование указателей объектов как ключей в хеш-таблице/бинарном дереве поиска.
    Not a bug.

    Само по себе действие совершенно валидно, просто применяется не в том месте где надо и не для того для чего надо.

  • http://-winnie.livejournal.com _winnie

    Оно внезапно выбивает землю из под ног. Раньше было ощущение, что для того что бы программа себя по разному при разных запусках – надо серьёзно накосячить, причем косячить можно только в “опасных” языках вроде C/C++ (неинициализированые переменные и тп). И что накосячить так в “безопасных” языках – почти невозможно (разве что только смотреть на time()). А оно вон как.

  • Earwin

    _winnie:
    Когда коллекцию, в документации на которую явно написано “doesn’t guarantee any particular iteration order”, используют там, где хотят этого “particular iteration order” – это серьёзнейший косяк. Так что в своём ощущении ты абсолютно прав :)

  • Sergei_am

    Я опять наверное не понимаю… но, тъ скорее хочеш чтобъ етот код детерминированно падал на конкретнъй даннъх. Т.е. там есть баг (очевидно), и тебе просто охота чтобъ он зависел только от входнъх даннъх, так?
    Ну, по мне все зло в том что есть баг вообще, там где-то и ето сделало порядок обхода – неприятнъм side-ефектом, но не багом.
    Хотя, если исправить баг, результат все равно может каждъй раз бъть разнъм, что в данном случае очень зло – все что юзало diff для етих даннъх идет к чертям.

  • http://www.frd.co.uk/ Nolo

    Ну действительно странно, что зависит что-то в данном случае от порядка. Т.е. вот если использовать поинтер, как ключ, то уж точно нельзя закладываться на порядок. Если это сделано в сторонней тулзе, то тут немного сложнее, и главное, чтобы такое открытие не возникло внезапно, как насколько я понимаю в твоем случае…

  • strangeraven

    Знакомый баг, встречал уже дважды.

    Первый был в героях. Там был p2p мультиплеер, в котором игровые миры синхронизировались входящими от пользователя командами и предположением, что компы вроде как должны работать одинаково.
    Соответственно, зависимость порядка перебора от адресов нарушала синхронизацию. Решение было простое: адреса как ключи тупо запрещены. В качестве ключей всегда удавалось найти что-то более безобидное.

    Второй раз на это наткнулись, когда сделали запись и проигрывание реплеев на сервере нашей текущей ММО. Если упрощенно, то входящий в сервер трафик записывается в поток, а потом этот поток проигрывается. Удобная штука для воспроизведения багов. Но иногда баги не вопспроизводились: foreach по HashMap в записи проходил не так, как в оригинале. В итоге запретили все HashMap, теперь пользуемся только LinkedHashMap, которая гарантирует порядок обхода.

    Общие впечатления остались такие: детерминированный код рулит. Указатель как хэш-функция – зло.

    >>[из-под стола, жалобно] зачем нужно что-то искать “в хеш-таблице/бинарном дереве поиска”, когда уже есть указатель?
    По указателю можно получить только содержимое самого объекта. Но иногда ведь нужно сопоставить объекту какую-то внешнюю информацию.

  • http://-winnie.livejournal.com _winnie

    aruslan:

    … надо по-другому – чтобы результат от порядка обхода не зависел.
    В отладочной версии – специально рандомизировать порядок обхода.

    Дело в том, что даже если что-то такое наворотишь, что зависеть не будет – то формального доказательства, что не зависит, скорее всего всё равно не будет.
    Хочется не обеспечивать сложными методами одинаковую работу программы, а что бы мне это обеспечило быстрый просмотр что используется из системных заголовков (файлы, время, интернет…). Хотя бы для той же самой отладки в дебаге при рандомном расположении объектов (я ж про ключ в хеш таблице, а не про перестановку объектов в упорядоченом списке). А то если по F5 и при Attach Process оно по разному ведёт – это неприятно отлаживать.