[Перевод] Самые быстрые мьютексы04.10.2024 19:45

Cosmopolitan Libc хорошо известна своим «полиглотным жирным бинарным» хаком, который позволяем исполняемым файлам запускаться на шести операционных системах для AMD64/ARM64. Вас может удивить, что при этом она может быть лучше С‑библиотекой для вашего продакшена. Чтобы продемонстрировать это, давайте сравним библиотеку мьютексов Cosmo с другими платформами.

Мы напишем простой тест, который создает 30 потоков, увеличивающих одно и то же число 100 000 раз. Это поможет проверить, насколько хорошо реализация мьютексов справляется с задачей при интенсивном использовании. По сути он будет следующим (см. сегмент внизу статьи для полного исходного кода).

int g_chores;
pthread_mutex_t g_locker = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
  for (int i = 0; i < ITERATIONS; ++i) {
    pthread_mutex_lock(&g_locker);
    ++g_chores;
    pthread_mutex_unlock(&g_locker);
  }
  return 0;
}

Теперь перейдем к самому интересному — результатам моих тестов.

Бенчмарки

Время будет измеряться в микросекундах. Wall time — это время, за которое выполняется тестовая программа. Оно включает накладные расходы на создание и завершение потоков. User time — это время, которое процессор потратил в пользовательском пространстве, а system time — это время, затраченное процессором в ядре. System и user time могут превышать фактическое wall time, поскольку несколько потоков работают параллельно.

Первые результаты, которые я покажу, касаются Windows, потому что Марк Уотерман провёл отличный тест мьютекс три месяца назад, где он сказал: «в условиях высокой конкуренции Windows выигрывает с его SRWLOCK». Ситуации с высокой конкуренцией показывают разницу в реализации мьютексов. Марк был настолько впечатлен SRWLOCK от Microsoft, что рекомендовал пользователям Linux и FreeBSD рассмотреть возможность перехода на Windows, если проблема заключается в конкуренции мьютексов.

9071030c10031670ad141493261a04fb.png

Как мы видим, мьютексы Cosmopolitan Libc работают в 2,75 раза быстрее, чем SRWLOCK от Microsoft (который ранее считался лучшим из лучших), при этом потребляют в 18 раз меньше ресурсов процессора. Мьютексы Cosmopolitan также оказались в 65 раз быстрее, чем Cygwin, который, как и Cosmopolitan, предоставляет реализацию POSIX на Windows. Мьютексы Cygwin настолько плохи, что для этого случая им было бы лучше использовать спинлоки.

Теперь перейдём к Linux, повелителю всех операционных систем.

fc33150343d7ec11342608cb15bf6044.png

Здесь мы видим, что мьютексы Cosmopolitan:

  • В 3 раза быстрее, чем glibc

  • В 11 раз быстрее, чем musl libc

  • Потребляют в 42 раза меньше процессорного времени, чем glibc

  • Потребляют в 178 раз меньше процессорного времени, чем musl libc

Вот как это работает на практике. Представьте, что у вас есть задача, где все потоки должны выполнять последовательную операцию. Если вы используете Cosmopolitan и посмотрите на htop, то будет казаться, что активно только одно процессорное ядро, в то время как glibc и musl libc буду использовать все ядра на вашем процессоре. Это плохие новости, если вы запускаете множество задач на одном сервере. Если хотя бы на одном из ваших серверов произойдет «кровавая баня» с мьютексами, то все ваши ресурсы будут исчерпаны, если вы не используете Cosmopolitan. Это все еще новая библиотека C, и у неё есть небольшие шероховатости. Но она настолько быстро совершенствуется, что я начинаю считать неиспользование её в продакшене отказом от профессиональной ответственности. Библиотека C так глубоко встроена в цепочку поставок программного обеспечения и настолько зависит от неё, что вам действительно не хочется, чтобы она стала «планетарным убийцей». Если столь важные и неоспоримые инструменты настолько расточительны, неудивительно, что Amazon Cloud зарабатывает такие деньги.

И, наконец, у нас есть MacOS.

9fd8e81256e4e07b41cd1367fb9ce97f.png

