Одним махом 100 миллионов убивахом. Или lock-free распределитель памяти

    Постановка задачи


    Один из алгоритмов, который я реализовывал, имел интересные особенности при работе с памятью:
    • Могло выделяться огромное количество, до десятков и сотен миллионов небольших объектов одного типа.
    • Объекты представляли собой POD- типы.
      POD
      A Plain Old Data Structure in C++ is an aggregate class that contains only PODS as members, has no user-defined destructor, no user-defined copy assignment operator, and no nonstatic members of pointer-to-member type.
    • Заранее было неизвестно какое количество объектов понадобится, могло так случится, что потребуется сотня, а может и сто миллионов.
    • Объекты никогда не удаляются по одному, в какой-то момент они становятся не нужны все сразу.
    • Алгоритм хорошо распараллеливается, по этому выделением объектов занимается одновременно несколько потоков, по количеству ядер процессора(ов).

    Использование в таких условиях стандартного new – delete приводит к очень большим потерям времени на удаление объектов. Если без отладчика удаление происходило хотя бы за несколько секунд, то в присутствии отладчика освобождение памяти замедляется примерно в 100(!) раз, и отладка проекта становится просто невозможной. Кроме того из-за большого количества выделенных объектов достаточно ощутимым становился перерасход памяти на внутренние данные распределителя памяти.
    Для решения задачи выделения огромного количества объектов одного типа, и их пакетного удаления, был сделан lock-free контейнер MassAllocator. Код компилируется Visual Studio 2012. Полный код проекта выложен на github.

    Дополнительные особенности


    В моем случае объекты могли ссылаться друг на друга, и для экономии памяти был придуман небольшой хак: вместо указателя сохраняется номер объекта, а сам объект получается запросом к хранилищу. Количество объектов гарантированно меньше четырех миллиардов, поэтому использовался 32 битный индекс вместо 64 битного указателя, что дает экономию 4 байта. Так мне удалось примерно на 12 % снизить потребление памяти.
    Приятным бонусом оказалось, что к хранилищу легко можно сделать итераторы, чтобы применять алгоритмы стандартной библиотеки, например std::sort.

    Реализация


    Идея заключается в последовательном выделении элементов блоками. Стандартным malloc выделяется блок памяти, который логически представляется в виде массива элементов. На каждый запрос пользователя о выделении элемента ему возвращается указатель на следующий элемент массива, и счетчик выделенных элементов инкрементируется. Когда все элементы из массива будут выделены, запрашивается следующий блок памяти, и т.д. Освобождение памяти происходит очень быстро, всего лишь происходит освобождение всех выделенных блоков, без каких-либо вызовов деструкторов для элементов.
    Все блоки имеют одинаковый размер, таким образом получается очень легко обратится к элементу по сквозному номеру:
    template <typename T>
    typename MassAllocator<T>::reference MassAllocator<T>::operator[](size_type index)
    {
        size_t indexOfBlock = index / elementsInBlockCount_;
        size_t indexInBlock = index % elementsInBlockCount_;
        return blocks_[indexOfBlock][indexInBlock];
    }
    

    Выделение нового элемента


    Итак, все элементы последовательно располагаются в блоках. Распределение нового элемента выглядит очень просто: нужно увеличить счетчик выделенных элементов, убедится, что место в текущем блоке, из которого ведется распределение элементов, не кончилось, и если потребуется, то выделить новый блок. Конечно же, счетчик, инкрементируемый из разных потоков, должен быть реализован через атомарную переменную std::atomic, а сам алгоритм должен быть lock-free!
    Атомарный счетчик последовательно выдает индексы, и все замечательно до тех пор, пока в блоке есть место. Но вот блок заканчивается, и необходимо выделить новый. Выделять блок должен какой-то один поток, а остальные на это время должны приостановиться и возобновить работу после выделения блока. С помощью одного атомарного счетчика мне удалось реализовать такую логику с одним допущением: время выделения блока памяти должно быть достаточно мало, чтобы оставшиеся потоки не смогли переполнить 32 битный счетчик в холостом цикле ожидания. Для синхронизации доступа использована 64 битная атомарная переменная, которая логически разделена на 2 части: младшие 32 бита — это счетчик элемента внутри блока, а старшие 32 бита — это счетчик выделенных блоков памяти. Счетчик объявляется как:
     std::atomic<uint64_t> curAtomicIndex_ 
    

    В каждом блоке памяти распределяется одинаковое количество элементов, например 100000. После инкрементирования счетчика может возникнуть три различных ситуации для счетчика элемента в блоке:
    • Было получено число от 1 до 99999. Это ситуация означает, что места в блоке хватает, и мы зарезервировали элемент с полученным номером.
    • Был получен индекс, совпадающий с размером блока – 100000. Означает что потоку «повезло», и именно на нем закончился блок. В этом случае требуется выделить новый блок памяти, забрать из него нулевой элемент себе, инкрементировать старший счетчик блоков, установить младший счетчик на первый свободный элемент – 1, и записать новое значение в атомарную переменную.
    • Был получен индекс с номером больше чем размер блока. Это означает что, в данный момент какой-то из потоков производит выделение памяти, а мы вынуждены ждать, пока он не выставит младший счетчик в значение 1. В этом случае торопиться не стоит, и можно отдавать процессорное время другим потокам вызовом
      std::this_thread::yield();
      

    Сначала я пытался сделать реализацию на двух 32битных счетчиках, но в этом случае возникает эффект гонки. Например, первым делается запрос индекса в блоке, а затем номер блока.
    // так делать нельзя!
    uint32_t itemIndex = atomicIndex++;
    uint32_t blockIndx = atomicBlock.load();
    

    Может случиться так, что поток получил валидный индекс элемента itemIndex, но до момента получения индекса блока blockIndx планировщик потоков усыпил его, а за время сна другим потоком был выделен новый блок, тогда по пробуждении поток получит индекс не того блока, где был зарезервирован элемент. По этому, и индекс элемента, и индекс блока должны получаться атомарно либо в критической секции, либо через одну атомарную переменную.
    Код выделения элемента имеет особенность в том, что одновременно с указателем на выделенный элемент может возвращаться индекс этого элемента, а обращение к верхней и нижней части 64 битного целого организуется через union, а не битовую арифметику.
    template <typename T>
    typename MassAllocator<T>::pointer MassAllocator<T>::createElement(size_type *returningIndex)
    {
        //Делаем union для доступа к старшим и младшим 32 битам 64 битного целого
        union {
            uint64_t index;
            struct HiLoParts {
                uint32_t itemIndex;
                uint32_t blockIndx;
            } parts;
        };
        //получаем новый полный индекс
        index = curAtomicIndex_++;
    
        //если индекс элемента в блоке входит в допустимые пределы, то мы быстренько возвращаем индекс и указатель выделенного элемента
        if(parts.itemIndex < elementsInBlockCount_)
        {
            if (returningIndex != nullptr)
                *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
            return &(blocks_[parts.blockIndx][parts.itemIndex]);
        }
    
        if (parts.itemIndex == elementsInBlockCount_)
        {
            //на нас закончился блок и именно нашему потоку нужно выделить еще один блок памяти
            auto bufferSize = elementsInBlockCount_ * sizeof(T);
            T* buffer = (T*)malloc(bufferSize);
            memset(buffer, 0, bufferSize);
            blocks_.push_back(buffer);
            
            //мы забираем себе нулевой элемент в блоке
            parts.blockIndx = (unsigned int)(blocks_.size() - 1);
            parts.itemIndex = 0;
            if (returningIndex != nullptr)
                *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
            //устанавливаем счетчик на первый элемент в блоке
            setIndex(parts.blockIndx, 1);
            return &(blocks_[parts.blockIndx][parts.itemIndex]);
        }
    
        //ждем, пока другой поток производит выделение нового блока
        while(true)
        {
            //получаем новый полный индекс
            index = curAtomicIndex_++;
            if (parts.itemIndex == 0xffffffff)
                //мы крутили цикл ожидания настолько долго, что произошло переполнение
                throw std::string("Atomic index overflow");
            
            if (parts.itemIndex >= elementsInBlockCount_)
            {
                //блок еще не выделен, продолжаем ожидание
                std::this_thread::yield();
                continue;
            }
            
            //блок был выделен другим потоком, мы захватили валидный индекс элемента из нового блока
            if (returningIndex != nullptr)
                *returningIndex = parts.blockIndx * elementsInBlockCount_ + parts.itemIndex;
            return &(blocks_[parts.blockIndx][parts.itemIndex]);
        }
    }
    

    Производительность


    Под платформу x64 выделение 80 миллионов элементов в 8 потоках с помощью MassAllocator выполняется на i5 2500K примерно за 2000 мс, освобождение за 70 мс. Выделение с помощью new происходит примерно за 1350 мс, а вот удаление через delete выполняется за целых 17400 мс! Под отладчиком, даже если проект собран в релизной конфигурации, я так ни разу и не смог дождаться завершения теста.
    Для тестирования на платформе x86 пришлось уменьшить количество выделяемых объектов вдвое, так как new-delete имеет большие накладные расходы и адресного пространства не хватает для 80 миллионов объектов. 40 миллионов объектов выделяются MassAllocator’ом за 2400 мс, освобождаются за 35 мс, тогда как new выполняет свою работу за 750 мс, а delete за 6430 мс.
    Как и ожидалось, профилирование показывает узкое место – инкрементирование атомарного счетчика, особенно под x86. Каких-то радикальных идей по ускорению этого фрагмента у меня пока нет.

    Заключение


    Lock-free алгоритмы это новая область для меня, потому буду рад выслушать соображения относительно корректности алгоритма и/или предложения по ускорению кода.

    Update1


    Как показало профилирование, основное время тратится на атомарный инкремент 64 битного счетчика curAtomicIndex_. В x64 это транслируется в одну ассемблерную команду lock xadd QWORD PTR, в режиме x86 транслируется в целую поэму
    $again$158:
    ; 2424 : 	again:
    ; 2425 : 		mov ecx, edx;
        mov	ecx, edx
    ; 2426 : 		mov ebx, eax;
        mov	ebx, eax
    ; 2427 : 		add ebx, dword ptr _Value;
        add	ebx, DWORD PTR $T7[ebp]
    ; 2428 : 		adc ecx, dword ptr _Value[4];
        adc	ecx, DWORD PTR $T7[ebp+4]
    ; 2429 : 		lock cmpxchg8b [esi];
        lock	 cmpxchg8b QWORD PTR [esi]
    ; 2430 : 		jnz again;
        jne	SHORT $again$158
    

    По этому выделение элемнта в 64битном режиме происходит значительно быстрее.
    Освобождение памяти происходит быстро и в x64 и в x86.

    В качестве альтернативы можно было бы использовать boost::object_pool, который подходит по идеологии, но он не многопоточен и может работать с несколькими потоками.
    На замену new-delete можно попробовать boost::fast_pool_allocator, он показывает лучшую скорость чем new-delete, и в 32 битном режиме даже идет наравне в общем зачете (выделение + освобождение) с MassAlloc за счет более быстрого выделения.
    По эффективности использования памяти все альтернативы уступают MassAlloc, так в 32 битном режиме ни у new-delete, ни у boost::fast_pool_allocator не хватает адресного пространства для размещения 80 миллионов объектов, тогда как MassAllocator потребляет всего 1570 МБ.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      +4
      Интересно было бы сравнить MassAllocator с boost::pool и Loki::SmallObjAllocator.
        0
        А запросто. Я просто скопипастил пример для new/delete и заменил их (надеюсь, что правильно)
        // auto obj = new ObjectA();
        auto obj = boost::fast_pool_allocator<ObjectA>::allocate();
        ...
        // delete *jj; 
        boost::fast_pool_allocator<ObjectA>::deallocate(*jj);
        

        А вот результаты:
        Allocation and deallocation 40000000 objects took 5.572+0.05 = 5.622sec
        boost::pool-based allocation and deallocation 40000000 objects took 2.14+0.73 = 2.87sec

        Насколько я понял, boost::fast_pool_allocator использует обычную синхронизацию через boost::mutex.
        Да, компилировал для x86-32.
          0
          Анализатор показывает, что по большей части потоки ждут захвата мьютекса (это я про boost::pool). А вот если понизить число потоков, скажем до двух (пропорционально увеличив число объектов) то у меня оно даже слегка быстрей работает.

          Не знаю конкретики задачи, но возможно стоит рассмотреть вариант, когда пулом управляет один поток, а все остальные только обсчитывают данные — так можно избавиться от синхронизации пула вообще.
          0
          boost::object_pool делает в точности что нужно, но есть ньюансы… Он не многопоточен!

          void func()
          {
            boost::object_pool<X> p;
            for (int i = 0; i < 10000; ++i)
            {
              X * const t = p.malloc();
              ... // Do something with t; don't take the time to free() it.
            }
          } // on function exit, p is destroyed, and all destructors for the X objects are called.
          
            0
            Loki::SmallObjAllocator не подходит идеологически — это аллокатор для классов типа std::list, std::map.
            +4
            Эмм, а что мешает сделать thread-local pool allocator для каждого потока? Чтобы никакой общей синхронизации не было?
              0
              Мне требовалось чтобы объекты выделялись последовательно, без пропусков, каждому присваивался индекс, и этот индекс можно было использовать для быстрого обращения к самому объекту.
                0
                Индексы в последствии использовались для сериализации, по этому их монотонность была очень важна. Для первоначального варианта, где объекты выделялись через new, потом приходилось делать проход по все объектам и назначать индексы.
                  0
                  А, так это легко сделать, просто маркируя размеры пулов.

                  Т.е. «виртуальный индекс» объекта номер ObjectNum в пуле номер N равен Thread0_PoolSize + Thread1_PoolSize +… Thread<N-1>_PoolSize + ObjectNum.

                  Если эти виртуальные индексы нужны только на момент сериализации (и в этот момент мы уже ничего больше не аллоцируем), то все ок будет.
                  +1
                  А оно действительно надо? Последовательно и без пропусков? Просто я знаю волшебный метод быстрого обращения к самому объекту безо всяких специальных индексов. Указатель называется. :) Если пулы фиксированные и влезают в 4GB, то можно хранить сжатый 32-битный указатель (ptr — base), как это делает, например java. Если размер объектов кратен 8, то и до 32 гигов можно пул держать (сдвиг на 3), если кратен 16 — то до 64 гигов и т.д.
                    0
                    Для этого требуется чтобы все объекты находились в ожном непрерывном блоке памяти.
                    Сколько объектов будет получено не известно на начало работы, может тысяча, а может и сто миллионов. Можно было конечно делать VirtualAlloc с флагом MEM_RESERVE для самого большого возможного количества объектов, а потом получать физическую память по необходимости, но проект кросс-платформенный и не хотелось завязываться на архитектуру.
                      0
                      В POSIX тоже есть резервирование памяти. см. mmap. А для производительности придется так или иначе завязываться на архитектуру.
                        +1
                        Подскажите пожалуйста, как именно можно использовать mmap для этих целей. Я в мануалах нашел только резервирование своп пространства и, соответственно, флаг MAP_NORESERVE, но он не относится к теме.
                          +1
                          Хм, в исходниках openjdk и harmony vm функции reserve/commit/uncommit под linux реализуются через mmap и mprotect. Возможно, я ошибся, и там всегда делается на самом деле явная аллокация памяти.
                          0
                          mmap не позволяет зарезевировать в памяти регион например на 4 гигабайта, а потом по частям отображать его на физическую память. Поправьте меня, если я не прав.
                            +2
                            Отображением по частям на физическую память занимается ОС. Этот механизм называется swap.
                              0
                              Можно замапить что-то малого размера на регион в 4 Гб, эффект будет как у резервирования в win.
                    +2
                    Если автор не против, предлагаю сравнить с решением на языках с автоматической сборкой мусора.
                      +1
                      Конечно не против!
                        +2
                        при таких объемах в .Net любая оплошность дает вагон и маленький состав тележек проблем:
                        — реализовали данные как класс = получили страшную нагрузку на GC и лаг при сборке (даже в серверном режиме, с blocking GC и такими объемами будет совсем грустно);
                        — сделали struct, но унаследовали от интерфейса = заимели головную боль с боксингом;
                        — использовали struct, но забыли ref при передаче данных в другую функцию и получили копирование на ровном месте;
                        — использовали string или любой массив в структуре и получили миллионы объектов (= субъектов для сборки);

                        Я уж не говорю о хранении пула таких данных, который иначе как в Linked Arrays не сделать (либо таки одним массивом в NNN элементов).

                        в Java структур нет вообще, потому сборка мусора для каждого объекта неизбежна, а значит надо руками подстраивать параметры сборщика (недавно была статья на эту тему).

                        В целом, нет ничего невозможного, не раз уже решались такие задачи для managed языков, но разумно было бы выбрать именно C++, чтобы держать руку на пульсе, а не надеяться на благосклонность сборщика мусора и 100% отсутствие ошибок.
                          0
                          В принципе так и есть:
                          github.com/DarthVictor/JavaTests/blob/master/MassAllocationTest.java
                          Для java -Xms3g -Xmx3g -server при 20млн. результат 234ms на создание и 7ms на удаление на итерацию.
                          Но стоит увеличить до 40млн и GC начинает запускаться во время аллокации и вешает программу секунд на 5-10.
                          Как ему это запретить — непонятно.
                            0
                            Настройками java — включить GC1 и огарничить время, на которое GC имеет право останавливать процесс. Плюс увеличить объём пула памяти.
                            Что-то вроде:
                            -XX:+UseG1GC
                            -XX:MaxGCPauseMillis=50
                            -Xms512m
                              +1
                              Попробовал GC1, разницы, особой не почувствовал, в данном тесте он только медленнее на массивах в 20млн. и также тормозит на массивах > 20млн.
                              На ограничение времени сборщику мусора вообще плевать, если он запустился до окончания аллокации, то это стабильно фриз на машине секунд на 10-30. Пул памяти я и так ставил 3гига, как стартовый так и максимальный.

                              С такими ограничениями Java подходит только как ориентир для тестов C++.

                              Ну либо как-то, еще модифицировать GC, хотя насколько знаю нельзя напрямую запретить его автоматический запуск.
                                0
                                Ну, я поигрался с тонкой настройкой — раза в два-три удалось поднять скорость. Но всё равно относительно медленно :)
                                  0
                                  Я, кстати, посмотрел тест — так на Java тестировать нельзя. Там накладные расходы на тест и округления соизмеримы с тестом.
                                    0
                                    Потыкал тест — каюсь — нормальный тест ;)
                          +3
                          Во-первых, при ожидании имеет смысл не yield сразу вызывать, а раз от 5..30 цикл с проверкой прокрутить, так как современных процессорах велика вероятность, что другой поток исполняется на отдельном ядре. А Yield очень тяжёлая и длительная операция. Процентов 15% можно прироста скорости получить.
                          Про переполнение счётчика тоже не понял. Если после инкремента выясняется, что блок закончился, то нужно выделять новый внутри классической критической секции (с повторной проверкой внутри критической секции). А если есть вероятность, что переполнится 32-бит счётчик (что невероятно, так как нужно иметь порядка 2^32 потоков), то нужно ещё раз проверять счётчик на переполнение ДО инкремента.
                          Зачем делать unoin для доступа к половинкам 64-битных чисел не ясно — это категорически вредно с точки зрения стандарта и идеологии c++ — всё держится на компиляторо- и платфо-зависимых допущениях. При настоящих atomicInc это всё излишне и избыточно.
                            0
                            Сначала было так:
                            auto index = curAtomicIndex_++;
                            uint32_t blocksCount = index >> 32;
                            uint32_t lastIndexInBlock = index & 0xffffffff;
                            

                            Потом я начал искать способы оптимизации и вариант с union дал небольшой прирост. А вообще да, union — хак.
                              0
                              Про переполнение счётчика тоже не понял. Если после инкремента выясняется, что блок закончился, то нужно выделять новый внутри классической критической секции (с повторной проверкой внутри критической секции). А если есть вероятность, что переполнится 32-бит счётчик (что невероятно, так как нужно иметь порядка 2^32 потоков), то нужно ещё раз проверять счётчик на переполнение ДО инкремента.

                              Критических секций не хотелось по причинам:
                              1 хотелось обойтись без критических секций :-)
                              2 войти в критическую секцию первым мог как поток, первым наткнувшийся на нехватку места, так и остальные. Пришлось бы усложнять логику, на решение кто же выделяет следующий блок, хотя по чесному конечно ничего сложного в этом нет
                              3 переполнение может произойти потому что потоки не останавливаются, а непрерывано запрашивают через атомарную переменную новый индекс, и как только он станет валидным с радостью выделяют элемент
                                0
                                Я всё же не понимаю зачем long переменная? Атомарность в данном случае никто не обещает — зависит от выравнивания памяти, архитектуры и настроек компилятора. с некоторой натяжкой на современных компиляторах архитектурах атомарность чтения/записи только 32-бита даёт. Что-то вроде:
                                volatile unsigned int atomic;

                                unsigned int tmp=atmoic; // Вот тут будет атомарность на всех современных архитектурах и компиляторах.

                                А 64-бита компилятор может смело разбить на два 32-битых чтения/записи. К тому же оно у Вас не volatile — так что он его и оптимизировать/кэшировать/хоть по-байтно читать может.
                                  +1
                                  index = curAtomicIndex_++;
                                  

                                  volatile в данном случае для index здесь не нужен, index локальная переменная и не может быть изменнена внешним кодом.
                                  Для х64 curAtomicIndex_++ транслируется в InterlockedExchangeAdd64, который ассемблируется в команду
                                  lock xadd QWORD PTR [rcx+32], r8. 
                                  
                                  Так что атомарность есть.
                                  Для х86 атомарность реализуется сложнее, но тем не меннее
                                  index = curAtomicIndex_++;
                                  
                                  в любом случае работает атомарно.
                                    0
                                    volatile нужен не для index, а для curAtomicIndex_. И не volatile, а использование atomic типа.
                                    в любом случае работает атомарно.

                                    Ну за счет чего оно будет работать атомарно? Компилятор имеет право даже в память её обратно не писать. Может загрузить на регистр и там её модифицировать. У каждого процесса свой регистр.
                                      +2
                                      Нашел код на гитхабе. Там curAtomicIndex_ объявлен как std::atomic<uint64_t>. Тогда да, атомарно на любой архитектуре.
                                        0
                                        атомарное чтение/запись, а не атомарный инкремент. Без этого вообще нельзя между потоками обмениваться — во-первых компилятор может обнаружить, что в текущей задаче значение никогда не пишется и закешировать его, во-вторых, на некоторых архитектурах запись в такие переменные осуществляется особым образом, а в-третьих большинство (все?) современные компиляторы исполняются чтение/запись volatile-базовых типов атомарно (иначе просто невозможно было бы писать драйвера устройств — запись/чтение регистров по определению должны быть атомарны).
                                          0
                                          В статье упустил момент, что curAtomicIndex_ объявлен как std::atomic<uint64_t>.
                                          Его инкримент будет атомарен, за этим следит компилятор. Для х64 транслируется в
                                          lock xadd QWORD PTR [rcx+32], r8. 
                                          

                                          Для х86 код сложнее, но сводится к атомарному cmpxchg8b
                                          $again$158:
                                          
                                          ; 2424 : 	again:
                                          ; 2425 : 		mov ecx, edx;
                                          
                                          	mov	ecx, edx
                                          
                                          ; 2426 : 		mov ebx, eax;
                                          
                                          	mov	ebx, eax
                                          
                                          ; 2427 : 		add ebx, dword ptr _Value;
                                          
                                          	add	ebx, DWORD PTR $T7[ebp]
                                          
                                          ; 2428 : 		adc ecx, dword ptr _Value[4];
                                          
                                          	adc	ecx, DWORD PTR $T7[ebp+4]
                                          
                                          ; 2429 : 		lock cmpxchg8b [esi];
                                          
                                          	lock	 cmpxchg8b QWORD PTR [esi]
                                          
                                          ; 2430 : 		jnz again;
                                          
                                          	jne	SHORT $again$158
                                          
                                          
                                    +1
                                    2 войти в критическую секцию первым мог как поток, первым наткнувшийся на нехватку места, так и остальные. Пришлось бы усложнять логику, на решение кто же выделяет следующий блок, хотя по чесному конечно ничего сложного в этом нет

                                    А вроде в критическую секцию потоки по одному заходят?
                                      0
                                      В критическую секцию конечно заходят по одному. Имел ввиду другое — первый захвативший секцию будет не обязательно поток который первый наткнулся на завершение данных в блоке.
                                    0
                                    Во-первых, при ожидании имеет смысл не yield сразу вызывать, а раз от 5..30 цикл с проверкой прокрутить, так как современных процессорах велика вероятность, что другой поток исполняется на отдельном ядре. А Yield очень тяжёлая и длительная операция. Процентов 15% можно прироста скорости получить.

                                    Делал и вообще без yield и с ним. Разницы в скоросте не заметил. Решил оставить вариант с yield, так как с ним ведем себя дружественнее по отношению к другим потокам, которые тоже хотят работать. Циклов ожидания в обоих случаях получалось в районе нескольких тысяч, с yield немного меньше.
                                      0
                                      Накладные расходы на Yield равны примерно нескольким сотням — тысяче циклов. А однопроцессорных систем нынче практически не осталось.
                                        +1
                                        Память выделяется большими блоками, по этому ситуация с выделением памяти происходит сравнительно редко и замедление не так заметно. В тесте я выделяю память блоками кажется по 65 тысяч объектов.
                                    +1
                                    Мне интересно, сколько в будет холостых циклов while(true) {… } в случае большой нагрузке, как указано в одном из комментов выше, будет использован lock, что приведет к блокировке шины, операция сама по себе не сильно шустрая, да еще и другим мешается. Когда я делал свой lock-free аллокатор, который за раз должен был выделять несколько блоков (у меня использовался стек по 2 InterlockedCompareAndExchange, в моем случае в deque хранились все свободные блоки памяти, которые можно было отдать), так в этом случае на большое кол-во блоков начинало работать не очень быстро, в моем случае критическая секция на spin-lock (1 lock операция на блокировку и всё, далее всё обычными) показала себя заметно лучше. Да и реализация была заметно проще.
                                      0
                                      Цикл while(true) {… } прогонятеся вхолостую в x64 примерно 6000 раз без yield и 4500 с yield.
                                      В х86 примерно 2500-3000.

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

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