Nedir &; önbellek-dostu" code"?

SORU

22 Mayıs 2013, ÇARŞAMBA

Nedir &; önbellek-dostu" code"?

Birisi muhtemelen "kod" ve "kod bu?" versiyonu önbellek dostu önbellek düşmanca bir örnek verebilir misiniz

Nasıl yazıyorum emin olun önbellek-verimli kod alabilir miyim?

CEVAP

22 Mayıs 2013, ÇARŞAMBA

Ön hazırlıklar

Modern bilgisayar mimarileri özelliği karmaşık hiyerarşileri bellek: kaydeder, genellikle birkaç seviyede önbellek içinde CPU chip (L1, L2, L3, talimat önbelleğe alır, ...), RAM, Sabit Disk (silahlı kendi önbelleğe alır) ve benzeri. Temel mantrahızlı bellek pahalıdır. Bu bugün gördüğümüz gelişmiş önbelleğe alma için temel nedendir. Önbellekleme etkisini azaltmak için ana yöntemlerden biridirgecikme(cfr. Herb Sutter konuşma ben başında bağlı). Herb Sutter (cfr. bu minvalde bağlantılar aşağıda):artan bant genişliği kolaydır, ama bizim bir şekilde gecikme kabul edemeyiz.

Veri her zaman bellek hiyerarşisi aracılığıyla alınır (en küçük == hızlı yavaş). Birönbellek/Bayan çarptıgenellikle CPU -- yüksek seviye önbellek, en üst düzeyde bir hit/Bayan anlamına gelir ben en büyük == yavaş. Önbellek isabet oranı her önbelleğe alır RAM (ya da daha kötüsü ...) alma Veri sonuçları Bayan beri performansı için çok önemlidirbir sürüzaman (RAM, Sabit disk için döngüleri milyonlarca kez döngüleri yüzlerce). Buna karşılık, okuma verileri (en yüksek seviye) önbellek genellikle döngüleri sadece bir avuç alır.

Modern bilgisayar mimarileri, performans darboğaz CPU ölmek (örneğin erişme veya daha fazla RAM) ayrılıyor. Bu sadece zaman içinde kötüye gidecek. İşlemci frekans artışı şu anda artık önemli performansını artırmak için.Sorun bellek erişimi.CPU donanım tasarım çabaları bu nedenle şu anda yoğun optimize önbelleğe, önbelleğe, boru hatları ve eşzamanlılık odaklanın. Örneğin, modern CPU depolama/veri taşıma için önbelleğe alır ve 99% öl � civarında harcama!

Bu konuda söylenecek çok şey var. Burada önbelleğe hakkında birkaç büyük kaynaklar, bellek hiyerarşisi ve doğru programlama:

Agner Fog's page. Onun mükemmel belgeler, ayrıntılı örnekler dilleri C Kurul arasında değişen kapsayan bulabilirsiniz .
Eğer video içine iseniz, ben güçlü Herb Sutter's talk on machine architecture (youtube) (özellikle 12:00 ve sonrası, check!) bakmanı tavsiye ederim.
Slides about memory optimization by Christer Ericson (Sony teknoloji @ Direktörü)
LWN.net's makale "What every programmer should know about memory"

Önbellek dostu kod için temel kavramlar

Önbellek dostu kod çok önemli bir yönüthe principle of localityamaç olan yakın bellek ile ilgili verileri verimli önbellekleme sağlar. CPU açısından önbellek, önemli olan bunun nasıl çalıştığını anlamak için önbellek satırları haberdar olmak için: How do cache lines work?

Özellikle aşağıdaki açıdan büyük önem önbelleği optimize etmek için

Zamansal konum: belirli bir bellek konumuna erişildiğinde, aynı konuma yakın gelecekte tekrar erişilebilir olması muhtemeldir. İdeal olarak, bu bilgiler hala bu noktada önbelleğe alınır.
Konum mekansalbu yerleştirme ile ilgili verileri birbirine yakın ifade eder. Önbellekleme pek çok düzeyde, sadece CPU hiçbir şey olmaz. RAM, okuma, örneğin, genellikle hafızanın büyük bir kısmını özellikle çok sık program verileri yakında gerektirir çünkü isteneni daha getirildi. HDD önbelleğe düşündüm aynı çizgiyi takip edin. CPU önbellek kavramı için özellikleönbellek satırlarıönemli.

c uygun kaplar kullanın

Önbellek-düşmanca karşı önbellek dostu basit bir örnek c 'In 3 ** std::list karşı. std::vector unsurları bellek bitişik ve onlara erişme saklanırçokdaha fazla önbellek-dostu öğeleri erişmek daha her yerde içeriğini saklayan std::list,. Bu mekansal konum nedeniyle.

Bu çok güzel bir örnek this youtube clip Bjarne Stroustrup (@teşekkürler link için Ali Mohammad Baydoun!) tarafından verilir.

