22 Soru: Sıralanmış bir diziyi neden sıralanmamış bir diziyi işlemekten daha hızlı işliyor?

tarafından oluşturulan soru Tue, Jun 4, 2019 12:00 AM

İşte size çok özel davranışlar gösteren bir C ++ kodu. Bazı garip sebeplerden dolayı, verileri mucizevi bir şekilde sıralamak, kodu neredeyse altı kat daha hızlı hale getirir:

 
#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;


    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);


    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • std::sort(data, data + arraySize); olmadan, kod 11.54 saniye içinde çalışır.
  • Sıralanan verilerle kod 1,93 saniye içinde çalışır.

Başlangıçta bunun yalnızca bir dil veya derleyici anomalisi olabileceğini düşündüm, bu yüzden Java'yı denedim:

 
import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;


        // !!! With this, the next loop runs faster
        Arrays.sort(data);


        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

benzer ancak daha az aşırı sonuçla.


İlk düşüncem, sıralama işleminin verileri önbelleğe getirdiği, ancak dizinin henüz oluşturulmasından dolayı ne kadar aptalca olduğunu düşündüm.

  • Neler oluyor?
  • Neden sıralanmış bir diziyi işlem sıralanmamış bir diziyi işlemekten daha hızlı yapıyor? Kod bazı bağımsız terimleri topluyor, bu yüzden sipariş önemli olmamalı.
