it-swarm-tr.com

Sıralanmış bir diziyi sıralanmamış bir diziden daha hızlı işlemek neden daha hızlı?

İşte size çok özel görünen bir C++ kodu. Bazı garip sebeplerden dolayı, verileri mucizevi bir şekilde sıralamak, kodu neredeyse altı kat daha hızlı yapar.

#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 verilerde, kod 1,93 saniye içinde çalışır.

Başlangıçta, bunun sadece bir dil veya derleyici anomalisi olabileceğini düşündüm. Bu yüzden Java da 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);
    }
}

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


İlk düşüncem, sıralama işleminin verileri önbelleğe getirdiği, ancak daha sonra dizilimin henüz yaratılmasının ne kadar saçma olduğunu düşündüm.

  • Ne oluyor?
  • Sıralanmış bir diziyi sıralanmamış bir diziden daha hızlı işlemek neden daha hızlı?
  • Kod bazı bağımsız terimleri topluyor ve sipariş önemli değil.
22968
GManNickG

Siz branş tahmininin kurbanısınız başarısız.


Şube Tahmini Nedir?

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

 Image showing a railroad junction Image Mecanismo tarafından, Wikimedia Commons aracılığıyla. CC-By-SA 3.0 lisansı altında kullanılmaktadı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şletmecisisin ve bir trenin geldiğini duyuyorsun. 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 atalet var. Bu yüzden sonsuza kadar başlamak ve yavaşlamak için alırlar.

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

  • Doğru tahmin ederseniz, devam ediyor.
  • Yanlış olduğunu tahmin edersen, kaptan duracak, geri duracak ve anahtarı çevirmen için sana bağıracak. Sonra diğer yoldan yeniden başlatılabilir.

Her seferinde doğru tahmin ederseniz , tren asla durmak zorunda kalmayacak.
Çok sık yanlış tahmin ederseniz , tren durmak, yedeklemek ve yeniden başlamak için çok zaman harcar.


Bir if-ifadesi düşünün: İşlemci düzeyinde, bir dallanma talimatıdır:

Screenshot of compiled code containing an if statement

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şık ve uzun boru hatlarına sahipler. Bu yüzden sonsuza dek “ısınmak” ve “yavaşlamak” için alıyorlar.

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

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

Her seferinde doğru tahmin ederseniz , yürütme asla durmaz.
Çok sık yanlış tahmin ederseniz , durma, geri alma ve yeniden başlatma için çok zaman harcıyorsunuz.


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 son ana kadar bir dalın hangi yöne gideceğini bilmiyor.

Peki, trenin geri çekilip diğer yoldan aşağı inmesi gereken zaman sayısını en aza indirmeyi nasıl stratejik olarak 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 3 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 belirleyicilerinin çalışma şekli az ya da çok.

Çoğu uygulamada iyi davranılmış 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şıldığında, dal tahmin edicileri neredeyse işe yaramaz.

Daha fazla okuma: "Şube belirleyicisi" Vikipedi .


Yukarıda da belirtildiği gibi, suçlu bu 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öne 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 tahmincisi rastgele verileri tahmin edemediğinden yararsız hale getirilir. Bu nedenle muhtemelen% 50 civarında yanlış tahmin olacaktır. (rastgele tahminden daha iyi değil)

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)

Peki ne yapılabilir?

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

Değiştir:

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

ile:

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

Bu, dalı ortadan kaldırır ve bazı bitsel işlemlerle değiştirir.

