Почему std:: mutex быстрее, чем std:: atomic?

Я хочу поместить объекты в std::vector в многопоточном режиме. Поэтому я решил сравнить два подхода: один использует std::atomic, а другой std::mutex. Я вижу, что второй подход быстрее, чем первый. Зачем?

Я использую GCC 4.8.1, и на моей машине (8 потоков) я вижу, что для первого решения требуется 391502 микросекунды, а для второго решения требуется 175689 микросекунды.

#include <vector>
#include <omp.h>
#include <atomic>
#include <mutex>
#include <iostream>
#include <chrono>

int main(int argc, char* argv[]) {
    const size_t size = 1000000;
    std::vector<int> first_result(size);
    std::vector<int> second_result(size);
    std::atomic<bool> sync(false);

    {
        auto start_time = std::chrono::high_resolution_clock::now();
        #pragma omp parallel for schedule(static, 1)
        for (int counter = 0; counter < size; counter++) {
            while(sync.exchange(true)) {
                std::this_thread::yield();
            };
            first_result[counter] = counter;
            sync.store(false) ;
        }
        auto end_time = std::chrono::high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() << std::endl;
    }

    {
        auto start_time = std::chrono::high_resolution_clock::now();
        std::mutex mutex; 
        #pragma omp parallel for schedule(static, 1)
        for (int counter = 0; counter < size; counter++) {
            std::unique_lock<std::mutex> lock(mutex);       
            second_result[counter] = counter;
        }
        auto end_time = std::chrono::high_resolution_clock::now();
        std::cout << std::chrono::duration_cast<std::chrono::microseconds>(end_time - start_time).count() << std::endl;
    }

    return 0;
}

Ответы

Ответ 1

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

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

Блокировка спина значительно быстрее, когда они блокируются (приобретаются) в течение относительно короткого промежутка времени - их получение очень дешево, но другие потоки, которые также пытаются заблокировать, активны для всего этого времени (работает постоянно в цикле).

Пользовательская блокировка спина может быть реализована следующим образом:

class SpinLock
{
private:
    std::atomic_flag _lockFlag;

public:
    SpinLock()
    : _lockFlag {ATOMIC_FLAG_INIT}
    { }

    void lock()
    {
        while(_lockFlag.test_and_set(std::memory_order_acquire))
        { }
    }

    bool try_lock()
    {
        return !_lockFlag.test_and_set(std::memory_order_acquire);
    }

    void unlock()
    {
        _lockFlag.clear();
    }
};

Mutex - это примитив, что намного сложнее. В частности, в Windows у нас есть два таких примитива: Critical Section, который работает на основе каждого процесса и Mutex, который не имеет такого ограничения.

Блокировка мьютекса (или критического раздела) намного дороже, но ОС имеет возможность действительно поместить другие ожидающие потоки в "сон", что повышает производительность и помогает планировщику задач в эффективном управлении ресурсами.

Почему я пишу это? Потому что современные мьютексы часто являются так называемыми "гибридными мьютексами". Когда такой мьютекс заблокирован, он ведет себя как нормальная прямая блокировка - другие ожидающие потоки выполняют некоторое количество "спинов", а затем тяжелые мьютекс блокируются, чтобы предотвратить трату ресурсов.

В вашем случае мьютекс заблокирован в каждой итерации цикла для выполнения этой команды:

second_result[counter] = omp_get_thread_num();

Он выглядит как быстрый, поэтому "реальный" мьютекс никогда не может быть заблокирован. Это означает, что в этом случае ваш "мьютекс" может быть таким же быстрым, как атомное решение (потому что оно становится само-основанным решением).

Кроме того, в первом решении вы использовали какое-то поведение, подобное спин-блокировке, но я не уверен, что это поведение предсказуемо в многопоточной среде. Я уверен, что "блокировка" должна иметь семантику acquire, а разблокировка - это release op. Relaxed порядок памяти может быть слишком слабым для этого варианта использования.

Я отредактировал код, чтобы быть более компактным и правильным. Он использует std::atomic_flag, который является единственным типом (в отличие от std::atomic<> специализаций), который гарантированно не блокируется (даже std::atomic<bool> не дает вам этого).

Кроме того, ссылаясь на комментарий ниже о "не уступающем": это вопрос конкретного случая и требований. Замки спина - очень важная часть многопоточного программирования, и их производительность часто может быть улучшена путем незначительной модификации ее поведения. Например, библиотека Boost реализует spinlock::lock() следующим образом:

void lock()
{
    for( unsigned k = 0; !try_lock(); ++k )
    {
        boost::detail::yield( k );
    }
}

[источник: http://www.boost.org/doc/libs/1_66_0/boost/smart_ptr/detail/spinlock_std_atomic.hpp]

Где detail::yield() (версия Win32):

inline void yield( unsigned k )
{
    if( k < 4 )
    {
    }
#if defined( BOOST_SMT_PAUSE )
    else if( k < 16 )
    {
        BOOST_SMT_PAUSE
    }
#endif
#if !BOOST_PLAT_WINDOWS_RUNTIME
    else if( k < 32 )
    {
        Sleep( 0 );
    }
    else
    {
        Sleep( 1 );
    }
#else
    else
    {
        // Sleep isn't supported on the Windows Runtime.
        std::this_thread::yield();
    }
#endif
}

[источник: http://www.boost.org/doc/libs/1_66_0/boost/smart_ptr/detail/yield_k.hpp]

Во-первых, спины потоков для некоторого фиксированного количества раз (в этом случае 4). Если мьютекс все еще заблокирован, вызывается pause инструкция (если доступна) или Sleep(0), что в основном вызывает контекст-переключатель и позволяет планировщику дать еще один заблокированный поток возможность сделать что-то полезное. Затем Sleep(1) вызывается для выполнения фактического (короткого) сна. Очень приятно!

Кроме того, это утверждение:

Назначение спин-блокировки ожидание

не совсем верно. Цель spinlock состоит в том, чтобы служить быстрым, простым в использовании блокирующим примитивом, но он все равно должен быть написан правильно, с учетом определенных возможных сценариев. Например, Intel говорит (относительно использования Boost _mm_pause() как метода получения внутри lock()):

В цикле спина-ожидания внутренняя пауза улучшает скорость, с которой код обнаруживает освобождение блокировки и обеспечивает особенно значительный прирост производительности.

Итак, реализации вроде void lock() { while(m_flag.test_and_set(std::memory_order_acquire)); } может быть не так хорошо, как кажется.