Soru Sıralanmamış bir diziden sıralanmış bir diziyi işlemesi neden daha hızlıdır?


İşte çok özel görünen bir C ++ kodu parçası. Bazı garip nedenlerden 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 saniyede çalışır.
  • Sıralanan verilerle kod, 1.93 saniyede çalışır.

Başlangıçta bunun sadece bir dil veya derleyici anomalisi olabileceğini düşündüm. Bu yüzden onu 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 ama daha az aşırı bir sonuçla.


İlk düşüncem sıralamaların veriyi önbellekte getirmesiydi, ama sonra ne kadar aptalca olduğunu düşündüm çünkü dizi yeni üretildi.

  • Ne oluyor?
  • Sıralanmamış bir diziden sıralanmış bir diziyi işlemesi neden daha hızlıdır?
  • Kod bazı bağımsız terimleri özetliyor ve sipariş önemli olmamalı.

21674
2018-06-27 13:51


Menşei


Sadece kayıt için. Windows / VS2017 / i7-6700K 4GHz'de iki versiyon arasında fark yoktur. Her iki durumda da 0,6 puan alır. Dış döngüdeki yineleme sayısı 10 kat artırılırsa, her iki durumda da yürütme süresi 6 saniyede 10 kat artar. - mp31415
@ user194715: kullanan herhangi bir derleyici cmov veya diğer şubesiz uygulama ( pcmpgtd) herhangi bir CPU'ya bağımlı olmayan bir performansa sahip olacaktır. Ama eğer şubeliyse, sıra dışı spekülatif yürütme ile herhangi bir CPU'ya göre sıralamaya bağlı olacaktır. (Yüksek performanslı sıralı CPU'lar bile, alınan dallardaki kabarcıkların alınmasını / şifresini çözmeyi önlemek için şube tahminini kullanır; hanımefendi cezaları daha küçüktür). - Peter Cordes
Woops ... yeniden: Meltdown ve Spectre - KyleMit
@KyleMit'in her ikisiyle de bir ilgisi var mı? İkisinde de fazla okumadım - mohitmun
@mohitmun, bu güvenlik açıklarının her ikisi de, şu şekilde sınıflandırılan geniş bir güvenlik kategorisine girer “Dal hedef enjeksiyon” saldırıları - KyleMit


Cevaplar:


Sen kurbanısın dal tahmini başarısız.


Şube Tahmin Nedir?

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

Licensed Image görüntü Wikimedia Commons üzerinden Mecanismo tarafından. Altında kullanılır CC-By-SA 3.0 lisans.

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

Bir kavşağın operatörü ve bir trenin geldiğini duyuyorsun. Hangi yöne gitmesi gerektiği hakkında hiçbir fikrin yok. Şoförü hangi yöne istediklerini sormak için durdur. Ve sonra anahtarı uygun şekilde ayarladınız.

Trenler ağır ve çok fazla atalet var. Böylece onlar sonsuza dek başlamak ve yavaşlatmak için alırlar.

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

  • Doğru tahmin ederseniz, devam ediyor.
  • Yanlış tahmin ederseniz, kaptan durur, yedeklenir ve düğmeyi çevirmeniz için size bağırır. Sonra diğer yolu tekrar başlatabilir.

Her seferinde doğru tahmin edersenizTren asla durmak zorunda kalmayacak.
Çok sık yanlış tahmin edersenizTren, durmak, yedeklemek ve yeniden başlatmak için çok zaman harcayacak.


Bir if deyimi düşünün: İşlemci düzeyinde, bir dal talimatıdır:

image2

Sen bir işlemci ve bir şube görüyorsun. Hangi yoldan gideceği hakkında hiçbir fikrin yok. Ne yaparsın? Yürütmeyi durdurursunuz ve önceki talimatlar tamamlanıncaya kadar beklersiniz. Sonra doğru yola devam edersiniz.

Modern işlemciler karmaşıktır ve uzun boru hatlarına sahiptir. Böylece "ısınmak" ve "yavaşlatmak" için sonsuza dek sürer.

Daha iyi bir yolu var mı? Dalın hangi yöne gideceğini tahmin et!

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

Her seferinde doğru tahmin edersenizİdam asla durmak zorunda kalmayacak.
Çok sık yanlış tahmin ederseniz, çok fazla zaman ayırıyor, geri çekiliyor ve yeniden başlıyorsunuz.


Bu dal tahmini. En iyi benzetme olmadığını itiraf ediyorum, çünkü tren sadece bir bayrakla yönünü gösterebiliyordu. Ancak bilgisayarlarda işlemci, bir şubenin son ana kadar hangi yöne gideceğini bilmiyor.

Öyleyse trenin yedeklenmesi ve diğer yoldan aşağı inmesi gereken süreyi en aza indirmek için stratejik olarak nasıl tahmin edersiniz? Geçmiş tarihe bakın! Tren saatin% 99'undan ayrılırsa, sanırım sola dönersiniz. Değişirse, tahminlerinizi değiştirirsiniz. Her 3 kere bir yol kat ederse, aynı şeyi tahmin edersin ...

Başka bir deyişle, bir kalıbı tanımlamaya ve onu takip etmeye çalışırsınız. Bu, az ya da çok kestiricilerin nasıl çalıştığıdır.

Çoğu uygulama iyi huylu dallara sahiptir. Dolayısıyla, modern şube tahmin edicileri tipik olarak>% 90 isabet oranlarına ulaşacak. Ancak, tanınabilir olmayan kalıpları olan tahmin edilemeyen dalları ile karşılaştıklarında, şube tahmin edicileri neredeyse işe yaramaz.

Daha fazla okuma: Vikipedi'de "Şube yordayıcı" makalesi.


Yukarıda ima edildiğ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, iterasyonların ilk yarısı kabaca if ifadesine girmeyecektir. Bundan sonra, hepsi if deyimini girecekler.

Bu, dallar birbirini takip eden defalarca aynı yöne doğru gittiğinden dolayı bu, şube tahmincisine son derece uygundur. Basit bir doyurucu sayaç bile, yön değiştirdikten sonra birkaç iterasyon haricinde dalı doğru bir şekilde tahmin edecektir.

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)

