Geçenlerde veri yapısı Skip list olarak bilinen geldi. İkili arama ağacına çok benzer bir davranış... benim sorum var - neden hiç kullanmak istiyorsanız bir ikili arama ağacı üzerinde atla liste misin? gibi

Listeleri değiştirme/eş zamanlı erişim için daha fazla sorumludurlar atlayın. Herb Sutter eşzamanlı ortamlarda article yaklaşık bir veri yapısı yazdı. Daha etraflı bilgi vardır.

İkili arama ağacının en sık kullanılan uygulama red-black tree. Eşzamanlı sorunları ağacı genellikle yeniden dengelemek gerekiyor değiştirildiğinde gelir. Yeniden dengelemek operasyon ağaç düğümleri çok üzerinde dışlama kilit gerektirecek bir ağaç, büyük bir bölümünü etkileyebilir. Bir liste atla içine bir düğüm ekleme daha yerelleştirilmiş, etkilenen düğüm düğüm doğrudan bağlantılı kilitli olması gerekir.

Jon güncelleme yorum Harrops

Fraser ve Harris'in son kağıt Concurrent programming without locks okudum. Eğer kilidi serbest veri yapıları ilgileniyorsanız gerçekten çok iyi. Kağıt Transactional Memory ve n-karşılaştırma ve takas teorik çalışma a l m üzerinde duruluyor. Bunların her ikisi de herhangi bir donanım henüz onları destekler gibi yazılım simüle. Yazılım l m inşa etmek oldukça etkilendim.

Çöp toplayıcı gerektirir işlemsel bellek şeyleri özellikle çekici bulmadım. Ayrıca software transactional memory performans sorunları ile boğuşuyor. Ancak, eğer donanım işlemsel bellek daha yaygın hale gelirse çok heyecanlanırdım. Sonunda hala araştırma ve bir on yıl için Üretim kodu için kullanım olmayacak.

Bölüm 8.2 birkaç eşzamanlı ağaç uygulamaları performansını karşılaştırır. Bulgularını özetleyeyim. Buna değer sayfa 50, 53, 54 ve üzerinde çok bilgilendirici bazı grafikler var pdf olarak indirmek için.

• Kilitleme atlama listeleridelicesine hızlı. Onlar inanılmaz iyi eşzamanlı erişim sayısı ile ölçek. Bu özel, diğer kilit tabanlı veri yapıları baskı altında ölmek eğilimindedir listeler atlama yapıyor.
• Kilidi serbest listeler atlayınsürekli listeler atla kilitleme daha hızlı olur ama çok zor.
• işlem atla listelerkilitleme olan ve olmayan kilitleme sürümlerine göre sürekli olarak 2-3 kat daha yavaş.
• kırmızı-siyah ağaçlar kilitlemeeş zamanlı erişim altında croak. Onların performansı her yeni eşzamanlı kullanıcı ile doğrusal olarak düşer. İki kırmızı-siyah ağaç uygulamaları kilitleme bilinen, aslında bir ağaç yeniden dengeleme sırasında küresel bir kilit vardır. Diğer kullanır süslü (ve karmaşık) yükseltme kilit ama yine de önemli ölçüde küresel kilit sürümünü yapmaz.
• kilidi serbest kırmızı-siyah ağaçlar(artık gerçek, Update) diye bir şey yok.
• kırmızı-siyah ağaçları işlemişlem ile karşılaştırılabilir atlama listeleri. Bu çok şaşırtıcı ve çok umut vericiydi. Yazmak çok daha kolay eğer daha yavaş olsa da işlemsel bellek. Hızlı Arama gibi kolay olacağını ve yerine eşzamanlı olmayan sürümü.

Güncelleme
Kilit serbest ağaçları ile ilgili haberler burada: Lock-Free Red-Black Trees Using CAS.
İçine derin derin baktı yok, ama görünüşte sağlam görünüyor.