▲

GN⁺: 가장 빠른 Mutexes

 (justine.lol)
2P by neo 2달전 | favorite | 댓글 1개
  • Cosmopolitan Libc는 여러 운영 체제에서 실행 가능한 이진 파일을 제공하는 것으로 유명하며, 생산 환경에서도 뛰어난 성능을 발휘할 수 있는 C 라이브러리임.
  • 성능 증명을 위한 뮤텍스 벤치마크 : 30개의 스레드가 동일한 정수를 100,000번 증가시키는 테스트를 통해 뮤텍스 구현의 성능을 비교함
    • Windows
      • Cosmopolitan pthread_mutex_t 는 Microsoft의 SRWLOCK보다 2.75배 빠르고, CPU 자원을 18배 적게 사용함
      • Cygwin의 뮤텍스는 성능이 매우 낮아 스핀 락을 사용하는 것이 더 나을 정도임.
    • Linux
      • Cosmopolitan pthread_mutex_t 는 glibc보다 3배, musl libc보다 11배 빠름
      • CPU 사용량은 glibc보다 42배, musl libc보다 178배 적음
    • MacOS
      • Apple Libc가 Cosmopolitan의 뮤텍스보다 약간 더 나은 성능을 보임
      • Cosmopolitan은 Ulrich Drepper의 "Futexes Are Tricky" 논문에 기반한 알고리듬을 사용하여 성능을 최적화함

어떻게 가능한거지?

  • Google의 저명한 엔지니어 Mike Burrows가 작성한 nsync 라이브러리를 사용하여 뛰어난 성능을 발휘함
    • 그는 예전 구글의 경쟁자였던 Altavista를 코딩한 사람임
  • nsync의 트릭과 분석
    • nsync는 경합이 없을 때 빠르게 잠금이 발생하도록 낙관적인 CAS(compare and swap)를 즉시 사용함
    • 잠금을 획득할 수 없을 때 nsync는 호출 스레드를 대기자의 이중 연결 리스트에 추가함
      • 각 대기자는 별도의 독립적인 캐시라인에 자체 세마포어를 받음
      • 스레드가 대기 상태에 들어가면 더 이상 기본 잠금을 건드리지 않음
      • 이것이 중요한 이유는 Ulrich Drepper의 "What Every Programmer Should Know About Memory" 문서에서 확인할 수 있음
      • 여러 코어가 동일한 캐시라인을 터치하면 프로세서 내에서 많은 통신 오버헤드가 발생함
    • nsync는 futex를 사용하여 운영 체제의 도움을 받음
      • futex는 Linux에서 몇 년 전에 발명된 훌륭한 추상화로, 다른 OS에서 빠르게 사용되기 시작함
      • MacOS에서는 ulock이라고 하고, Windows에서는 WaitOnAddress()라고 함
      • Cosmo가 지원하는 OS 중 futex가 없는 유일한 OS는 NetBSD임 (POSIX 세마포어를 커널 공간에 구현하며, 각 세마포어는 새 파일 디스크립터를 만들어야 함)
      • futex와 세마포어의 중요한 점은 OS가 스레드를 잠자게 할 수 있다는 것임. 이를 통해 nsync는 수행할 작업이 없을 때 CPU 시간을 소비하지 않을 수 있음
    • nsync는 "긴 대기(long wait)" 개념으로 기아 상태를 피함
      • 대기자가 30번 깨어나고 내부적으로 잠금 획득에 실패하면 아직 기다리지 않은 스레드가 획득하는 것을 방지하는 비트를 잠금에 추가함
      • 대기열이 어느 정도 해소될 때까지 다른 모든 사람에 대해 초기 CAS가 실패함
    • nsync는 "지정된 깨우는 사람(designated waker)" 개념을 사용하여 벤치마크한 사용 사례(작은 임계 영역이 있는 경합 잠금)를 빠르게 만듦
      • 잠금을 얻으려고 시도하는 스레드가 깨어 있을 때 기본 잠금에 이 비트가 설정됨
      • nsync에서 잠금 해제 함수는 잠금을 기다리는 다음 스레드를 깨우는 역할을 함
      • 이 비트가 있으면 잠금 해제 스레드는 하나의 잠금 장치가 이미 깨어 있기 때문에 두 번째 잠금 장치를 깨울 필요가 없다는 것을 알 수 있음

온라인 증명

  • Cosmopolitan 뮤텍스를 사용한 소프트웨어의 라이브 데모를 통해 성능을 확인할 수 있음.
  • http://ipv4.games/ 웹 서버는 대규모 DDOS 공격에도 견딜 수 있는 성능을 보여줌.
▲
neo 2달전  [-]
Hacker News 의견

  • 새로운 뮤텍스 구현과 그 성능 비교를 보는 것은 항상 흥미로움. 하지만 이번 벤치마크는 미세 벤치마크처럼 보임. 대규모 멀티스레드 프로그램을 사용해 성능을 테스트하는 것이 일반적임. 복잡한 작업 부하에서는 뮤텍스의 성능이 다르게 나타남

    • WebKit에서 사용하는 빠른 락을 작성한 경험이 있으며, ParkingLot 추상화를 발명한 사람임. 이는 Rust와 Unreal Engine에서도 사용됨

  • Cosmopolitan Mutexes가 좋은 이유는 nsync라는 라이브러리를 사용했기 때문임. 이 라이브러리는 Google의 저명한 엔지니어 Mike Burrows가 작성함. 하지만 이 뮤텍스 구현이 벤치마크에 포함되지 않은 이유가 궁금함

    • macOS에서 __ulock을 사용한다면, libc++의 atomic 라이브러리의 wait(), notify_one() 함수로 더 간단하게 구현할 수 있음

  • Cosmo/ape/redbean에 대한 긍정적인 의견이 많지만, 실제로 사용하는 사람을 본 적이 없음. 이러한 도구들이 정말 혁신적이지만 아직 널리 사용되지 않은 것인지 궁금함

  • Cosmopolitan 프로젝트를 높이 평가하지만, 과장된 우월성 주장에는 의심이 듦. 모든 C 라이브러리가 같은 트릭을 채택하지 않은 이유는 특정 아키텍처나 CPU 모델, 작업 부하에만 항상 빠르기 때문일 수 있음

  • 프로덕션 환경에서는 속도나 효율성보다 신뢰성이 중요함. 시스템이 고장 나지 않도록 하는 것이 더 중요함

  • nsync의 뮤텍스 해제 함수에서 발견한 버그를 수정한 경험이 있음. Cosmopolitan 프로젝트 내에서 nsync의 개선 사항을 보고 있음. 업스트림 nsync를 사용하는 것이 안전한지 궁금함

  • 스레드와 뮤텍스는 컴퓨터 과학에서 가장 복잡한 요소 중 하나임. 새로운 구현이 대규모로 사용되기 전까지는 항상 회의적임. Java가 등장했을 때 Solaris에서 많은 스레드와 뮤텍스 버그가 드러났음

  • nsync가 SRWLOCK보다 훨씬 빠르다는 점에 놀람. win32 SRWLOCKs를 역설계한 경험이 있음

  • 뮤텍스를 볼 때마다 부정적인 감정이 생김. 많은 코드에서 락을 제거하고 큐나 메시징 추상화로 대체하는 작업을 해왔음. 최근에는 다양한 락킹 알고리즘을 탐구하고 있음. nsync와 같은 효율적인 락킹 도구를 사용해보고자 함

답변달기