Bununla birlikte, veriler tamamen rastgele olduğunda, şube tahmincisi, rastgele veriyi öngöremediği için işe yaramaz hale gelir. Böylece muhtemelen yaklaşık% 50 yanlış tahmin olacaktır. (rastgele tahmin etmekten 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ı bir koşullu harekete göre optimize edemiyorsa, performans için okunabilirliği feda etmeniz isteniyorsa bazı korsanlar 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 biraz bitly işlemlerle değiştirir.

(Bu kesmenin orijinal if ifadesine kesinlikle eşdeğer olmadığını unutmayın. Fakat bu durumda, tüm giriş 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ıralanmamış veriler arasında büyük bir fark var.
  • Hack ile: Sıralı ve sıralanmamış veriler arasında fark yoktur.
  • C ++ durumunda, veri sıralandığında, kesmek aslında daldan biraz daha yavaştır.

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


Güncelleştirme:

  • GCC 4.6.1 ile -O3 veya -ftree-vectorize x64 üzerinde koşullu bir hareket üretebilir. Yani sıralanmış ve sıralanmamış veriler arasında fark yoktur - ikisi de hızlıdır.

  • VC ++ 2010, bu dal için şartlı hamleler oluşturamıyor /Ox.

  • Intel Compiler 11, mucizevi bir şey yapıyor. O iki döngüyü değiştirirböylece öngörülemeyen branşmanı dış çevrime kaldırır. Bu yüzden sadece yanlış tahminleri değil, aynı zamanda VC ++ ve GCC'nin üretebileceği kadar iki kat hızlıdır! Başka bir deyişle, ICC, referans noktasını yenmek için test döngüsünden yararlandı ...

  • Intel derleyicisine dalsız kod verirseniz, bu tam olarak vektörü simgeleştirir ... ve şube ile olduğu kadar hızlıdır (döngü değişimi ile).

Bu, olgun modern derleyicilerin bile kodları optimize etme becerilerinde çılgınca değişebileceğini gösteriyor ...


28593
2018-06-27 13:56



@Mysticial Değişen hack önlemek için gibi bir şey yazabilirsiniz int t=-((data[c]>=128)) Maskeyi üretmek için Bu da daha hızlı olmalı. Derleyicinin koşullu bir hareket eklemek için yeterince akıllı olup olmadığını bilmek ilginç olurdu. - Mackie Messer
@phonetagger Bu takip soruya bir göz atın: stackoverflow.com/questions/11276291/... Intel Derleyici, dış döngüden tamamen kurtulmaya oldukça yaklaştı. - Mysticial
@Novelocrat Sadece yarısı doğru. Sıfır olduğunda bir işaret-bitine 1 kaydırmak gerçekten UB'dir. Bunun nedeni tamsayı taşmasıdır. Fakat işaret-işaretinden 1'i değiştirmek IB'dir. Negatif imzalı bir tamsayıyı sağa kaydırmak IB'dir. C / C ++ 'nun üst bitin işaret göstergesi olması gerekmediği argümanına girebilirsiniz. Ancak uygulama detayları IB'dir. - Mysticial
@Mysticial Bağlantı için çok teşekkürler. Umut verici görünüyor. Yine de gideceğim. Son bir istek. Üzgünüm, lütfen sakın unutma, bunu nasıl yapabileceğini söyleyebilir misin? int t = (data[c] - 128) >> 31; sum += ~t & data[c]; Yukarıdaki orijinal koşullandırma koşulunu değiştirmek için? - Unheilig
İçimdeki dilbilgisi, bunun okunması gerektiğini düşünmemi istiyor. "... Şube tahmini kurbanı başarısız olduobilyaları"sadece değil" ... şube kurbanı kurbanı başarısız. " - jdero


Şube tahmini.

Sıralı bir dizi ile koşul data[c] >= 128 ilk false bir değer çizgisi için, o zaman olur true tüm sonraki değerler için. Tahmin etmek çok kolay. Sıralanmamış bir dizi ile, dallanma maliyeti için ödeme yaparsınız.


3640
2018-06-27 13:54



Dallanma tahmini, farklı desenlere sahip diziler ve diziler üzerinde daha iyi çalışır mı? Örneğin, dizi için -> {10, 5, 20, 10, 40, 20, ...} dizideki dizideki bir sonraki öğe 80'dir. Bu tür bir dizi şube tahmini ile hızlandırılır mı desen takip edilirse, sonraki elemanın hangisi 80 olduğu? Veya genellikle sadece sıralanmış dizilerde yardımcı olur mu? - Adam Freeman
Yani temelde büyük-O hakkında geleneksel olarak öğrendiğim her şey pencerenin dışında mı? Bir dallanma maliyetinden daha iyi bir maliyete katlanmak daha mı iyi? - Agrim Pathak
@AgrimPathak Bu bağlıdır. Çok büyük olmayan bir giriş için, daha yüksek karmaşıklığa sahip bir algoritma, daha yüksek karmaşıklığa sahip algoritmalar için sabitler daha küçük olduğunda daha düşük karmaşıklığa sahip bir algoritmadan daha hızlıdır. Kestirme noktanın tahmin edilmesi zor olabilir. Ayrıca, bunu karşılaştır, yerellik önemlidir. Big-O önemlidir, ancak performansın tek kriteri değildir. - Daniel Fischer
Şube tahmini ne zaman yapılır? Dil, dizinin ne zaman sıralanacağını bilecek? Şu gibi görünen dizinin durumunu düşünüyorum: [1,2,3,4,5, ... 998,999,1000, 3, 10001, 10002]? Bu belirsiz 3 çalışma süresini artıracak mı? Sıralanmamış dizi kadar mı olacak? - Filip Bartuzi
@FilipBartuzi Şube tahmini işlemcisinde, dil seviyesinin altında gerçekleşir (ancak dil, derleyiciye neyin olası olduğunu söyleme yolları sunabilir, dolayısıyla derleyici buna uygun kodlar yayınlayabilir). Örneğinizde, sıra dışı 3, bir dalın yanlış tahmin edilmesine yol açacaktır (uygun koşullar için, 3, 1000'den farklı bir sonuç verir) ve bu dizinin işlenmesi, büyük olasılıkla, bir veya daha fazla bir çift düzine veya yüz nanosaniyeden daha uzun bir süre alacaktır. sıralanmış dizi neredeyse hiç fark edilmezdi. Ne zaman maliyetler yüksek oranda yanlış tahminlerdir, 1000 başına bir yanlış hesaplama çok fazla değil. - Daniel Fischer


Veriler sıralandığında performansın büyük ölçüde artmasının nedeni, şube tahmin cezasının, Mysticialcevabı.

Şimdi, eğer kodlara bakarsak

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

bu özelliğin anlamını bulabiliriz if... else... Bir koşul tatmin edildiğinde bir şey eklemektir. Bu tür bir dal kolayca bir dönüşebilir şartlı hareket koşullu hareket talimatı olarak derlenecek ifade: cmovl, bir x86 sistemi. Şube ve dolayısıyla potansiyel şube tahmini cezası kaldırılır.

İçinde C, Böylece C++koşullu hareket komutuna doğrudan (herhangi bir optimizasyon olmaksızın) derlenecek olan beyan, x86, üçlü operatördür ... ? ... : .... Bu yüzden yukarıdaki ifadeyi bir denkliğe yeniden yazalım:

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

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

Intel'de Çekirdek i7-2600K @ 3.4 GHz ve Visual Studio 2010 Sürüm Modu, referans (Mysticial'den kopyalanan formattır):

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 edilemediğinde büyük bir hız kazanırız, ancak tahmin edilebilir olduğunda biraz acı çekeriz. Aslında, koşullu bir hareket kullanıldığında, veri modelinden bağımsız olarak performans aynıdır.

Şimdi araştırmaya daha yakından bakalım. x86 oluşturdukları montaj. Sadelik için iki fonksiyon kullanıyoruz max1 ve 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ü operatör kullanır ... ? ... : ...:

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

X86-64 makinesinde GCC -S aşağıdaki montajı üretir.

: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 öğretim kullanımı nedeniyle çok daha az kod kullanır cmovge. Ama gerçek kazanç şu ki max2 dal atlayışlarını içermez, jmpTahmin edilen sonuç doğru değilse, önemli bir performans cezası alır.

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

Tipik olarak x86 İşlemci, bir talimatın yürütülmesi birkaç aşamaya ayrılır. Kabaca, farklı aşamalarla uğraşmak için farklı donanımlarımız var. Bu yüzden bir talimatın yeni bir tane başlatmak için bitmesini beklemek zorunda değiliz. Buna denir ardışık düzen.

Bir dal durumunda, aşağıdaki talimat bir öncekiyle belirlenir, bu yüzden borulama işlemini yapamayız. Beklememiz ya da tahmin etmeliyiz.

Koşullu bir hareket durumunda, yürütme koşullu hareket talimatı birkaç aşamaya ayrılır, ancak daha önceki aşamalar gibi Fetch ve Decode önceki talimatın sonucuna bağlı değildir; Sadece son aşamalar sonuca ihtiyaç duyar. Böylece, bir komutun yürütme süresinin bir kısmını bekleriz. Bu nedenle, şartlı hareket versiyonu, tahmin kolay olduğunda daldan daha yavaştır.

Kitap Bilgisayar Sistemleri: Bir Programcının Perspektifi, ikinci baskı Bunu ayrıntılı olarak açıklar. Bölüm 3.6.6'yı kontrol edebilirsiniz. Koşullu Hareket Talimatları4. Bölümün tamamı İşlemci Mimarisive özel bir tedavi için Bölüm 5.11.2 Şube Tahmin ve Yanlış Ceza Cezaları.

Bazen, bazı modern derleyiciler, kodumuzu daha iyi performansla birleştirmek için optimize edebilirler, bazen bazı derleyiciler yapamazlar (söz konusu kod Visual Studio'nun yerel derleyicisini kullanıyordur). Şube ve koşullu hareket arasındaki performans farkını tahmin edilemediğinde, senaryonun karmaşık hale gelmesi durumunda, derleyicinin bunları otomatik olarak optimize edememesi durumunda daha iyi performansla kod yazmamıza yardımcı olabilir.


2961
2018-06-28 02:14



GCC komut satırlarına -O eklemediğiniz sürece varsayılan optimizasyon seviyesi yoktur. (Ve benimkinden daha kötü bir ingilizce olamaz;) - Yann Droneaud
Derleyicinin üçlü operatörün eşdeğer if deyiminden daha iyi bir şekilde optimize edilebileceğine inanmakta zorlanıyorum. GCC'nin üçlü operatörünü koşullu bir harekete geçirdiğini gösterdiniz; sen yok if deyimi için tam olarak aynı şeyi yapmadığını gösterdi. Aslında, yukarıdaki Mystical göre, GCC yapar if-ifadesini koşullu bir harekete göre optimize eder, bu da bu cevabı tamamen yanlış yapar. - BlueRaja - Danny Pflughoeft
@WiSaGaN Kod hiçbir şey göstermez, çünkü iki kod parçanız aynı makine koduna derlenir. İnsanların, örneğinizdeki if ifadesinin, örneğinizdeki terraerden farklı olduğu fikrini almamaları kritik derecede önemlidir. Son paragrafınızdaki benzerliğe sahip olduğunuz doğrudur, ancak bu örnek geri kalanının zararlı olduğu gerçeğini ortadan kaldırmaz. - Justin L.
@WiSaGaN Yanıltıcı olayları ortadan kaldırmak için cevabınızı değiştirdiyseniz, aşağı çekilmem kesinlikle bir oylamaya dönüşür -O0 örnek ve farklılığı göstermek için optimize İki testisinizde asm. - Justin L.
@UpAndAdam Testin yapıldığı an, VS2010, gcc'nin olabileceği gibi, yüksek optimizasyon seviyesi belirlenirken bile orijinal dalı bir koşullu hareket haline getiremez. - WiSaGaN


Bu koda daha fazla optimizasyon yapmayı düşünüyorsanız, şunları düşünün:

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ü güvenli bir şekilde değiştirebilirsiniz:

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

Sonra, bunu görebilirsiniz if koşullu yürütme boyunca sabit i döngü, böylece kaldırabilirsiniz if dışarı:

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ği sürece, iç döngüün tek bir ifadeye daraltılabileceğini görürsünüz (örneğin, / fp: hızlı atılır)

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

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


2026
2017-07-03 02:25



Eğer hile yapmak istiyorsanız, çarpmayı döngü dışında da alabilir ve döngüden sonra * = 100000 yazabilirsiniz. - Jyaif
@Michael - Bu örnek aslında bir örnek olduğuna inanıyorum loop-invariant kaldırma (LIH) optimizasyonu ve DEĞİL döngü takası. Bu durumda, tüm iç döngü dış döngüden bağımsızdır ve bu nedenle dış döngüden kaldırılabilir, bunun üzerine sonuç basitçe bir toplam ile çarpılır. i bir birim = 1e5. Son sonuç için bir fark yaratmıyor, ama sadece rekoru kırmak istedim çünkü bu çok sık kullanılan bir sayfa. - Yair Altman
Takas döngülerinin basit ruhu olmasa da, iç if bu noktada şu şekilde dönüştürülebilir: sum += (data[j] >= 128) ? data[j] * 100000 : 0; derleyicinin indirebileceği cmovge veya esdeger. - Alex North-Keys
Dış döngü, iç halka tarafından alınan zamanı profil için yeterince büyük yapmaktır. Öyleyse neden takas edersiniz. Sonunda, bu döngü zaten kaldırılacak. - saurabheights
@saurabheights: Yanlış soru: neden derleyici değil döngü takas. Mikro benekler zor;) - Matthieu M.


Şüphesiz, bazılarımız, CPU'nun şube-belirleyicisi için sorun yaratan kodları tanımlama yolları ile ilgilenecekti. Valgrind aracı cachegrind Kullanarak etkinleştirilen bir şube-tahmin simülatörü vardır --branch-sim=yes bayrağı. Bu sorudaki örneklerin üzerinde çalışarak, dış döngü sayısı 10000'e düşürüldü ve g++, bu 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%   )

Tarafından üretilen hat-by-line çıktısına sondaj cg_annotate söz konusu döngü için görüyoruz:

sıralama:

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

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 164.050,007 yanlış öngörülü koşullara neden oluyorBcm) cachegrind'ın branş-prediktör modeli altındayken, sıralı versiyonda sadece 10,006'ya neden olmaktadır.