(Bu hack'in kesinlikle orijinal if-ifadesiyle aynı olmadığını unutmayın. Ancak bu durumda, data[] öğesinin tüm girdi 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ıralanmamış veriler arasında büyük fark var.
  • Hack ile: Sıralanan ve sıralanmamış veriler arasında fark yoktur.
  • C++ durumunda, hack aslında veriler sıralanırken daldan biraz daha yavaştır.

Genel bir kural, kritik döngülerdeki verilere bağlı dallanmalardan kaçınmaktır. (bu örnekte olduğu gibi)


Güncelleme:

  • GCC 4.6.1, x64'te -O3 veya -ftree-vectorize ile koşullu bir hareket üretebilir. Dolayısıyla, sıralanan ve sıralanmayan veriler arasında fark yoktur - ikisi de hızlıdır.

  • VC++ 2010, bu kod için /Ox altında bile koşullu hamle oluşturamıyor.

  • Intel Compiler 11 mucizevi bir şey yapıyor. Bu iki halkayı birbiriyle değiştirir , böylece öngörülemeyen dalı dış halkaya kaldırır. Bu yüzden sadece yanlış öngörüleri immünize etmekle kalmaz, aynı zamanda VC++ ve GCC'nin üretebildiğinin iki katı daha hızlıdır! Başka bir deyişle, ICC, ölçütü yenmek için test döngüsünden faydalandı ...

  • Eğer Intel Compiler'a branşsız kodu verirseniz, sadece sağa doğru vektörleşir ... ve branşta olduğu kadar hızlıdır (döngü değişimi ile).

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

30104
Mysticial

Şube tahmini.

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

3879
Daniel Fischer

Veriler sıralanırken performansın şiddetli bir şekilde artmasının nedeni, Mysticial 'in cevabında güzel bir şekilde açıklandığı gibi, şube tahmin cezasının kaldırılmasıdır.

Şimdi, koda bakarsak

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

bu belirli if... else... dalının anlamının, bir koşul sağlandığında bir şeyler eklemek olduğunu görebiliriz. Bu dal türü, bir x86 sisteminde, bir koşullu hamle deyimine dönüştürülebilir, bu da koşullu bir hareket komutuna derlenir: cmovlname__. Şube ve dolayısıyla potansiyel şube kestirim cezası kaldırılır.

Cname__, yani C++'da, x86'deki koşullu hareket komutunda doğrudan (herhangi bir optimizasyon olmadan) derlenen ifade, ... ? ... : ...'deki üçlü operatördür. 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.

Intel Core i7 - 2600K @ 3,4 GHz ve Visual Studio 2010 Sürüm Modunda, referans (Mysticial'dan kopyalanan format):

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

Sonuç, çoklu testlerde 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, şartlı bir hareket kullanılırken performans, veri deseninden bağımsız olarak aynıdır.

Şimdi ürettikleri x86 Assembly'yi inceleyerek daha yakından inceleyelim. Basit olması için, iki işlevi max1 ve max2 kullanıyoruz.

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

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

max2, üçlü operatör ... ? ... : ... 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, cmovgekomutunun kullanımı nedeniyle daha az kod kullanır. Ancak asıl kazanç, max2'nin, dallanan atlamaları, jmpname__'yi içermemesidir; bu, öngörülen sonuç doğru olmazsa, önemli bir performans cezasına sahip olur.

Öyleyse neden koşullu bir hareket 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. Bunaboru hattıdenir.

Şube durumunda, aşağıdaki talimat öncekiyle belirlenir, dolayısıyla boru hattını yapamayız. Beklemek ya da tahmin etmek zorundayız.

Koşullu bir taşıma durumunda, yürütme koşullu taşıma talimatı birkaç aşamaya ayrılır, ancak Fetchve Decodegibi daha ö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, koşullu taşıma sürümünün, tahmin yapmak kolay olduğunda şubeden daha yavaş olmasının nedeni budur.

Bilgisayar Sistemleri: Bir Programcının Perspektifi, ikinci baskı kitabı 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ış Tahmin Cezaları için özel bir muamele için Bölüm 5.11.2'yi kontrol edebilirsiniz.

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

3125
WiSaGaN

Bu koda yapılabilecek daha fazla optimizasyon hakkında merak ediyorsanı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];
    }
}

Ardından, if koşulunun i döngüsünün çalışması boyunca sabit olduğunu görebilirsiniz, böylece if out öğesini kaldırabilirsiniz:

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

Ardından, kayan nokta modelinin izin verdiğini varsayarak iç döngünün tek bir ifadede daraltılabileceğini görüyorsunuz (/ fp: örneğin hızlı atılmış)

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