На MacOS с микропроцессором M2 на базе ARM64 библиотека Apple Libc немного превосходит мьютексы Cosmopolitan. По причинам, которые я ещё полностью не понимаю, стандартная реализация мьютексов Cosmopolitan работает не так эффективно на этой платформе. Возможно, это связано с тем, что M2 и ядро XNU работают в связке. Поэтому на MacOS ARM Cosmopolitan использует более простый алгоритм, основанный на статье Ульриха Дреппера «Futexes Are Tricky», который по сути передаёт всю сложную работу системным вызовам XNU ulock. Вот почему производительность практически идентична тому, что делает Apple.

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

Как я это сделал

Причина, по которой мьютексы Cosmopolitan такие эффективные, заключается в том, что я использовал библиотеку nsync. У нее всего 371 звезда на GitHub, но ее написал выдающийся инженер из Google по имени Mike Burrows. Если вы не знаете, кто это, то это человек, который разработал главного конкурента Google — Altavista. Если вы не настолько стары, чтобы помнить Altavista, то это был первый действительно хороший поисковик и он работал на одном компьютере.

Мне очень понравилось интегрировать nsync в Cosmopolitan. Более того, у меня даже была возможность внести изменения в upstream. Например, я нашел и исправил баг в функции разблокировки мьютекса, который оставался незамеченным годами. Также мне удалось ускорить работу мьютексов nsync на 30% по сравнению с оригинальной версией на AARCH64, портировав их для использования атомарных операций из стандарта C11. Я написал новую системную интеграцию для таких вещей, как futex, которые позволяют обеспечить переносимость во время выполнения. И, наконец, я добился того, чтобы библиотека безупречно работала с отменой потоков в POSIX.

Итак, как же nsync это делает? Какие трюки она использует? Вот мои мысли и анализ:

  • nsync использует оптимистичный CAS (compare and swap) сразу же, чтобы блокировка происходила быстро, если нет конкуренции за ресурсы.

  • Когда захватить блокировку не удается, nsync добавляет вызывающий поток в двусвязный список ожидающих. Каждый ожидающий поток получает собственный семафор на отдельной независимой кеш‑линии. Это важно, так как как только поток переходит в состояние ожидания, он больше не взаимодействует с основной блокировкой.

    Чтобы понять, почему это важно, стоит ознакомиться с работой Ульриха Дреппера What Every Programmer Should Know About Memory. В ней он подробно описывает протоколы когерентности, используемые современными микропроцессорами. Эти протоколы позволяют ядрам «общаться» друг с другом на низком уровне, отслеживая, какие кеш‑линии они используют. Когда несколько ядер обращаются к одним и тем же линиям, это создает значительные накладные расходы на коммуникацию внутри процессора.

  • nsync использует помощь операционной системы через futex«ы. Это отличная абстракция, изобретенная Linux несколько лет назад и быстро получившая распространение в других ОС. На macOS futex«ы называются ulock, а на Windows — WaitOnAdress (). Единственная ОС, поддерживаемая Cosmo, где нет futex«ов — NetBSD, которая реализует POSIX‑семафоры на уровне ядра, но каждый семафор требует создания нового файлового дескриптора, что не очень удобно.

    Главное преимущество futexэов и семафоров заключается в том, что они позволяют операционной системе «усыплять» поток. Это дает nsync возможность избегать использования процессорного времени, когда нет работы, которую нужно выполнить.

  • nsync избегает ситуации голодания, используя концепцию «долгого ожидания». Если поток, ожидающий разблокировки,  был пробужден 30 раз и каждый раз не смог получить блокировку, то nsync добавляет бит к блокировке, который предотвращает получение блокировки потоками, которые еще не успели дождаться своей очереди. Это означает, что первоначальный CAS будет неудачными для всех остальных потоков, пока очередь не освободиться.

  • nsync ускоряет тестируемый нами кейс (конкурирующая блокировка с небольшой критической секцией) благодаря концепции «назначенного пробудителя». Этот бит на главной блокировке устанавливается, когда поток пробуждается и пытается получить блокировку. В nsync функция разблокировки отвечает за пробуждение следующего потока в очереди, ожидающем блокировку. Наличие этого бита позволяет потоку, освобождающему разблокировку, пониматься, что нет необходимости пробуждать второй ожидающий поток, так как один поток уже пробужден.

