29.10.2018 08:48
thatsme 42 2200 Источник

На написание данной статьи меня подвигли комментарии к статье "Как правильно и неправильно спать".


Речь в данной статье пойдёт о разработке многопоточных приложений, применимости lock-free к некоторым кейсам возникшим в процессе работы над LAppS, о функции nanosleep и насилии над планировщиком задач.


NB: Всё обсуждаемое касается разработки на C++ под Linux, но может быть применимо ко всем POSIX.1-2008 совместимым системaм (с оглядкой на конкретную реализацию).

Вобщем всё довольно сумбурно, надеюсь ход мысли в изложении будет понятен. Если интересно то прошу под кат.


Событийно- ориентированное ПО всегда чего-то ждёт. Будь то GUI или сетевой сервер, они ждут каких-либо событий: поступления ввода с клавиатуры, события мыши, поступление пакета данных по сети. Но всякое ПО ждёт по разному. Lock-free системы вообще не должны ждать. По крайней мере использование lock-free алгоритмов, должно происходить там где ждать не нужно, и даже вредно. Но ведь мы говорим о конкурентных (много-поточных) системах, и как ни странно lock-free алгоритмы тоже ждут. Да они не блокируют исполнение параллельных потоков, но сами при этом ждут возможности сделать что-либо без блокировки.


LAppS очень активно использует мьютексы и семафоры. При этом в стандарте C++ семафоры отсутствуют. Механизм очень важный и удобный, однако C++ должен работать в системах, в которых нет поддержки семафоров, и поэтому в стандарт семафоры не включены. При этом если семафоры, я использую потому, что они удобны, то мьютексы потому, что вынужден.


Поведение мьютекса в случае конкурентного lock() также как и sem_wait() в Linux, помещает ожидающий поток в конец очереди планировщика задач, и когда она оказывается в топ-е, проверка повторяется и без возврата в userland, поток помещается опять в очередь, если ожидаемое событие ещё не произошло. Это очень важный момент.


И я решил проверить, могу-ли я отказаться от std::mutex и POSIX-семафоров, эмулируя их с помощью std::atomic, перенеся нагрузку по большей части в userland. На самом деле не удалось, но обо всём по порядку.


Во первых у меня есть несколько секций в которых эти эксперименты могли-бы оказаться полезными:


  • блокировки в LibreSSL (case 1);
  • блокировки при передаче payload полученных пакетов, в приложения Lua (case 2);
  • Ожидание событий о поступлении payload готовых для обработки приложениями Lua (case 3).

Начнём с "неблокирующих-блокировок". Давайте напишем свой мьютекс с использованием атомиков, как это показано в некоторых выступлениях Х. Саттера (оригинального кода нет, поэтому по памяти и поэтому код на 100% с оригиналом не совпадает, да и у Саттера этот код относился к прогрессу C++20, поэтому есть отличия). И несмотря на простоту этого кода, в нём есть подводные камни.


#include <atomic>
#include <pthread.h>

namespace test
{
    class mutex
    {
    private:
      std::atomic<pthread_t> mLock;
    public:
      explicit mutex():mLock{0}
      {
      }
      mutex(const mutex&)=delete;
      mutex(mutex&)=delete;

      void lock()
      {
        pthread_t locked_by=0; // в C++20 эта переменная будет не нужна, т.к. compare_exchange_strong сможет работать со значениями вместо референса в первом аргументе
        while(!mLock.compare_exchange_strong(locked_by,pthread_self()))
        {
          locked_by=0; // это тоже будет не нужно
        }
      }

      void unlock()
      {
        pthread_t current=pthread_self();

        if(!mLock.compare_exchange_strong(current,0))
        {
          throw std::system_error(EACCES, std::system_category(), "An attempt to unlock the mutex owned by other thread");
        }
      }

      const bool try_lock()
      {
        pthread_t unused=0;
        return mLock.compare_exchange_strong(unused,pthread_self());
      }
    };
}

В отличии от std::mutex::unlock(), поведение test::mutex:unlock() при попытке разблокировать из другого потока, — детерминированное. Будет выброшено исключение. Это хорошо, хоть и не соответствует поведению стандарта. А что в этом классе плохо? Плохо то, что метод test::mutex:lock() будет безбожно жрать ресурсы ЦП в выделенных потоку квотах времени, в попытках завладеть мьютексом, которым уже владеет другой поток. Т.е. цикл в test::mutex:lock() приведёт к бесполезной трате ресурсов ЦП. Каковы наши варианты выхода из этой ситуации?