23151
  1. Sadece kayıt için. Windows /VS2017 /i7-6700K 4GHz’de iki sürüm arasında hiçbir fark yoktur. Her iki durumda da 0.6 sn sürer. Harici döngüdeki yineleme sayısı 10 kat artarsa, yürütme süresi her iki durumda da 10 kat fazla 6s artar.
    2017-11-15 20: 45: 37Z
  2. @ user194715: cmov veya başka bir dalsız uygulama kullanan (pcmpgtd ile otomatik vektörleştirme gibi) herhangi bir derleyici, herhangi bir CPU'ya bağlı olmayan bir performansa sahip olacaktır. Ancak bu dallı ise, sıra dışı spekülatif yürütmesi olan herhangi bir CPU'ya göre sıralanacaktır. (Yüksek performanslı sıralı işlemciler bile, alınan dallardaki kabarcıkların alınmasını /kodunun çözülmesini önlemek için dal tahmini kullanır; özledim cezası daha küçüktür).
    2017-12-26 07: 14: 57Z
  3. @ KyleMit'in ikisiyle de bir ilgisi var mı? Her ikisinde de fazla okumadım
    2018-01-10 06: 26: 02Z
  4. @ mohitmun, bu güvenlik açılarının her ikisi de “ şube hedefi enjeksiyonu ”saldırıları
    2018-01-10 14: 26: 37Z
  5. 22 Yanıtlar                              22                         

    şube tahmini başarısızlığına maruz kaldınız.


    Şube Tahmini Nedir?

    Bir demiryolu kavşağı düşünün:

     Demiryolu bağlantılarını gösteren resim Wikimedia Commons aracılığıyla Mecanismo'dan Resim . CC-By-SA 3.0 lisansı altında kullanılır.

    Şimdi argüman uğruna, bunun 1800'lerde geri döndüğünü varsayalım - uzun mesafe veya radyo iletişiminden önce.

    Bir kavşağın işletmecisisiniz ve bir trenin geldiğini duyuyorsunuz. Hangi yöne gideceği hakkında hiçbir fikrin yok. Treni, sürücüye hangi yöne istediklerini sorması için durduruyorsunuz. Sonra anahtarı uygun şekilde ayarlayın.

    Trenler ağır ve çok fazla atalet var. Bu yüzden başlamak ve yavaşlamak sonsuza kadar sürer.

    Daha iyi bir yolu var mı? Trenin hangi yöne gideceğini tahmin edersiniz!

    • Doğru tahmin ederseniz, devam eder.
    • Hatalı olduğunu tahmin ederseniz, kaptan durur, geri döner ve anahtarı çevirmek için size bağırır. Sonra diğer yolu yeniden başlatabilir.

    Her zaman doğru tahmin ederseniz , trenin hiçbir zaman durması gerekmez.
    Çok sık yanlış olduğunu tahmin ederseniz , tren durma, yedekleme ve yeniden başlatma için çok zaman harcar.


    Bir if ifadesi göz önünde bulundurun: İşlemci düzeyinde bir şube talimatıdır:

    Bir if ifadesi içeren derlenmiş kodun ekran görüntüsü

    Sen bir işlemcisin ve bir dal görüyorsun. Hangi yöne gideceğine dair hiçbir fikrin yok. Ne yaparsın? İşlemi durdurur ve önceki talimatların tamamlanmasını beklersiniz. Sonra doğru yolda devam edin.

    Modern işlemciler karmaşıktır ve uzun boru hatlarına sahiptir. Bu yüzden sonsuza dek “ısınmak” ve “yavaşlamak” için alırlar.

    Daha iyi bir yolu var mı? Şubenin hangi yöne gideceğini tahmin edersiniz!

    • Doğru tahmin ederseniz, uygulamaya devam edersiniz.
    • Yanlış tahmin ederseniz, boru hattını yıkamanız ve dallara geri dönmeniz gerekir. Sonra diğer yolu yeniden başlatabilirsiniz.

    Her zaman doğru tahmin ederseniz , yürütmenin hiçbir zaman durması gerekmez.
    Çok sık yanlış tahmin ediyorsanız , çok fazla zaman harcayarak, geriye yuvarlayarak ve yeniden başlatarak geçirirsiniz.


    Bu şube tahminidir. Trenin bir bayrakla yönünü gösterebileceği için en iyi benzetme olmadığını itiraf ediyorum. Ancak bilgisayarlarda, işlemci bir kolun son ana kadar hangi yöne gideceğini bilmez.

    Öyleyse, trenin geri çekilmesi ve diğer yoldan aşağı inmesi gereken sayısı en aza indirmeyi stratejik olarak nasıl tahmin edersiniz? Geçmişe bakıyorsun! Tren zamanın% 99'unu terk ederse, tahminen sola gidersiniz. Değişirse, tahminlerinizi değiştirirsiniz. Her üç seferde bir yol açarsa, aynı şeyi tahmin edersiniz ...

    Başka bir deyişle, bir deseni tanımlamaya ve onu izlemeye çalışırsınız. Bu, şube tahmincilerin çalışma şekli az ya da çok olur.

    Çoğu uygulamada iyi davranış gösteren dallar vardır. Dolayısıyla, modern dal tahmincileri tipik olarak>% 90 isabet oranlarına ulaşacaktır. Ancak, tanınabilir modellerin olmadığı tahmin edilemeyen dallarla karşılaştığınızda, dal tahmin edicileri neredeyse işe yaramazdır.

    Daha fazla okuma: Wikipedia'daki "Şube tahmincisi" makalesi .


    Yukarıda da belirtildiği gibi, suçlu şu if ifadesidir:

     
    if (data[c] >= 128)
        sum += data[c];
    

    Verilerin 0 ile 255 arasında eşit dağıldığına dikkat edin. Veriler sıralandığında, kabaca yinelemelerin ilk yarısı if-ifadesine girmez. Ondan sonra, hepsi if-ifadesine gireceklerdir.

    Bu, şube belirleyicisine çok dostça davranır, çünkü şube art arda aynı yönde gider. Basit bir doygunluk sayacı bile yön değiştirdikten sonraki birkaç yinelemenin dışında dalı doğru bir şekilde tahmin eder.

    Hızlı görselleştirme:

     
    T = branch taken
    N = branch not taken
    
    data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
    branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...
    
           = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)
    

    Ancak, veriler tamamen rastgele olduğunda, dal belirleyicisi rastgele verileri tahmin edemediğinden yararsız hale getirilir. Bu nedenle, muhtemelen% 50 civarında yanlış anlama olacaktır (rastgele tahminde bulunmaktan iyidir).

     
    data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
    branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...
    
           = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)
    

    Öyleyse ne yapılabilir?

    Derleyici şubeyi koşullu bir hareket halinde optimize edemiyorsa, performans için okunabilirliği feda etmeye istekli iseniz, bazı saldırıları deneyebilirsiniz.

    değiştirin:

     
    if (data[c] >= 128)
        sum += data[c];
    

     
    int t = (data[c] - 128) >> 31;
    sum += ~t & data[c];
    

    Bu, dalı elimine eder ve bazı bitsel işlemlerle değiştirir.

    (Bu kesmenin, orijinal if-ifadesine kesinlikle eşit olmadığına dikkat edin. Ancak bu durumda, data[]'un tüm giriş değerleri için geçerlidir.)

    Karşılaştırmalar: Core i7 920 @ 3.5 GHz

    C ++ - Visual Studio 2010 - x64 Sürümü

     
    //  Branch - Random
    seconds = 11.777
    
    //  Branch - Sorted
    seconds = 2.352
    
    //  Branchless - Random
    seconds = 2.564
    
    //  Branchless - Sorted
    seconds = 2.587
    

    Java - NetBeans 7.1.1 JDK 7 - x64

     
    //  Branch - Random
    seconds = 10.93293813
    
    //  Branch - Sorted
    seconds = 5.643797077
    
    //  Branchless - Random
    seconds = 3.113581453
    
    //  Branchless - Sorted
    seconds = 3.186068823
    

    Gözlemler:

    • Şube ile: Sıralanan ve sıralanmayan veriler arasında büyük fark var.
    • Hack ile: Sıralanan ve sıralanmayan veriler arasında fark yoktur.
    • C ++ durumunda, hack aslında veriler sıralandığında daldan biraz daha yavaştır.

    Genel bir kural, kritik döngülerdeki (bu örnekte olduğu gibi) verilere bağlı dallanmayı önlemektir.


    Güncelleme:

    • GCC 4.6.1 ile -O3 veya x64'te -ftree-vectorize ile koşullu bir hareket meydana getirebilir. Dolayısıyla, sıralanan ve sıralanmayan veriler arasında fark yoktur - ikisi de hızlıdır.
    • VC ++ 2010, bu dal için /Ox’un altında bile şartlı hamle üretemez.

    • Intel C ++ Derleyici (ICC) 11 mucizevi bir şey yapar. iki döngüyü birleştirir , böylece öngörülemeyen dalı dış döngüye çeker. Yani değilYanlış anlaşılmaları immünize ediyor, aynı zamanda VC ++ ve GCC'nin üretebildiğinin iki katı daha hızlı! Başka bir deyişle, ICC, ölçütü yenmek için test döngüsünden faydalandı ...

    • Intel derleyicisine branşsız kod verirseniz, tam olarak onu dışa aktarır ... ve daldaki kadar hızlıdır (döngü değişimi ile).

    Bu, olgunlaşmış modern derleyicilerin bile kodu optimize etme kabiliyetlerinde çılgınca değişebildiğini gösteriyor ...

        
    30295
    2019-05-27 12: 42: 11Z
    1. @ Mysticial Değişen kesmeyi önlemek için maskeyi oluşturmak üzere int t=-((data[c]>=128)) gibi bir şey yazabilirsiniz. Bu da daha hızlı olmalı. Derleyicinin koşullu bir hareket ekleyecek kadar akıllı olup olmadığını bilmek ilginç olurdu.
      2012-06-27 16: 47: 51Z
    2. @ phonetagger Bu takip eden soruya bir göz atın: stackoverflow.com/questions/11276291/… Intel Compiler tamamen dış döngüden kurtulmak için çok yaklaştı.
      2012-07-10 17: 08: 39Z
    3. @ Novelocrat Bunun sadece yarısı doğru. Sıfır olduğunda 1 değerini işaret bitine kaydırmak gerçekten UB'dir. Bunun nedeni işaretli tamsayı taşması. Ancak, işaret bitinden bir tanesini değiştirmek IB'dir. Negatif işaretli bir tamsayıyı sağa kaydırma IB'dir. C /C ++ 'nın üst bitin işaret göstergesi olmasını gerektirmediği argümanına girebilirsiniz. Ancak uygulama detayları IB'dir.
      2013-08-18 21: 04: 38Z
    4. @ Mysticial Bağlantı için çok teşekkürler. Umut verici görünüyor. Yine de gideceğim. Son bir istek. Üzgünüz, ama lütfen sakıncası yoksa, bu int t = (data[c] - 128) >> 31; sum += ~t & data[c];'u yukarıdaki orijinal durumun yerine koymak için nasıl yapabileceğinizi söyler misiniz?
      2014-03-08 20: 05: 22Z
    5. İçimdeki dilbilgisi bunun "... şube tahmininin kurbanı başarısız olmak yerine ure " yazdığını düşünmemi istiyor. şube tahmininin kurbanı başarısız oldu. "
      2015-06-27 11: 35: 58Z

    Şube tahmini.

    Sıralanmış bir diziyle, data[c] >= 128 koşulu, ilk önce bir değerler dizisi için false'dur, daha sonra tüm sonraki değerler için true olur. Tahmin etmek kolay. Sıralanmamış bir diziyle, dallanma maliyetini ödersiniz.

        
    3907
    2016-08-05 07: 53: 10Z
    1. Şube tahmini, sıralı dizilere karşı farklı desenlere sahip dizilerde daha iyi çalışır mı? Örneğin, dizi için - > {10, 5, 20, 10, 40, 20, ...}, dizideki dizideki bir sonraki eleman 80'dir. Bu tür bir dizilim, bir sonraki öğenin burada 80 olduğu dal tahmini ile hızlandırılır mı? desen takip edilir? Yoksa genellikle yalnızca dizileri sıralamaya yardımcı olur mu?
      2014-09-23 18: 58: 12Z
    2. Yani temelde büyük O hakkında geleneksel olarak öğrendiğim her şey pencerede değil mi? Dallanma maliyetinden daha düşük bir sıralama maliyetine maruz kalmak daha mı iyidir?
      2014-10-30 07: 51: 58Z
    3. @ AgrimPathak Buna bağlı. Çok büyük olmayan girdiler için, daha yüksek karmaşıklığa sahip bir algoritma, daha yüksek karmaşıklığa sahip algoritma için sabitler daha küçük olduğunda düşük karmaşıklığa sahip bir algoritmaya göre daha hızlıdır. Kesinti noktasının nerede olduğunu tahmin etmek zor olabilir. Ayrıca, bunu karşılaştırın , yerellik önemlidir. BiG-O önemlidir, ancak performans için tek kriter değildir.
      2014-10-30 10: 14: 12Z
    4. Şube tahmini ne zaman yapılır? Dil bu dizinin sıralandığını ne zaman bilecek? Görünüşe göre dizinin durumunu düşünüyorum: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? Bu belirsiz 3 çalışma süresini artıracak mı? Sıralanmamış bir dizi olacak mı?
      2014-11-09 13: 37: 18Z
    5. @ FilipBartuzi Şube tahmini, işlemcide dil düzeyinin altında gerçekleşiyor (ancak dil, derleyiciye muhtemel olanı söyleme yöntemleri sunabilir, böylece derleyici uygun kodlar verebilir Buna). Örneğinizde, sıra dışı 3, dal yanlış değerlendirmesine yol açacaktır (uygun koşullar için, 3'ün 1000'den farklı bir sonuç vermesi durumunda) ve bu nedenle bu dizinin işlenmesi büyük olasılıkla birkaç düzine veya yüz nanosaniye alacaktır. Sıralanmış dizi, neredeyse hiç farkedilmez. Ne kadar zaman harcıyorum, yüksek oranda yanlış tahmin yapıyorum, 1000 başına bir yanlış tahmin fazla değil.
      2014-11-09 13: 49: 37Z

    Veriler sıralanırken performansın şiddetli bir şekilde artmasının nedeni, Gizemli'nin cevabı .

    Şimdi, koda bakarsak

     
    if (data[c] >= 128)
        sum += data[c];
    

    bu özel if... else... dalının anlamının, bir koşul sağlandığında bir şeyler eklemek olduğunu görebiliriz. Bu tür bir şube, cmovl sisteminde, koşullu bir hareket talimatına (x86) derlenecek olan koşullu hareket ifadesine kolayca dönüştürülebilir. Şube ve dolayısıyla potansiyel şube kestirim cezası kaldırılır.

    C'da, dolayısıyla C++'da, doğrudan (herhangi bir optimizasyon olmadan) x86'daki koşullu hareket komutunda derlenecek olan ifade, üçlü operatör ... ? ... : ...'dur. Bu yüzden yukarıdaki ifadeyi eşdeğer bir ifadeye yeniden yazıyoruz:

     
    sum += data[c] >=128 ? data[c] : 0;
    

    Okunabilirliği korurken, hızlanma faktörünü kontrol edebiliriz.

    Bir Intel'de Core i7 -2600K @ 3.4 GHz ve Visual Studio 2010 Yayın Modu , kıyaslama şudur (Mysticial'dan kopyalandı):

    86

     
    //  Branch - Random
    seconds = 8.885
    
    //  Branch - Sorted
    seconds = 1.528
    
    //  Branchless - Random
    seconds = 3.716
    
    //  Branchless - Sorted
    seconds = 3.71
    

    64

     
    //  Branch - Random
    seconds = 11.302
    
    //  Branch - Sorted
     seconds = 1.830
    
    //  Branchless - Random
    seconds = 2.736
    
    //  Branchless - Sorted
    seconds = 2.737
    

    Çoklu testlerde sonuç sağlamdır. Şube sonucu tahmin edilemez olduğunda büyük bir hızlanırız, ancak tahmin edilebilir olduğunda biraz acı çekeriz. Aslında, koşullu bir hareket kullanılırken performans, veri deseninden bağımsız olarak aynıdır.

    Şimdi ürettikleri x86 düzeneğini araştırarak daha yakından bakalım. Basit olması için max1 ve max2 işlevlerini kullanıyoruz.

    max1, if... else ... koşullu dalını kullanır:

     
    int max1(int a, int b) {
        if (a > b)
            return a;
        else
            return b;
    }
    

    max2, ... ? ... : ... üçlü operatörünü kullanır:

     
    int max2(int a, int b) {
        return a > b ? a : b;
    }
    

    Bir x86-64 makinesinde, GCC -S aşağıdaki montajı oluşturur.

     
    :max1
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        movl    -4(%rbp), %eax
        cmpl    -8(%rbp), %eax
        jle     .L2
        movl    -4(%rbp), %eax
        movl    %eax, -12(%rbp)
        jmp     .L4
    .L2:
        movl    -8(%rbp), %eax
        movl    %eax, -12(%rbp)
    .L4:
        movl    -12(%rbp), %eax
        leave
        ret
    
    :max2
        movl    %edi, -4(%rbp)
        movl    %esi, -8(%rbp)
        movl    -4(%rbp), %eax
        cmpl    %eax, -8(%rbp)
        cmovge  -8(%rbp), %eax
        leave
        ret
    

    max2, cmovge numaralı talimatın kullanımı nedeniyle daha az kod kullanıyor. Ancak asıl kazanç, max2'un, öngörülen sonuç doğru değilse, önemli bir performans cezasına sahip olacak olan jmp dal atlamalarını içermemesidir.

    Öyleyse şartlı bir hamle neden daha iyi performans gösteriyor?

    Tipik bir x86 işlemcide, bir talimatın uygulanması birkaç aşamaya ayrılır. Kabaca, farklı aşamalarla baş etmek için farklı donanımlarımız var. Dolayısıyla, bir talimatın yeni bir tanesini başlatmak için bitmesini beklememiz gerekmez. Buna boru hattı denir.

    Bir dal durumunda, aşağıdaki talimat öncekine göre belirlenir, bu nedenle boru hattını yapamayız. Beklemek ya da tahmin etmek zorundayız.

    Koşullu bir hareket durumunda, yürütme koşullu hareket talimatı birkaç aşamaya ayrılır, ancak Fetch ve Decode gibi önceki aşamalar önceki komutun sonucuna bağlı değildir; sadece sonraki aşamalar sonuca ihtiyaç duyar. Bu nedenle, bir komutun yürütme zamanının bir kısmını bekliyoruz. Bu nedenle, koşullu taşıma sürümü, tahmin yapmak kolay olduğunda şubeden daha yavaştır.

    kitabı Bilgisayar Sistemleri: Bir Programcının Bakış Açısı, second baskısı bunu detaylı olarak açıklar. Koşullu Taşıma Talimatları için Bölüm 3.6.6'yı, İşlemci Mimarisi için Bölüm 4'ün tamamını ve Şube Tahmini ve Yanlışlaması için özel bir muamele için Bölüm 5.11.2'yi kontrol edebilirsiniz. cezalar .

    Bazen, bazı modern derleyiciler kodumuzu daha iyi performansla derlemeye uygun hale getirebilir, bazen bazı derleyiciler yapamaz (söz konusu kod Visual Studio'nun yerel derleyicisini kullanıyor). Şube ve koşullu hareket arasındaki performans farkını tahmin edilemez olduğunda bilmek, senaryo o kadar karmaşık hale geldiğinde derleyicinin bunları otomatik olarak optimize edemeyeceği şekilde daha iyi performansla kod yazmamıza yardımcı olabilir.

        
    3144
    2019-05-27 12: 50: 22Z
    1. GCC komut satırlarınıza -O eklemediğiniz sürece varsayılan optimizasyon düzeyi yoktur. (Ve benimkinden daha kötü bir ingilizceye sahip olamazsın;)
      2012-06-28 14: 04: 45Z
    2. Derleyicinin üçlü-işleçini eşdeğer if-ifadesinden daha iyi hale getirebileceğine inanmak zor. GCC'nin üçlü operatörü koşullu bir harekete en iyi duruma getirdiğini gösterdiniz; yapmadıysanız , if ifadesi için tam olarak aynı şeyi yapmadığını gösterdiniz. Aslında, yukarıdaki Mystical’e göre, GCC if-ifadesini koşullu bir harekete göre optimize eder, bu da cevabı tamamen yanlış yapar.
      2012-06-30 15: 29: 23Z
    3. @ WiSaGaN Kod, hiçbir şey göstermez, çünkü iki kod parçanız aynı makine kodunu derler. İnsanların, örneğinizdeki if if ifadesinin, örneğindeki terener'den farklı olduğu fikrini almamaları kritik derecede önemlidir. Son paragrafınızdaki benzerliğe sahip olduğunuz doğrudur, ancak bu, örneğin geri kalanının zararlı olduğu gerçeğini silmez.
      2012-10-11 03: 12: 02Z
    4. @ WiSaGaN Yanıltıcı -O0 örneğini kaldırmak ve optimize edilmiş öğesindeki farkı göstermek için cevabınızı değiştirdiyseniz, kesinlikle benim oyum olmaz iki test vitrini doldur.
      2012-10-11 04: 13: 03Z
    5. @ UpAndAdam Test sırasında, VS2010, yüksek optimizasyon seviyesi belirlerken bile, gcc yapabileceği halde, orijinal dalı koşullu bir hareket halinde optimize edemiyor.
      2013-09-14 15: 18: 02Z

    Bu koda yapılabilecek daha da fazla iyileştirme yapmak istiyorsanız, şunu göz önünde bulundurun:

    Orijinal döngüden başlayarak:

     
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned j = 0; j < arraySize; ++j)
        {
            if (data[j] >= 128)
                sum += data[j];
        }
    }
    

    Döngü değişimi ile bu döngüyü güvenle değiştirebiliriz:

     
    for (unsigned j = 0; j < arraySize; ++j)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            if (data[j] >= 128)
                sum += data[j];
        }
    }
    

    Öyleyse, if koşulunun i döngüsünün yürütülmesi boyunca sabit olduğunu görebilirsiniz, böylece if'u kaldırabilirsiniz:

     
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
        {
            for (unsigned i = 0; i < 100000; ++i)
            {
                sum += data[j];
            }
        }
    }
    

    Sonra, kayan nokta modelinin izin verdiğini varsayarak (örneğin, /fp:fast atılır) iç döngünün tek bir ifadede daraltılabileceğini görürsünüz.  

    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
        {
            sum += data[j] * 100000;
        }
    }
    

    Bu, öncekinden 100.000 kat daha hızlı.

        
    2159
    2019-05-27 12: 51: 33Z
    1. Hile yapmak istiyorsanız, döngü dışında çarpmayı da alabilir ve döngüden sonra toplamı * = 100000 yapabilirsiniz.
      2012-10-11 01: 48: 01Z
    2. 2013-03-04 12: 59: 11Z
    3. Basit döngü değiştirme döngülerinde olmasa da, bu noktadaki iç if, derleyicinin sum += (data[j] >= 128) ? data[j] * 100000 : 0; veya eşdeğerini azaltabileceği cmovge'a dönüştürülebilir.
      2013-05-15 11: 57: 16Z
    4. Dış döngü, iç döngü tarafından alınan süreyi profile yetecek kadar büyük yapmaktır. Öyleyse neden değiş tokuş yapmayı düşünüyorsun? Sonunda, bu döngü yine de kaldırılacak.
      2016-06-22 15: 45: 19Z
    5. @ saurabheights: Yanlış soru: neden derleyici neden DEĞİŞTİRME döngüsünü değiştirmedi? Microbenchmarks zordur;)
      2016-12-29 13: 58: 53Z

    Hiç şüphesiz bazılarımız CPU'nun şube belirleyicisi için sorunlu olan kodları belirleme yöntemleriyle ilgilenir. Valgrind aleti cachegrind, --branch-sim=yes bayrağını kullanarak etkinleştirilen dal tahmin edici bir simülatöre sahiptir. Bu sorudaki örneklerin üzerinden geçmek, 10000'e indirgenmiş ve g++ ile derlenen dış döngü sayısıyla şu sonuçları verir:

    Sıralama:

     
    ==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
    ==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
    ==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )
    

    Unsorted:

     
    ==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
    ==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
    ==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )
    

    cg_annotate tarafından üretilen satır satır çıktının içine inen söz konusu döngü için görüyoruz:

    Sıralama:

     
              Bc    Bcm Bi Bim
          10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
               .      .  .   .      {
               .      .  .   .          // primary loop
     327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
               .      .  .   .          {
     327,680,000 10,006  0   0              if (data[c] >= 128)
               0      0  0   0                  sum += data[c];
               .      .  .   .          }
               .      .  .   .      }
    

    Unsorted:

     
              Bc         Bcm Bi Bim
          10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
               .           .  .   .      {
               .           .  .   .          // primary loop
     327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
               .           .  .   .          {
     327,680,000 164,050,007  0   0              if (data[c] >= 128)
               0           0  0   0                  sum += data[c];
               .           .  .   .          }
               .           .  .   .      }
    

    Bu sorunlu satırı kolayca tanımlamanıza olanak tanır - sıralanmamış sürümde if (data[c] >= 128) satırı, önbellek dalı yordayıcı modelinde 164.050,007 yanlış öngörülen koşullu dallara (Bcm) neden olurken, sıralanan sürümde yalnızca 10,006'ya neden olur.


    Alternatif olarak, Linux'ta aynı görevi gerçekleştirmek için performans sayaçları alt sistemini, ancak CPU sayaçlarını kullanan yerel performansla kullanabilirsiniz.

     
    perf stat ./sumtest_sorted
    

    Sıralama:

     
     Performance counter stats for './sumtest_sorted':
    
      11808.095776 task-clock                #    0.998 CPUs utilized          
             1,062 context-switches          #    0.090 K/sec                  
                14 CPU-migrations            #    0.001 K/sec                  
               337 page-faults               #    0.029 K/sec                  
    26,487,882,764 cycles                    #    2.243 GHz                    
    41,025,654,322 instructions              #    1.55  insns per cycle        
     6,558,871,379 branches                  #  555.455 M/sec                  
           567,204 branch-misses             #    0.01% of all branches        
    
      11.827228330 seconds time elapsed
    

    Unsorted:

     
     Performance counter stats for './sumtest_unsorted':
    
      28877.954344 task-clock                #    0.998 CPUs utilized          
             2,584 context-switches          #    0.089 K/sec                  
                18 CPU-migrations            #    0.001 K/sec                  
               335 page-faults               #    0.012 K/sec                  
    65,076,127,595 cycles                    #    2.253 GHz                    
    41,032,528,741 instructions              #    0.63  insns per cycle        
     6,560,579,013 branches                  #  227.183 M/sec                  
     1,646,394,749 branch-misses             #   25.10% of all branches        
    
      28.935500947 seconds time elapsed
    

    Ayrıca sökme işlemiyle kaynak kodu ek açıklaması da yapabilir.

     
    perf record -e branch-misses ./sumtest_unsorted
    perf annotate -d sumtest_unsorted
    
     
     Percent |      Source code & Disassembly of sumtest_unsorted
    ------------------------------------------------
    ...
             :                      sum += data[c];
        0.00 :        400a1a:       mov    -0x14(%rbp),%eax
       39.97 :        400a1d:       mov    %eax,%eax
        5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
        4.60 :        400a26:       cltq   
        0.00 :        400a28:       add    %rax,-0x30(%rbp)
    ...
    

    Daha fazla ayrıntı için performans eğitimine bakın.

        
    1800
    2012-10-18 19: 20: 21Z
    1. Bu korkutucu, sıralanmamış listede, listeye girme şansının% 50 olması gerekir. Her nasılsa, şube tahmini yalnızca% 25'lik bir özsermaye oranına sahiptir,% 50'lik özden daha iyi nasıl yapabilir?
      2013-12-09 04: 00: 09Z
    2. @ tall.b.lo:% 25'i tüm dallardan biridir - döngüde iki dal vardır, biri data[c] >= 128 için (ki bu önerdiğin gibi% 50 oranında kayıp oranı var) ve ~% 0 oranında kayıp oranı olan c < arraySize döngü koşulu için bir tane var.
      2013-12-09 04: 29: 25Z

    Bu soruyu ve cevaplarını okudum ve yanıtın eksik olduğunu hissediyorum.

    Yönetilen dillerde çok iyi çalıştığını düşündüğüm şube tahminini ortadan kaldırmanın yaygın bir yolu, şube kullanmak yerine tablo aramasıdır (bu durumda sınamamıştım).

    Bu yaklaşım genel olarak aşağıdaki durumlarda çalışır:

    1. bu küçük bir tablodur ve işlemcide önbelleğe alınma olasılığı yüksektir ve
    2. bir şeyleri oldukça dar bir döngüde çalıştırıyorsunuz ve /veya işlemci verileri önceden yükleyebilir.

    Arka plan ve neden

    İşlemci açısından, belleğiniz yavaş. Hız farkını telafi etmek için, işlemcinize birkaç önbellek yerleştirilmiştir (L1 /L2 önbellek). Öyleyse güzel hesaplamalarınızı yaptığınızı ve bir parça belleğe ihtiyacınız olduğunu anlayın. İşlemci 'load' işlemini gerçekleştirir ve hafıza parçasını önbelleğe yükler - ve hesaplamaların geri kalanını yapmak için önbelleği kullanır. Çünkü benmory nispeten yavaştır, bu 'yükleme' programınızı yavaşlatır.

    Dal tahmini gibi, bu da Pentium işlemcilerde optimize edilmiştir: işlemci bir veri parçası yüklemesi gerektiğini tahmin eder ve işlem gerçekten önbelleğe çarpmadan önce önbelleğe yüklemeyi dener. Daha önce gördüğümüz gibi, şube tahmini bazen çok yanlış gider - en kötü senaryoda geri dönmeniz ve aslında sonsuza dek sürecek bir bellek yükü beklemeniz gerekir ( başka bir deyişle: başarısız şube tahmini kötüdür) , şube tahmini başarısız olduktan sonra bir bellek yükleme sadece korkunç! ).

    Neyse ki bizim için, eğer hafıza erişim paterni tahmin edilebilir ise, işlemci onu hızlı önbelleğine yükler ve her şey yolunda.

    Bilmemiz gereken ilk şey küçük olan nedir? Daha küçük genellikle daha iyi olsa da, bir kuralın boyutu < = 4096 bayt boyutunda olan arama tablolarına bağlı kalmaktır. Üst sınır olarak: arama tablonuz 64 K’dan büyükse, muhtemelen yeniden düşünmeye değer.

    Tablo oluşturma

    Böylece küçük bir masa oluşturabileceğimizi düşündük. Bir sonraki yapılacak şey arama işlevini yerine getirmektir. Arama işlevleri genellikle birkaç temel tam sayı işlemi kullanan küçük işlevlerdir (ve, veya xor, shift, add, remove ve belki çarpın). Girişinizi arama işleviyle tablonuzdaki bir tür 'benzersiz anahtar'a çevirmek istersiniz; bu da size yapmak istediğiniz tüm çalışmanın cevabını verir.

    Bu durumda: > = 128, değeri koruyabileceğimiz anlamına gelir, < 128 ondan kurtulacağımız anlamına gelir. Bunu yapmanın en kolay yolu 'VE' kullanmaktır: eğer onu tutarsak, 7FFFFFFF ile biz ve biz; ondan kurtulmak istiyorsak, biz VE 0 ile dikkat edin. Aynı zamanda 128'in 2'nin bir gücü olduğuna dikkat edin - bu yüzden devam edip 32768/128 tamsayılardan oluşan bir tablo oluşturabilir ve onu bir sıfır ve bir sürü ile doldurabiliriz. 7FFFFFFFF en.

    Yönetilen diller

    Bunun neden yönetilen dillerde iyi sonuçlandığını merak edebilirsiniz. Ne de olsa, yönetilen diller karışıklığa uğramamak için dizilerin sınırlarını bir dalla kontrol ederler ...

    Şey, tam olarak değil ... :-)

    Bu şubenin yönetilen diller için kaldırılması konusunda bazı çalışmalar yapılmıştır. Örneğin:

     
    for (int i = 0; i < array.Length; ++i)
    {
       // Use array[i]
    }
    

    Bu durumda, derleyiciye sınır şartının asla karşılanmayacağı açıktır. En azından Microsoft JIT derleyicisi (ancak Java’nın benzer şeyler yapmasını bekliyorum) bunu fark edecek ve tümüyle çekimi kaldıracaktır. Vay, bu dal yok demektir. Benzer şekilde, diğer bariz davalarla da ilgilenecektir.

    Yönetilen dillerde arama yaparken sorunla karşılaşırsanız, anahtar sınır kontrolünü tahmin edilebilir hale getirmek için arama işlevinize & 0x[something]FFF eklemek ve daha hızlı çalışmasını sağlamaktır.

    Bu davanın sonucu

     
    // Generate data
    int arraySize = 32768;
    int[] data = new int[arraySize];
    
    Random random = new Random(0);
    for (int c = 0; c < arraySize; ++c)
    {
        data[c] = random.Next(256);
    }
    
    /*To keep the spirit of the code intact, I'll make a separate lookup table
    (I assume we cannot modify 'data' or the number of loops)*/
    
    int[] lookup = new int[256];
    
    for (int c = 0; c < 256; ++c)
    {
        lookup[c] = (c >= 128) ? c : 0;
    }
    
    // Test
    DateTime startTime = System.DateTime.Now;
    long sum = 0;
    
    for (int i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (int j = 0; j < arraySize; ++j)
        {
            /* Here you basically want to use simple operations - so no
            random branches, but things like &, |, *, -, +, etc. are fine. */
            sum += lookup[data[j]];
        }
    }
    
    DateTime endTime = System.DateTime.Now;
    Console.WriteLine(endTime - startTime);
    Console.WriteLine("sum = " + sum);
    Console.ReadLine();
    
        
    1259
    2019-01-16 04: 47: 21Z
    1. Şube belirleyicisini atlamak istiyorsunuz, neden? Bu bir optimizasyon.
      2013-04-24 17: 50: 33Z
    2. Hiçbir dal bir daldan daha iyi olmadığından :-) Çoğu durumda bu sadece çok daha hızlıdır ... optimize ediyorsanız, kesinlikle değer Deneyin. Ayrıca f.ex'te de biraz kullanıyorlar. graphics.stanford.edu/~seander/bithacks.html
      2013-04-24 21: 57: 13Z
    3. Genelde arama tabloları hızlı olabilir, ancak bu özel durum için testler yaptınız mı? Kodunuzda hala bir dallanma koşuluna sahip olacaksınız, ancak şimdi arama tablosu oluşturma bölümüne taşındı. Yine de, performans artışını elde edemezsin
      2013-12-19 21: 45: 03Z
    4. @ Zain gerçekten bilmek istiyorsanız ... Evet: şubemle 15 saniye ve sürümümle 10 saniye. Ne olursa olsun, her iki şekilde de bilmek yararlı bir tekniktir.
      2013-12-20 18: 57: 29Z
    5. Neden sum += lookup[data[j]], lookup 256 girişli bir dizi değil, ilki sıfır, sonuncusu dizine eşit mi?
      2014-03-12 12: 17: 49Z

    Dizi sıralandığında veriler 0 ile 255 arasında dağıtıldığından, yinelemelerin ilk yarısı yaklaşık if aşamasına girmez (if ifadesi aşağıda paylaşılmaktadır).

     
    if (data[c] >= 128)
        sum += data[c];
    

    Soru şudur: Yukarıdaki ifadeyi, belirli verilerde olduğu gibi, belirli durumlarda yürütülemeyen kılan nedir? İşte "şube belirleyicisi" geliyor. Bir dal belirleyicisi, bir dalın (örneğin, bir if-then-else yapı) bu şekilde kesin olarak bilinmeden önce hangi yöne gideceğini tahmin etmeye çalışan bir dijital devredir. Dal tahmincisinin amacı, talimat boru hattındaki akışı iyileştirmektir. Şube belirleyicileri, yüksek etkili performans elde etmede kritik bir rol oynamaktadır!

    Bunu daha iyi anlamak için bazı işaretler koyalım

    Bir if aşamasının performansı, durumunun öngörülebilir bir patern olup olmamasına bağlıdır. Koşul her zaman doğruysa veya her zaman yanlışsa, işlemcideki dal tahmini mantığı kalıbı alır. Öte yandan, kalıp tahmin edilemez ise, if aşaması çok daha pahalı olacaktır.

    Bu döngünün performansını farklı koşullarla ölçelim:

     
    for (int i = 0; i < max; i++)
        if (condition)
            sum++;
    

    İşte farklı doğru-yanlış desenlere sahip döngünün zamanlamaları:

     
    Condition                Pattern             Time (ms)
    -------------------------------------------------------
    (i & 0×80000000) == 0    T repeated          322
    
    (i & 0xffffffff) == 0    F repeated          276
    
    (i & 1) == 0             TF alternating      760
    
    (i & 3) == 0             TFFFTFFF…           513
    
    (i & 2) == 0             TTFFTTFF…           1675
    
    (i & 4) == 0             TTTTFFFFTTTTFFFF…   1275
    
    (i & 8) == 0             8T 8F 8T 8F …       752
    
    (i & 16) == 0            16T 16F 16T 16F …   490
    

    Kötü ” doğru-yanlış bir model, if aşamalı bir ifadeyi “ iyi ” düzenden altı kat daha yavaş hale getirebilir! Elbette, hangi şablonun iyi ve hangisinin kötü olduğu, derleyici tarafından oluşturulan talimatlara ve belirli işlemciye göre değişir.

    Yani, şube tahmininin performans üzerindeki etkisinden şüphe yok!

        
    1129
    2019-02-27 10: 58: 32Z
    1. "Rastgele" TF modelinin zamanlamasını göstermiyorsunuz.
      2013-02-23 02: 31: 21Z
    2. @ MooingDuck 'Fark yaratmayacağı için - bu değer herhangi bir şey olabilir, ancak yine de bu eşiklerin sınırlarında olacaktır. Öyleyse sınırları zaten bildiğiniz halde neden rastgele bir değer gösterelim? Yine de bir tanesinin iyiliği uğruna ve 'sadece bunun için' gösterebileceğini kabul ediyorum.
      2016-03-28 12: 58: 51Z
    3. @ cst1992: Şu anda en yavaş zamanlaması, insan gözüme göre oldukça tahmin edilebilir görünen TTFFTTFFTTFF. Rastgele doğası gereği önceden tahmin edilemez, bu yüzden hala daha yavaş olması ve dolayısıyla burada gösterilen sınırların dışında kalması tamamen mümkün. OTOH, TTFFTTFF'nin patolojik olaya mükemmel şekilde varabileceği anlamına gelebilir. Söyleyemem, çünkü rastgele zamanlamaları göstermedi.
      2016-03-28 18: 27: 16Z
    4. @ MooingDuck İnsan gözüne göre, "TTFFTTFFTTFF" tahmin edilebilir bir dizidir, ancak burada konuştuğumuz şey, bir işlemcinin içine yerleştirilmiş dal tahmincisinin davranışıdır. Dal tahmincisi AI-seviye patern tanıma değildir; çok basit. Sadece şubeleri değiştirdiğinizde, iyi bir tahmin olmaz. Çoğu kodda dallar hemen hemen her zaman aynı şekilde gider; Bin kez yürüten bir döngü düşünün. Döngünün sonundaki dal 999 kez döngünün başlangıcına geri döner ve sonra bininci zaman farklı bir şey yapar. Çok basit bir şube belirleyicisi, genellikle iyi çalışır.
      2016-07-20 21: 07: 37Z
    5. @ steveha: CPU dalı tahmincisinin nasıl çalıştığı hakkında varsayımlar yaptığınızı düşünüyorum ve bu metodolojiye katılmıyorum. Bu dal tahmininin ne kadar gelişmiş olduğunu bilmiyorum, ama sanırım senden çok daha gelişmiş. Muhtemelen haklısın, ama ölçümler kesinlikle iyi olurdu.
      2016-07-20 21: 10: 18Z

    Şube tahmin hatalarını önlemenin bir yolu, arama tablosu oluşturmak ve verileri kullanarak dizine eklemektir. Stefan de Bruijn bunu cevabında tartıştı.

    Ancak bu durumda, değerlerin [0, 255] aralığında olduğunu biliyoruz ve yalnızca değerleri önemsiyoruz > = 128. Bu, bir değer isteyip istemediğimizi bize söyleyecek tek bir parçayı kolayca çıkarabileceğimiz anlamına gelir. Not: Verileri sağa kaydırarak7 bit, 0 biti veya 1 biti kaldı ve sadece 1 biti sahip olduğumuzda değeri eklemek istiyoruz. Bu bit'e "karar bitini" diyelim.

    Karar bitinin 0/1 değerini dizideki bir dizin olarak kullanarak, verilerin sıralanıp sıralanmamasına eşit olarak hızlı olacak bir kod yapabiliriz. Kodumuz her zaman bir değer katacaktır, ancak karar biti 0 olduğunda, değeri umursamadığımız bir yere ekleyeceğiz. İşte kod:

     
    // Test
    clock_t start = clock();
    long long a[] = {0, 0};
    long long sum;
    
    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            int j = (data[c] >> 7);
            a[j] += data[c];
        }
    }
    
    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
    sum = a[1];
    

    Bu kod, eklerin yarısını boşa harcar, ancak hiçbir zaman dal tahmin hatası olmaz. Rastgele verilerde, gerçek bir if ifadesi olan sürümden çok daha hızlıdır.

    Ancak testlerimde, açık bir arama tablosu bundan biraz daha hızlıydı, çünkü muhtemelen bir arama tablosuna indeksleme bit kaydırmadan biraz daha hızlıydı. Bu, kodumun nasıl oluşturulduğunu ve arama tablosunu nasıl kullandığını (koddaki "Arama Tablosu" için yaratıcı bir şekilde lut olarak adlandırılır) gösterir. İşte C ++ kodu:

     
    // Declare and then fill in the lookup table
    int lut[256];
    for (unsigned c = 0; c < 256; ++c)
        lut[c] = (c >= 128) ? c : 0;
    
    // Use the lookup table after it is built
    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            sum += lut[data[c]];
        }
    }
    

    Bu durumda, arama tablosu yalnızca 256 bayttı, bu nedenle bir önbellekte güzel bir şekilde uyuyor ve hepsi hızlıydı. Veriler 24 bitlik değerler olsaydı bu teknik işe yaramazdı ve biz sadece yarısını istiyorduk ... arama tablosu pratik olamayacak kadar büyük olurdu. Öte yandan, yukarıda gösterilen iki tekniği birleştirebiliriz: önce bitleri kaydırın, sonra bir arama tablosunu indeksleyin. Yalnızca en üst yarı değeri istediğimiz 24 bitlik bir değer için, verileri sağa doğru 12 bit kaytabilir ve bir tablo dizini için 12 bitlik bir değerle bırakılabilir. 12 bit tablo dizini, pratik olabilecek 4096 değerinden oluşan bir tablo anlamına gelir.

    Hangi tanıtıcının kullanılacağına karar vermek için if ifadesi kullanmak yerine diziye endeksleme tekniği kullanılabilir. İkili ağaçlar uygulayan bir kütüphane gördüm ve iki adlandırılmış işaretçi (pLeft ve pRight ya da her neyse) olması yerine, uzunluk-2 işaretçi dizisine sahipti ve hangisini takip edeceğine karar vermek için "karar bitini" tekniğini kullandım. Örneğin, yerine:

     
    if (x < node->value)
        node = node->pLeft;
    else
        node = node->pRight;
    

    bu kitaplık şöyle bir şey yapar:

     
    i = (x < node->value);
    node = node->link[i];
    

    İşte bu koda bir link: Kırmızı Siyah Ağaçlar , Sonsuza dek Karışmış

        
    1051
    2019-05-27 13: 08: 32Z
    1. Doğru, sadece doğrudan biti kullanabilir ve çoğaltabilirsiniz (data[c]>>7 - burada da bir yerde tartışılır); Bu çözümü bilerek bıraktım, ama elbette haklısın. Sadece küçük bir not: Arama tablolarının temel kuralı, 4KB'ye sığması (önbellekleme nedeniyle) işe yaramasıdır - tercihen masayı mümkün olduğu kadar küçük yapmasıdır. Yönetilen diller için bunu 64KB'ye çıkardım, C ++ ve C gibi düşük seviyeli diller için, muhtemelen tekrar düşünürdüm (bu sadece benim deneyimim). typeof(int) = 4’dan bu yana en fazla 10 bit yapmayı denerdim.
      2013-07-29 12: 05: 24Z
    2. 0/1 değeriyle indekslemenin muhtemelen bir tamsayı çarpımından daha hızlı olacağını düşünüyorum, ancak performans gerçekten kritikse, onu profillemelisiniz. Küçük arama tablolarının önbellek baskısından kaçınmak için gerekli olduğunu kabul ediyorum, ancak açıkça daha büyük bir önbelleğe sahipseniz daha büyük bir arama tablosundan kurtulabilirsiniz, bu nedenle 4KB zor bir kuraldan çok bir kuraldır. Bence sizeof(int) == 4 mu demek istedin? Bu 32 bit için doğru olurdu. İki yaşındaki cep telefonumun 32KB L1 önbelleği var, bu nedenle, özellikle arama değerleri int yerine bir bayt olsaydı 4K'lık bir arama tablosu bile işe yarayabilir.
      2013-07-29 22: 02: 13Z
    3. Muhtemelen bir şeyim eksik ama j'unuz 0 veya 1 yöntemine eşittir, neden dizini dizine eklemeyi kullanmak yerine değerinizi j ile çarpmadığınızı (muhtemelen 1-j yerine j ile çarpılmalıdır)
      2014-03-04 15: 38: 24Z
    4. @ steveha Çarpma daha hızlı olmalı, Intel kitaplarında aramaya çalıştım, ancak bulamadım ... her iki şekilde de, kıyaslama bana bu sonucu veriyor burada.
      2014-03-18 08: 45: 05Z
    5. @ steveha P.S .: bir başka olası cevap int c = data[j]; sum += c & -(c >> 7); olur, bu da hiç çarpma gerektirmez.
      2014-03-18 08: 52: 11Z

    Sıralanan durumda, başarılı şube tahminine veya dalsız karşılaştırma yöntemine güvenmekten daha iyisini yapabilirsiniz: şubeyi tamamen kaldırın.

    Nitekim, dizi data < 128 ile bitişik bir bölgede ve data >= 128 ile bir başka bölüme ayrılmıştır. Öyleyse, bölümleme noktasını dikhotomik arama (Lg(arraySize) = 15 karşılaştırmaları kullanarak) ile bulmalı ve sonra bir düzlem yapmalısınız. bu noktadan birikme.

    Gibi bir şey (işaretlenmemiş)

     
    int i= 0, j, k= arraySize;
    while (i < k)
    {
      j= (i + k) >> 1;
      if (data[j] >= 128)
        k= j;
      else
        i= j;
    }
    sum= 0;
    for (; i < arraySize; i++)
      sum+= data[i];
    

    veya biraz daha fazla şaşırtılmış

     
    int i, k, j= (i + k) >> 1;
    for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
      j= (i + k) >> 1;
    for (sum= 0; i < arraySize; i++)
      sum+= data[i];
    

    Hem sıralanan hem de sıralanmamış olanlar için yaklaşık bir çözüm sunan, ancak daha hızlı bir yaklaşım: sum= 3137536; (gerçekten tekdüze bir dağıtım olduğu varsayılırsa, 191.5 beklenen değeri olan 16384 örnek) : -) üçlü>

        
    950
    2019-05-11 11: 31: 12Z
    1. sum= 3137536 - akıllıca. Belli ki sorunun amacı bu değil. Soru açıkça şaşırtıcı performans özelliklerini açıklamaktan ibaret. std::partition yerine std::sort yapmanın değerli olduğunu söylemeye meyilliyim. Asıl soru verilen sentetik kriterden daha fazlasını içeriyor olsa da.
      2013-07-24 16: 31: 30Z
    2. @ DeadMG: bu aslında verilen bir anahtar için standart bir dikotomik arama değil, bölümleme endeksi için bir aramadır; yineleme başına tek bir karşılaştırma yapılmasını gerektirir. Ama bu koda güvenme, ben kontrol etmedim. Garantili bir doğru uygulama ile ilgileniyorsanız, bana bildirin.
      2013-07-24 20: 37: 31Z

    Yukarıdaki davranış Şube tahmini nedeniyle gerçekleşiyor.

    Şube tahminini anlamak için önce Talimat Pipeline 'ı anlamanız gerekir:

    Herhangi bir komut, bir adım dizisine bölünerek farklı adımların aynı anda paralel olarak yürütülebilmesini sağlar. Bu teknik talimat boru hattı olarak bilinir ve modern işlemcilerde verimi arttırmak için kullanılır. Bunu daha iyi anlamak için lütfen şu Wikipedia'daki örneğe bakın.

    Genel olarak, modern işlemciler oldukça uzun boru hatlarına sahiptir, ancak kolaylıkla bu 4 adımı göz önünde bulunduralım.

    1. IF - Talimatı bellekten al   
    2. Kimlik - Talimatın kodunu çözün   
    3. EX - Talimatı yürütün   
    4. WB - CPU kaydına geri yaz

    2 talimat için genel olarak 4 aşamalı boru hattı. Genel olarak 4 aşamalı boru hattı

    Yukarıdaki soruya geri dönerek aşağıdaki talimatları göz önünde bulunduralım:

     
                            A) if (data[c] >= 128)
                                    /\
                                   /  \
                                  /    \
                            true /      \ false
                                /        \
                               /          \
                              /            \
                             /              \
                  B) sum += data[c];          C) for loop or print().
    

    Şube tahmini olmadan aşağıdakiler gerçekleşir:

    B komutunu veya C komutunu uygulamak için, işlemcinin B komutuna veya C komutuna gitme kararı A komutunun sonucuna bağlı olduğundan, A komutunun boru hattındaki EX aşamasına kadar ulaşmasını beklemelidir. Böylece boru hattı böyle gözükecek.

    koşulun doğru gelmesi durumunda: resim tanımını buraya girin

    Koşul yanlışsa ne zaman: resim tanımını buraya girin

    A komutunun sonucunu beklemenin bir sonucu olarak, yukarıdaki durumda harcanan toplam CPU döngüsü (dal tahmini olmadan; hem doğru hem de yanlış için) 7'dir.

    Peki şube tahmini nedir?

    Şube tahmincisi, kesin olarak bilinmeden önce bir dalın (eğer öyleyse bir yapının) hangi yöne gideceğini tahmin etmeye çalışacaktır. A talimatının boru hattının EX aşamasına ulaşmasını beklemeyecektir, ancak kararı tahmin edip bu talimatlara (örneğin örneğimizde B veya C) gidecektir.

    Doğru bir tahmin durumunda, boru hattı şunun gibi görünüyor: resim tanımını buraya girin

    Daha sonra tahmininin yanlış olduğu tespit edilirse, kısmen uygulanan talimatlar diskarded ve boru hattı doğru dallanma ile başlar ve gecikmeye neden olur. Bir dalın yanlış kullanılması durumunda boşa harcanan zaman, boru hattındaki getirme aşamasından yürütme aşamasına kadar olan aşama sayısına eşittir. Modern mikroişlemciler oldukça uzun boru hatlarına sahip olma eğilimindedir, böylece yanlış tahmin gecikmesi 10 ila 20 saat döngüsü arasındadır. Boru hattı ne kadar uzun olursa, iyi bir şube kestiricisi ne kadar çok ihtiyaç duyar.

    OP'nin kodunda, şartlı olarak ilk kez, şube belirleyicisinin tahminde bulunma konusunda herhangi bir bilgiye sahip olmadığı, bu nedenle ilk defa rasgele bir sonraki talimatı seçeceği belirlenir. For döngüsünün ilerleyen bölümlerinde, öngörüyü tarihe dayandırabilir. Artan sırada sıralanmış bir dizi için, üç olasılık vardır:

    1. Tüm öğeler 128'den küçük
    2. Tüm öğeler 128'den büyük
    3. Bazı yeni başlangıç ​​elemanları 128'den küçüktür ve daha sonra 128'den büyük olur

    Tahmincinin her zaman ilk çalıştırmada gerçek dalı alacağını varsayalım.

    Bu nedenle, ilk durumda, tarihsel olarak tüm öngörüleri doğru olduğu için her zaman gerçek dalı alacak. İkinci durumda, başlangıçta yanlış tahmin eder, ancak birkaç yinelemeden sonra doğru şekilde tahmin eder. 3. durumda, başlangıçta, unsurlar 128'den küçük olana kadar doğru tahmin eder. Bundan sonra, bir süre başarısızlığa uğrar ve tarihte dal tahmini başarısızlığı gördüğü zaman doğru kendini gösterir.

    Tüm bu durumlarda, başarısızlık sayıca çok az olacaktır ve sonuç olarak, sadece birkaç kez, kısmen yürütülen talimatları atmak ve daha az CPU çevrimi ile sonuçlanan doğru daldan başlamak gerekir.

    Ancak rastgele sıralanmamış bir dizinin kullanılması durumunda, tahminin kısmen yürütülen talimatları atması ve çoğu zaman doğru dalla başlaması ve sıralanan diziye kıyasla daha fazla CPU çevrimi sağlaması gerekir.

        
    774
    2018-04-10 20: 13: 26Z
    1. iki komut nasıl birlikte yürütülür? bu işlem ayrı işlemci çekirdekleriyle mi yapılıyor yoksa boru hattı talimatı tek işlemci çekirdeğine mi entegre edildi?
      2017-10-11 14: 49: 42Z
    2. @ M.kazemAkhgary Hepsi bir mantıksal çekirdeğin içinde. İlgileniyorsanız, bu örnek, örneğin Intel Yazılım Geliştirici Kılavuzu
      2017-11-03 07: 45: 12Z

    Resmi bir cevap

    olacaktır.
    1. Intel - Şube Yanlışlığının Maliyetini Önlemek
    2. Intel - Şube ve Döngü Yeniden Yapılanması Yanlış Tahminleri Önleme Nasıl Yapılır
    3. Bilimsel makaleler - şube tahmini bilgisayar mimarisi
    4. Kitaplar: J.L. Hennessy, D.A. Patterson: Bilgisayar mimarisi: nicel bir yaklaşım
    5. Bilimsel yayınlardaki makaleler: T.Y. Yeh, Y.N. Patt, şube tahminlerinde bunların çoğunu yaptı.

    Bu sevimli şema 'dan da görebilirsiniz > neden şube tahmincisinin kafası karışıyor?

     2 bit durum diyagramı

    Orijinal koddaki her öğe rastgele bir değerdir

     
    data[c] = std::rand() % 256;
    

    böylece öngörücü, std::rand() darbesiyle taraf değiştirir.

    Öte yandan, sıralama yapıldıktan sonra, öngörücü ilk önce kesinlikle alınamayan bir duruma geçecektir ve değerler yüksek değere değiştiğinde, öngörücü üç aşamada olacak, kesinlikle alınmamış olana kadar güçlü bir şekilde değişmeyecektir. kaldırıldı.


    678
    2017-01-31 11: 39: 33Z

    Aynı satırda (bunun herhangi bir cevapla vurgulanmadığını düşünüyorum), bazen (özel olarak performansın önemli olduğu yazılımlarda - Linux çekirdeğinde olduğu gibi) aşağıdaki gibi if ifadeleri bulabileceğinizi belirtmek iyidir:  

    if (likely( everything_is_ok ))
    {
        /* Do something */
    }
    

    veya benzer şekilde:

     
    if (unlikely(very_improbable_condition))
    {
        /* Do something */    
    }
    

    Hem likely() hem de unlikely(), derleyicinin kullanıcı tarafından sağlanan bilgileri dikkate alarak koşulu lehine tahmin kodunu eklemesine yardımcı olmak için GCC'nin __builtin_expect gibi bir şey kullanarak tanımlanmış makrolardır. GCC, çalışan programın davranışını değiştirebilecek veya önbelleği temizleme vb. Gibi düşük düzey yönergeler yayan diğer yerleşikleri destekler. Bkz. bu dokümantasyon .

    Normalde bu tür optimizasyonlar, gerçek zamanlı uygulamalarda veya uygulama zamanının önemli olduğu ve kritik olduğu gömülü sistemlerde bulunur. Örneğin, yalnızca 1/10000000 kez gerçekleşen bir hata durumunu kontrol ediyorsanız, neden derleyiciyi bu konuda bilgilendirmiyorsunuz? Bu şekilde, varsayılan olarak şube tahmini, koşulun yanlış olduğunu varsayar.

        
    645
    2016-10-28 10: 28: 11Z

    Sık kullanılan Boolean işlemleri C ++ 'ta derlenmiş programda birçok dal oluşturur. Bu dallar ilmek içindeyse ve tahmin edilmesi zorsa, yürütmeyi önemli ölçüde yavaşlatabilir. Boolean değişkenleri, 0 için false ve 1 için true değerleriyle 8 bit tamsayılar olarak kaydedilir.

    Boolean değişkenleri, giriş olarak Boolean değişkenleri olan tüm operatörlerin, girişlerin 0 veya 1'dan başka bir değeri olup olmadığını kontrol etmeleri, ancak 0 veya 1'dan başka hiçbir değer üretemedikleri anlamına gelirken belirlenir. Bu, Boole değişkenleriyle yapılan işlemleri girdi gereğinden daha az verimli hale getirir. Örnek düşünün:

     
    bool a, b, c, d;
    c = a && b;
    d = a || b;
    

    Bu genellikle derleyici tarafından aşağıdaki şekilde uygulanır:

     
    bool a, b, c, d;
    if (a != 0) {
        if (b != 0) {
            c = 1;
        }
        else {
            goto CFALSE;
        }
    }
    else {
        CFALSE:
        c = 0;
    }
    if (a == 0) {
        if (b == 0) {
            d = 0;
        }
        else {
            goto DTRUE;
        }
    }
    else {
        DTRUE:
        d = 1;
    }
    

    Bu kod optimal olmaktan uzak. Şubeler yanlış öngörülerde uzun sürebilir. Boolean işlemleri, işlenenlerin 0 ve 1'dan başka hiçbir değeri olmadığı kesin olarak biliniyorsa çok daha verimli yapılabilir. Derleyicinin böyle bir varsayımda bulunmamasının nedeni, değişkenlerin başlatılmamış olması veya bilinmeyen kaynaklardan gelmesi durumunda değişkenlerin başka değerlere sahip olabileceğidir. Yukarıdaki kod, a ve b geçerli değerlere sıfırlanmışsa veya Boolean çıktısı üreten operatörlerden geliyorsa optimize edilebilir. Optimize edilmiş kod şöyle görünür:

     
    char a = 0, b = 1, c, d;
    c = a & b;
    d = a | b;
    
    Boolean operatörleri (char ve bool) yerine bitsel operatörlerin (& ve |) kullanılmasını mümkün kılmak için && yerine || kullanılır. Bitsel operatörler, yalnızca bir saat döngüsü alan tek talimatlardır. OR operatörü (|), a ve b, 0 veya 1'dan farklı değerlere sahip olsa bile çalışır. AND işleci (&) ve EXCLUSIVE OR işleci (^), işlenenler 0 ve 1'dan farklı değerlere sahipse tutarsız sonuçlar verebilir.

    ~, NOT için kullanılamaz. Bunun yerine, 0 ile XOR'layarak 1 veya 1 olarak bilinen bir değişken üzerinde Boole NOT yapabilirsiniz:

     
    bool a, b;
    b = !a;
    

    şuna göre optimize edilebilir:

     
    char a = 0, b;
    b = a ^ 1;
    
    a && b, a & b b ise değerlendirilmemesi gereken bir ifade ise a, false ile değiştirilemez. Aynı şekilde, &&, b, & ise değerlendirilmemesi gereken bir ifade ise, a || b, a | b ile değiştirilemez.

    İşlenenler, işlenenlerin karşılaştırılmasından daha değişkendirse, bitsel işleçleri kullanmak daha avantajlıdır:

     b

    çoğu durumda en uygunudur (a ifadesinin birçok dal yanlışlığı üretmesini beklemiyorsanız).

        
    614
    2019-05-30 16: 34: 26Z

    Bu kesin! ...

    Şube tahmini , telefonunuzda gerçekleşen geçiş nedeniyle mantığı yavaşlatırKod! Düz bir caddeye veya çok fazla dönüşü olan bir caddeye gidiyor gibisiniz, elbette ki düz olan daha çabuk bitecek! ...

    Dizi sıralanırsa, durumunuz ilk adımda yanlıştır: true, ardından caddenin sonuna kadar giden gerçek bir değer haline gelir. Mantığın sonuna kadar bu şekilde ulaşıyorsunuz. Öte yandan, sıralanmamış bir dizi kullanarak kodunuzun daha yavaş çalışmasını sağlayan çok fazla döndürme ve işleme gereksiniminiz var ...

    Aşağıda sizin için yarattığım resme bakın. Hangi cadde daha hızlı bitecek?

     Şube Tahmini

    Yani programsal olarak, şube tahmini işlemin daha yavaş olmasına neden olur ...

    Ayrıca, kodunuzu farklı şekilde etkileyecek iki tür şube tahminimiz olduğunu bilmek güzel:

    1 . Statik

    2 . Dinamik

     Şube Tahmini

      

    Statik dal kestirimi mikroişlemci tarafından ilk kez kullanılır   koşullu bir dalla karşılaşılır ve dinamik dal tahmini   koşullu dal kodunun yürütülmesinde başarılı olmak için kullanılır.

         

    Bunlardan yararlanmak için kodunuzu etkin bir şekilde yazmak için   Kurallar, eğer varsa veya değiştir ifadeleri yazarken, en çok   ilk önce ortak davalar ve en yaygın olana kadar kademeli olarak çalışın.   Döngüler için özel olarak herhangi bir kod sıralaması gerekmez   statik dal kestirimi, sadece döngü yineleyicinin koşulu olarak   normalde kullanılır.

        
    289
    2018-05-03 06: 35: 51Z

    Bu soru zaten defalarca mükemmel bir şekilde yanıtlandı. Yine de grubun dikkatini başka bir ilginç analize çekmek istiyorum.

    Son zamanlarda, bu örnek (çok az değiştirilmiş), Windows'ta programın içinde bir kod parçasının nasıl profillenebileceğini göstermenin bir yolu olarak da kullanılmıştır. Yol boyunca, yazar aynı zamanda kodun zamanın çoğunu hem sıralı & sıralanmamış dava. Son olarak, parça ayrıca, sıralanmamış durumda ne kadar dal yanlışlığı olduğunu belirlemek için HAL'ın (Donanım Soyutlama Katmanı) az bilinen bir özelliğinin nasıl kullanılacağını gösterir.

    Bağlantı burada: http://www.geoffchappell.com/studies/windows/km/ntoskrnl /aPI /ex /profil /demo.htm

        
    266
    2017-01-17 18: 02: 31Z
    1. Çok ilginç bir makale (aslında hepsini okudum), ancak soruyu nasıl yanıtlıyor?
      2018-03-16 12: 47: 19Z
    2. @ PeterMortensen Sorunuzla biraz şaşkınım. Örneğin, işte bu parçadan bir satır daha:
      bool a; double x, y, z;
      a = x > y && z < 5.0;
      
      Yazar, burada yayınlanan kod bağlamında ve sıralanan davanın neden bu kadar hızlı olduğunu açıklayan süreçte profillemeyi tartışmaya çalışıyor.
      2018-03-16 15: 37: 16Z

    Başkaları tarafından daha önce bahsedildiği gibi, gizemin ardında ne olduğu:

    Bir şey eklemeye çalışmıyorum, kavramı başka bir şekilde açıklamaya çalışıyorum. Wiki'de metin ve diyagram içeren kısa bir giriş var. Şube Öngörüsünü sezgisel olarak ayrıntılandırmak için bir şema kullanan aşağıdaki açıklamayı seviyorum.

      

    Bilgisayar mimarisinde dal belirleyicisi   Dalın hangi yolla olduğunu tahmin etmeye çalışan dijital devre   if-then-else yapısı) kesin olarak bilinmeden önce gidecektir.   Dal tahmininin amacı, içindeki akışı iyileştirmektir.   komut satırı. Sutyennch prediktörleri kritik bir rol oynamaktadır.   birçok modern boru hattında yüksek etkili performans elde etmek   x86 gibi mikroişlemci mimarileri.

         

    İki yönlü dallanma genellikle koşullu bir sıçrama ile uygulanır   talimat. Koşullu bir sıçrama "alınmamış" olabilir ve devam edebilir   hemen takip eden ilk kod dalı ile yürütme   koşullu atlamadan sonra, veya "alınabilir" ve "   ikinci kod dalının bulunduğu program belleğinde farklı bir yer   saklanmış. Koşullu bir sıçrama olup olmayacağı kesin olarak bilinmemektedir   durum hesaplanana ve   koşullu atlama talimattaki yürütme aşamasını geçti   boru hattı (bkz. şekil 1).

     şekil 1

    Açıklanan senaryoya göre, talimatların bir boru hattında farklı durumlarda nasıl yürütüldüğünü göstermek için bir animasyon demosu yazdım.

    1. Şube Tahmini Yapmadan.
      

    Şube tahmini olmadan, işlemcinin işlemine kadar beklemesi gerekir.   Koşullu atlama komutu, yürütmeden önceki yürütme aşamasını geçti.   sonraki talimat, boru hattına getirme aşamasına girebilir.

    Örnek üç talimat içeriyor ve ilki koşullu atlama talimatı. Son iki komut, koşullu atlama talimatı yerine getirilinceye kadar boru hattına girebilir.

     şube belirleyicisi olmadan

    3 komutun tamamlanması 9 saat sürecektir.

    1. Branch Predictor kullanın ve koşullu bir sıçrama yapmayın. Tahminin koşullu atlamayı almak için değil olduğunu varsayalım.

     buraya resim açıklamasını girin

    3 talimatın tamamlanması 7 saat sürecektir.

    1. Şube Predictor kullanın ve koşullu bir sıçrama yapın. Tahminin koşullu atlamayı almak için değil olduğunu varsayalım.

     buraya resim açıklamasını girin

    3 komutun tamamlanması 9 saat sürecektir.

      

    Bir dalın yanlış kullanılması durumunda boşa harcanan zaman eşittir.   Boru hattındaki getirme aşamasından teslim aşamasına   sahne yürütmek. Modern mikroişlemciler oldukça uzun olma eğilimindedir   yanlış tahmin gecikmesi 10 ila 20 saat arasında olacak şekilde   çevrimleri. Sonuç olarak, bir boru hattının daha uzun sürede yapılması,   daha gelişmiş şube belirleyicisi.

    Gördüğünüz gibi Şube Tahmini kullanmamak için bir nedenimiz yok gibi görünüyor.

    Branch Predictor'ün çok temel bölümünü açıklığa kavuşturmak oldukça basit bir demo. Bu gifler can sıkıcıysa, lütfen onları yanıttan çıkarmaktan çekinmeyin; ziyaretçiler demoyu BranchPredictorDemo

        
    183
    2019-06-04 16: 20: 33Z

    Şube tahmini kazancı!

    Şube yanlış tahmininin programları yavaşlatmadığını anlamak önemlidir. Cevapsız bir tahminin maliyeti, tıpkı dal tahmininin olmadığı gibi ve hangi kodun çalıştırılacağına karar vermek için ifadenin değerlendirilmesini beklediniz (bir sonraki paragrafta daha fazla açıklama).

     &&

    Bir data[c] >= 128 \When the input is unsorted, all the rest of the loop takes substantial time. But with sorted input, the processor is somehow able to spend not just less time in the body of the loop, meaning the buckets at offsets 0x18 and 0x1C, but vanishingly little time on the mechanism of looping. ifadesi olduğunda, hangi bloğun yürütüleceğini belirlemek için ifadenin değerlendirilmesi gerekir. Derleyici tarafından oluşturulan montaj kodunda koşullu şube talimatları eklenmiştir.

    Dallı bir komut, bilgisayarın farklı bir komut dizisi yürütmeye başlamasına neden olabilir ve bu nedenle, varsayılan olarak komut yürütme davranışından sapabilir (örneğin, ifade yanlışsa, program

    if (expression)
    {
        // Run 1
    } else {
        // Run 2
    }
    
    bloğunun kodunu atlar). durumumuzda ifade değerlendirmesi olan durum.

    Söylendiği gibi, derleyici gerçekte değerlendirilmeden önce sonucu tahmin etmeye çalışır. Bu ondan talimatlar alacake if-else blok ve ifadenin doğru olduğu ortaya çıkarsa, o zaman harika! Değerlendirmek için harcadığımız zamanı kazandık ve kodda ilerleme kaydettik; o zaman yanlış kodu kullanıyorsak, boru hattı boşaltılır ve doğru blok çalıştırılır.

    Görselleştirme:

    Diyelim, rota 1 veya rota 2'yi seçmeniz gerektiğini varsayalım. Eşinizin haritayı kontrol etmesini bekleyin, ## ile durup beklediniz veya rota1'i seçebilir ve şanslıysanız (rota 1 doğru mu?) rota), daha sonra eşinizin haritayı kontrol etmesini beklemeniz gerekmedi (haritayı kontrol etmek için harcayacağı zamanı kurtardınız), aksi takdirde geri döneceksiniz.

    Boru hatlarını yıkamak süper hızlı olsa da, bugünlerde bu kumar oynamak buna değer. Sıralanan verileri veya yavaş değişen bir veriyi tahmin etmek, hızlı değişiklikleri önceden tahmin etmekten her zaman daha kolay ve iyidir.

     switch     
    172
    2018-03-16 12: 30: 45Z

    Şube tahmini ile ilgili. Bu nedir?

    • Bir dal tahmincisi, hala modern mimarilerle alaka bulduğu eski performans geliştirme tekniklerinden biridir. Basit tahmin teknikleri hızlı arama ve güç verimliliği sağlarken, yüksek bir yanlış tahmin oranından muzdariptir.

    • Öte yandan, karmaşık şube tahminleri - ya sinirsel tabanlı ya da iki seviyeli şube tahmininin varyantları - daha iyi tahmin doğruluğu sağlar, ancak daha fazla güç tüketirler ve karmaşıklık katlanarak artar.

    • Buna ek olarak, karmaşık tahmin tekniklerinde dalları tahmin etmek için geçen zaman, 2 ila 5 döngü arasında değişen, fiili dalların yürütme zamanıyla karşılaştırılabilir olan, çok yüksektir.

    • Şube tahmini, esasen olası en düşük kayıp oranı, düşük güç tüketimi ve minimum kaynaklarla düşük karmaşıklık elde etmenin önemini vurgulayan bir optimizasyon (minimizasyon) sorunudur.

    Gerçekten üç farklı dal türü vardır:

    Koşullu dalları yönlendirin - bir çalışma zamanı koşuluna bağlı olarak, PC (program sayacı), talimat akışında ileriye yönelik bir adrese işaret edecek şekilde değiştirilir.

    Koşullu dalları geriye sarma - PC, talimat akışında geriye dönük olarak değiştirildi. Dal, döngünün sonundaki bir test, döngünün tekrar yürütülmesi gerektiğini belirttiğinde, bir program döngüsünün başlangıcına geri dallanma gibi bir koşula dayanır.

    Koşulsuz dallar - buna, özel koşulu olmayan sıçramalar, prosedür çağrıları ve iadeler dahildir. Örneğin, koşulsuz bir atlama talimatı, montaj dilinde basitçe "jmp" olarak kodlanabilir ve talimat akışı hemen, atlama talimatı tarafından belirtilen hedef konuma yönlendirilmeli, buna karşılık koşullu atlama ise "jmpne" olarak kodlanmalıdır. talimat akışını yalnızca önceki bir "karşılaştırma" talimatındaki iki değerin karşılaştırmasının sonucu eşit olmayan değerler gösteriyorsa yönlendirecektir. (X86 mimarisi tarafından kullanılan bölümlendirilmiş adresleme şeması, ekstra karmaşıklık ekler çünkü atlamalar "yakın" (bir bölüm içinde) veya "uzak" (bölüm dışında) olabilir. Her türün dal tahmin algoritmaları üzerinde farklı etkileri vardır.)

    Statik /dinamik Şube Tahmini : Statik branş tahmini, mikroişlemci tarafından koşullu bir branşla ilk karşılaşıldığında ilk kez kullanılır ve koşullu branş kodunun yürütülmesinde başarılı olmak için dinamik branş tahmini kullanılır.

    Kaynaklar:

    116
    2018-03-16 10: 57: 23Z

    Şube tahmininin sizi yavaşlatabileceği gerçeğinin yanı sıra, sıralanmış bir dizinin başka bir avantajı vardır:

    Sadece kontrol etmek yerine durdurma şartınız olabilirdeğer, bu şekilde sadece ilgili verilerin üzerinden geçersiniz ve gerisini görmezden gelirsiniz.
    Şube tahmini yalnızca bir kez özlenecek.

     if     
    110
    2019-03-05 09: 58: 40Z
    1. Doğru, ancak diziyi sıralamanın kurulum maliyeti O (N log N) 'dir, bu nedenle diziyi sıralamanızın tek sebebi erken kırmak size yardımcı olmaz erken kırabilmektir. Bununla birlikte, diziyi önceden sıralamak için başka nedenleriniz varsa, o zaman evet, bu değerlidir.
      2018-11-06 12: 28: 29Z
    2. @ LukeHutchison iyi gözlem; lütfen farklı bir çekim için aşağıdaki cevabımı görün.
      2019-02-27 11: 47: 22Z
    3. Verileri, kaç kez kullandığınıza göre sıraladığınıza göre değişir. Bu örnekteki sıralama sadece bir örnektir, döngüden hemen önce olması gerekmez
      2019-02-27 12: 23: 22Z
    4. Evet, ilk yorumumda kesinlikle yazdığım nokta :-) Diyorsunuz ki, "Şube tahmini yalnızca bir kez kaçıracak". Ancak, sıralama algoritmasının içindeki O (N log N) dal tahmininin özlediğini saymazsınız, bu da aslında sıralanmamış durumda O (N) dal tahmininin özlediğinden daha büyüktür. Bu nedenle, sıralama algoritmasına bağlı olarak, örneğin önbellek eksikliğinden dolayı hızlı sıralama için eşit sıralama yapmak için O (log N) süresinin tamamını (muhtemelen N'ye daha yakın (10 log N)) kullanmanız gerekir. daha önbellek uyumlu olduğundan, kırmak için O (2 log N) kullanımına daha yakın olmanız gerekir.)
      2019-02-28 12: 28: 14Z
    5. Önemli bir optimizasyon, yalnızca "hedeflenen değer 127'den küçük olan öğeleri sıralayarak (" her şeyin veya altında olduğunu varsayarak) eşittir , pivot pivottan sonra sıralanır). Pivota ulaştığınızda, pivottan önceki elemanları toplayın. Bu, O (N log N) yerine O (N) başlangıç ​​saatinde çalışır, ancak daha önce verdiğim sayılara bağlı olarak muhtemelen O (5 N) sırasına bağlı olarak hala çok sayıda branş tahmini özlemi olacaktır. yarısı bir hızlı bağlantı noktası.
      2019-02-28 12: 34: 48Z

    ARM'ta dal gerekmez, çünkü her komutun sıfır maliyetle test edilen 4 bitlik bir koşul alanı vardır. Bu, kısa dallara olan ihtiyacı ortadan kaldırır ve hiçbir dal tahminde etki olmaz. Bu nedenle, sıralanan sürüm, fazladan sıralama eklenmesi nedeniyle ARM'deki sıralanmamış sürümden daha yavaş çalışacaktır. İç döngü aşağıdaki gibi bir şeye benzeyebilir:

     if     
    106
    2018-05-14 14: 01: 18Z
    1. Her komutun şartlı olabileceğini mi söylüyorsunuz? Bu nedenle,
       O      Route 1  /-------------------------------
      /|\             /
       |  ---------##/
      / \            \
                      \
              Route 2  \--------------------------------
      
      ekine sahip birden çok komut,
       // sort backwards (higher values first), may be in some other part of the code
       std::sort(data, data + arraySize, std::greater<int>());
      
       for (unsigned c = 0; c < arraySize; ++c) {
             if (data[c] < 128) {
                    break;
             }
             sum += data[c];               
       }
      
      'un değeri arasındaki değişmeden sırayla gerçekleştirilebilir.
      2018-05-14 14: 04: 03Z
    2. Evet, doğru, her komut ARM'de, en azından 32 ve 64 bit komut kümelerinde koşullu olabilir. Sadık bir 4 bit koşul alanı var. Aynı koşulu içeren bir sırada birkaç talimatınız olabilir, ancak bir noktada şartın yanlış olma ihtimali ihmal edilemezse, şube eklemek daha verimli olur.
      2018-05-15 17: 06: 42Z
    3. ARM'teki diğer yenilik, S komutunun son ekinin eklenmesidir, ayrıca (neredeyse) tüm talimatlarda isteğe bağlı olarak (varsa) durum bitlerini değiştirmek istemez işi durum bitlerini ayarlamak olan CMP komutunun istisnası, bu yüzden S sonekine ihtiyaç duymaz). Bu, karşılaştırma yapılmadığı sürece birçok durumda CMP talimatlarını önlemenizi sağlar.sıfır veya benzeri ile (örneğin, SUBS R0, R0, # 1, R0 sıfıra ulaştığında Z (Sıfır) bitini ayarlayacaktır). Şartlı Cümleler ve S eki sıfır yüke neden olur. Oldukça güzel bir ISA.
      2018-05-15 17: 06: 54Z
    4. S sonekini eklememek, bir tanesinin durum bitlerini değiştirebileceğinden endişe etmeden birkaç koşullu talimat almanıza izin verir; koşullu talimatların geri kalanını atlama.
      2018-05-15 17: 08: 22Z

    Sıralanmış diziler, dal tahmini olarak adlandırılan bir olay nedeniyle sıralanmamış bir diziden daha hızlı işlenir.

    Şube belirleyicisi, bir dalın hangi yöne gideceğini tahmin etmeye çalışan ve komut satırındaki akışı iyileştiren dijital bir devredir (bilgisayar mimarisinde). Devre /bilgisayar bir sonraki adımı tahmin eder ve yürütür.

    Yanlış bir tahmin yapmak önceki adıma geri dönmeye ve başka bir tahminle yürütmeye yol açar. Tahminin doğru olduğunu varsayarak, kod bir sonraki adıma devam edecektir. Yanlış bir tahmin, doğru bir tahmin gerçekleşene kadar aynı adımı tekrarlamakla sonuçlanır.

    Sorunuzun cevabı çok basit.

    Sıralanmamış bir dizide, bilgisayar birden fazla öngörüde bulunur ve bu da hata olasılığının artmasına neden olur. Oysa, sıralı bir dizide, bilgisayar daha az tahmin yaparak hata olasılığını azaltır. Daha fazla tahmin yapmak daha fazla zaman gerektirir.

    Sıralanmış Dizi: Düz Yol     ____________________________________________________________________________________     - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -     TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

    Sıralanmamış Dizi: Eğri Yol

     
    MOV R0, #0     // R0 = sum = 0
    MOV R1, #0     // R1 = c = 0
    ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
    .inner_loop    // Inner loop branch label
        LDRB R3, [R2, R1]     // R3 = data[c]
        CMP R3, #128          // compare R3 to 128
        ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
        ADD R1, R1, #1        // c++
        CMP R1, #arraySize    // compare c to arraySize
        BLT inner_loop        // Branch to inner_loop if c < arraySize
    

    Şube tahmini: Hangi yolun düz olduğunu ve kontrol etmeden takip edildiğini tahmin etme /tahmin etme

     GE

    Her iki yol da aynı hedefe ulaşmasına rağmen, düz yol daha kısa ve diğer yol daha uzundur. Öyleyse yanlışlıkla diğerini seçerseniz, geri dönüş olmaz ve daha uzun yolu seçerseniz fazladan zaman harcarsınız. Bu bilgisayarda olanlara benzer ve umarım bu daha iyi anlamanıza yardımcı olur.


    Ayrıca yorumlardan @Simon_Weaver alıntı yapmak istiyorum:

      

    Daha az tahmin yapmaz - daha az yanlış tahmin yapar. Yine de döngü boyunca her zaman için tahmin yapması gerekir ...

        
    96
    2019-05-27 12: 47: 18Z
    1. "Basit kelimelerle" - Açıklamanızı trenle diğerlerine göre daha az basit ve diğer cevaplardan çok daha az doğru buluyorum. Ben acemi değilim. Neden çok fazla yükseltme olduğunu merak ediyorum, belki de gelecekteki seçmenlerden biri bana söyleyebilir?
      2018-07-04 13: 54: 21Z
    2. @ Sinatr muhtemelen gerçekten görüşe dayalı, kendimi o kadar iyi bulabilirim ki, diğer örnekler kadar doğru değil, bütün mesele bu: Cevap (hepimizin kabul ettiği gibi dal tahmininin burada yer alması gibi) diğerlerinin de yaptığı gibi teknik açıklamalara katılmış okuyuculara sahip olmadan (çok iyi). Ve bence yeterince iyi yaptı.
      2018-07-09 12: 45: 50Z
    3. Daha az tahmin yapmaz - daha az yanlış tahmin yapar. Yine de döngü boyunca her zaman için tahmin yapması gerekir.
      2018-07-16 01: 28: 03Z
    4. Doğru dürüstüm, benim hatam, teşekkür ederim @Simon_Weaver, bir süre içinde düzeltirim veya lütfen bazı düzenlemelerinizi düzenleyebilir ve onaylarım , şimdiden teşekkürler ...
      2018-07-16 05: 52: 47Z

    AssumVerilerin sıralanması gereken diğer cevaplara göre, doğru değildir.

    Aşağıdaki kod dizinin tamamını sıralamaz, ancak yalnızca 200 elemanlı bölümleri ve böylece en hızlı şekilde çalışır.

    Yalnızca k öğesi bölümlerini sıralamak, ön işlemi R3 yerine doğrusal zamanda tamamlar.

     
    ______   ________
    |     |__|
    

    Bu, sıralama düzeni gibi herhangi bir algoritmik sorunla ilgisi olmadığını ve gerçekten de dal tahmini olduğunu "kanıtlar".

        
    17
    2019-02-28 15: 24: 59Z
    1. Bunun nasıl bir şey kanıtladığını gerçekten anlamıyorum? Gösterdiğiniz tek şey, "tüm diziyi sıralama işini yapmamak bütün diziyi sıralamaktan daha az zaman alır" dır. Bunun "aynı zamanda en hızlı şekilde çalıştığını" iddia ediyorsunuz mimariye bağımlı. Bunun ARM üzerinde nasıl çalıştığıyla ilgili cevabımı görün. PS, 200 elemanlı blok döngüsünün içine toplamı koyarak, tersten sıralayarak ve ardından aralık dışı bir değer elde ettiğinizde Yochai Timmer'in kırma önerisini kullanarak, ARM olmayan mimarilerde kodunuzu daha hızlı yapabilirsiniz. Bu şekilde, her 200 elemanlı blok toplamı erken iptal edilebilir.
      2019-02-28 12: 18: 29Z
    2. @ LukeHutchison Kanıt, sizin gibi iyi bilgilendirilmiş bir cevaplayıcı için OP değil. OP için bu, sınıflandırmanın daha hızlı işlemeyle ilgisi olduğu hipotezini geçersiz kılar (bkz. Soru başlığı ifadesi). Genel amaçlı bir mimaride algoritmik anlamda "en hızlı çalışır" - ARM özel bir durumdur. Yochai Timmer'in önerisi, büyük O anlamında algoritmik olmayan, oldukça mantıklı bir optimizasyon. Ayrıca, genel olarak, insanlar hem gerçek hem de yanlış durumlarda bir şeyler yaparlardı, böylece Yochai'nin kesmesi uygulanmayacaktı & muhtemelen toplamdan daha önemli bir şey.
      2019-02-28 15: 21: 15Z
    ___________________________________________ Straight road
     |_________________________________________|Longer road
    
kaynak yerleştirildi İşte