Чтобы узнать больше секретов nsync, вы можете ознакомиться с исходным кодом по следующим ссылкам: https://github.com/jart/cosmopolitan/blob/master/third_party/nsync/mu.c и https://github.com/jart/cosmopolitan/blob/master/libc/intrin/pthread_mutex_lock.c

Online Proof

Если вы хотите увидеть живую демонстрацию программного обеспечения, созданного с использованием мьютексов Cosmopolitan, тогда сделайте самую худшую DDoS‑атаку на веб‑сервер http://ipv4.games/. Это действительно игра для хакеров, соревнующихся за доминирование в Интернете. Вы уже играете в эту игру, потому что ваш IP только что был зарегистрирован для jart. Этот сервис работает на виртуальной машине GCE с двумя ядрами и до сих пор успешно выдерживает DDoS‑атаки ботнетов численностью до 49,131,669 IP‑адресов. Во многом это стало возможным благодаря библиотеке nsync, которая позволила мне переместить SQL‑запросы в фоновые потоки, которые отправляют сообщения друг другу. В нем еще есть что улучшать, но в целом система работает хорошо. Вы даже можете отслеживать ее метрики состояния на странице /statusz.

Исходный код

#define ITERATIONS 100000
#define THREADS    30

int g_chores;
pthread_mutex_t g_locker = PTHREAD_MUTEX_INITIALIZER;

void *worker(void *arg) {
  for (int i = 0; i < ITERATIONS; ++i) {
    pthread_mutex_lock(&g_locker);
    ++g_chores;
    pthread_mutex_unlock(&g_locker);
  }
  return 0;
}

struct timeval tub(struct timeval a, struct timeval b) {
  a.tv_sec -= b.tv_sec;
  if (a.tv_usec < b.tv_usec) {
    a.tv_usec += 1000000;
    a.tv_sec--;
  }
  a.tv_usec -= b.tv_usec;
  return a;
}

long tomicros(struct timeval x) {
  return x.tv_sec * 1000000ul + x.tv_usec;
}

int main() {
  struct timeval start;
  gettimeofday(&start, 0);

  pthread_t th[THREADS];
  for (int i = 0; i < THREADS; ++i)
    pthread_create(&th[i], 0, worker, 0);
  for (int i = 0; i < THREADS; ++i)
    pthread_join(th[i], 0);
  assert(g_chores == THREADS * ITERATIONS);

  struct rusage ru;
  struct timeval end;
  gettimeofday(&end, 0);
  getrusage(RUSAGE_SELF, &ru);
  printf("%16ld us real\n"
         "%16ld us user\n"
         "%16ld us sys\n",
         tomicros(tub(end, start)),
         tomicros(ru.ru_utime),
         tomicros(ru.ru_stime));
}

Причина, по которой нас интересуют сценарии с высокой конкуренцией, заключается в том, что именно в таких случаях проявляется неравенство в реализации мьютексов. Неконкурирующие мьютексы обычно работают одинаково во всех реализациях, и даже в таких случаях вы можете предпочесть использовать спинлок, которая требует всего несколько строк кода: 

void spin_lock(atomic_int *lock) {
  if (atomic_exchange_explicit(lock, 1, memory_order_acquire)) {
    for (;;) {
      for (;;)
        if (!atomic_load_explicit(lock, memory_order_relaxed))
          break;
      if (!atomic_exchange_explicit(lock, 1, memory_order_acquire))
        break;
    }
  }
}

void spin_unlock(atomic_int *lock) {
  atomic_store_explicit(lock, 0, memory_order_release);
}

Обратите внимание, что спинлок следует использовать только в тех случаях, когда у вас нет другого выбора. Они полезны в ядрах операционных систем, где строгие низкоуровневые ограничения не позволяют применять более сложные решения. Спинлоки также являются полезной деталью реализации в блокировках nsync. Но в целом они плохи. Я предполагаю, что многие разработчики считают их хорошими. Если это так, то, скорее всего, потому, что они делали бенчмарки только для wall time. При использовании блокировок важно также учитывать процессорное время. Вот почему мы используем функцию getrusage ().

© Habrahabr.ru