Эффективность разных реализаций бинарного поиска в Си

Question

Читаю книгу "Язык программирования Си" Брайана Кернигана. В разделе про условные операторы наткнулся на реализацию бинарного поиска, представленную в коде ниже, а далее шло интересное упражнение, где указывалось, что можно написать бинарный поиск с меньшим количеством проверок внутри цикла. И предлагалось подумать над тем, какой же из них будет быстрее. Я, логично, предположил, что выиграет реализация с меньшим количеством условных операторов, но эксперименты показали интересный обратный результат. Я использовал модуль time.h для измерения времени выполнения программы. Помогите разобраться почему же так выходит.

Команда для компиляции gcc binarysearch.c -o binarysearch.exe

    //Task 3.1
    #include <stdio.h>
    #include <time.h>

    #define ML 100000u //Размер массива
    #define BETTER_BIN_SEARCH

    int binsearch(int x, int v[], int n); 

    int main(){
        int v[ML];//Массив в котором ведется поиск
        int i = 0;
        for(i = 0; i < ML; ++i){//Инициализация элементов
            v[i] = i;
        }

        //printf("CLOCKS_PER_SEC = %d\n", CLOCKS_PER_SEC);//Выдает 1000
    #ifdef BETTER_BIN_SEARCH
        printf("My search\n");
    #else
        printf("Book's search\n");
    #endif
        //Многократное выполнение поиска
        clock_t st = clock(); //StartTime
        for(int j = 0; j < 2000; ++j)
            for(i = 0; i < ML; ++i){
                binsearch(i, v, ML);
            }
        clock_t oat = clock() - st;//OverAllTime
        printf("Over all time = %d\n", oat);

        return 0;
    }

    #ifdef BETTER_BIN_SEARCH
    //Моя версия поиска
    //В среднем время выполнения 20200-20300
    int binsearch(int x, int v[], int n){
        unsigned low, mid, high;
        low = 0;
        high = n-1;
        while(low < high){
            mid = (low + high) / 2;
            if(v[mid] < x){
                low = mid + 1;
            }
            else{
                high = mid;
            }
        }
        if(x == v[low])
            return low;
        return -1;
    }
    #else
    //Реализация из книги
    //В среднем время выполнения 18700-19100
    int binsearch(int x, int v[], int n){
        unsigned low, high, mid;
        low = 0;
        high = n - 1 ;
        while (low <= high) {
            mid = (low + high) / 2;
            if (x < v[mid])
                high = mid - 1;
            else if (x > v[mid])
                low = mid + 1 ;
            else /* совпадение найдено */
                return mid;
         }
         return -1; /* совпадения нет */

    }
    #endif

Answer 1

Ключевое наблюдение не совсем верно: на самом деле для маленьких массивов «книжная» версия действительно быстрее, а для больших (N>2²⁰ ~ 2²⁴) быстрее оказывается «твоя».

У такого поведение две основные причины:

Во-первых, «твоя» версия в среднем даёт одну лишнюю итерацию цикла. Это заложено алгоритмом, а т.к. итераций в цикле не много (~log₂N), то это оказывает эффект замедления.
Во-вторых, сравнения не равнозначны по скорости.
На практике компилятор почти наверняка преобразует «книжную версию» в нечто подобное (ассеблеро-подобный псевдокод):
```
loop_iteration:
  cmp low, high
  jle exit

  cmp x, v[mid] ; сравнить x и v[mid]
  jl less       ; jump if less,    перейти на less, если (x - v[mid]) < 0
  jg more       ; jump if greater, перейти на more, если (x - v[mid]) > 0
  ; если ни один из переходов не произошёл, то вернуть 0
  ret x

less:
  eval  high := mid - 1
  jmp loop_iteration ; Переход на следующую итерацию цикла
more:
  eval  low  := mid + 1
  jmp loop_iteration ; Переход на следующую итерацию цикла

exit:
  ret -1
```
Для современных процессоров значительное влияние на скорость вычислений оказывает то, насколько точно они могут предугадать, когда будет совершён условный переход (jg и jl), а когда нет.

Так вот, в фрагменте выше предсказать, будет ли совершён jl или нет — практически невозможно, его вероятность близка к 50%, поэтому в половине случаев блок предсказаний ошибается и это «сравнение» оказывается довольно дорогим.

Переход по jg, напротив, стохастически, намного чаще происходит, чем нет: ведь элемент намного чаще оказывается меньшеше искомого, чем в точности равным ему. Поэтому блок предсказаний делает вывод, что он обычно происходит и часто оказывается прав, так что в большинстве случаев это «сравнение» оказывается дешёвым.

В случае же с «твоей» реализацией сравнение действительно одно и оно в половине случаев оказывается «дорогим», как и jl в «книжном» варианте.

Так вот, для малых N одно такое «дорогое сравнение» из-за лишний итерации оказывается медленнее, чем много «дешёвых». Но с ростом размера массива эта ситуация изменяется в обратную сторону.

Другие замечания

Как уже заметили в комментариях, при проверках на производительность стоит компилировать с оптимизацией (ключ -ON для gcc, где N одно из 1, 2, 3, S). Хотя в данном случае это не должно было оказать серьёзного эффекта.
С методикой тестирования также есть проблемы: последовательный поиск всех элементов массива также может внести свои искажения. Следовало бы заменить это на поиск [псевдо]случайных значений.
«Твоя» реализация бинарного поиска имеет важную особенность — она находит наименьший индекс. По сути это поиск нижней грани в упорядоченной последовательности.
У «Книжной» реализации есть проблема — она выходит за границы, если ищется элемент меньше минимального.

БЛОГ НА HUSL

Эффективность разных реализаций бинарного поиска в Си

Ответы (1 шт):

Другие замечания