Bu bir öncekinden 100,000x daha hızlı

2143
vulcan raven

Hiç şüphesiz bazılarımız CPU'nun şube belirleyicisi için sorunlu olan kodları tanımlama yollarıyla ilgilenir. Valgrind aracı cachegrindname__, --branch-sim=yes bayrağı kullanılarak etkinleştirilen bir dal kestirici simülatörüne sahiptir. Bu sorudaki örneklerin üzerinden geçmek, 10000'e düşürülen ve g++ ile derlenen dış döngü sayısıyla şu sonuçları verir:

Sıralandı:

==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%   )

Sıralanmamış:

==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ısını delip geçerken, söz konusu döngü için görüyoruz:

Sıralandı:

          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];
           .      .  .   .          }
           .      .  .   .      }

Sıralanmamış:

          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 yanlış belirlenmiş koşullu dallara (Bcmname__) neden olurken, sıralanan sürümde yalnızca 10,006'ya neden olur.


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

perf stat ./sumtest_sorted

Sıralandı:

 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

Sıralanmamış:

 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

Aynı zamanda demontaj ile kaynak kodu 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 bilgi için performans dersine bakınız.

1784
caf

Ben sadece bu soruyu ve cevaplarını okudum ve cevabın eksik olduğunu hissediyorum.

Özellikle yönetilen dillerde 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 test etmemiş olmama rağmen).

Bu yaklaşım genel olarak şu durumlarda çalışır:

  1. bu küçük bir masa ve işlemcide önbelleğe alınması muhtemeldir ve
  2. işleri oldukça dar bir döngüde çalıştırıyorsunuz ve/veya işlemci verileri önceden yükleyebilir.

Arka plan ve neden

Bir işlemci açısından, hafızanız yavaş. Hız farkını telafi etmek için, işlemcinize birkaç önbellek yerleştirilmiştir (L1/L2 önbellek). Öyleyse, Nice 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. Bellek nispeten yavaş olduğundan, bu 'yük' programınızı yavaşlatır.

Dal tahmini gibi, bu da Pentium işlemcilerde optimize edilmiştir: işlemci, bir veri parçasının yüklenmesi gerektiğini öngörür 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 gerçekte 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) dal tahmini başarısız sonra bir bellek yükü sadece korkunç!).

Neyse ki, bizim için, eğer hafıza erişim şablonu öngörülebilir ise, işlemci onu hızlı önbelleğine yükler ve her şey yolundadır.

Bilmemiz gereken ilk şey small nedir? Daha küçük genellikle daha iyi olsa da, bir kural, <= 4096 byte boyutundaki 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.

Bir tablo oluşturmak

Böylece küçük bir masa yaratabileceğ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şinizin arama işleviyle tablonuzdaki bir tür 'benzersiz anahtar'a çevrilmesini isteyin, 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 ise 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. Sonuçta, 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, derleyici için 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 açık vakalarla da ilgilenecektir.

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

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();
1247
atlaste

Dizi sıralandığında veriler 0 ile 255 arasında dağıtıldığı için, yinelemelerin ilk yarısı etrafında ifname __- deyimi girilmez (ifdeyimi aşağıda paylaşılı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 şey nedir? İşte "şube belirleyicisi" geliyor. Bir dal tahmincisi, bir dalın (örneğin bir if-then-else yapısı) 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 bir takım işaretler yapalım

ifname __- ifadesinin 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, ifname __- ifadesi ç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ış kalıplara 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

Bir “ bad ” doğru-yanlış deseni, ifname __- ifadesini “ good ” düzeninden altı kat daha yavaş hale getirebilir! Elbette, hangi modelin iyi ve hangisinin kötü olduğu, derleyici tarafından oluşturulan talimatlara ve işlemciye göre değişir.

Bu nedenle şube tahmininin performans üzerindeki etkisinden şüphe yok!

1118
Saqlain

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

Fakat bu durumda, değerlerin [0, 255] aralığında olduğunu biliyoruz ve sadece>> 128 değerlerini önemsiyoruz. Bu, bir değer isteyip istemediğimizi bize söyleyecek tek bir parçayı kolayca çıkarabileceğimiz anlamına geliyor: değiştirerek Sağdaki 7 bit veri, 0 bit veya 1 bit kalıyor ve sadece 1 bit olduğunda değer eklemek istiyoruz. Bu bit'e "karar bitini" diyelim.

Karar bitinin 0/1 değerini bir dizinin dizini 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ü bir arama tablosuna indeksleme biraz kaymadan biraz daha hızlıydı. Bu, kodumun nasıl kurulduğunu ve arama tablosunu nasıl kullandığını gösterir (koddaki "Arama Tablosu" için yaratıcı bir şekilde lut olarak adlandırılır). İş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 sadece 256 byte'dı, bu nedenle bir önbellekte güzel bir şekilde uyuyordu 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.

Bir diziye indeksleme tekniği, if deyimi kullanmak yerine, hangi işaretçinin kullanılacağına karar vermek için 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) iki yerine işaretçi dizisi koymak yerine, hangisinin takip edeceğine karar vermek için "karar biti" tekniğini kullandım. Örneğin, yerine:

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