Мы можем воспользоваться sched_yield() (как предлагается в одном из коментариев к вышеупомянутой статье). Так-ли это просто? Во первых для того что-бы использовать sched_yield() необходимо что-бы потоки исполнения использовали политики SCHED_RR, SCHED_FIFO, для своей приоритезации в планировщике задач. В противном случае вызов sched_yield() будет бесполезной тратой ресурсов ЦП. Во вторых, очень частый вызов sched_yield() всё равно повышает расход ресурсов ЦП. Более того, использование real-time политик в вашем приложении, и при условии, что в системе нет других real-time приложений, ограничит очередь планировщика с выбранной политикой только вашими потоками. Казалось-бы, — это хорошо! Нет не хорошо. Вся система станет менее отзывчива, т.к. занята задачей с приоритетом. CFQ окажется в загоне. А ведь в приложении есть и другие потоки, и очень часто возникает ситуация, когда захвативший мьютекс поток, ставится в конец очереди (истекла квота), а поток который ждёт освобождения мьютекса прямо перед ним. В моих экспериментах (case 2) этот метод дал примерно те-же результаты (на 3.8% хуже), что и std::mutex, но система при этом менее отзывчива и расход ресурсов ЦП повышается на 5%-7%.


Можно попытаться изменить test::mutex::lock() так (тоже плохо):


void lock()
{
  pthread_t locked_by=0;
  while(!mLock.compare_exchange_strong(locked_by,pthread_self()))
  {
     static thread_local const struct timespec pause{0,4}; // - можно поиграть с длительностью сна

     nanosleep(&pause,nullptr);
     locked_by=0; 
  }
}

Тут можно экспериментировать с длительностью сна в наносекундах, 4нс задержки оказались оптимальными для моего ЦП и падение производительности относительно std::mutex в том-же case 2, составило 1.2%. Не факт что nanosleep спал 4нс. На самом деле или больше (в общем случае) или меньше (если прерывался). Падение (!) потребления ресурсов ЦП составило 12%-20%. Т.е. это был такой здоровый сон.


В OpenSSL и LibreSSL есть две функции устанавливающие коллбэки для блокирования при использовании этих библиотек в многопоточной среде. Выглядит это так:


// Сам callback
void openssl_crypt_locking_function_callback(int mode, int n, const char* file, const int line)
{
  static std::vector<std::mutex> locks(CRYPTO_num_locks());
  if(n>=static_cast<int>(locks.size()))
  {
    abort();
  }

  if(mode & CRYPTO_LOCK)
    locks[n].lock();
  else
    locks[n].unlock();
}

//  назначение callback-a
CRYPTO_set_locking_callback(openssl_crypt_locking_function_callback);

// определение id
CRYPTO_set_id_callback(pthread_self);

А теперь самое страшное, использование вышеприведённого мьютекса test::mutex в LibreSSL снижает производительность LAppS почти в 2 раза. Причём независимо от варианта (пустой цикл ожидания, sched_yield(), nanosleep()).


Вобщем case 2 и case 1 вычёркиваем, и остаёмся с std::mutex.


Перейдём к семафорам. Есть множество примеров того как реализовать семафоры с помощью std::condition_variable. Все они используют std::mutex в том числе. И такие симуляторы семафоров медленнее (по моим тестам), чем системные POSIX семафоры.


Поэтому сделаем семафор на атомиках:


    class semaphore
    {
     private:
      std::atomic<bool> mayRun;
      mutable std::atomic<int64_t> counter;

     public:

      explicit semaphore() : mayRun{true},counter{0}
      {
      }

      semaphore(const semaphore&)=delete;
      semaphore(semaphore&)=delete;

      const bool post() const
      {
        ++counter;
        return mayRun.load();
      }

      const bool try_wait()
      {
        if(mayRun.load())
        {
          if(counter.fetch_sub(1)>0)
            return true;
          else 
          {
            ++counter;
            return false;
          }
        }else{
          throw std::system_error(ENOENT,std::system_category(),"Semaphore is destroyed");
        }
      }

      void wait()
      {
        while(!try_wait())
        {
          static thread_local const struct timespec pause{0,4};
          nanosleep(&pause,nullptr);
        }
      }

      void destroy()
      {
        mayRun.store(false);
      }

      const int64_t decrimentOn(const size_t value)
      {
        if(mayRun.load())
        {
          return counter.fetch_sub(value);
        }else{
          throw std::system_error(ENOENT,std::system_category(),"Semaphore is destroyed");
        }
      }

      ~semaphore()
      {
        destroy();
      }
    };