Alternatif olarak, Linux'ta aynı işi gerçekleştirmek için performans sayaçları alt sistemini kullanabilir, ancak CPU sayaçlarını kullanarak yerel performans elde edebilirsiniz.

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

Ayrıca demontaj ile kaynak kodu ek açıklama 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)
...

Görmek performans öğreticisi daha fazla ayrıntı için.


1690
2017-10-12 05:53



Bu korkusuz, sıralanmamış listede,% 50 oranında ekleme isabet şansı olmalı. Bir şekilde şube tahmini sadece% 25'lik bir kayıp oranına sahip,% 50'den daha iyi bir şekilde nasıl daha iyi olabilir? - TallBrianL
@ tall.b.lo: Tüm dalların% 25'i - iki dallar, biri için data[c] >= 128 (hangisinin önerdiğine göre% 50'lik bir gecikme oranı vardır) ve döngü durumu için bir tane c < arraySize ~% 0 eksik oranı vardır. - caf


Sadece bu soruya ve cevaplarına baktım ve bir yanıtın eksik olduğunu hissediyorum.

Yönetilen dillerde özellikle iyi çalıştığını belirlediğim şube tahminini ortadan kaldırmanın yaygın bir yolu, bir dal kullanmak yerine bir tablo aramasıdır (bu durumda test etmemiş olmamıza rağmen).

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

  1. Küçük bir tablodur ve işlemcide önbelleğe alınabilir.
  2. İşleri oldukça sıkı bir döngüde kullanıyorsunuz ve / veya işlemci verileri önceden yükleyebilir

