Cache-Conscious Binary Search

    Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.

    Дисклеймер: я не пытаюсь создать самое эффективное решение данной задачи. Мне хотелось бы просто обсудить подход к построению структур данных на основе учёта особенностей работы с кэшом процессора, т.к. многие при решении оптимизационных задач в принципе не задумываются о процессорной архитектуре. Я также не собираюсь писать идеальную реализацию Cache-Conscious Binary Search, мне хотелось бы посмотреть эффект от подобного подхода на достаточно простом примере (также в целях упрощения кода количество вершин берётся равным N=2^K-1). В качестве языка программирования я буду использовать C# (общее быстродействие для нас не принципиально, т.к. основной акцент делается не на создании самой быстрой программы в мире, а на относительном сравнении различных подходов к решению задачи). Стоит также отметить, что алгоритм эффективен только на больших массивах, поэтому не следует использовать данный подход во всех задачах, сперва нужно убедиться в его целесообразности. Предполагается, что у читателя имеются базовые представления о том, что такое кэш процессора, и как он работает.

    Рассмотрим классическую реализацию бинарного поиска: пусть у нас имеется отсортированный массив a и некоторый элемент x, который мы будем в нём искать:
    public bool Contains(int x)
    {
        int l = 0, r = N - 1;
        while (l <= r)
        {
            int m = (l + r) / 2;
            if (a[m] == x)
                return true;
            if (a[m] > x)
                r = m - 1;
            else
                l = m + 1;
        }
        return false;
    }
    
    В данной реализации на первых итерациях алгоритма запросы будут осуществляться к элементам массива, которые находятся далеко друг от друга. Изобразим дерево поиска для массива из 15-и элементов:

    Из рисунка видно, что при проходе по такому дереву сперва будет обращение к 7-му элементу, а затем (в случае a[7]!=x) к 3-ему или 11-ому. На таком маленьком массиве это не критично, но в большом массиве эти обращения будут соответствовать разным строчкам кэша процессора, что негативно скажется на производительности. Давайте попробуем переупорядочить элементы так, чтобы последовательные обращения к массиву приходились на близкие участки памяти. В первом приближении можно попробовать расположить друг за другом каждый уровень дерева с помощью простого поиска в ширину. На нашем тестовом дереве получим следующий результат:

    Теперь элементы массива, к которым мы будем обращаться на первых итерациях, находятся недалеко друг от друга. Но с ростом номера итерации мы всё равно получим большое количество cache miss-ов. Чтобы исправить данную ситуацию, разобьём наше «большое» дерево бинарного поиска на небольшие поддеревья. Каждое такое поддерево будет соответствовать нескольким уровням оригинального дерева, а элементы поддерева будут находится недалеко друг от друга. Таким образом, cache miss будут образовываться в основном при переходе к очередному поддереву. Высоту поддерева можно варьировать, подбирая её в соответствии с процессорной архитектурой. Проиллюстрируем данные построения на нашем примере, взяв высоту поддерева равным 2:

    А теперь перейдём к практическим исследованиям. Для чистоты эксперимента и получения точных результатов будем замерять время с помощью проекта BenchmarkDotNet. Рассмотрим самую тривиальную реализацию рассмотренного алгоритма без каких-либо дополнительных оптимизаций (исходный код приведён на GitHub). Сравнивать будем классическую реализацию и cache-conscious-реализации с разными высотами поддеревьев (CacheConsciousSearchK соответствует поддереву с высотой K). Высоту дерева возьмём равной 24. На моей машине (Intel Core i7-3632QM CPU 2.20GHz) получились следующие результаты (алгоритм очень чувствителен к процессорной архитектуре, поэтому у вас могут получиться совсем другие временные оценки):
    // Microsoft.NET 4.5 x64
    SimpleSearch          : 6725ms
    CacheConsciousSearch1 : 4428ms
    CacheConsciousSearch2 : 3963ms
    CacheConsciousSearch3 : 3778ms
    CacheConsciousSearch4 : 3774ms
    CacheConsciousSearch5 : 3762ms
    
    Исходный код бенчмарка
    public class CacheConsciousBinarySearchCompetition : BenchmarkCompetition
    {
        private const int K = 24, N = (1 << K) - 1, IterationCount = 10000000;
        private readonly Random random = new Random();
    
        private Tree originalTree;
        private int[] bfs;
    
        protected override void Prepare()
        {
            originalTree = new Tree(Enumerable.Range(0, N).Select(x => 2 * x).ToArray());
            bfs = originalTree.Bfs();
        }
    
        [BenchmarkMethod]
        public void SimpleSearch()
        {
            SingleRun(originalTree);
        }
    
        [BenchmarkMethod]
        public void CacheConsciousSearch1()
        {
            SingleRun(new CacheConsciousTree(bfs, 1));
        }
    
        [BenchmarkMethod]
        public void CacheConsciousSearch2()
        {
            SingleRun(new CacheConsciousTree(bfs, 2));
        }
    
        [BenchmarkMethod]
        public void CacheConsciousSearch3()
        {
            SingleRun(new CacheConsciousTree(bfs, 3));
        }
    
        [BenchmarkMethod]
        public void CacheConsciousSearch4()
        {
            SingleRun(new CacheConsciousTree(bfs, 4));
        }
    
        [BenchmarkMethod]
        public void CacheConsciousSearch5()
        {
            SingleRun(new CacheConsciousTree(bfs, 5));
        }
        
        private int SingleRun(ITree tree)
        {
            int searchedCount = 0;
            for (int iteration = 0; iteration < IterationCount; iteration++)
            {
                int x = random.Next(N * 2);
                if (tree.Contains(x))
                    searchedCount++;
            }
            return searchedCount;
        }
    
        interface ITree
        {
            bool Contains(int x);
        }
    
        class Tree : ITree
        {
            private readonly int[] a;
    
            public Tree(int[] a)
            {
                this.a = a;
            }
    
            public bool Contains(int x)
            {
                int l = 0, r = N - 1;
                while (l <= r)
                {
                    int m = (l + r) / 2;
                    if (a[m] == x)
                        return true;
                    if (a[m] > x)
                        r = m - 1;
                    else
                        l = m + 1;
                }
                return false;
            }
    
            public int[] Bfs()
            {
                int[] bfs = new int[N], l = new int[N], r = new int[N];
                int tail = 0, head = 0;
                l[head] = 0;
                r[head++] = N - 1;
                while (tail < head)
                {
                    int m = (l[tail] + r[tail]) / 2;
                    bfs[tail] = a[m];
                    if (l[tail] < m)
                    {
                        l[head] = l[tail];
                        r[head++] = m - 1;
                    }
                    if (m < r[tail])
                    {
                        l[head] = m + 1;
                        r[head++] = r[tail];
                    }
                    tail++;
                }
                return bfs;
            }
        }
    
        class CacheConsciousTree : ITree
        {
            private readonly int[] a;
            private readonly int level;
    
            public CacheConsciousTree(int[] bfs, int level)
            {
                this.level = level;
                int size = (1 << level) - 1, counter = 0;
                a = new int[N];
                var was = new bool[N];
                var queue = new int[size];
                for (int i = 0; i < N; i++)
                    if (!was[i])
                    {
                        int head = 0;
                        queue[head++] = i;
                        for (int tail = 0; tail < head; tail++)
                        {
                            a[counter++] = bfs[queue[tail]];
                            was[queue[tail]] = true;
                            if (queue[tail] * 2 + 1 < N && head < size)
                                queue[head++] = queue[tail] * 2 + 1;
                            if (queue[tail] * 2 + 2 < N && head < size)
                                queue[head++] = queue[tail] * 2 + 2;
                        }
                    }
            }
    
            public bool Contains(int x)
            {
                int u = 0, deep = 0, leafCount = 1 << (level - 1);
                int root = 0, rootOffset = 0;
                while (deep < K)
                {
                    int value = a[root + u];
                    if (value == x)
                        return true;
                    if (++deep % level != 0)
                    {
                        if (value > x)
                            u = 2 * u + 1;
                        else
                            u = 2 * u + 2;
                    }
                    else
                    {
                        int subTreeSize = (1 << Math.Min(level, K - deep)) - 1;
                        if (value > x)
                            rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2;
                        else
                            rootOffset = rootOffset * leafCount * 2 + (u - leafCount + 1) * 2 + 1;
                        root = (1 << deep) - 1 + rootOffset * subTreeSize;
                        u = 0;
                    }
                }
                return false;
            }
        }
    }
    
    На всякий случай я запустил бенчмарк под различными версиями .NET Framework и с различной битностью. Все конфигурации дали схожие результаты:

    Под Mono 3.3.0 результаты также получились аналогичными:

    Из этих картинок видно, что классическая реализация бинарного поиска значительно уступает Cache-Conscious-реализации. Стоит отметить, что по началу с ростом высоты поддеревьев быстродействие возрастает, но эта тенденция наблюдается недолго (поддеревья начинают приносить мало пользы, если внутри поддерева возникает большое количество cashe miss-ов).

    Разумеется, Cache-Conscious Binary Search является лишь примером того, как можно адаптировать программу к особенностям работы кэша процессора. Подобные Cache-Conscious Data Structures могут оказать неоценимую помощь при оптимизации приложения, если ваши структуры данных имеют достаточно большой объём, а последовательные запросы к ним приходятся на разные участки памяти. Но не стоит бездумно бросаться переписывать всё под Cache-Conscious: помните, что код станет намного сложнее, а повышение эффективности в значительной степени зависит от используемой процессорной архитектуры. В реальной жизни лучше сперва подумать о выборе наиболее оптимальных алгоритмов с хорошей асимптотикой, различных предподсчётах, эвристиках и т.п., а Cache-Conscious приберечь на времена, когда всё станет совсем плохо.

    Быстрых вам приложений!
    Также можно почитать по теме:
    Update. Дополнение от MikeMirzayanov: Есть такой трюк. Если надо бинпоиском поискать в массиве длине n, то можно разбить его на sqrt(n) блоков по sqrt(n) элементов. Затем бинпоиском за log(sqrt(n)) подыскать нужный блок и в нём вторым бинпоиском за log(sqrt(n)) найти элемент. В сумме получается всё тот же log(n), но попаданий в кэш значительно больше, т.к. каждый раз ищем на довольно коротком массиве длины sqrt(n).
    Enterra
    0,00
    Компания
    Поделиться публикацией

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 12

      +3
      Интересное решение. Любопытно было бы глянуть, насколько оно отстает от B-tree, которое не только на диске можно использовать, но и для работы с кэшем.
        0
        Разве это не одно и то же?
          +1
          B-tree в общем случае не является бинарным деревом.
            +1
            Тут бинарное дерево. В общем случае B-ttree не бинарное. В-дерево оперирует страницами на которых может быть с десяток элементов, а не два. Кол-во элементов нужно определить исходя из длины кэшлайнс. Причем любопытно поэкспериментировать со строками L1,L2,L3. Еще можно поэкспериментировать с чередующимся порядком элементов и ссылок, и сравнить с раздельным хранением элементов и ссылок.
              0
              Ах, да. Не одно и то же. Меня сбил с толку префикс «B» :-(
                0
                Кстати, типичная ошибка, принимать B-tree как binary tree. Это логично, когда начинают изучение с двоичных деревьев.

                Сами авторы никогда не раскрывали смысл буквы B, но у одного из них фамилия на B начинается (Rudolf Bayer, Ed McCreight) и работали они в то время в Boing. Еще были версии «balanced,» «broad,» or «bushy».

                Еще можно обратить внимание, что полный функционал B-tree избыточен для условий задачи. Автор зафиксировал, что на входе неизменный набор данных, т.е. есть время на то чтобы его оптимально упорядочить один раз и затем многократно использовать.
                  0
                  Всегда считал что B означает Block.
                  Те Block-tree, ведь оперирует блоками
          +4
          Есть такой трюк. Если надо бинпоиском поискать в массиве длине n, то можно разбить его на sqrt(n) блоков по sqrt(n) элементов. Затем бинпоиском за log(sqrt(n)) подыскать нужный блок и в нём вторым бинпоиском за log(sqrt(2)) найти элемент. В сумме получается всё тот же log(n), но попаданий в кэш значительно больше, т.к. каждый раз ищем на довольно коротком массиве длины sqrt(n).
            0
            Спасибо за интересный трюк! Добавил его в пост.
            +1
            Для ускорения отсеивания тех чисел, которых в списке нет, можно использовать фильтр Блума

            Но в вашем конкретном случае вы используете int, который 32х битный. Это будет 256 мегабайт, если хранить все в битовом массиве. Если таких массивов не много, то можно вполне обойтись таким решением. Понятно, все зависит от задачи.
              +1
              Согласен, фильтр Блума хорош для своих задач.
              Но в данной статье я не рассматривал различные подходы к решению рассматриваемой задачи, мне хотелось просто немного рассказать про Cache-Conscious Data Structures, а бинарный поиск взят в качестве июллюстрации ввиду его простоты.
              +1
              Есть ещё дружественное кэшу семейство Judy контейнеров: en.wikipedia.org/wiki/Judy_array

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

              Самое читаемое