Когда Алексей TheShade Шипилёв рассказывал про особенности поведения Java-строк с нулевым значением хэшкода, он приводил в качестве примера строку "лжеотождествление электровиолончели". Когда FindBugs предупреждает вас о проблемах с вычислением абсолютного значения хэшкода, равного Integer.MIN_VALUE, он приводит примеры строк, имеющих такой хэшкод — "polygenelubricants" или "DESIGNING WORKHOUSES". Откуда взялись эти примеры? Как самому составить красивую строку с заданным наперёд хэшкодом?

Различных хэшкодов существует 2³² — немногим более четырёх миллиардов, а слов в человеческом языке — порядка ста тысяч. Найти одно слово с нужным хэшкодом почти нереально, а вот сочетание из двух слов вполне можно. Если добавить ещё вариации вроде предлогов, то появится выбор.

Перебирать все возможные комбинации долго, но можно процесс оптимизировать, выполнив несложные преобразования над формулой хэшкода строки. Давайте напишем генератор словосочетаний с заданным хэшкодом. Писать будем на чистой Java 8, в модном нынче функциональном стиле.

Новая версия FindBugs доступна для скачивания на официальном сайте. Несмотря на то что поменялась только третья цифра в номере версии, вас ждёт множество новых интересных детекторов, а также улучшение старых. Если основная фича 3.0.0 заключалась в поддержке Java 8 и новых детекторов практически не было, то в 3.0.1 упор был сделан на функционал. Здесь я хочу вкратце осветить некоторые новые детекторы, разработанные лично мной.

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

Тим Петерс разработал гибридный алгоритм сортировки Timsort в 2002 году. Алгоритм представляет собой искусную комбинацию идей сортировки слиянием и сортировки вставками и заточен на эффективную работу с реальными данными. Впервые Timsort был разработан для Python, но затем Джошуа Блох (создатель коллекций Java, именно он, кстати, отметил, что большинство алгоритмов двоичного поиска содержит ошибку) портировал его на Java (методы java.util.Collections.sort и java.util.Arrays.sort). Сегодня Timsort является стандартным алгоритмом сортировки в Android SDK, Oracle JDK и OpenJDK. Учитывая популярность этих платформ, можно сделать вывод, что счёт компьютеров, облачных сервисов и мобильных устройств, использующих Timsort для сортировки, идёт на миллиарды.

Но вернёмся в 2015-й год. После того как мы успешно верифицировали Java-реализации сортировки подсчётом и поразрядной сортировки (J. Autom. Reasoning 53(2), 129-139) нашим инструментом формальной верификации под названием KeY, мы искали новый объект для изучения. Timsort казался подходящей кандидатурой, потому что он довольно сложный и широко используется. К сожалению, мы не смогли доказать его корректность. Причина этого при детальном рассмотрении оказалась проста: в реализации Timsort есть баг. Наши теоретические исследования указали нам, где искать ошибку (любопытно, что ошибка была уже в питоновской реализации). В данной статье рассказывается, как мы этого добились.

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

Как известно, в языке Java существуют вложенные (nested) классы, объявленные внутри другого класса. Их даже четыре разновидности — статические вложенные, внутренние (inner), локальные (local) и анонимные (anonymous) (в этой статье мы не затрагиваем лямбда-выражения, появившиеся в Java 8). Всех их объединяет одна интересная особенность: виртуальная машина Java не имеет понятия об особенном статусе этих классов. С её точки зрения это обычные классы, расположенные в том же пакете, что и внешний класс. Вся работа по преобразованию вложенных классов в обычные ложится на компилятор. И здесь любопытно посмотреть, как разные компиляторы с ней справляются. Мы посмотрим на поведение javac 1.8.0.20 и компилятора ecj из Eclipse JDT Core 3.10 (идёт в комплекте с Eclipse Luna).