Arkaplan ve neden

Pfew, peki bu ne demek oluyor?

İşlemci bakış açısından, belleğiniz yavaş. Hızdaki farkı telafi etmek için, işlemcinizde (L1 / L2 önbellek) bunu telafi eden birkaç önbellek oluştururlar. Güzel hesaplamalarınızı yaptığınızı ve bir parça belleğe ihtiyacınız olduğunu anladığınızı hayal edin. İşlemci, 'yükleme' işlemini gerçekleştirecek ve bellek parçasını ön belleğe yükleyecek - ve daha sonra hesaplamaların geri kalanını yapmak için önbelleği kullanacak. Bellek nispeten yavaş olduğu için, bu 'yük' programınızı yavaşlatacaktır.

Şube tahmini gibi, bu da Pentium işlemcilerde optimize edildi: İşlemci, bir veri parçasının yüklenmesi gerektiğini ve işlemin önbelleğe yüklenmeden önce önbelleğe yüklemeye çalışacağını tahmin ediyor. Şimdiye kadar gördüğümüz gibi, şube tahmini bazen korkunç bir şekilde yanlış gidiyor - en kötü senaryoda geri dönmeniz gerekiyor ve aslında sonsuza dek sürecek bir bellek yükü beklemeniz gerekiyor (diğer bir deyişle: dallanma kestirimi kötüdür, dal tahmininden sonra hafıza yükü sadece korkunçtur!).