bu kütüphane şöyle bir şey yapar:

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

İşte bu koda bir link: Kırmızı Siyah Ağaçlar , Eternally Confuzzled

1039
steveha

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.

Aslında, dizi data < 128 ve diğeri data >= 128 ile bitişik bir bölgede bölümlenir. Öyleyse, bölümleme noktasını dikotomik arama (Lg(arraySize) = 15 kıyaslamalarını kullanarak) ile bulmalı, sonra o noktadan düz bir birikim yapmalısınız.

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 karışık

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ıralanmayanlar için yaklaşık çözümü veren, ancak daha hızlı bir yaklaşım: sum= 3137536; (gerçekten tekdüze bir dağılım olduğu varsayılırsa, beklenen değer 191.5 olan 16384 örnek) :-)

942
Yves Daoust

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

Şube tahminini anlamak için önce şunu anlamak gerekir: Instruction Pipeline :

Herhangi bir talimat, bir adım sırasına bölünür, böylece farklı adımlar aynı anda paralel olarak gerçekleştirilebilir. 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 şunu görün Wikipedia'da örnek .

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. ID - Talimatın kodunun çözülmesi
  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ı. 4-stage pipeline in general

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().

Dal 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 gelinceye kadar beklemesi gerekir. bu gibi görünecek.

koşul doğru olduğunda:: enter image description here

Koşul yanlışsa:: enter image description here

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.

Öyleyse ş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ı şuna benziyor: enter image description here

Daha sonra tahminin yanlış olduğu tespit edilirse, kısmen uygulanan talimatlar atılır ve boru hattı bir gecikmeyle doğru dallamayla başlar. 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, o kadar iyi bir ihtiyaç dal kestiricisi .

OP kodunda, şartlı ilk kez, şube öngörücüsünde öngörüyü temel alacak herhangi bir bilgi yoktur, bu nedenle ilk defa rastgele bir sonraki talimatı seçecektir. 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 elemanlar 128'den az
  2. Tüm elemanlar 128'den büyük
  3. Bazı yeni elemanlar 128'den küçüktür ve daha sonra 128'den büyük olur

Tahmin edenin ilk çalıştırmada daima 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ı alacaktır. İ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ı atıp, daha az CPU çevrimi ile sonuçlanan doğru dalla baştan başlayacaktır.

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

765
Harsh Sharma

Resmi bir cevap

  1. Intel - Şube Yanlışlığı Maliyetini Önlemek
  2. Intel - Yanlış Tahminleri Önlemek İçin Şube ve Döngü Yeniden Yapılanması
  3. Bilimsel makaleler - şube tahmini bilgisayar mimarisi
  4. Kitaplar: J. H, 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ı.

Ayrıca, bu sevimli diyagram da dal tahmincinin kafasının karışmasını da görebilirsiniz.

 2-bit state diagram

Orijinal koddaki her öğe rastgele bir değerdir

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

bu yüzden, yorucu std::Rand() darbesi olarak taraf değiştirir.

Öte yandan, bir kez sıralama yapıldığında, yorucu ilk önce güçlü bir şekilde alınamayan bir duruma geçecektir ve değerler yüksek değere değiştiğinde yordayıcı, üç harekette, alınmadan güçlü bir şekilde alınmadan sonuna kadar değişecektir.


669
Surt

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() aslında, 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 talimatlar yayan diğer yapıtaşlarını destekler. Bkz. bu dokümantasyon , mevcut GCC'nin yerleşiklerinden geçer.

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 dal tahmini, koşulun yanlış olduğunu varsayar.

634
rkachach

C++ 'da sık kullanılan Boolean işlemleri derlenmiş programda birçok dal üretir. Bu dallar ilmek içindeyse ve tahmin edilmesi zorsa, yürütmeyi önemli ölçüde yavaşlatabilir. Boolean değişkenleri, false için 0 ve true için 1 değerine sahip 8 bitlik tamsayılar olarak depolanır.

Boolean değişkenleri, Boolean değişkenleri giriş olarak Boe değişkenleri olan tüm operatörlerin, girdilerin 0 veya 1 dışında bir değere sahip olup olmadığını kontrol etmeleri anlamında belirlenir, ancak çıktı olarak Boole değerine sahip operatörler 0 veya 1 değerlerinden başka bir değer üretemez. 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 dışında hiçbir değere sahip olmadığı kesin olarak bilinirse ç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ırlandıysa veya Boolean çıktısı üreten işleçlerden geldiyse 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örlerinin (& ve |) yerine bitsel operatörlerin (&& ve ||) kullanılmasını sağlamak için char yerine bool kullanılır. Bitsel operatörler, yalnızca bir saat döngüsü alan tek talimatlardır. OR operatörü (|), a ve b0 veya 1 dışındaki değerlere sahip olsa bile çalışır. AND işleci (&) ve EXCLUSIVE OR operatörü (^), işlenenler 0 ve 1 dışında bir değere sahipse tutarsız sonuçlar verebilir.

~ NOT için kullanılamaz. Bunun yerine, Boolean NOT'u, 0 veya 1 olarak bilinen bir değişkende, 1 ile XOR'layarak yapabilirsiniz:

bool a, b;
b = !a;

aşağıdakiler için optimize edilebilir:

char a = 0, b;
b = a ^ 1;

a && ba & b ile değiştirilemez, eğer ba ise false ise (&&b, & değerlendirmez) değerlendirilirse değerlendirilmemesi gereken bir ifadedir. Benzer şekilde, a || ba | b ile değiştirilemez, b, atrue ise değerlendirilmemesi gereken bir ifadedir.

İşlenenler, işlenenlerin karşılaştırılmasından daha değişkendirse, bitsel operatörlerin kullanılması daha avantajlıdır:

bool a; double x, y, z;
a = x > y && z < 5.0;

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

603
Maciej

Kesinlikle!...

Şube tahmini , kodunuzda meydana gelen anahtarlama nedeniyle mantığı yavaşlatır! Düz bir caddeye veya çok fazla dönüşü olan bir caddeye gidiyor gibisiniz, kesin olanı daha çabuk bitecek! ...

Dizi sıralanırsa, koşulunuz ilk adımda yanlıştır: data[c] >= 128, sonra caddenin sonuna kadar olan yol için 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 tornalama ve işleme gerekir.

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

 Branch Prediction

Yani programlı olarak, dal tahmini işlemin yavaşlamasına neden olur ...

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

1. Statik

2. Dinamik

 Branch Prediction

Statik dal kestirimi, mikroişlemci tarafından koşullu dallara ilk kez rastlandığında kullanılır ve koşullu dal kodunun yürütülmesinde başarılı olmak için dinamik dal kestirimi kullanılır.

Bu kurallardan yararlanmak için kodunuzu etkin bir şekilde yazabilmek için, if-else veya switch deyimlerini yazarken, ilk önce en yaygın durumları kontrol edin ve en az yaygın olana kadar yavaş yavaş çalışın. Döngüler, normalde yalnızca döngü yineleyicinin koşulu kullanıldığından, statik dal kestirimi için herhangi bir özel kod sıralaması gerektirmez.