Статей про double-checked locking на Хабре было столько, что казалось бы ещё одна — и Хабр лопнет. Вот только по Java неплохие публикации: Реализация Singleton в JAVA, Правильный Singleton в Java, А как же всё-таки работает многопоточность? Часть II: memory ordering или вот замечательный пост от TheShade (слава web-archive!). В наши дни, наверно, каждый Java-разработчик слышал, что если используешь DCL, будь добр объявить переменную volatile. Найти сегодня в коде известных опенсорсных проектов DCL без volatile довольно трудно, но оказалось, что проблемы ещё не полностью решены. Поэтому я добавлю небольшую заметку по теме с примерами из реальных проектов.

Иногда складывается ощущение, что программисты не включают мозги и не пытаются понять, как что работает, а просто следуют простым и понятным правилам вроде «объяви переменную volatile, используй DCL, и всё будет хорошо». К сожалению, такой подход в программировании не всегда работает.

В Java для введения порядка среди определённых объектов можно написать компаратор — класс, содержащий функцию compare, которая сравнивает два объекта. Альтернативой компаратору является естественный порядок объектов: объект реализует интерфейс Comparable, который содержит метод compareTo, позволяющий сравнить этот объект с другим. Сравнивающая функция должна вернуть 0, если объекты равны, отрицательное число (обычно -1), если первый объект меньше второго, и положительное число (обычно 1), если первый больше. Обычно реализация такой функции не представляет сложностей, но имеется один случай, о котором многие забывают.

Сравнение используется различными алгоритмами от сортировки и двоичного поиска до поддержания порядка в сортированных коллекциях вроде TreeMap. Эти алгоритмы завязаны на три важных свойства сравнивающей функции: рефлексивность (сравнение элемента с самим собой всегда даёт 0), антисимметричность (сравнение A с B и B с A должны дать разный знак) и транзитивность (если сравнение A с B и B с C выдаёт одинаковый знак, то и сравнение A с C должно выдать такой же). Если сравнивающая функция не удовлетворяет этим свойствам, алгоритм может выдать совершенно непредсказуемый результат. Причём скорее всего вы не получите никакого исключения, просто результат будет неверный.

Как обнаружилось, несоблюдение этих свойств — не такая уж редкая ситуация. Проблема возникает при сравнении вещественных чисел — float или double.

FindBugs — это статический анализатор кода для Java с открытым исходным кодом (под LGPL). Он содержит множество детекторов, которые определяют те или иные проблемы в коде. С недавних пор я являюсь участником проекта и пишу для него новые детекторы. Об одном из них я и расскажу в этой статье. Также мы посмотрим примеры багов, найденных в реальных проектах.

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

Можно поискать какие-то короткие конструкции языка, которые компилируются в длинные цепочки байткода, но линейный прирост меня не устраивал. Я сразу подумал про компиляцию finally-блоков: про неё уже писали на Хабре. Если вкратце, то для каждого finally-блока при непустом try-блоке создаётся минимум два варианта в байткоде: для случая нормального завершения try-блока и для случая завершения с исключением. В последнем случае исключение сохраняется в новую локальную переменную, выполняется код finally, затем исключение достаётся из локальной переменной и перебрасывается. А что если внутри finally снова разместить try-finally и так далее? Результат превзошёл все ожидания.

Дуглас Крокфорд

2007-02-21

Введение

В 1973 году на первом ежегодном симпозиуме «Принципы языков программирования» (Principles of Programming Languages Symposium) Вон Пратт представил статью «Нисходящий парсер с операторным предшествованием» (Top Down Operator Precedence). В этой статье Пратт описал метод синтаксического разбора, который объединяет лучшие стороны рекурсивного спуска и метода операторного предшествования Флойда. Метод Пратта очень похож на рекурсивный спуск, но требует меньше кода и работает гораздо быстрее. Пратт заявил, что его метод прост в освоении, реализации и использовании, необычайно эффективен и очень гибок. Благодаря своей динамичности он может использоваться для расширяемых языков.

Но если метод действительно безупречен, почему же разработчики компиляторов по сей день его игнорируют? В своей статье Пратт предположил, что БНФ-грамматики и их многочисленные модификации, а также связанные с ними теоремы и автоматы заняли нишу раньше и теперь препятствуют развитию теории синтаксического анализа в других направлениях.