Neyse ki bizim için, bellek erişim modeli öngörülebilir ise, işlemci hızlı önbelleğine yükler ve her şey iyi durumdadır.

Bilmemiz gereken ilk şey, küçük? Daha küçük genellikle daha iyi olsa da, bir başparmak kuralı <= 4096 bayt boyutundaki arama tablolarına yapışmaktır. Üst sınır olarak: eğer arama tablonuz 64 K'dan büyükse, muhtemelen yeniden düşünmeye değer.

Bir tablo oluşturma

Bu yüzden küçük bir masa oluşturabileceğimizi anladık. Yapılacak sonraki şey yerinde bir arama fonksiyonu olsun. Arama işlevleri genellikle birkaç temel tam sayı işlemi kullanan küçük işlevlerdir (ve, veya xor, shift, add, remove ve belki de çoğalır). Girişinizi, arama fonksiyonunuz tarafından tablonuzda bir çeşit “benzersiz anahtar” a çevirmek istersiniz, ki o zaman basitçe size yapmak istediğiniz tüm işlerin cevabını verir.

Bu durumda:> = 128 değeri tutabileceğimiz anlamına gelir, <128 bundan kurtuluruz demektir. Bunu yapmanın en kolay yolu bir 'AND' kullanmaktır: eğer tutarsak, biz 7FFFFFFF ile birlikte çalışırız; ondan kurtulmak istiyorsak, biz de 0 ile birlikte oluruz. Dikkat edin ki 128 de 2'lik bir güçtür - böylece devam edebiliriz ve 32768/128 tamsayılarla dolu bir tablo yapabiliriz ve bir sıfırı ve bir sürü doldurarak doldurabiliriz. 7FFFFFFFF en.

Yönetilen diller

Bunun neden yönetilen dillerde iyi çalıştığını merak edebilirsiniz. Sonuçta, yönetilen diller dağınık olmadığından emin olmak için dizinin sınırlarını bir dalla kontrol eder ...

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

Yönetilen diller için bu şubenin kaldırılması konusunda oldukça fazla çalışma 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 koşulunun asla vurulmayacağı açıktır. En azından Microsoft JIT derleyicisi (ancak Java'nın benzer şeyler yaptığını tahmin ediyorum) bunu fark edecek ve çekleri tamamen kaldıracaktır. WOW - bu, şube olmadığı anlamına gelir. Benzer şekilde, diğer bariz vakalarla ilgilenecektir.

Yönetilen dillerdeki aramalarda sorun yaşarsanız, & 0x[something]FFFsınır kontrolünü öngörülebilir hale getirmek için arama fonksiyonunuza gidin ve daha hızlı ilerlemesini izleyin.

Bu davanın sonucu

// 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.Next(256);

//To keep the spirit of the code in-tact 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();

1160
2018-04-24 06:26



Şube prediktörünü atlatmak istiyorsun, neden? Bu bir optimizasyon. - Dustin Oprea
Hiçbir dal bir daldan daha iyi olmadığı için :-) Birçok durumda bu çok daha hızlıdır ... eğer optimizasyon yapıyorsanız, kesinlikle denemeye değer. Onlar da f.ex. graphics.stanford.edu/~seander/bithacks.html - atlaste
Genel arama tabloları hızlı olabilir, ancak bu özel durum için testleri yaptınız mı? Kodunuzda hala bir dal koşulu olacak, sadece şimdi tablo oluşturma kısmına taşındı. Hala mükemmel desteğini alamazsın. - Zain Rizvi
@Zain gerçekten bilmek istiyorsan ... Evet: şubem ile 15 saniye ve versiyonumla 10. Ne olursa olsun, her iki yolu bilmek için yararlı bir tekniktir. - atlaste
Neden olmasın sum += lookup[data[j]] nerede lookup 256 girişli bir dizidir, ilk olanlar sıfır ve son olanlar dizine eşittir? - Kris Vandermotten