О, этот семафор оказывается многократно более быстрым чем системный семафор. Результат отдельного тестирования этого семафора с одним провайдером и 20 консамерами:


OS semaphores test. Started 20 threads waiting on a semaphore
Thread(OS): wakes: 500321
Thread(OS): wakes: 500473
Thread(OS): wakes: 501504
Thread(OS): wakes: 502337
Thread(OS): wakes: 498324
Thread(OS): wakes: 502755
Thread(OS): wakes: 500212
Thread(OS): wakes: 498579
Thread(OS): wakes: 499504
Thread(OS): wakes: 500228
Thread(OS): wakes: 499696
Thread(OS): wakes: 501978
Thread(OS): wakes: 498617
Thread(OS): wakes: 502238
Thread(OS): wakes: 497797
Thread(OS): wakes: 498089
Thread(OS): wakes: 499292
Thread(OS): wakes: 498011
Thread(OS): wakes: 498749
Thread(OS): wakes: 501296
OS semaphores test. 10000000 of posts for 20 waiting threads have taken 9924 milliseconds
OS semaphores test. Post latency: 0.9924ns

=======================================

AtomicEmu semaphores test. Started 20 threads waiting on a semaphore
Thread(EmuAtomic) wakes: 492748
Thread(EmuAtomic) wakes: 546860
Thread(EmuAtomic) wakes: 479375
Thread(EmuAtomic) wakes: 534676
Thread(EmuAtomic) wakes: 501014
Thread(EmuAtomic) wakes: 528220
Thread(EmuAtomic) wakes: 496783
Thread(EmuAtomic) wakes: 467563
Thread(EmuAtomic) wakes: 608086
Thread(EmuAtomic) wakes: 489825
Thread(EmuAtomic) wakes: 479799
Thread(EmuAtomic) wakes: 539634
Thread(EmuAtomic) wakes: 479559
Thread(EmuAtomic) wakes: 495377
Thread(EmuAtomic) wakes: 454759
Thread(EmuAtomic) wakes: 482375
Thread(EmuAtomic) wakes: 512442
Thread(EmuAtomic) wakes: 453303
Thread(EmuAtomic) wakes: 480227
Thread(EmuAtomic) wakes: 477375
AtomicEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 341 milliseconds
AtomicEmu semaphores test. Post latency: 0.0341ns

T.e. этот семафор с почти бесплатным post(), который в 29 раз быстрее системного, ещё и очень быстр в пробуждении ждущих его потоков: 29325 пробуждений? в милисeкунду, против 1007 пробуждений в милисeкунду у системного. У него детерминированное поведение при разрушенном семафоре или разрушаемом семафоре. И естественно segfault при попытке использовать уже уничтоженный.


(?) На самом деле столько раз в милисeкунду поток не может быть отложен и пробужен планировщиком. Т.к. post() не блокирующий, при данном синтетическом тесте, wait() очень часто оказывается в ситуации когда и спать не нужно. При этом как минимум 7-мь потоков параллельно читают значение семафора.


Но использование его в case 3 в LAppS приводит к потерям производительности независимо от времени сна. Он слишком часто просыпается для проверки, а события в LAppS поступают гораздо медленнее (латентность сети, латентность клиентской части генерирующей нагрузку, и т.д.). А проверять реже, — значит также потерять в производительности.


Более того использование сна в подобных случаях и подобным образом совсем вредно, т.к. на другом железе результаты могут оказаться совсем другими (как и в случае ассемблерной инструкции pause), и для каждой модели ЦПУ ещё и придётся подбирать время задержки.


Преимущество системных мьютекса и семафора, в том что поток исполнения не просыпается до тех пор пока событие (разблокировка мьютекса или инкремент семафора) не произойдёт. Лишние циклы ЦП не тратятся, — профит.


