S─▒ralanm─▒┼č bir diziyi neden s─▒ralanmam─▒┼č bir diziyi i┼člemekten daha h─▒zl─▒ i┼čliyor?


Al─▒nan cevaba git


Baz─▒ ├žok tuhaf davran─▒┼č g├Âsteren C ++ kodunun bir par├žas─▒. 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;
}
 
  • Olmadan std::sort(data, data + arraySize); , 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'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├ž.


─░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 neden s─▒ralanmam─▒┼č bir diziyi i┼člemekten daha h─▒zl─▒ i┼čliyor?

Kod baz─▒ ba─č─▒ms─▒z terimleri topluyor, bu y├╝zden sipari┼č ├Ânemli olmamal─▒.


23544









Cevap say─▒s─▒n─▒ say: 23






┼×ube tahmininin kurban─▒ oldu─čun i├žin ba┼čar─▒s─▒zs─▒n.


┼×ube Tahmini Nedir?

Bir demiryolu kav┼ča─č─▒ d├╝┼č├╝n├╝n:


Bir demiryolu kav┼ča─č─▒ g├Âsteren resim

G├Âr├╝nt├╝ Wikimedia Commons arac─▒l─▒─č─▒yla Mecanismo taraf─▒ndan. 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┼č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─▒┼č oldu─čunu tahmin ederseniz , tren durma, yedekleme ve yeniden ba┼člatma i├žin ├žok zaman harcar.


Bir if ifadesi d├╝┼č├╝n├╝n: ─░┼člemci d├╝zeyinde, bir dallanma 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┼č─▒k ve uzun boru hatlar─▒ var. 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 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 zaman do─čru tahmin ederseniz , y├╝r├╝tme asla durmak zorunda kalmaz.
├çok s─▒k yanl─▒┼č oldu─čunu tahmin ederseniz , durma, geri d├Ânme ve yeniden ba┼člatma i├žin ├žok zaman harcars─▒n─▒z.


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┼č tarihe bakars─▒n! Tren zaman─▒n% 99'unu terk ederse, tahminen sola gidersiniz. De─či┼čirse, tahminlerinizi de─či┼čtirirsiniz. Her ├╝├ž seferde bir giderse, ayn─▒ ┼čeyi tahmin edersiniz ...

Ba┼čka bir deyi┼čle, bir deseni tan─▒mlamaya ve onu takip etmeye ├žal─▒┼č─▒n. Bu, ┼čube belirleyicilerinin nas─▒l ├žal─▒┼čt─▒─č─▒n─▒ a┼ča─č─▒ yukar─▒ hareket ediyor.

├ç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: Vikipedi "┼×ube tahmin" makalesi .


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 belirleyicisi rastgele verileri tahmin edemedi─činden i┼če yaramaz hale gelir. Bu nedenle, muhtemelen% 50 civar─▒nda yanl─▒┼č anlama olacakt─▒r (rastgele tahminlerden daha iyisi yoktur).

 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 kesmenin kesinlikle orijinal if-ifadesine e┼čde─čer olmad─▒─č─▒n─▒ unutmay─▒n. Ancak bu durumda, t├╝m girdi de─čerleri i├žin ge├žerlidir data[] .)

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─▒ralanm─▒┼č 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 (bu ├Ârnekte oldu─ču gibi) verilere ba─čl─▒ dallanmay─▒ ├Ânlemektir.


G├╝ncelle┼čtirme:

  • GCC 4.6.1 x64'te -O3 veya -ftree-vectorize ├╝st├╝nde, 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 alt─▒nda bile olsa bu ┼čube i├žin ┼čartl─▒ hamle ├╝retemez /Ox .

  • Intel C ++ Compiler (ICC) 11 mucizevi bir ┼čey yap─▒yor. Bu iki d├Âng├╝ al─▒┼čveri┼čini sa─člar , b├Âylece d─▒┼č d├Âng├╝ye ├Âng├Âr├╝lemeyen dal─▒ kald─▒rma. 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─▒ ...

  • 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, olgun modern derleyicilerin bile kodu optimize etme kabiliyetlerinde ├ž─▒lg─▒nca de─či┼čebildi─čini g├Âsteriyor ...


30773







┼×ube tahmini

S─▒ralanm─▒┼č bir dizide, ko┼čul data[c] >= 128 ├Ânce false bir de─čerler dizisi i├žin olur, daha sonra true t├╝m de─čerler i├žin olur . Tahmin etmesi kolay. S─▒ralanmam─▒┼č bir diziyle, dallanma maliyetini ├Âdersiniz.


3958







Veriler s─▒ralan─▒rken performans─▒n ┼čiddetli bir ┼čekilde artmas─▒n─▒n nedeni , Mysticial'─▒n cevab─▒nda g├╝zel bir ┼čekilde a├ž─▒kland─▒─č─▒ gibi, ┼čube ├Âng├Ârme cezas─▒n─▒n kald─▒r─▒lmas─▒d─▒r .

┼×imdi, koda bakarsak

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

Belirli bir if... else... dal─▒n anlam─▒n─▒n, bir ko┼čul sa─čland─▒─č─▒nda bir ┼čeyler eklemek oldu─čunu g├Ârebiliriz. Bu t├╝r dallar, bir sistemde ko┼čullu bir hareket talimat─▒na derlenecek olan ko┼čullu bir hareket ifadesine kolayca d├Ân├╝┼čt├╝r├╝lebilir :. ┼×ube ve dolay─▒s─▒yla potansiyel ┼čube kestirim cezas─▒ kald─▒r─▒l─▒r. cmovl x86

In C , b├Âylece C++ , ko┼čullu ta┼č─▒ma talimat─▒ i├žine (herhangi bir optimizasyon olmadan) do─črudan derlemek istiyorum a├ž─▒klamada, x86 , ├╝├ž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.

Bir Intel Core i7 -2600K @ 3.4 GHz ve Visual Studio 2010 S├╝r├╝m Modunda, temel ├Âl├ž├╝ (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 x86 ├╝rettikleri montaj─▒ inceleyerek daha yak─▒ndan bakal─▒m . Basit olmas─▒ i├žin, iki i┼člevi max1 ve kullan─▒n max2 .

max1 ko┼čullu dal─▒ kullan─▒r if... else ... :

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

max2 ├╝├žl├╝ i┼člecini kullan─▒r ... ? ... : ... :

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

Bir x86-64 makinesinde, GCC -S a┼ča─č─▒daki d├╝zene─či 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 talimat kullan─▒m─▒ nedeniyle ├žok daha az kod kullan─▒r cmovge . Ancak as─▒l kazan├ž, tahmin edilen sonu├ž do─čru de─čilse, ├Ânemli bir performans cezas─▒na sahip olacak max2 dal atlamalar─▒n─▒ jmp i├žermemesidir.

├ľ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. Buna boru 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 hareket durumunda, y├╝r├╝tme ko┼čullu hareket komutu birka├ž a┼čamaya ayr─▒l─▒r, ancak ├Ânceki a┼čamalar ├Ânceki komutun sonucuna benzer Fetch ve Decode buna 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 adl─▒ kitap , ikinci bask─▒ , bunu ayr─▒nt─▒l─▒ olarak a├ž─▒klar. Sen i├žin B├Âl├╝m 3.6.6 kontrol edebilirsiniz ┼×artl─▒ Ta┼č─▒ Talimatlar─▒ i├žin t├╝m B├Âl├╝m 4 ─░┼člemci Mimarisi i├žin ├Âzel bir tedavi i├žin, ve B├Âl├╝m 5.11.2 ┼×ube Prediction ve Misprediction Cezalar─▒ .

Bazen, baz─▒ modern derleyiciler kodumuzu daha iyi performansla derlemeye 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.


3199







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┼čulun i d├Âng├╝n├╝n y├╝r├╝t├╝lmesi boyunca sabit oldu─čunu g├Ârebilirsiniz, b├Âylece if d─▒┼čar─▒ya ├žekebilirsiniz :

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

Daha sonra, kayan nokta modelinin izin verdi─čini varsayarak ( /fp:fast ├Ârne─čin 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─▒.


2192







Hi├ž ┼č├╝phesiz baz─▒lar─▒m─▒z CPU'nun ┼čube belirleyicisi i├žin sorunlu olan kodlar─▒ tan─▒mlama yollar─▒yla ilgilenir. Valgrind arac─▒ cachegrind , --branch-sim=yes bayrak kullan─▒larak etkinle┼čtirilen bir dal kestirici sim├╝lat├Âr├╝ne sahiptir . Bu sorudaki ├Ârneklerin ├╝zerinden ge├žmek, 10000'e d├╝┼č├╝r├╝len ve derlenen d─▒┼č d├Âng├╝ say─▒s─▒yla g++ ┼č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%   )
 

Boylanmam─▒┼č:

 ==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 S├Âz konusu d├Âng├╝ i├žin g├Ârd├╝─č├╝m├╝z sat─▒r sat─▒r ├ž─▒kt─▒s─▒n─▒ delip ge├žiyoruz:

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

Boylanmam─▒┼č:

           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, Bcm ├Ânbellek dal─▒ dal belirleyici modelinde 164.050,007 yanl─▒┼č ├Âng├Âr├╝len ko┼čullu dallara ( ) 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─▒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
 

Boylanmam─▒┼č:

  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 ayr─▒nt─▒ i├žin performans e─čitimine bak─▒n.


1828


2012-10-12





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.

Arkaplan 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 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. 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 asl─▒nda sonsuza dek s├╝recek bir bellek y├╝k├╝ beklemeniz gerekir ( di─čer bir deyi┼čle: ba┼čar─▒s─▒z ┼čube tahmini k├Ât├╝d├╝r, bir bellek Dal tahmin ba┼čar─▒s─▒zl─▒ktan sonra y├╝kleme 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 k├╝├ž├╝k olan 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 masa in┼ča etmek

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 bunu bir s─▒f─▒r ve ├žok 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 & 0x[something]FFF s─▒n─▒r kontrol├╝n├╝ tahmin edilebilir k─▒lmak i├žin arama i┼člevinize bir ekleme yapmak 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();
 

1287







Dizi s─▒raland─▒─č─▒nda veriler 0 ile 255 aras─▒nda da─č─▒t─▒ld─▒─č─▒ndan, yinelemelerin ilk yar─▒s─▒ yakla┼č─▒k if -statement'e girmeyecektir ( if ifade 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 ┼čey nedir? ─░┼čte "┼čube belirleyicisi" geliyor. Dal tahmincisi, if-then-else kesin olarak bilinmeden ├Ânce bir dal─▒n (├Ârne─čin bir yap─▒n─▒n) 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!

Daha iyi anlamak i├žin baz─▒ tezgah i┼čaretleme yapal─▒m

Bir if ifadenin performans─▒ , durumunun tahmin edilebilir bir yap─▒ya sahip 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 durum ├ž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
 

ÔÇť K├Ât├╝ ÔÇŁ bir do─čru-yanl─▒┼č kal─▒p, if ÔÇť iyi ÔÇŁ bir kal─▒ptan alt─▒ kat daha yava┼č bir kademe olu┼čturabilir ! 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!


1152







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, lut kodumun nas─▒l olu┼čturuldu─čunu ve arama tablosunu nas─▒l kulland─▒─č─▒n─▒ g├Âsterir ( kodsuz bir ┼čekilde "Arama Tablosu" i├žin kullan─▒lmaz). ─░┼č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, bir if ifade 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) uzunluk-2 i┼čaret├ži dizisine sahip olmak yerine, hangisinin takip edece─čine karar vermek i├žin "karar bit" 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─▒ Kar─▒nca A─ča├žlar─▒ , Eternly Confuzzled


1077







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 biti┼čik bir b├Âlgede data < 128 ve bir di─čeriyle ayr─▒lm─▒┼čt─▒r data >= 128 . Bu nedenle, b├Âlme noktas─▒n─▒ iki Lg(arraySize) = 15 y├Ânl├╝ bir arama ile bulmal─▒ ( kar┼č─▒la┼čt─▒rmalar─▒ kullanarak ), 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─▒ralanm─▒┼č hem de s─▒n─▒fland─▒r─▒lmam─▒┼č olanlar i├žin yakla┼č─▒k bir ├ž├Âz├╝m sunan hen├╝z daha h─▒zl─▒ bir yakla┼č─▒m : sum= 3137536; (ger├žekten d├╝zg├╝n bir da─č─▒l─▒m varsayarsak, beklenen de─čeri 191.5 olan 16384 ├Ârnek) :-)


974







Yukar─▒daki davran─▒┼č, ┼×ube tahmini nedeniyle ger├žekle┼čiyor.

┼×ube tahminini anlamak i├žin ├Ânce bir Talimat Boru Hatt─▒'n─▒ anlaman─▒z gerekir :

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 Wikipedia'daki bu ├Â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. 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─▒.
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().
 

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 olursa ne zaman:
g├Âr├╝nt├╝ tan─▒m─▒n─▒ buraya girin

Ne zaman ko┼čul yanl─▒┼č d├Ând├╝r├╝rse:
g├Âr├╝nt├╝ 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─▒ ┼č├Âyle g├Âr├╝n├╝r:
g├Âr├╝nt├╝ tan─▒m─▒n─▒ buraya girin

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, iyi bir dal kestiricisine olan ihtiya├ž o kadar b├╝y├╝k olur .

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.


794







Resmi bir cevap

  1. Intel - ┼×ube Yanl─▒┼čl─▒─č─▒ Maliyetinin ├ľnlenmesi
  2. Intel - Yanl─▒┼č Yanl─▒┼člar─▒ ├ľnlemek ─░├žin ┼×ube ve D├Âng├╝ Yeniden Yap─▒lanmas─▒
  3. Bilimsel makaleler - ┼čube tahmini bilgisayar mimarisi
  4. Kitaplar: JL Hennessy, DA Patterson: Bilgisayar mimarisi: nicel bir yakla┼č─▒m
  5. Bilimsel yay─▒nlarda yer alan makaleler: TY Yeh, YN Patt, ┼čube tahminleriyle ilgili pek ├žok ┼čey yapt─▒.

Ayr─▒ca, bu g├╝zel diyagramdan , dal kestiricisinin neden kar─▒┼čt─▒─č─▒n─▒ g├Ârebilirsiniz.


2 bit durum diyagram─▒

Orijinal koddaki her ├Â─če rastgele bir de─čerdir

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

bu y├╝zden tahminci std::rand() darbe 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.



695


2015-10-11





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 */    
}
 

Her ikisi de likely() ve unlikely() asl─▒nda __builtin_expect , derleyicinin kullan─▒c─▒ taraf─▒ndan sa─članan bilgileri dikkate alarak ko┼čulu lehine tahmin kodunu koymas─▒na yard─▒mc─▒ olmak i├žin GCC'ler 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 . Mevcut GCC'nin yerle┼čiklerinden ge├žen bu belgeye bak─▒n .

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.


664







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 de─čeri ile 8 bitlik tamsay─▒lar olarak depolan─▒r 0 i├žin false ve 1 i├žin true .

Boolean de─či┼čkenleri, girdilerin 0 veya d─▒┼č─▒nda herhangi bir de─čere sahip olup olmad─▒klar─▒n─▒, girdi olarak Boolean de─či┼čkenleri olan t├╝m operat├Ârlerin, ancak ├ž─▒kt─▒ olarak Boole de─čerine sahip olan 1 operat├Ârlerin 0 veya de─čerlerinden ba┼čka bir de─čer ├╝retemedi─či anlam─▒nda belirlenir 1 . 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 de─čerlerinden ba┼čka hi├žbir de─čeri olmad─▒─č─▒ kesin olarak biliniyorsa, ├žok daha verimli yap─▒labilir 1 . 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 ge├žerli de─čerlere ayarlanm─▒┼č a ve b ba┼člat─▒lm─▒┼č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;
 

char yerine kullan─▒lan bool s─▒rayla m├╝mk├╝n bitsel operat├Ârleri (kullanmak yapmak & ve | ) yerine Boolean operat├Ârleri ( && ve || ). Bitsel operat├Ârler, yaln─▒zca bir saat d├Âng├╝s├╝ alan tek talimatlard─▒r. VEYA operat├Âr├╝ ( | ) bile ├žal─▒┼č─▒r a ve b d─▒┼č─▒ndaki de─čerlere sahip 0 veya 1 . AND i┼čleci ( & ) ve EXCLUSIVE OR i┼čleci ( ^ ), i┼členenlerin 0 ve de─čerlerinden ba┼čka de─čerleri varsa tutars─▒z sonu├žlar verebilir 1 .

~ NOT i├žin kullan─▒lamaz. Bunun yerine, Boolean NOT'u ┼ču ┼čekilde bilinen 0 veya 1 XOR''la bilinen bir de─či┼čkende yapabilirsiniz 1 :

 bool a, b;
b = !a;
 

A┼ča─č─▒dakiler i├žin optimize edilebilir:

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

a && b ile ikame edilemez a & b ise b , e─čer de─čerlendirilmesi gereken bir ifade olan a bir false ( && de─čerlendirmek olmaz b , & olacakt─▒r). Ayn─▒ ┼čekilde, a || b birlikte ikame edilemez a | b ise b , e─čer de─čerlendirilmesi gereken bir ifadesidir a olup true .

─░┼členenler, i┼členenlerin kar┼č─▒la┼čt─▒r─▒lmas─▒ndan daha de─či┼čkendirse, bitsel i┼čle├žlerin kullan─▒lmas─▒ daha avantajl─▒d─▒r:

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

├ço─ču durumda en uygunudur ( && ifadenin bir├žok dal yanl─▒┼čl─▒─č─▒ ├╝retmesini beklemiyorsan─▒z ).


637







Kesinlikle!...

┼×ube tahmini , mant─▒k ├žal─▒┼čmas─▒n─▒ yava┼člat─▒r, ├ž├╝nk├╝ kodunuzda meydana gelen anahtarlama! 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 daha sonra soka─č─▒n sonuna kadar t├╝m├╝yle 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?


┼×ube Tahmini

Yani programl─▒ olarak, ┼čube tahmini s├╝recin 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


┼×ube Tahmini

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.

Etkin bir yazma zaman bu kurallar─▒n, yararlanmak i├žin kod yazmak i├žin if-else veya anahtar ifadeleri, kademeli a┼ča─č─▒ az─▒ndan ortak i┼člerimiz ilk en genel durumu kontrol edip. 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.


306







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


278







Ba┼čkalar─▒ taraf─▒ndan daha ├Ânce de belirtildi─či gibi, gizemin ard─▒nda olan ┼čey ┼×ube Tahminidir .

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 varsa ba┼čka bir yap─▒n─▒n) 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).


┼×ekil 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.


dal belirleyicisi olmadan

Tamamlanmas─▒ gereken 3 talimat i├žin 9 saat devri gerekecektir.

  1. Branch Predictor kullan─▒n ve ko┼čullu bir s─▒├žrama yapmay─▒n. Tahminin ┼čartl─▒ atlamay─▒ almad─▒─č─▒n─▒ varsayal─▒m .


g├Âr├╝nt├╝ tan─▒m─▒n─▒ buraya girin

3 talimat─▒n tamamlanmas─▒ 7 saat s├╝recektir.

  1. Branch Predictor kullan─▒n ve ko┼čullu bir s─▒├žrama yap─▒n. Tahminin ┼čartl─▒ atlamay─▒ almad─▒─č─▒n─▒ varsayal─▒m .


g├Âr├╝nt├╝ tan─▒m─▒n─▒ buraya girin

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 BranchPredictorDemo'dan da alabilirler.https://github.com/Eugene-Mark/BranchPredictorDemo


206







┼×ube tahmin kazan├ž!

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 montaj kodunda ko┼čullu bran┼č talimatlar─▒ 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 (├Ârne─čin, ifade yanl─▒┼čsa, program if blo─čun kodunu atlar ). Olgumuzda ifade de─čerlendirmesi.

Oldu─ču s├Âyleniyor, derleyici asl─▒nda de─čerlendirilmeden ├Ânce sonucu tahmin etmeye ├žal─▒┼č─▒r. if Bloktan talimatlar alacak 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  \--------------------------------
 

185







┼×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.

├ť├ž farkl─▒ dal t├╝r├╝ var:

Ko┼čullu dallar─▒ ileriye alma - bir ├žal─▒┼čma zaman─▒ ko┼čuluna ba─čl─▒ olarak, PC (program sayac─▒) komut ak─▒┼č─▒nda ileri bir adrese i┼čaret edecek ┼čekilde de─či┼čtirilir.

Geri ko┼čullu dallar - PC komut ak─▒┼č─▒nda geriye d├Ân├╝k olarak de─či┼čtirilir. 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 baz─▒ ko┼čullara dayan─▒r.

Ko┼čulsuz dallar - buna s─▒├žramalar, yordam ├ža─čr─▒lar─▒ ve belirli bir ko┼čulu olmayan d├Ân├╝┼čler 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 "jmpne" olarak kodlanm─▒┼č ko┼čullu bir atlay─▒┼č 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 Dal Tahmini : Statik dal tahmini, mikroi┼člemci taraf─▒ndan ko┼čullu bir dal ilk kez kar┼č─▒la┼č─▒ld─▒─č─▒nda kullan─▒l─▒r ve ko┼čullu dal kodunun yerine getirilmesi i├žin dinamik dal tahmini kullan─▒l─▒r.

Referanslar:


126







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

120







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
 

119







S─▒ralanan diziler, dal tahmini olarak adland─▒r─▒lan fenomenler nedeniyle s─▒ralanmam─▒┼č dizilerden daha h─▒zl─▒ i┼členir.

Dal kestiricisi, 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 neden olur. 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.

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─▒ral─▒ bir dizide, bilgisayar daha az tahmin yaparak hata olas─▒l─▒─č─▒n─▒ azalt─▒r. Daha fazla tahmin yapmak daha fazla zaman gerektirir.

S─▒ralama Dizisi: 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 yorumlardan @Simon_Weaver al─▒nt─▒ yapmak istiyorum :

Daha az tahmin yapmaz - daha az yanl─▒┼č tahmin yapar. Hala d├Âng├╝ boyunca her zaman i├žin tahmin etmek zorunda ...


108







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 ├Â─česi b├Âl├╝mlerini s─▒ralamak, t├╝m diziyi s─▒ralamak i├žin gereken zaman O(n) yerine ├Ân i┼člemeyi do─črusal zaman i├žinde tamamlar O(n.log(n)) .

 #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.


33







Bjarne Stroustrup's Bu soruya cevap:

Bu bir r├Âportaj sorusu gibi geliyor. Bu do─čru mu? Nas─▒l bildin Verimlilikle ilgili sorular─▒ ├Ânce baz─▒ ├Âl├ž├╝mler yapmadan cevaplamak k├Ât├╝ bir fikirdir, bu nedenle nas─▒l ├Âl├ž├╝lece─čini bilmek ├Ânemlidir.

B├Âylece, bir milyon tam say─▒ vekt├Âr├╝yle denedim ve:

 Already sorted    32995 milliseconds
Shuffled          125944 milliseconds

Already sorted    18610 milliseconds
Shuffled          133304 milliseconds

Already sorted    17942 milliseconds
Shuffled          107858 milliseconds
 

Emin olmak i├žin birka├ž kez ko┼čtum. Evet, fenomen ger├žektir. Anahtar kodum:

 void run(vector<int>& v, const string& label)
{
    auto t0 = system_clock::now();
    sort(v.begin(), v.end());
    auto t1 = system_clock::now();
    cout << label 
         << duration_cast<microseconds>(t1 ÔÇö t0).count() 
         << " milliseconds\n";
}

void tst()
{
    vector<int> v(1'000'000);
    iota(v.begin(), v.end(), 0);
    run(v, "already sorted ");
    std::shuffle(v.begin(), v.end(), std::mt19937{ std::random_device{}() });
    run(v, "shuffled    ");
}
 

En az─▒ndan bu derleyici, standart k├╝t├╝phane ve iyile┼čtirici ayarlar─▒yla fenomen ger├žek. Farkl─▒ uygulamalar farkl─▒ cevaplar verebilir ve verir. Asl─▒nda, birisi daha sistematik bir ├žal─▒┼čma yapt─▒ (h─▒zl─▒ bir web aramas─▒ bulacakt─▒r) ve ├žo─ču uygulama bu etkiyi g├Âstermektedir.

Bunun bir nedeni bran┼č tahminidir: s─▒ralama algoritmas─▒ndaki anahtar i┼člem ÔÇťif(v[i] < pivot]) ÔÇŽÔÇŁ veya e┼čde─čeridir. Test edilen s─▒ral─▒ bir dizi i├žin her zaman do─črudur, rastgele bir s─▒ra i├žin se├žilen dal rastgele de─či┼čir.

Ba┼čka bir neden, vekt├Âr zaten s─▒raland─▒─č─▒nda, elemanlar─▒ asla do─čru konumlar─▒na getirmemize gerek kalmamas─▒d─▒r. Bu k├╝├ž├╝k ayr─▒nt─▒lar─▒n etkisi g├Ârd├╝─č├╝m├╝z be┼č ya da alt─▒ fakt├Âr├╝d├╝r.

Quicksort (ve genel olarak s─▒ralama), bilgisayar biliminin en b├╝y├╝k beyinlerinden baz─▒lar─▒n─▒ ├žeken karma┼č─▒k bir ├žal─▒┼čmad─▒r. ─░yi bir s─▒ralama i┼člevi, hem iyi bir algoritma se├žmenin hem de uygulamas─▒nda donan─▒m performans─▒na dikkat etmenin bir sonucudur.

Verimli kod yazmak istiyorsan─▒z, makine mimarisi hakk─▒nda biraz bilgi sahibi olman─▒z gerekir.


10