Dizi sıralandığında, 0 ile 255 arasında veri dağıtıldığında, yinelemelerin ilk yarısı etrafa girmeyecektir. if-sürüm ( if ifadesi aşağıda paylaşılmıştır).

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

Soru şudur: Yukarıdaki ifadenin, belirli durumlarda, sıralı verilerde olduğu gibi yürütülmemesi nedir? İşte "şube tahmincisi" geliyor. Bir dal tahmincisi, bir dalı (ör. if-then-else Bu, kesin olarak bilinmeden önce yapacaktır. Şube belirleyicisinin amacı, talimat boru hattındaki akışı iyileştirmektir. Şube belirleyicileri, yüksek etkili performans elde etmek için kritik bir rol oynamaktadır!

Daha iyi anlamak için biraz işaretleme yapalım

Bir performans if-sipariş, durumunun öngörülebilir bir paterne sahip olup olmamasına bağlıdır. Durum her zaman doğru veya her zaman yanlışsa, işlemcideki dal tahmini mantığı deseni alır. Öte yandan, eğer model öngörülemezse, if-sipariş çok daha pahalı olacak.

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

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

İşte farklı gerçek-yanlış desenleri olan 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 “kötü”Doğru-yanlış desen yapabilir if-sayıdan altı kat daha yavaş “iyi" Desen! Tabii ki, hangi modelin iyi ve kötü olması, derleyicinin ve belirli işlemcinin oluşturduğu tam talimatlara bağlıdır.

Bu yüzden, şube tahmininin performans üzerindeki etkisinden şüphe yoktur!


1035
2018-02-15 07:24



"Rasgele" TF modelinin zamanlamasını göstermezsiniz. - Mooing Duck
@MooingDuck 'Çünkü bir fark yaratmayacak - bu değer bir şey olabilir, ama yine de bu eşiklerin sınırları içinde olacaktır. Peki, sınırları zaten bildiğinizde neden rastgele bir değer gösteriliyor? Her ne kadar tamlık adına bir tane gösterebileceğinizi ve “sadece bunun için” olduğunu kabul ediyorum. - cst1992
@ cst1992: Şu anda onun en yavaş zamanlaması benim gözüme göre oldukça öngörülebilir olan TTFFTTFFTTFF. Rastgele doğası gereği tahmin edilemez, bu yüzden hala daha yavaş ve böylece burada gösterilen sınırların dışında olabilir. OTOH, TTFFTTFF'nin patolojik duruma mükemmel bir şekilde vurması olabilir. Söyleyemem, çünkü o rasgele zamanlamalarını göstermedi. - Mooing Duck
@MooingDuck Bir insan gözüne "TTFFTTFFTTFF" öngörülebilir bir dizidir, fakat burada bahsettiğimiz şey bir işlemci içine yerleştirilmiş olan şube tahmincisinin davranışıdır. Şube belirleyicisi, AI seviyesinde model tanıma değildir; çok basit. Sadece dalları değiştirdiğinizde iyi tahmin etmez. Çoğu kodda, dallar neredeyse her zaman aynı şekilde gider; Bin kez yürüten bir döngü düşünün. Döngünün sonundaki dal, döngü başlangıcına geri döner 999 kez, ve daha sonra bininci kez farklı bir şey yapar. Çok basit bir şube tahmincisi genellikle iyi çalışır. - steveha
@steveha: Bence CPU şube tahmincisinin nasıl çalıştığı hakkında varsayımlarda bulunuyorsunuz ve bu metodolojiye katılmıyorum. Şube tahmincisinin ne kadar gelişmiş olduğunu bilmiyorum, ama bence sizden çok daha gelişmiş olduğunu düşünüyorum. Muhtemelen haklısınız, ama ölçümler kesinlikle iyi olur. - Mooing Duck


Şube tahmini hatalarından kaçınmanın bir yolu, bir arama tablosu oluşturmak ve verileri kullanarak indekslemektir. Stefan de Bruijn cevabında bunu tartıştı.

Fakat bu durumda, değerlerin [0, 255] aralığında olduğunu biliyoruz ve sadece değerlerle ilgileniyoruz.> = 128. Bu, bir değeri isteyip istemediğimizi söyleyeceğimiz tek bir biti kolayca çıkarabileceğimiz anlamına geliyor: Sağ 7 bit veri, biz bir 0 bit veya 1 bit ile bırakılır ve biz sadece 1 bit olduğunda değeri eklemek istiyorum. Buna "karar biti" diyelim.

Karar bitinin 0/1 değerini bir diziye indeks olarak kullanarak, verilerin sıralanıp sıralanmadığına veya eşitlenmediğine eşit derecede hızlı bir şekilde kod yazabiliriz. Kodumuz her zaman bir değer katacak, ancak karar biti 0 olduğunda, önemsemediğimiz bir yeri 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ı kaybeder, ancak hiçbir zaman bir dal tahmini hatası yoktur. Rastgele veriler üzerinde, gerçek bir if ifadesi olan versiyondan çok daha hızlıdır.

Ancak benim testlerimde, açık bir arama tablosu bundan biraz daha hızlıydı çünkü muhtemelen bir arama tablosuna indeksleme, bit kaymasından biraz daha hızlıydı. Bu, kodumun nasıl ayarlandığını ve arama tablosunu nasıl kullandığını gösterir (düşünülemez olarak adlandırılır) lut koddaki "LookUp Table" için). İş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 bayt oldu, bu yüzden bir önbellek güzel uyuyor ve tüm hızlıydı. Veriler 24 bitlik değerlerdeyse ve yarının sadece yarısını istediğimizde işe yaramazsa ... ... bu teknik işe yaramazdı. Öte yandan, yukarıda gösterilen iki tekniği birleştirebiliriz: önce bitleri kaydırın, sonra bir arama tablosunu indeksleyin. Yalnızca en üstteki yarım değeri istediğimiz 24 bitlik bir değer için, verileri 12 bitlik bir şekilde sağa kaydırabiliriz ve bir tablo dizini için 12 bitlik bir değer bırakabiliriz. 12 bitlik bir tablo dizini, pratik olabilecek bir 4096 değer tablosu içerir.

