En hızlı mutex'ler

 (justine.lol)
2 puan yazan GN⁺ 2024-10-03 | 1 yorum | WhatsApp'ta paylaş
  • Cosmopolitan Libc, birden fazla işletim sisteminde çalışabilen ikili dosyalar sunmasıyla bilinir ve üretim ortamında da üstün performans gösterebilen bir C kütüphanesidir.
  • Performansı kanıtlamak için yapılan mutex benchmark'ı: 30 thread'in aynı tamsayıyı 100.000 kez artırdığı test üzerinden mutex uygulamalarının performansı karşılaştırılıyor.
    • Windows
      • Cosmopolitan pthread_mutex_t, Microsoft'un SRWLOCK'undan 2,75 kat daha hızlı ve CPU kaynaklarını 18 kat daha az kullanıyor.
      • Cygwin'in mutex'i o kadar düşük performans gösteriyor ki spin lock kullanmak bile daha iyi olabilir.
    • Linux
      • Cosmopolitan pthread_mutex_t, glibc'den 3 kat, musl libc'den 11 kat daha hızlı.
      • CPU kullanımı glibc'den 42 kat, musl libc'den 178 kat daha az.
    • MacOS
      • Apple Libc, Cosmopolitan'ın mutex'inden biraz daha iyi performans gösteriyor.
      • Cosmopolitan, performansı optimize etmek için Ulrich Drepper'ın "Futexes Are Tricky" makalesine dayanan bir algoritma kullanıyor.

Bu nasıl mümkün?

  • Google'ın saygın mühendislerinden Mike Burrows'un yazdığı nsync kütüphanesi sayesinde üstün performans sağlanıyor.
    • Kendisi, geçmişte Google'ın rakibi olan Altavista'nın kodunu yazan kişiydi.
  • nsync'in hileleri ve analizi
    • nsync, çekişme olmadığında hızlı kilitleme için iyimser CAS (compare and swap) işlemini hemen kullanıyor.
    • Kilit alınamadığında nsync, çağıran thread'i bekleyenlerin çift bağlı listesine ekliyor.
      • Her bekleyici, ayrı ve bağımsız bir cache line üzerinde kendi semaphore'unu alıyor.
      • Thread bekleme durumuna girdiğinde artık temel kilide dokunmuyor.
      • Bunun neden önemli olduğunu Ulrich Drepper'ın "What Every Programmer Should Know About Memory" belgesinde görmek mümkün.
      • Birden fazla çekirdek aynı cache line'a dokunduğunda işlemci içinde büyük iletişim ek yükü oluşuyor.
    • nsync, işletim sisteminden destek almak için futex kullanıyor.
      • futex, birkaç yıl önce Linux'ta icat edilen harika bir soyutlama ve diğer işletim sistemlerinde de hızla kullanılmaya başlandı.
      • MacOS'ta buna ulock, Windows'ta ise WaitOnAddress() deniyor.
      • Cosmo'nun desteklediği işletim sistemleri arasında futex bulunmayan tek sistem NetBSD; burada POSIX semaphore'ları çekirdek alanında uygulanıyor ve her semaphore için yeni bir file descriptor oluşturulması gerekiyor.
      • futex ve semaphore'un kritik yanı, işletim sisteminin thread'i uyutabilmesidir. Bu sayede nsync, yapılacak iş olmadığında CPU zamanı harcamaz.
    • nsync, aç kalma durumunu önlemek için "uzun bekleme (long wait)" kavramını kullanıyor.
      • Bir bekleyici 30 kez uyandırılıp içeride kilidi alma denemesinde başarısız olursa, henüz beklememiş thread'lerin kilidi almasını engelleyen bir bit kilide ekleniyor.
      • Kuyruk bir ölçüde boşalana kadar herkes için ilk CAS başarısız oluyor.
    • nsync, benchmark'ta ölçülen kullanım senaryosunu (küçük kritik bölgeli çekişmeli kilitler) hızlandırmak için "atanmış uyandırıcı (designated waker)" kavramını kullanıyor.
      • Kilidi almaya çalışan bir thread uyanık olduğunda temel kilitte bu bit ayarlanıyor.
      • nsync'te kilit açma fonksiyonu, kilidi bekleyen bir sonraki thread'i uyandırmaktan sorumludur.
      • Bu bit sayesinde kilidi açan thread, bir kilidin zaten uyanık olduğunu ve ikinci bir kilidi uyandırmasına gerek olmadığını bilir.

