Я отчетливо помню первую лекцию Джона Бентли по алгоритмам в CMU, где он попросил всех нас, начинающих Ph.D, написать бинарный поиск, а затем разобрал критически одну из наших реализаций перед аудиторией. Конечно же, она была нерабочей, как и большинство наших реализаций. Это произвело на меня большое впечатление, так же как и обработка этого материала в его замечательной книге Programming Pearls (Addison-Wesley, 1986; Second Edition, 2000) Ключевой урок был в осторожном обдумывании стабильности в ваших программах.

Быстро возвращаясь к 2006-му. Я был глубоко потрясен, обнаружив, что программа, заявленная Бентли, как рабочая и впоследствии протестированная в главе 5 в Programming Pearls содержит дефект (bug). Как только я расскажу, в чем он состоит, вы поймете, почему ему удавалось избежать выявления в течение двух десятков лет. Чтобы вы не подумали, что я придираюсь к Бентли, давайте я расскажу, как же мне удалось обнаружить этот дефект: версия бинарного поиска, который я написал для JDK, содержал этот же дефект. О нем было заявлено Sun, как только поломалась чья-то программа, и это случилось после девяти лет выжидания.

Так в чем же дефект? Вот стандартный бинарный поиск для Java (Это тот, что я написал для java.util.Arrays):

public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }

    return -(low + 1);  // key not found.
}

Дефект содержится в строчке 6:

int mid =(low + high) / 2;

Бентли в Programming Pearls говорит, что аналогичная строка «m задается как среднее между 1 и u, усеченная вниз к ближайшему целому.» Перед лицом этого, данное утверждение может быть и правильным, но оно неверно для больших значений int в переменных low и high. В частности, оно «падает» если сумма low и high больше чем наибольшее положительное значение int (2³¹ – 1). Сумма переполняется к отрицательному значению, и это значение остается отрицательным, когда делиться на 2. В языке C это вызвало бы «array index out of bounds» с непредсказуемыми результатами. В Java это вызывает ArrayIndexOutOfBoundsException.

Этот дефект обнаруживается в массивах длинна которых (поэлементно) 2³⁰ или больше (грубо миллиард элементов). Это было немыслимо в 80-х, когда была написана Programming Pearls, но это обыденно в наши дни в Google и других местах. В Programming Pearls Бентли сказал «Хоть и бинарный поиск был опубликован впервые в 1946-м, первый бинарный поиск, который работает правильно для всех значений n — не появился раньше 1962-го» Правда в том, что очень мало правильных версий были когда-либо опубликованы, по крайней мере, на основных языках программирования.

Так какой же лучший способ исправить дефект? Вот один способ:

int mid = low + ((high - low) / 2);

Возможно более быстрый, и также более понятный:

int mid = (low + high) >>> 1;

В C и C++ (где нет оператора >>>) вы можете сделать так:

mid = ((unsigned) (low + high)) >> 1;

Сейчас мы знаем, что двоичный поиск не содержит дефектов, так? Ну, мы сильно это подозреваем, но не знаем наверняка. Не достаточно только утвердить, что программа верна, вы должны протестировать со всеми возможными значениями ввода, однако это редко осуществимо. В параллельных программах, ситуация еще хуже: вы должны протестировать для всех внутренних состояний, что для всех практических намерений — неосуществимо.

Дефект в бинарном поиске особенно применим к сортировке слиянием (mergesort) и к другим алгоритмам «разделяй и властвуй». Если у вас есть код, реализующий один из этих алгоритмов, исправьте его, прежде чем он взлетит на воздух. Общий урок, который я почерпнул из этого дефекта – это смирение: очень тяжело написать даже очень небольшой кусочек кода правильно, а наш мир работает на больших, сложных кусках кода.

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

Мы должны программировать внимательно, предохраняясь и всегда оставаясь бдительными.

От автора перевода

Эта статья попалась мне тогда, как судьба заставила заниматься адаптацией и тестированием проекта, оригинально написанным под .NET, на Mono. К этому времени мне удалось обнаружить несколько дефектов в самой платформе Mono, что, в общем-то, не было чем-то из ряда вон, т.к. проект с виду «зеленый», open-source, с широким community и латиноамериканской тусовкой разработчиков. После прочтения статьи, первая мысль, что пришла мне в голову: «10:1, что у Mono есть такие проблемы». Сразу же решил это установить, написав такой тест кейс:

using System;
class Search {
    static void Main() {
        int ind = 0;
        byte[] array = new byte[1100000000];
        array[array.Length - 1] = 1;
        ind = System.Array.BinarySearch(array,1);

        if (ind!=0)
            Console.WriteLine("found " + ind);
        else
            Console.WriteLine("not found");
    }
}

Написал в Notepad’е, откомпилировал с помощью CSC (.NET 1.1) с целью запустить его под Mono. Но после компиляции рука не удержалась и автоматически запустила полученный «exe-шник» в Windows. Каково же было мое искреннее удивление обнаружить проблемы подобного рода еще и у Microsoft. Уже можно и не упоминать, что тест на Mono дал подобные результаты. После я взял у mono-team исходный код класса Array.BinarySearch, затем глянул рефлектором соответствующую сборку у .NET — вся та же проблема с делением переполненного значения!

Sun, исправила этот дефект в JDK 1.6 (“Mustang”). Команда Mono, надеюсь, тоже когда-то за это возьмется. А в службе поддержки Microsoft, лично для меня, все оказалось не так прозрачно, для того чтобы просто уведомить их о «баге», а не подписаться на программу beta-тестирования или чего-нибудь еще. От части поэтому, пишу я это здесь.

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

Ссылки

• Оригинал: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
• Отчет о данном дефекте на Mono Bugzilla