Есть и другое объяснение: этот метод наиболее эффективен для динамических, функциональных языков программирования и использовать его в статическом, процедурном языке куда сложнее. Свою статью Пратт иллюстрирует на примере Lisp и играючи строит синтаксические деревья по потоку лексем. Но методы синтаксического разбора не особо ценятся в сообществе Lisp-программистов, которые проповедуют спартанский отказ от синтаксиса. С момента создания Lisp предпринималось немало попыток придать этому языку богатый синтаксис в стиле ALGOL: CGOL Пратта, Lisp-2, MLISP, Dylan, Interlisp's Clisp, оригинальные М-выражения Маккарти и так далее. Но все они провалились. Для Lisp-сообщества согласованность программ и данных оказалась важнее выразительного синтаксиса. С другой стороны, подавляющее большинство программистов любит синтаксис, поэтому сам Lisp так и не стал популярен. Методу Пратта нужен динамический язык, но сообщество динамических языков исторически не пользовалось синтаксисом, который так удобно реализуется методом Пратта.

12 мая ЦЕРН объявил «Higgs Boson Machine Learning Challenge», конкурс на лучший алгоритм по поиску событий с участием бозона Хиггса в наборе экспериментальных данных. Конкурс продлится до 15 сентября, победителей ждут денежные призы от $2000 до $7000. Удачное решение может быть интегрировано в реальный процесс обработки данных с детектора ATLAS. Для участия в конкурсе не нужны специальные знания в физике элементарных частиц.

Многие знают, что в каждом .class-файле есть замечательная структура данных, которая называется пулом констант. Но далеко не каждый Java-разработчик, глядя на исходник, сможет даже примерно оценить, сколько констант будет создано в пуле.

Возьмём, к примеру, такой код:

System.out.println("Hello World!");

Он транслируется в три инструкции байткода: getstatic (для загрузки статического поля System.out), ldc (для загрузки константной строки «Hello World!») и invokevirtual (для выполнения виртуальной функции println). Попробуйте прикинуть, сколько констант нужно для того, чтобы этот код работал.

Эта простая статья скорее для начинающих разработчиков Java, хотя я нередко вижу и опытных коллег, которые беспомощно глядят на stack trace, сообщающий о NullPointerException (сокращённо NPE), и не могут сделать никаких выводов без отладчика. Разумеется, до NPE своё приложение лучше не доводить: вам помогут null-аннотации, валидация входных параметров и другие способы. Но когда пациент уже болен, надо его лечить, а не капать на мозги, что он ходил зимой без шапки.

Итак, вы узнали, что ваше приложение упало с NPE, и у вас есть только stack trace. Возможно, вам прислал его клиент, или вы сами увидели его в логах. Давайте посмотрим, какие выводы из него можно сделать.

Update: сбор средств завершёл и статья напечана!


Пока некоторые центробанки считают, что криптовалюты нужны для финансирования терроризма и создания финансовых пирамид, энтузиаст из Вьетнама saigoned проводит акцию по сбору лайткоинов в поддержку детского приюта Gò Vấp, где много больных детей, в том числе испытывающих на себе последствия от «Агент Оранж».

Статические анализаторы кода любят за то, что они помогают найти ошибки, сделанные по невнимательности. Но гораздо интереснее то, что они помогают исправить ошибки, сделанные по незнанию. Даже если в официальной документации к языку всё написано, не факт, что все программисты это внимательно прочитали. И программистов можно понять: всю документацию читать замучаешься.

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

В этом посте я расскажу о некоторых тонкостях Java, о которых я узнал в результате использования статического анализатора FindBugs. Возможно, какие-то вещи окажутся неожиданными и для вас. Важно, что все примеры не умозрительны, а основаны на реальном коде.

Тернарный оператор ?:

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

Type var = condition ? valTrue : valFalse;

и

Type var;
if(condition)
  var = valTrue;
else
  var = valFalse;

Некоторые из вас, вероятно, видали на просторах сети эту задачку: какое число продолжает следующий ряд?

Предлагался такой очевидный правильный ответ:

