28 сентября 2010 г.

Импорт классов из default package

C удивлением обнаружил, что, оказывается, классы из дефолтного пакета (которые в корне иерархии) нельзя импортировать и использовать в классах из любых других пакетов! Т.е. использовать можно, но только через reflection -- Class.forName(".."), etc. Более того, оказывается когда-то в java это было разрешено -- специальной конструкцией import Unfinished; (а я даже не знал, что такая есть...). О, сколько нам открытий чудных...

15 сентября 2010 г.

Развернутый связный список

Стыдно признаться, но я никогда еще в своей практике не использовал LinkedList. Не находилось оказии -- всегда оказывалось, что ArrayList либо в принципе подходит лучше, либо алгоритм можно так перестроить, что будет подходить лучше, либо в принципе он хуже, но на потребных размерах выигрывает. Последовательный доступ, большие накладные расходы памяти на хранение указателей в узлах, недружественность к кэшу и векторным инструкциям -- на мой взгляд, этого достаточно, чтобы 10 раз подумать, прежде чем его использовать. Тем не менее, никуда не деться -- вставка в случайное место для ArrayList дороже, чем для Linked уже начиная где-то с 500-1000 элементов (ну еще есть многопоточные приложения, где недружественность к кэшу становится преимуществом -- меньше конкуренция разных вычислительных ядер за строки кэша).

Не далее как вчера я обдумывал эту мысль, и пришел к выводу, что если бы мне нужен был быстрый список без (быстрого) случайного доступа но со всеми остальными плюшками, я бы попробовал сделать что-то вроде смеси array и linked -- узлы с массивами по нескольку элементов, так, чтобы узел вместе со всей служебной информацией влезал, скажем, в cache line. Получаем сразу и меньшие накладные расходы памяти -- одна пара указателей не на один, а сразу на несколько элементов. И лучшую локальность данных, и поле применимости для векторых инструкций. Все плюшки, кроме быстрого случайного доступа.

А сегодня обнаруживаю, что идею украли прямо из головы. И даже обозвать уже успели, и в википедии записали. Называется развернутый связный список (unrolled linked list). Неплохая статья на MSDN по этой структуре данных. Автор провел небольшое исследование производительности, и нашел, что развернутый список обходится (последовательно) примерно в 2.5 раза медленнее массива (обычный связный -- в 12 раз медленнее). На мой взгляд -- вполне разумный компромисс.

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

5 сентября 2010 г.

Потестировал на днях свою реализацию lock-free BufferedQueue. Неожиданно, но версия с блокировками всухую обходит CAS. Пока не могу понять, в чем дело -- грешу на ConcurrentLinkedQueue

Оказывается, с атомиками все тоже не так-то просто. Они, конечно, дешевле блокировок, но создают ничуть не меньший траффик на межпроцессорной (межядерной) шине. В определенных условиях это может сильно ухудшать производительность.

1 сентября 2010 г.

Shared exceptions

Доктор Хейнс Кабуц в очередной рассылке пишет про интересную вещь -- оказывается, если в коде часто выбрасываются RuntimeException типа NPE, или ArrayIndexOutOfBoundsException, то JIT в серверном режиме их оптимизирует -- начиная с какого-то момента он перестанет создавать новый экземпляр исключения на каждый случай, а начнет каждый раз бросать один и тот же экземпляр, с пустым stack trace! Я припоминаю, что в самом деле видел такие исключения без стека вызовов -- но как-то не подумал, с чем это может быть связано, списал на баг протоколирования. Оказывается эта оптимизация выполняется аж с 2002 года -- хотя я до сих пор нигде не встречал ее описания.