İhmal veri yapısı ve algoritma tasarımı önbellek yok

Mümkün olduğunda, veri yapıları ve önbelleği maksimum fayda sağlayan bir şekilde hesaplama sipariş adapte etmeye çalışın. Bu konuda ortak bir teknik, yüksek performanslı bilgi işlem (cfr. aşırı önem veren cache blocking. örnek 24**).

Ve veri örtülü yapısı istifade eder

Bu alanda birçok insan bazen sütun ana unutmak olan başka bir basit örnek, (ex. fortran,matlab) satır ana sıralama (ex. vs İki boyutlu diziler depolamak için c,c ). Örneğin, aşağıdaki matris düşünün:

1 2
3 4

Satır ana sıralarken, bu 1 2 3 4; sütun ana bu 1 3 2 4 olarak saklanır, sipariş olarak hafızada saklanır. Kolay sipariş istismar olmayan uygulamaları hızlı bir şekilde içine kolayca önlenebilir!) çalışacağını görmek önbellek sorunları. Ne yazık ki, bu gibi şeyler görüyorumçokbenim etki alanı (makine öğrenmesi) sık sık. @Matteoİtalia onun cevabını daha detaylı bir şekilde bu örnek gösterdi.

Bellekten bir matrisin belirli bir öğe getirilirken, yakın öğeleri ve bir önbellek satırı getirilen saklanır. Eğer sipariş kullanılırsa, bu daha az bellek erişir sonraki hesaplamalar için gerekli olan önümüzdeki birkaç değerleri zaten önbellek satırı var çünkü) neden olur.

Basitlik için, önbellek 2 matris elemanları içeren ve belirli bir öğe bellekten getirilen, bir sonrakini de tek bir önbellek satırı içerir varsayalım. Örnek 2x2 matris yukarıdaki tüm unsurları (hadi M çağrı): toplam almak istediğini söylüyor

Sipariş (c örneğin ilk sütun dizin değiştirme) istismar:

M[0][0] (memory)   M[0][1] (cached)   M[1][0] (memory)   M[1][1] (cached)
= 1   2   3   4
--> 2 cache hits, 2 memory accesses

Sipariş (c örneğin ilk satır dizin değiştirme) istismar:

M[0][0] (memory)   M[1][0] (memory)   M[0][1] (memory)   M[1][1] (memory)
= 1   3   2   4
--> 0 cache hits, 4 memory accesses

Bu basit örnekte, sipariş istismar yaklaşık infaz hızlı bellek erişimi toplamları hesaplama daha döngüleri gerektirir beri) iki katına çıkar. Uygulamada performans farkı olabilirçokdaha büyük.

Öngörülemeyen dalları kaçının

Gecikmeler bellek erişimi özelliği nedeniyle en aza indirmek için boru hatları ve Derleyiciler yeniden kod çok iyi hale geliyor Modern mimarileri. Kritik kod (öngörülemeyen) dalları içeriyorsa, veya verilerini imkansız. Bu da dolaylı olarak daha fazla önbellek özlüyor yol açacaktır.

Bu açıklanmıştırçokburada (link için @0x90 için teşekkürler): Why is processing a sorted array faster than an unsorted array?

Sanal fonksiyonlar kaçının

c , virtual bağlamında yöntemleri önbellek özlüyor konusunda tartışmalı bir konu (genel bir uzlaşma mümkün olduğunda Kaçınılması gerektiğini var performans açısından) temsil eder. Sanal fonksiyonları önbellek aramak sırasında özlüyor neden olabilir, ama bu sadece olureğerbelirli bir işlevi genellikle yoktur (aksi takdirde büyük olasılıkla önbelleğe olurdu), bu bazıları tarafından sorun olarak kabul edilir. Başvuru için ilgili bu sorun, kontrol edin: What is the performance cost of having a virtual method in a C class?

Ortak sorunlar

Çok işlemcili önbelleğe ile modern mimarilerde ortak bir sorun false sharing denir. Bu her işlemci bir bellek bölgesinde veri kullanmaya çalışıyor ve aynı depo çalıştığında oluşurönbellek satırı. Bu başka bir işlemci kullanabilir verileri içeren bir önbellek satırı üzerine tekrar tekrar neden olur. Etkili, farklı konuları birbirine bu durumda ikna önbellek özlüyor bekleyin. Ayrıca Bkz: (link için @Matt için teşekkürler): How and when to align to cache line size?

Zavallı RAM bellek önbellekleme aşırı bir belirti ne demek istediğini muhtemelen bu bağlamda, sözde thrashing. Bu disk erişimi gerektiren süreci sürekli sayfa hatası (Geçerli sayfayı değil örneğin erişir bellek) oluşturur oluşur.

Bunu Paylaş: