Burada bir parçaCkod çok tuhaf görünüyor. Bazı garip nedenle, verileri sıralama mucizevi bir şekilde kod neredeyse altı kat daha hızlı yapar.

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

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

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

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

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

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

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

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

• std::sort(data, data arraySize); kod çalışır olmadan11.54saniye.
• Sıralanmış veri, kod çalışır1.93saniye.

Başlangıçta, bu sadece bir dil veya derleyici anomali olabileceğini düşündüm. Bunu denedimJava.

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

İlk aklıma gelen sıralama önbelleğine veri getiriyor, ama bir sonraki düşüncem bu dizi sadece oluşturulan çünkü, nasıl oldu.

• Neler oluyor?
• Neden sıralanmış bir dizi hızlı sıralanmamış bir dizi daha mı?
• Kod bazı bağımsız hüküm özetle, sırası önemli değil.

branch prediction kurbanı başarısız.

Şube Tahmini nedir?

Bir demiryolu kavşağı göz önünde bulundurun:

Wikimedia Commons yoluyla Mecanismo Image,. CC-By-SA 3.0 Lisans altında kullanılır.

Şimdi tartışmanın iyiliği için, bu 1800 - uzun mesafe önce veya radyo iletişimi geri varsayalım.

Bir kavşak işletmecisi ve tren geliyor, duyuyorum. Gitmesi gereken hiçbir fikrim yok. Tren istiyor hangi kaptana sormak için durdurmak. Ve sonra anahtarı uygun şekilde ayarlayın.

Tren ağır ve atalet var. Sonsuza kadar başlatmak ve yavaşlatmak için kullanıyorlar.

Daha iyi bir yolu var mı? Trende gidecek olan Sen tahmin et!

• Eğer doğru tahmin ederseniz, o devam ediyor.
• Eğer yanlış tahmin ederseniz, kaptan dur, geri git ve anahtarı çevirmek gibi bağırıp çağıracak. Diğer yolu yeniden aşağı çekebilir.

Her seferinde doğru tahmin ederseniztreni durdurmak asla.
Çok sık yanlış tahmin ederseniztren çok zaman durdurma, yedekleme ve yeniden geçireceksiniz.

Eğer açıklama: bir düşününİşlemci seviyesinde, şube talimatı:

Bir işlemci ve bir şube görüyorsunuz. Gidecek hiçbir fikrim yok. Sen ne yapıyorsun? Sen yürütme durdurmak ve önceki talimatları tamamlanana kadar bekleyin. Sonra aşağı doğru yola devam.

Modern işlemciler karmaşık ve uzun boru hattı var. Sonsuza dek sürer bu yüzden "yukarı" ve "aşağı". yavaş sıcak

Daha iyi bir yolu var mı? Şubeye gidecek sen tahmin et!

• Eğer doğru tahmin ederseniz, yürütme devam.
• Eğer yanlış tahmin ederseniz, boru hattı temizleme ve şubeye geri. O zaman diğer yolu yeniden başlatın.

Her seferinde doğru tahmin edersenizbu idamı durdurmak asla.
Çok sık yanlış tahmin edersenizçok zaman oyalama , geri dönme ve yeniden geçiriyorsun.

Bu dal tahmini. Tren bayraklı yönünde sinyal olabilir çünkü en iyi benzetme değil kabul ediyorum. Ama bilgisayarlar, işlemci şube son ana kadar gideceğini bilmiyor.

Nasıl stratejik bir tren yedeklemek gerekir sayısını en aza indirmek ve başka bir yoldan gitmek sanırım misin? Geçmiş tarihine bak! Eğer tren 99% sol giderse, o halde sanırım. Alternatifler varsa, o zaman tahmin alternatif. Varsa bir yolu, her 3 kez giderse, aynı sen .

Diğer bir deyişle, bir model belirlemek ve takip etmek deneyin.Bu şube belirleyicileri çalışmak nasıl daha fazla veya daha az.

Çoğu uygulama terbiyeli şubeleri var. Modern şube belirleyicileri genellikle ^ elde edecek . 90% oranları çarptı. Ama hiçbir tanınabilir desenleri ile öngörülemeyen dalları ile karşılaşınca, şube belirleyicileri neredeyse işe yaramaz.

Daha fazla okuma: "Branch predictor" article on Wikipedia.

Yukarıda ima gibi, suçlu bu-açıklama:

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

Verileri 0 ile 255 arasında eşit olarak dağıtılır dikkat edin. Veriler sıralandığında, tekrarlamalar kabaca ilk yarısı-deyimi girin. Bundan sonra, eğer deyimi girin.

Bu şube bu yana şube tahmini için çok samimi arka arkaya aynı yöne giden pek çok kez. Hatta basit doyurarak bir karşı yöne geçer sonra doğru birkaç yineleme hariç dalını tahmin etmek olacaktır.

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)

Veriler tamamen rasgele ise, şube tahmini rastgele veri tahmin edemez çünkü işe yaramaz hale gelir. Böylece muhtemelen 50% misprediction civarında olacak. (rasgele tahmin daha iyi)

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)

Ne yapılabilir?

Eğer derleyici koşullu bir hareket içine şube optimize etmek mümkün değil ama, eğer performans için okunabilirliği feda etmeye istekli olup olmadığını bazı kesmek 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ı bit düzey işlemleri ile değiştirir.

(Bu hack orijinal kesinlikle eşdeğer eğer deyim değildir. Ama bu durumda,*. *17) tüm giriş değerleri için geçerli değil

Kriterler: @ 3.5 GHz Core i7 920

C - Visual Studio 2010 - x 64 Sürümü

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java - 7 - 64 Eclipse 7.1.1 ile İLGİLENİYORUZ

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

Gözlemler:

• Şube:Sıralanmış ve sıralanmamış veri arasında büyük bir fark vardır.
• Hack: ileSıralanmış ve sıralanmamış veri arasında fark yoktur.
• C durumunda, hack aslında verileri sıralama yaparken bir tad şube ile daha yavaştır.

Başparmak genel bir kural veri-bağımlı kritik döngüler dallanma kaçınmaktır. (bu örnekte olduğu gibi)

Güncelleme :

• -O3 veya x 64 -ftree-vectorize ile GCC 4.6.1 koşullu bir hareket oluşturmak mümkün değildir. Sıralanmış ve sıralanmamış veri hem hızlı arasında bir fark yok.

• VC 2010 bile /Ox altında bu şube için Koşullu hareket oluşturulamadı.

• Intel Derleyici 11 mucizevi bir şey yok. 28**, böylece dış döngü için öngörülemeyen şube kaldırma. Sadece mispredictions bağışıklık, VC ve GCC üretebilir ne de iki kat daha hızlı olarak. Diğer bir deyişle, ICC test-döngü avantaj kriter yenilgi aldı...

• Eğer Intel Derleyici şubesiz kodu verirsen,-vectorizes... ve şube ile kadar hızlı (döngü değişimi ile).

Bu bile olgun modern Derleyiciler çılgınca değişebilir olduğunu göstermek için kodu optimize etmek için yeteneklerini gidecek