March 31st, 2011

nyaload

HashSet , детерминированный обход.

Я предпочел бы что бы HashSet и LinkedHashSet в Java назывались бы UnorderedHashSet и HashSet

HashSet -> UnorderedHashSet
LinkedHashSet -> HashSet

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

На двух проектах где я был, это дефолтное именование таблиц приводило к потере времени из-за недетерминированного порядка обхода Set. ИМХО, человеческого времени из-за ребилдов и кофликтов в svn было потеряно больше, чем выигрыш от сэкономленных килобайтов. А пользователи потратили больше времени на скачку патчей для для игры из-за диффов или из-за багов на сервере. А чуваки которые оптимизируют память - они вообще с каждым битом бегают, думая как покруче упаковать в byte[], а не только выбирают правильные контейнеры. А тем кто не думает о выборе контейнера - лучше давать более безопасную реализацию с детерминированным обходом.

На всякий случай об этом трюке, который делает обход хеш-таблицах детерминированным (и проще в реализации): Пусть хеш-таблица реализована как массив, элементы которого - связные указателями списки элементов ("корзины"). Можно дополнительно "перевязать" указателями эти элементы корзин во второй связный список, общий на всю хеш-таблицу. И для итерации использовать именно этот список.

В питоне до Python 2.7 были только словари и множества с недетерминированным порядка обхода. В python 2.7 появился collections.OrderedDict. Имхо, лучше бы сделали что бы в хеш-таблицах всегда был определенный порядок обхода, что бы не было как здесь - http://avva.livejournal.com/2323823.html

PS. Есть ещё TreeSet (TreeMap), априори нельзя сказать какой лучше в смысле стабильности по сравнению с LinkedHashSet (LinkedHashMap). Сортированный TreeSet может "абсорбировать" дамаг от того, что откуда-то вывод уже пришёл в недетерминированном порядке ( напр. ответ от компьютеров кластера ). Но зато при кодогенрации расставляет поля в алфавитном порядке, который иногда противоестествен (типа (old_value, new_value) превращается в (new_value, old_value)).
nyaload

(no subject)

Вроде не существует такого исправления библиотек, которое гарантированно не испортит произвольный говнокод.

Если мы провели оптимизацию нашей библиотеки без изменения поведения, то из-за наших оптимизаций какие-то потоки будут работать быстрее, и в неправильном многопоточном коде возникнут новые race conditions и дедлоки.

Если мы добавили какие-то функции в интерфейс, то поедет карта памяти, какие-то указатели будут указывать в другие места. Раньше адрес функции делился на 64, а теперь нет.

Мы добавили новую функцию, и какой-то код про reflection выдаёт другой список методов.

Значит, при любом изменении библиотеки нужно увеличивать её major version, так как можно придумать код который падает от таких изменений?

Поскольку в теории и на практике (см. memcpy-срач) такой код существует, то получается всегда-всегда надо увеличивать мажорную версию библиотеки. А минорных просто не существует. Ну или считать их просто вероятностным признаком, типа "мы не знаем что может сломаться, если пользователь либы не слишком хакер и не слишком обезьяна".