Вобщем, всё от это лукавого, отключение iptables на моей системе даёт от 12% (с TLS) до 30% (без TLS) прироста производительности...

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


  1. ianzag
    29.10.2018 12:40
    #19296785

    Позанудствуем чуток…

    Как говорится в священном писании:

    Issue 6

    IEEE Std 1003.1-2001/Cor 2-2004, item XBD/TC2/D6/26 is applied, adding pthread_t to the list of types that are not required to be arithmetic types, thus allowing pthread_t to be defined as a structure.

    откуда следует, что pthread_t — это не обязательно арифметический тип. Это может быть и прозрачная структура. Как следствие, попытка инициализировать её нулем некорректна.

    class mutex
    {
    private:
      std::atomic<pthread_t> mLock;
    public:
      explicit mutex():mLock{0}
      {
      }


    Да и вообще в общем случае завернуть её в атомик не получится по той же самой причине.


    1. thatsme Автор
      29.10.2018 14:28
      #19297317

      Во первых не у меня, а у Саттера на одном из слайдов (сейчас даже не вспомню в каком из видео о прогрессе в работе над C++20 он этот код показывал).

      Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.

      В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).

      Но это не отменяет вашей правоты, и для каждой ОС нужно будет убедиться, что pthread_t арифметический.


      1. ianzag
        29.10.2018 14:59
        #19297485

        > Во первых не у меня, а у Саттера на одном из слайдов

        Нет, ну если у самого Саттера то конечно да. Это весомый аргумент.

        > Во вторых если мы говорим о Linux в первую очередь, то pthread_t это unsigned long int.

        Как там было выше…

        ========
        NB: Всё обсуждаемое касается разработки на C++ под Linux, но может быть применимо ко всем POSIX.1-2008 совместимым системaм (с оглядкой на конкретную реализацию).
        ========

        Все-так скорее «Все обсуждаемое применимо сугубо для Linux и не применимо к остальным POSIX совместимым платформам» т.к. вы делаете фундаментальные допущения, которые верны и то с оговорками только для Linux.

        > В третьих, сомневаюсь, что этот элемент (XBD/TC2/D6/26), в какой-либо распространнённой ОС применяется. Я-бы предположил, что в целях совместимости pthread_t в большинстве систем останется арифметическим, либо может быть имплементирован как указатель на структуру (что оставлят его арифметическим).

        Неверное предположение. Первое, что приходит в голову — *BSD. Второе — почти уверен что QNX. Третье — скорее всего остальные *NIX. Сугубо для проформы:

        github.com/freebsd/freebsd/blob/master/sys/sys/_pthreadtypes.h

        Просто потому, что pthread_t нигде не используется по значению. Мы всегда оперируем указателем на этот тип. Детали реализации по-определению скрыты от пользователя и он не должен делать каких-либо предположений на этот счет. Как следствие, гораздо удобнее объявить его как прозрачную структуру чтобы упростить себе жизнь внутри реализации.


        1. ianzag
          29.10.2018 15:11
          #19297515

          Впрочем, если pthread_t сам по себе — это указатель на структуру, код выше вполне валиден т.к. арифметических операций над ним не производится но лишь присваивание или сравнение на равенство. Хотя выглядит все равно подозрительно.


        1. thatsme Автор
          29.10.2018 15:12
          #19297525

          Вот сразу из вашей-же ссылки на исходники BSD:


          typedef struct  pthread         *pthread_t

          На этом вопрос можно считать закрытым, т.к. никто в здравом уме не будет ломать совместимость систем.


          Если конечно очень хочется занудствовать, то найдите ссылки на исходники с ОС, где pthread_t не указатель или интегральный тип.


          1. ianzag
            29.10.2018 16:30
            #19297915

            А, вспомнил, что мне показалось таким неправильным в попытке запихнуть pthread_t куда-либо включая атомик. Даже если вы не проводите над ними арифметических операций, даже сравнивать два потока нужно не абы как но через pthread_equal()

            pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_equal.html#

            Все остальное UB. Как эксперимент на попробовать здесь и сейчас — согласен, забавно. Но как тенденция — навряд ли.


            1. thatsme Автор
              29.10.2018 18:30
              #19298373

              Основная проблема с UB, это то что Thread ID может быть инвалидным, именно тогда UB. pthread_self() всегда гарантируемо и предсказуемо вернёт одно и тот-же значение для того-же самого потока. Даже если pthread_t это указатель на структуру, то pthread_self() всегда вернёт один и тот-же адрес. unlock() может подвиснуть если заблокировавший мьютекс поток умер, не разблокировав его. Но тут уже неважно кто сравнивает значения pthread_t.

              Т.е. с практической точки зрения, всё прекрасно будет работать, с вышеупомянутой оговоркой.

              Хотя, как я уже заметил в самой статье, — эти костыли просто плохо, предоставляемое системной лучше.


  1. 3dcryx
    29.10.2018 13:09
    #19296913

    Крайне интересный результат с семафорами. Можно код самого теста? Системный семафор построен на спинлоках или на обычных мьютексах?


    1. thatsme Автор
      29.10.2018 15:05
      #19297493

      Системный семафор построен на спинлоках или на обычных мьютексах

      ./kernel/locking/rwsem-spinlock.c


      Но в glibc (см. sem_waitcommon.c) используются как атомарные операции (попытка получить без блокировки: __new_sem_wait_fast (struct new_sem sem, int definitive_result)), так и атомарные + ожидание по времени (__new_sem_wait_slow (struct new_sem sem, const struct timespec *abstime)) в do_futex_wait (sem, abstime).


      Вообще семафор имеет среди прочего интерфейс sem_timedwait, что намекает на необходимость использования ожидания по времени в том числе.


      Так вот вот это ожидание с квотой времени, которое не поднимается до уровня userland очень классно экономит ресурсы. Т.к. с каждым nanosleep в userland мы проваливаемся до ядра там наш поток перепланируют, потом мы просыпаемся, потом понимаем что нужно ждать ещё и опять спим. Вобщем это результат с lock-free, вполне нормально объясняет.


      Вот так ...


      Алгоритм тестов простой, запускается N потоков, каждый из этих потоков ожидает на одном и том-же семафоре, в случае срабатывания семафора, инкрементирует аттрибут wake для данного потока. В деструкторе печать значения wake.
      В основном потоке, после старта N-ждущих, получаем срез времени (старт), запускаем sem_post() на М итераций, получаем срез времени (стоп), принудительно останавливаем все потоки (получая печать результатов wakes на экран), и выводим результат стоп-старт в милисeкундах для M итераций sem_post().


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


  1. zowers
    29.10.2018 15:06
    #19297495
    +1

    битая ссылка на LAppS (ithub вместо github)


  1. mayorovp
    29.10.2018 15:26
    #19297593

    Lock-free mutex невозможен, ведь задача мьютекса — блокировать. Для того, чтобы алгоритм назывался Lock-free, недостаточно добавить в него спинлок на атомике! Должно выполняться еще одно условие: любой провал спинлока означает, что другой поток успешно продвинулся.


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


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


    1. thatsme Автор
      29.10.2018 15:40
      #19297671

      Я с вами полностью согласен. Более того в приведённом семафоре (в отличии от мьютекса), это условие выполняется. Там как минимум 7-мь потоков параллельно в состоянии получить значение семафора(т.к. post() многократно быстрее). Однако, в событийно ориентированной системе, ждать приходится. Применимость чистого lock-free для моих кейсов вообще сомнительная и это просто эксперименты.


      1. mayorovp
        29.10.2018 16:04
        #19297779

        Нет, для семафора оно тоже в общем виде не выполняется. Потому что у него тоже есть достижимое состояние когда вызов lock будет ждать прихода другого потока неопределенно долго (а если оно недостижимо — то этот семафор нафиг не нужен).

        И чтобы не жечь под нагрузкой процессор впустую — надо бы вместо nanosleep откатываться на обычное решение с mutex и condition variable.


        1. thatsme Автор
          29.10.2018 17:06
          #19298077

          А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор. А семафоры в LAppS используются что-бы ждать событий. Из за латентности сетевого стека, кол-во операций post() в реальной системе (а не в синтезе), всегда медленнее операций чтения.

          И не нужен mutex с condition_variable, т.к. они ни чем не лучше POSIX семафоров. А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.


          1. mayorovp
            29.10.2018 17:19
            #19298133

            А вы статью не внимательно читали. nanosleep, как-раз и не зжёт процессор.

            Но все равно процессорное время тратится впустую.


            А вышеприведённая имплементация не хуже mutex с condition_variable. По крайней мере на моих тестах.

            Ну нет, вышеприведенная реализация — как раз хуже чем mutex с condition_variable. По крайней мере, в ситуации когда все потоки сделали wait, и никто не делает post (чему эта ситуация соответствует — высокой нагрузке или простою — зависит от того как семафор используется). Возможно, этой ситуации просто нет в ваших тестах.


            1. thatsme Автор
              29.10.2018 18:19
              #19298345

              int nanosleep(const struct timespec rqtp, struct timespec rmtp);


              Но все равно процессорное время тратится впустую.

              Нет, оно отдаётся другим потокам.


              man nanosleep(3)


              int nanosleep(const struct timespec *rqtp, struct timespec *rmtp);

              Description
              The nanosleep() function shall cause the current thread to be suspended from execution until either the time interval specified by the rqtp argument has elapsed or a signal is delivered to the calling thread, and its action is to invoke a signal-catching function or to terminate the process.

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


              1. mayorovp
                29.10.2018 18:22
                #19298355

                В пустую тратится не то время про которое вы подумали, а время в течении которого переключаются контексты плюс время на проверку условия цикла.


                1. thatsme Автор
                  29.10.2018 18:40
                  #19298395

                  Да. Об этом я и в статье написал. По моему с condition_variable будет экономнее только если использовать notify_one(), a если notify_all(), то даже хуже. ведь там и на блокировке мьютекса контекст переключается и на вызов к wait() и на notify. Вообще нужно считать и тестировать. Потестирую сейчас пожалуй. И сообщу.


                  Протестировал. Если вас устроит такая поделка на condition_variable вместо семафора:


                  class SemEmuCond
{
private:
  std::mutex              mMutex;
  std::condition_variable mCond;
  size_t counter;
public:
  SemEmuCond():mMutex(),mCond(),counter(0){}