DÜZENLEME: Girmeyi unuttuğum bir şey.

Bir dizinin yerine dizinin dizini oluşturma tekniği if deyimi, hangi işaretçiyi kullanacağına karar vermek için kullanılabilir. İkili ağaçları uygulayan bir kütüphane gördüm ve iki tane işaretçi yerinepLeft ve pRight ya da her neyse) bir uzunluk-2 dizi işaretçiye sahipti ve hangisinin takip edileceğine karar vermek için "karar biti" tekniğini kullandı. Örneğin, yerine:

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

Bu kütüphane şöyle bir şey yapardı:

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

İşte bu kodun bir bağlantısı: Kırmızı Siyah Ağaçlar, Ebedi Şaşkın


963
2017-07-22 08:29



Doğru, sadece biti doğrudan kullanabilir ve çarpabilirsiniz (data[c]>>7 - Burada da bir yerde tartışılan); Bu çözümü bilerek bıraktım ama tabi ki haklısın. Sadece küçük bir not: Arama tabloları için başparmak kuralı, eğer 4KB'de (önbellekleme nedeniyle) uyuyorsa, işe yarar - tercihen tabloyu olabildiğince küçük hale getirin. Yönetilen diller için bunu 64KB'ye, C ++ ve C gibi düşük seviyeli diller için, muhtemelen yeniden düşünürdüm (bu sadece benim deneyimim). Dan beri typeof(int) = 4En fazla 10 bite yapışmayı denerdim. - atlaste
0/1 değeriyle indekslemenin muhtemelen bir tamsayıdan daha hızlı olacağını düşünüyorum, ancak eğer performans gerçekten çok kritikse, onu izlemelisiniz. Küçük arama tablolarının önbellek basıncından kaçınmak için şart olduğunu kabul ediyorum, ancak daha büyük bir önbelleğiniz varsa daha büyük bir önbellek tablosuna sahip olursanız, 4KB daha çok bir kuraldır. Bence demek istedin sizeof(int) == 4? Bu 32-bit için geçerli olurdu. İki yaşındaki cep telefonumun 32KB L1 önbelleği var, bu yüzden 4K bir arama tablosu bile işe yarayabilir, özellikle arama değerleri bir int yerine bir baytsa. - steveha
Muhtemelen bir şey eksik ama senin içinde j 0 veya 1 yöntemine eşittir, neden sadece değerinizi çarpmıyorsunuz? j dizi indekslemeyi kullanmak yerine eklemeden önce (muhtemelen 1-j ziyade j) - Richard Tingle
Çarpma daha hızlı olmalı, Intel kitaplarına bakmaya çalıştım ama bulamadım ... her iki durumda da kıyaslama bana bu sonucu verdi. - atlaste
@steveha P.S .: başka bir olası cevap olurdu int c = data[j]; sum += c & -(c >> 7); hiç çoğullama gerektirmez. - atlaste


Sıralanan durumda, başarılı şube tahminine ya da herhangi bir dalsız karşılaştırma numarasına güvenmekten daha iyisini yapabilirsiniz: dalı tamamen kaldırın.

Gerçekten, dizi ile bitişik bir bölgede bölümlendirilir data < 128 ve başka bir data >= 128. Yani bölme noktasını dikotomik bir arama ile bulmalısınız ( Lg(arraySize) = 15 Karşılaştırmalar), daha sonra bu noktadan düz bir birikim yapın.

Bir şey gibi (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];

ya da biraz daha gizlenmiş

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

Daha hızlı bir yaklaşım, yaklaşık hem sıralanmış hem de sıralanmamış için çözüm: sum= 3137536; (Gerçekten tekdüze bir dağılım varsayarsak, beklenen değeri 191.5 olan 16384 örnek) :-)


883
2017-07-24 07:57



sum= 3137536 - zekice. Belli ki bu sorunun konusu değil. Soru, şaşırtıcı performans özelliklerini açıklamakla ilgilidir. Yapmanın ilavesini söylemek zorundayım std::partition yerine std::sort değerlidir. Asıl soru, verilen sentetik ölçütten daha fazlasını kapsamasına rağmen. - sehe
@DeadMG: Bu, belirli bir anahtar için standart dikotomik arama değil, bölümleme endeksi için bir aramadır; Her iterasyonda tek bir karşılaştırmayı gerektirir. Ama bu koda güvenmeyin, kontrol etmedim. Garantili bir doğru uygulama ile ilgileniyorsanız, bana bildirin. - Yves Daoust


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

Şube tahminini anlamak için ilk önce anlamak gerekir Yönlendirme Hattı:

Herhangi bir komut, bir dizi sıraya bölünür, böylece farklı adımlar paralel olarak eşzamanlı olarak yürütülebilir. Bu teknik, talimat boru hattı olarak bilinir ve bu, modern işlemcilerdeki verimi artırmak için kullanılır. Bunu daha iyi anlamak için lütfen bunu gör Wikipedia'da örnek.

Genellikle modern işlemciler oldukça uzun boru hatlarını var, ama kolaylığı için tek bu 4 adımı düşünelim.

  1. IF - talimatı hafızadan getir   
  2. ID - Talimatın kodunu çöz   
  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önelim, aşağıdaki talimatları dikkate alalım:

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

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

İşlemci boru hattı EX sahneye kadar ulaşmaz talimat A kadar beklemek zorunda kalacak C talimat B veya talimat C gitmek için karar olarak, talimat B veya talimat yürütmek için boru hattı Yani talimat A. sonuçlarına bağlıdır böyle görünecek.

durum doğruysa geri döndüğünde: enter image description here

Durum yanlış döndüğünde: enter image description here

Talimat A'nın sonucunun beklenmesi sonucunda, yukarıdaki davada harcanan toplam CPU döngüleri (şube tahmini olmaksızın, hem doğru hem de yanlış için) 7'dir.

Peki şube tahmini nedir?

Şube yordayıcısı, bir şubenin (eğer başka bir yapının) hangi yoldan kesin olarak bilinmeyeceğ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 edecek ve bu talimatı inceleyecektir (örneğimizde B veya C).

Doğru tahminin yapılması durumunda, boru hattı böyle bir şeye benziyor: enter image description here

Daha sonra tahminin yanlış olduğu tespit edilirse, kısmen yürütülen talimatlar atılır ve boru hattı, gecikme meydana getiren doğru şube ile baştan başlar. Bir dalın yanlış tahmin edilmesi durumunda boşa harcanan zaman, getiri aşamasından yürütme aşamasına kadar boru hattındaki aşamaların sayısına eşittir. Modern mikroişlemciler oldukça uzun boru hatlarına sahip olma eğilimindedirler, böylece yanlış tahmin gecikmesi 10 ila 20 saat arasındadır. Boru hattı ne kadar uzun olursa, iyi bir ihtiyaç duyulur. şube tahmincisi.

OP'nin kodunda, koşullu ilk kez, şube tahmincisinin tahmini temel alan herhangi bir bilgisi yoktur, bu yüzden ilk kez bir sonraki talimatı rasgele seçecektir. Daha sonra for döngüsünde, tahmin tarihine dayanabilir. Artan sıraya göre sıralanmış bir dizi için üç olasılık vardır:

  1.  Tüm öğeler 128'den az
  2.  Tüm elemanlar 128'den büyük
  3.  Bazı yeni elemanlar 128'den küçük ve daha sonra 128'den büyük

Öngörücünün her zaman ilk daldaki gerçek dalı kabul edeceğini varsayalım.

Yani ilk durumda, tarihsel olarak tüm tahminleri doğru olduğu için, her zaman gerçek dalı alır. 2. durumda, başlangıçta yanlış tahmin eder, ancak birkaç kez yinelemeden sonra doğru olarak tahmin eder. Üçüncü durumda, elemanlar 128'den küçük olana kadar başlangıçta doğru olarak tahmin edilir. Daha sonra bir süre için başarısız olur ve tarihin dallanma tahmini başarısızlığını gördüğü zaman doğrudur.

Tüm bu durumlarda, başarısızlık sayı olarak çok daha az olacaktır ve sonuç olarak, yalnızca birkaç kez kısmi yürütme talimatlarını atmak ve doğru şube ile başlayıp daha az CPU döngüsüyle sonuçlanmak gerekecektir.

Ancak rastgele sıralanmamış bir dizi durumunda, tahminin kısmen yürütülen talimatları atması ve çoğu zaman doğru şube ile başlaması ve sıralı diziye kıyasla daha fazla CPU döngüsüne yol açması gerekecektir.


697
2017-07-03 15:35



iki talimat nasıl birlikte yürütülür? ayrı cpu çekirdekleriyle mi yoksa boru hattı talimatı tek cpu çekirdeğine mi entegre edilmiş? - M.kazem Akhgary
@ M.kazemAkhgary Hepsi bir mantıksal çekirdek içinde. İlgilenirseniz, bu örneğin Intel Yazılım Geliştirici Kılavuzu - Sergey.quixoticaxis.Ivanov


Resmi bir cevap

  1. Intel - Şube Yanlışlığı Maliyetinden Kaçınmak
  2. Intel - Yanlış Anlamaları Önlemek için Şube ve Döngü Yeniden Yapılandırma
  3. Bilimsel makaleler - şube tahmini bilgisayar mimarisi
  4. Kitaplar: J.L. Hennessy, D.A. Patterson: Bilgisayar mimarisi: sayısal bir yaklaşım
  5. Bilimsel yayınlardaki makaleler: T.Y. Yeh, Y.N. Patt, şube tahminlerinde çok şey yaptı.

Bu güzelden de görebilirsiniz. diyagram Şube belirleyicisinin neden kafası karışır?

2-bit state diagram

Orijinal koddaki her öğe rastgele bir değerdir

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

böylece tahminci tarafları std::rand() darbe.

Öte yandan, sıralama yapıldıktan sonra, öngörücü ilk olarak güçlü bir şekilde alınmamış bir duruma geçecektir ve değerler yüksek değere dönüştüğünde, kuvvetli bir şekilde alınmadan güçlü bir şekilde alınmaksızın değişimle üç koşucuda yordayıcı olacaktır.



612
2017-10-11 21:05