280
Alireza

Bu soru zaten defalarca mükemmel bir şekilde cevaplandı. 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 hem sıralanmış hem de sıralanmamış durumda zamanının çoğunu nerede geçirdiğini belirlemek için sonuçların nasıl kullanılacağını gösterir. Son olarak parça, sıralanmamış durumda ne kadar dal yanlışlığı olduğunu belirlemek için HAL'in (Donanım Soyutlama Katmanı) az bilinen bir özelliğinin nasıl kullanılacağını da gösterir.

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

262
ForeverLearning

Başkaları tarafından daha önce de belirtildiği gibi, gizemin ardında olan şey Branch Predictor .

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

Bilgisayar mimarisinde, bir dal belirleyicisi, bir dalın (örneğin, eğer öyleyse bir yapı) bu şekilde kesin olarak bilinmeden önce nasıl gideceğini tahmin etmeye çalışan bir dijital devredir. Dal tahmincisinin amacı, talimat boru hattındaki akışı iyileştirmektir. Şube tahmin edicileri, x86 gibi birçok modern boru hattı işlemcisi mimarisinde yüksek etkili performans elde edilmesinde kritik bir rol oynamaktadır.

İki yönlü dallanma genellikle koşullu bir sıçrama talimatıyla uygulanır. Koşullu bir atlama ya "alınamaz" olabilir ve koşullu atlamadan hemen sonra izlenen ilk kod dalıyla yürütülmeye devam edilebilir veya "kod alınabilir" ve ikinci kod dalının bulunduğu program belleğinde farklı bir yere atlanabilir saklanmış. Koşullu bir atlamanın, koşul hesaplanıp koşullu atlamanın talimat boru hattında uygulama aşamasından geçinceye kadar alınıp alınmayacağı kesin olarak bilinmemektedir (bakınız şekil 1).

 figure 1

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

  1. Şube Predictor olmadan.

Dal tahmini olmadan, işlemcinin bir sonraki komutun boru hattına getirme aşamasına girmeden önce koşullu atlama talimatının yürütme aşamasını geçmesini beklemesi gerekir.

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

 without branch predictor

Tamamlanması gereken 3 talimat için 9 saat devri gerekecektir.

  1. Branch Predictor kullanın ve koşullu bir sıçrama yapmayın. Tahminin koşullu atlamayı alarak değil olduğunu kabul edelim.

 enter image description here

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

  1. Branch Predictor kullanın ve koşullu bir sıçrama yapın. Tahminin koşullu atlamayı alarak değil olduğunu kabul edelim.

 enter image description here

Tamamlanması gereken 3 talimat için 9 saat devri gerekecektir.

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. Sonuç olarak, bir boru hattının daha uzun hale getirilmesi daha gelişmiş bir dal tahmincisine olan ihtiyacı arttırır.

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

Branch Predictor'ın çok temel kısmını açıklığa kavuşturmak oldukça basit bir demo. Eğer bu gifler can sıkıcıysa, lütfen onları cevaptan çıkarmaktan çekinmeyin; ziyaretçiler demoyu git

176
Gearon

Şube tahmin kazancı!

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

if (expression)
{
    // Run 1
} else {
    // Run 2
}

Bir if-else\switch ifadesi olduğunda, hangi bloğun yürütüleceğini belirlemek için ifadenin değerlendirilmesi gerekir. Derleyici tarafından oluşturulan derleme kodunda koşullu şube komutları eklenmiştir.

Dallı bir komut, bilgisayarın farklı bir komut dizisi yürütmeye başlamasına neden olabilir ve bu nedenle sırayla komutları yerine getirme konusundaki varsayılan davranışından sapabilir (yani, eğer ifade yanlışsa, program if bloğunun kodunu atlar). olgumuzda ifade değerlendirmesidir.