Çevrimiçi kanıt

  • Cosmopolitan mutex kullanan yazılımların canlı demosu üzerinden performans görülebilir.
  • http://ipv4.games/ web sunucusu, büyük ölçekli DDOS saldırılarına bile dayanabilecek performans sergiliyor.

İlgili okumalar

1 yorum

 
GN⁺ 2024-10-03
Hacker News görüşleri

  • Yeni mutex uygulamalarını ve performans karşılaştırmalarını görmek her zaman ilgi çekici. Ancak bu benchmark bu kez daha çok bir mikro benchmark gibi görünüyor. Performansı büyük ölçekli çok iş parçacıklı programlarla test etmek daha yaygındır. Karmaşık iş yüklerinde mutex performansı farklı görünebilir

    • WebKit'te kullanılan hızlı lock'u yazma deneyimim var ve ParkingLot soyutlamasını icat eden kişiyim. Bu, Rust ve Unreal Engine'de de kullanılıyor

  • Cosmopolitan Mutexes'ın iyi olmasının nedeni nsync adlı bir kütüphane kullanması. Bu kütüphane Google'ın tanınmış mühendisi Mike Burrows tarafından yazıldı. Ancak bu mutex uygulamasının neden benchmark'a dahil edilmediğini merak ediyorum

    • macOS'ta __ulock kullanılıyorsa, libc++'ın atomic kütüphanesindeki wait() ve notify_one() fonksiyonlarıyla daha basit bir uygulama yapılabilir

  • Cosmo/ape/redbean hakkında çok sayıda olumlu görüş var ama bunları gerçekten kullanan birini hiç görmedim. Bu araçların gerçekten yenilikçi olup da henüz yaygınlaşmamış şeyler mi olduğunu merak ediyorum

  • Cosmopolitan projesini takdir ediyorum ama abartılı üstünlük iddialarına şüpheyle yaklaşıyorum. Tüm C kütüphanelerinin aynı hileleri benimsememesinin nedeni, bunların yalnızca belirli mimarilerde, CPU modellerinde veya iş yüklerinde sürekli hızlı olması olabilir

  • Prodüksiyon ortamında hız ya da verimlilikten çok güvenilirlik önemlidir. Sistemin bozulmamasını sağlamak daha önemlidir

  • nsync'in mutex unlock fonksiyonunda bulduğum bir bug'ı düzeltme deneyimim oldu. Cosmopolitan projesi içinde nsync için yapılan iyileştirmeleri görüyorum. Upstream nsync kullanmanın güvenli olup olmadığını merak ediyorum

  • Thread'ler ve mutex'ler bilgisayar bilimindeki en karmaşık unsurlardan biri. Yeni bir uygulama büyük ölçekte kullanılana kadar her zaman şüpheciyim. Java ilk çıktığında Solaris'te çok sayıda thread ve mutex bug'ı ortaya çıkmıştı

  • nsync'in SRWLOCK'tan çok daha hızlı olmasına şaşırdım. win32 SRWLOCK'ları tersine mühendislikle inceleme deneyimim var

  • Mutex gördüğümde her seferinde olumsuz duygular hissediyorum. Pek çok kod tabanında lock'ları kaldırıp yerlerine kuyruk veya mesajlaşma soyutlamaları koyma işi yaptım. Son zamanlarda çeşitli locking algoritmalarını araştırıyorum. nsync gibi verimli bir locking aracını denemek istiyorum