Для тех, кому неочевидно, как он получен, предлагалось объяснение. Пусть (ну и 1 при x = 0, хотя неважно). Тогда каждый член ряда — это значение следующего интеграла в цепочке:

Пока всё идёт хорошо, но тут внезапно:

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

Затеяли мы амбициозный проект — открыть свой электронный научный журнал. Поначалу казалось, что это дело неподъёмное и ничего хорошего не выйдет, тем более, что мы никогда издательским делом не занимались. Однако как и с любым делом тут главное начать. Хотя будущее нашего журнала ещё под вопросом, но я решил описать наш опыт на этом нелёгком пути и, надеюсь, этот рассказ сподвигнет ещё кого-нибудь создать свои хорошие журналы на благо российской науки.

Нам хотелось примерно следующее: создать электронный рецензируемый журнал на английском языке, полностью официальный, который бы воспринимался всерьёз западными учёными, на статьи в котором бы ссылались, чтобы высчитывался импакт-фактор. Программа-минимум — попасть в список журналов ВАК, в идеале — попасть в PubMed (журнал у нас по биоинформатике). Коммерческая выгода не предполагалась.

Мне всегда интересно читать посты от PVS-Studio о том, как они ищут баги в каком-нибудь опенсорсном проекте. Я решил, что я тоже смогу написать такой пост, только про Java. Существует совершенно замечательный бесплатный статический анализатор Java-кода FindBugs. О нём на удивление мало писали на Хабре.

Помимо анализатора кода для такой статьи требуется подопытный кролик. Нужен довольно большой проект, но при этом не настолько распространённый, чтобы разработчики идеально вылизывали код. Я выбрал проект Chemistry Development Kit (версия 1.4.19), которым доводилось пользоваться. FindBugs я установил как плагин к Eclipse, потому что мне так привычнее.

Если кто-то ещё не знает, что такое хвостовая рекурсия, вот простой пример метода, складывающего в лоб натуральные числа от 1 до n (n≥0):

function add(n,acc) {
  if(n===0) return acc;
  return add(n-1,acc+n);
}

Изначально функция вызывается с параметром acc=0. В случае, если n не равно нулю, метод вызывает сам себя с другими параметрами и возвращает результат. Компилятор (или интерпретатор, или виртуальная машина) могут понять, что текущий вызов функции в стеке уже не нужен, стереть его и заменить следующим вызовом. Таким образом, рекурсия не приводит к разрастанию стека. Строго говоря, хвостовой вызов не обязан обращаться к текущей функции: вызов любой другой тоже может быть хвостовым. Главное условие: вызов функции и возврат её результата должны быть последними действиями в текущей функции. К примеру, в такой реализации метода хвостовой рекурсии нет, так как после вызова происходит ещё сложение:

function add(n) {
  if(n===0) return 0;
  return n+add(n-1);
}

По ряду причин хвостовая рекурсия в JavaScript не поддерживается (обсуждение на эту тему есть на StackOverflow). Поэтому вызов вроде add(100000,0) завершится исключением. На Хабре предпринимались попытки решить эту проблему через setTimeout, но это выглядит не очень честно и не очень красиво. Более изящное решение для языка Python было предложено с использованием «трамплина». Похожий подход для JavaScript рассмотрен здесь. Но мне захотелось, чтобы работало быстро и чтобы функцию можно было записать прямо как в примере выше. Посмотрим, что можно сделать.

Всё началось с того, что я в очередной раз ковырял в Eclipse Memory Analyzer дамп памяти Java-приложения и увидел такую интересную вещь:

С кодом HashMap я знаком весьма неплохо, но вложенного класса FrontCache никогда там не видел. Может, с последним обновлением JDK мне прислали обновлённый HashMap? Я заглянул в исходники, но слова «front» там не обнаружилось. Стало интересно, откуда же этот класс берётся и что он делает.

Не последнюю роль в биоинформатике занимает визуализация. Учёные в этой области работают с огромными объёмами информации, которую хорошо бы как-то охватить взглядом и представить в голове. Ярким примером средства визуализации являются браузеры геномов (genome browser), о которых я и хочу рассказать.