  void post()
  {
    std::unique_lock<std::mutex> lk(mMutex);
    mCond.wait(lk,[this]{++counter; return true;});
    mCond.notify_all();
  }

  void wait()
  {
    while(1)
    {
       std::unique_lock<std::mutex> lk(mMutex);
       mCond.wait(lk);
       if(counter>0)
       {
         --counter;
         break;
       }
    }
  }
};

                  То результаты печальные:


                  1. терминация потока ожидающего на подобном семафоре приводит к UB.
                  2. производительность: 

                  Started 4 EmuCond threads waiting on a semaphore
CondEmu semaphores test. 10000000 of posts for 4 waiting threads have taken 5349 miliseconds
CondEmu semaphores test. Post latency: 0.5349ns

                  По потокам проблема, см п. 1


                  20 threads:


                  CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12529 miliseconds
CondEmu semaphores test. Post latency: 1.2529ns
Thread(EmuCond) wakes: 353156
terminate called without an active exception
Аварийный останов

                  т.е. хуже.


                  1. mayorovp
                    29.10.2018 20:05
                    #19298675

                    Э… зачем вы делаете mCond.wait в post? Почему не notify_one? Зачем вы делаете mCond.wait в wait безусловно? Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep, а не вместо всего вашего алгоритма…


                    1. thatsme Автор
                      29.10.2018 20:26
                      #19298719

                      Вы правы в post() совершенно не нужно делать: mCond.wait(lk,[this]{++counter; return true;});
                      Там как-бы итак мьютекс эксклюзивно локируется. Заменил на ++counter;

                      Результат:

                      Started 20 EmuCond threads waiting on a semaphore
                      CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 12106 miliseconds
                      CondEmu semaphores test. Post latency: 1.2106ns

                      Т.е. выигрышь 5% относительно предыдущего.

                      notify_one() — плохо, т.к. будить будет последовательно, а если post() быстрее потребления и аппаратных потоков в системе например 4-е, то при пробуждении 3 консамера должны суметь декрементировать семафор практически одновременно.

                      Как подтверждение результат с notify_one():

                      Started 20 EmuCond threads waiting on a semaphore
                      CondEmu semaphores test. 10000000 of posts for 20 waiting threads have taken 22821 miliseconds
                      CondEmu semaphores test. Post latency: 2.2821ns

                      > Наконец, куда делись ваши атомики? Я же предлагал использовать это решение вместо nanosleep

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

                      Фигня получилась. Тут тебе и мьютекс, тут тебе и атомики тут и кондишн-вар, я пока делал понял, что фигня будет. Как результат:

                      … 10000000 of posts for 20 waiting threads have taken 12704 milisecond
                      Post latency: 1.2704ns

                      Т.е это вообще не вариант, а учитывая что потоки произвольно теперь убивать нельзя пока они на кондиш-не ждут, то вообще но-гоу.


                      1. mayorovp
                        29.10.2018 22:17
                        #19298971

                        То есть с атомиками получилось столько же, сколько и без них, и это все — медленнее чем с нанослипом? А вы точно атомики снаружи мьютекса менали? :-)


                        1. thatsme Автор
                          29.10.2018 23:15
                          #19299199

                          Да точно. На самом деле всё ещё проще. Попробуйте сами. Это-же элементарно.


      1. mayorovp
        29.10.2018 16:19
        #19297857

        По поводу же применимости lock-free для ваших кейсов — тут все просто. В первом кейсе lock-free должны были применять авторы LibreSSL, а не вы.

        Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.


        1. thatsme Автор
          29.10.2018 17:10
          #19298093

          Во втором и третьем кейсах, я так понимаю, вся lua-часть выполняется в один поток, и где-то крутится цикл ожидания событий? В таком случае lock-free невозможен, опять-таки, исходя из задачи.


          Нет не верно. Потоков Lua может быть столько сколько инстансов каждого сервера выполняется. Поступление событий по сети (в моих условиях), заведомо медленнее чем их обработка в потоках lua (парадокс, но на echo тестах это так). И простое отключение iptables производительность сервера увеличивает на 30%… вот как…


          1. mayorovp
            29.10.2018 17:20
            #19298141

            Ну значит, у вас несколько потоков крутится в цикле ожидания события? Это ничего не меняет...


    1. mk2
      29.10.2018 17:24
      #19298155

      Вы сейчас что-то странное сказали.

      «Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.

      «если системный планировщик почему-то решит, что только один поток достоин получать процессорное время, то этому самому потоку ничего не должно помешать» — это obstruction freedom, самое слабое условие lock-free алгоритмов. Это условие, кстати, сильнее deadlock freedom.

      Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса. Редко когда эффективная, это да.

      А собственно смысл lock-free не в том, что мы никогда не ждём. Он в том, что в алгоритме не должно быть критических секций. То есть мьютексов/спинлоков не должно быть в принципе.


      1. mayorovp
        29.10.2018 17:35
        #19298193

        «Любой провал спинлока означает, что другой поток успешно продвинулся» — точнее, другой поток получил лок. Это deadlock freedom, самое слабое условие алгоритмов с блокировками.

        Нет, deadlock freedom требует чтобы хоть какой-нибудь поток в конечном счете (Whatever the time T… then there is a time T' > T at which ...) успешно получил лок. А я писал о том, что происходит за одну итерацию, это и есть требование lock freedom.


        Сведение мьютекса исключительно к спин-локам в теории проблем не вызывает, т.к. спин-лок — одна из возможных реализаций мьютекса/

        Сведение мьютекса исключительно к спин-локам проблем, может быть, и не вызывает — но не позволяет мьютексу называться lock-free.


        1. mk2
          29.10.2018 17:47
          #19298237

          А, то есть вы хотели lock freedom описать. Только тогда стоит написать «провал операции» как более абстрактное, или вообще «хотя бы один поток выполнит операцию при любых действиях других потоков» — в вашем определении забыт случай с 1 потоком :-)

          Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.


          1. mayorovp
            29.10.2018 17:51
            #19298245

            Когда операция — это получение блокировки через спинлок, провал операции — это провал спинлока.


            Касательно спинлоков — они тоже не lock-free. Вообще lock-free — это когда как минимум нет блокировок, т.е. ни мьютексов, ни спинлоков, ни семафоров.

            Ну так я именно это и написал же. С чем вы спорите?


            1. mk2
              29.10.2018 17:57
              #19298275

              Наверное, с неудачной формулировкой.

              Должно выполняться еще одно условие

              Как бы подразумевается, что как-то это условие сделать, и мьютекс становится lock-free. Хотя на самом деле единственный способ получить lock-free это выкинуть все мьютексы вообще.
              вся затея со сведением мьютекса исключительно к спин-локам обречена на провал

              Лучше было бы «вся затея с получением lock-free мьютекса», потому что сводить мьютекс к его реализации на спин-локах нам ничто не мешает, а заменять первые на вторые может даже оказаться полезно.


              1. mayorovp
                29.10.2018 18:18
                #19298339

                Так все правильно же. Достаточно выполнить невыполнимое условие — и мьютекс станет lock-free :-)


  1. Videoman
    29.10.2018 16:05
    #19297789

    Если занудствовать дальше, то у автора получился «не честный» семафор, так как «настоящий» семафор должен гарантировать равный шанс для каждого ждущего потока при доступе к ресурсу, а тут уже простым счетчиком не ограничишься. Придется городить lock-free список ждущих потоков и т.д. Глядишь и скорость выровнится, по сравнению со стандартным семафором. А так — да, срезать углы можно, но надо понимать за счет чего.


    1. thatsme Автор
      29.10.2018 17:02
      #19298053

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


      1. Videoman
        29.10.2018 17:16
        #19298115

        Я представляю как работает семафор и, не много, не об этом. Представьте что счетчик ресурсов исчерпан (нуль) и в этот момент еще 10 потоков пытаются захватить ресурс. Ясно что все они буду ждать пока ресурс не появится. Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны. Хорошая реализация семафора должна пробуждать потоки гарантируя, в среднем, каждому ожидающему потоку равную возможность получить ресурс.


        1. thatsme Автор
          29.10.2018 18:06
          #19298309

          Вопрос в том, какие потоки, из уже ожидающих, пробудятся в случае когда ресурсы семафора снова станут доступны


          А тут также как и в системной реализации, какой поток CFQ пробудит первым, тот и получит преимущество, а в среднем шансы у них действительно равные. POSIX многоядерности OS не специфицирует кстати, поэтому параллельного пробуждения планировщиком также не существует и кто-то становится «первым среди равных».


      1. mk2
        29.10.2018 17:36
        #19298205

        Не совсем с теми же.
        На системном семафоре у всех потоков 500000 +- 3000 сообщений. Практически поровну.
        На вашем есть «удачливый» поток с 600000 сообщениями, и пара «неудачников» с 450000 — разница на треть.


        1. thatsme Автор
          29.10.2018 18:10
          #19298321

          А тут как раз просто. Этот фокус элементарен, в этом тесте (см пояснения выше), некоторые потоки довольно долго вообще в сон не уходят, т.к. post() многократно быстрее чем wait(). Ведь 20 потоков ждут, каки-е то спят, а какие-то молотят, так вот преимущество у тех потоков, у которых квота процессорного времени не истекла, но вы их посчитайте, — 7 потоков с изначальным преимуществом (Core i7).


  1. robert_ayrapetyan
    29.10.2018 19:07
    #19298489

    А можно ссылку на код с тестами?


    1. thatsme Автор
      29.10.2018 19:15
      #19298523

      Посмотрите плиз в этот комментарий, там пояснено почему вам эти исходники ничего не дадут и описан алгоритм теста. Напишите свои, это на пол часа работы.


  1. vintage
    29.10.2018 22:54
    #19299097

    А вы не думали использовать wait-free алгоритмы? Например, передачу сообщений между потоками можно делать через циклический буфер с двумя указателями. Каждый перемещает свой указатель, не ожидая других. Чтение чужого указателя и перемещение своего разделяем барьерами памяти — это гарантирует, что один другой не обгонит. Если надо надо слать многим потокам или принимать из разных мест — создаём по такому буферу на каждую пару и шлём через раунд-робин. Если хотим записать, а все буферы переполнены — либо подвисаем в ожидании, либо делаем что-то ещё. И наоборот, если хотим получить, а буферы пусты, то либо подвисаем, либо делаем что-то ещё. Вот тут я описываю использование горутин и каналов реализованных по этим принципам. А тут можно глянуть исходники.


    1. thatsme Автор
      30.10.2018 07:58
      #19299827

      Интересно, нужно подумать. Вполне возможно, что очередь сообщений между продьюсерами и консамерами можно заменить на такой кольцевой буфер с барьерами, но что делать консамеру когда нет данных, когда буфер пуст? nanosleep опять?


      1. vintage
        30.10.2018 09:40
        #19300117

        Если он больше ничего не умеет, а новых задач нет, то видимо да.