Olduğu söyleniyor, derleyici aslında değerlendirilmeden önce sonucu tahmin etmeye çalışır. if bloğundan talimatlar alır ve ifade doğru çıkacaksa harika olur! 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 ki rota 1 veya rota 2'yi seçmeniz gerekir. Eşinizin haritayı kontrol etmesini bekliyorum, ## ile durup beklediniz veya sadece rota1'i seçebilirsiniz ve şanslıysanız (rota 1 doğru rota), o zaman eşinizin haritayı kontrol etmesini beklemeniz gerekmiyordu (haritayı kontrol etmek için harcayacağı zamanı aldınız), yoksa geri dönersiniz.

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

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

Şube tahmini ile ilgili. Bu ne?

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

  • Öte yandan, karmaşık şube tahminleri - ne sinirsel temelli veya iki düzeyli branş tahmininin bir değişkeni - 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ın öngörülmesi 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 zamandır.

  • Şube tahmini, esasen mümkün olan en düşük kayıp oranını, düşük güç tüketimini ve minimum kaynaklarla düşük karmaşıklığı elde etmenin önemini vurgulayan bir optimizasyon (minimizasyon) problemidir.

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

Koşullu dalları ileri yönlendirme - çalışma zamanı durumuna bağlı olarak, PC (program sayacı) komut akışında ileri bir adrese işaret edecek şekilde değiştirilir.

Koşullu dalların geriye gitmesi - PC komut 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 geriye doğru dallanma gibi bir koşula dayanır.

Koşulsuz dallar - buna, özel koşulu olmayan sıçramalar, prosedür çağrıları ve geri dönüşler dahildir. Örneğin, koşulsuz bir atlama talimatı Assembly dilinde basitçe "jmp" olarak kodlanabilir ve komut akışı hemen, atlama talimatı tarafından belirtilen hedef konuma yönlendirilmeli, buna karşılık koşullu atlama "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 yerine getirilmesinde başarılı bir branş tahmini kullanılır.

Referanslar:

113
Farhad

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

Sadece değeri kontrol etmek yerine bir stop koşuluna sahip olabilirsiniz, bu şekilde sadece ilgili verilerin üzerinden geçersiniz ve gerisini görmezden gelirsiniz.
Şube tahmini yalnızca bir kez özleyecektir.

 // 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];               
 }
107
Yochai Timmer

ARM'da 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 şey olurdu:

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
103
Luke Hutchison

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

Dal tahmincisi, bir dalın hangi yöne gideceğini tahmin etmeye çalışan, 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 neden olur. Tahminin doğru olduğunu varsayarak, kod bir sonraki adıma devam edecektir. Yanlış tahmin, doğru tahmin gerçekleşene kadar aynı adımı tekrarlamakla sonuçlanır.

Sorunuza cevap ç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ıralandığında, bilgisayar hata olasılığını azaltan daha az tahmin yapar. Daha fazla tahminde bulunmak daha fazla zaman gerektirir.

Sıralanmış Dizi: Düz Yol

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

Sıralanmamış Dizi: Eğri Yol

______   ________
|     |__|

Şube tahmini: Hangi yolun düz olduğunu tahmin ederek/tahmin ederek kontrol etmeden takip edin

___________________________________________ Straight road
 |_________________________________________|Longer road

Her iki yol da aynı hedefe ulaşsa da, 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 @Simon_Weaver 'dan alıntı yapmak istiyorum:

Daha az tahmin yapmaz - daha az yanlış tahmin yapar. Hala döngü boyunca her zaman için tahmin etmek zorunda ..

92
Omkaar.K

Diğer cevapların verilerini sıralamak için ihtiyaç duyduğu varsayımı doğru değildir.

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

Yalnızca k elemanı bölümlerini sıralamak, ön işleme işlemini n.log(n) yerine doğrusal zamanda tamamlar.

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

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

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

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

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

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

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

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

14
user2297550

Çünkü sıralandı!

Sıralı verileri, sıralanmamış verilerden almak ve değiştirmek kolaydır.

Tıpkı dükkanlardan (sipariş edilen) ve gardırobumdan (berbat) giysiler seçmek gibi.

0
Arun Joshla