Neden sıralı bir diziyi işlemek, sıralanmamış bir diziyi işlemekten daha hızlıdır?
Yazılım Neden Yavaş Çalışır? Basit bir örnek ile anlatalım
İşte çok tuhaf davranışlar gösteren bir C ++ kodu parçası. Garip bir nedenden dolayı, verileri mucizevi bir şekilde sıralamak, kodu neredeyse altı kat daha hızlı hale getirir:
#include
#include
#include
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(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
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 anormalliği 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 sonuçları JAVA ile de almış bulundum.
İlk düşüncem, sıralamanın verileri önbelleğe getirmesiydi , ama sonra bunun ne kadar yanlış olduğunu düşündüm çünkü dizi yeni oluşturulmuştu.
- Ne oluyor?
- Neden sıralı bir diziyi işlemek, sıralanmamış bir diziyi işlemekten daha hızlıdır?
Kod bazı bağımsız terimleri özetliyor, bu nedenle sıra önemli olmamalı.
Sonuç;
Bir demiryolu kavşağını düşünün:
Şimdi tartışmanın, 1800’lü yıllara geri döndüğünü varsayalım – uzun mesafe veya radyo iletişiminden önce.
Bir kavşağın operatörüsünüz ve bir trenin geldiğini duyarsınız. Hangi yöne gitmesi gerektiğine dair hiçbir fikrin yok. Sürücüye hangi yöne gitmek istediklerini sormak için treni durduruyorsunuz. Ve sonra anahtarı uygun şekilde ayarlarsınız.
Trenler ağırdır ve çok fazla ataleti vardır. Bu yüzden başlaması ve yavaşlaması sonsuza kadar sürer.
Daha iyi bir yol var mı? Trenin hangi yöne gideceğini tahmin edin!
- Doğru tahmin ettiyseniz, devam ediyor.
- Yanlış tahmin ettiyseniz, kaptan duracak, geri dönecek ve düğmeyi çevirmeniz için size bağıracak. Ardından diğer yolu yeniden başlatabilir.
Her seferinde doğru tahmin ederseniz , tren asla durmak zorunda kalmayacak.
Çok sık yanlış tahmin ederseniz , tren durmak, yedeklemek ve yeniden başlatmak için çok zaman harcayacaktır.
Bir if ifadesini düşünün: İşlemci düzeyinde, bu bir dal talimattır:
Sen bir işlemcisin ve bir dal görüyorsun. Hangi yöne gideceğine dair hiçbir fikrin yok. Ne yaparsın? Yürütmeyi durdurur ve önceki talimatlar tamamlanana kadar beklersiniz. Sonra doğru yola devam edersiniz.
Modern işlemciler karmaşıktır ve uzun boru hatlarına sahiptir. Bu yüzden “ısınmaları” ve “yavaşlamaları” sonsuza kadar sürer.
Daha iyi bir yol var mı? Dalın hangi yöne gideceğini tahmin edin!
- Doğru tahmin ettiyseniz, uygulamaya devam edersiniz.
- Yanlış tahmin ettiyseniz, boru hattını yıkamanız ve şubeye geri dönmeniz gerekir. Ardından diğer yolu yeniden başlatabilirsiniz.
Her seferinde doğru tahmin ederseniz , infazın asla durması gerekmeyecek.
Çok sık yanlış tahmin ederseniz , çok fazla zaman harcarsınız, oyalanıp geri çekilirsiniz ve yeniden başlarsınız.
Bu şube tahminidir. Tren sadece bir bayrakla yönü işaret edebildiği için bunun en iyi benzetme olmadığını kabul ediyorum. Ancak bilgisayarlarda işlemci son ana kadar bir şubenin hangi yöne gideceğini bilemez.
Öyleyse, trenin yedeklenmesi ve diğer yola inmesi gereken zamanı en aza indirmek için stratejik olarak nasıl tahmin edersiniz? Geçmişe bakıyorsun! Tren zamanın% 99’unu terk ederse, sanırım sola. Değişirse, tahminlerinizi değiştirirsiniz. Her üç seferde bir yöne giderse, aynı tahmin edersiniz …
Başka bir deyişle, bir model belirlemeye ve onu takip etmeye çalışırsınız. Bu, aşağı yukarı şube tahmincilerinin nasıl çalıştığıdır.
Çoğu uygulamanın iyi huylu dalları vardır. Dolayısıyla, modern şube tahmincileri tipik olarak>% 90 isabet oranlarına ulaşacaktır. Ancak, tanınabilir örüntüleri olmayan, öngörülemeyen dallarla karşılaşıldığında, dal belirleyicileri neredeyse işe yaramaz.
Daha fazla bilgi için: Wikipedia’daki “Dal belirleyici” makalesi .
Yukarıdan ima edildiği gibi, suçlu bu if-ifadesidir:
if (data[c] >= 128)
sum += data[c];
Verilerin 0 ile 255 arasında eşit olarak dağıtıldığına dikkat edin. Veriler sıralandığında, iterasyonların kabaca ilk yarısı if ifadesine girmeyecektir. Bundan sonra, hepsi if ifadesini girecekler.
Şube arka arkaya birçok kez aynı yöne gittiği için bu, şube tahmincisi için çok dostudur. Basit bir doygunluk sayacı bile, yön değiştirdikten sonraki birkaç yineleme dışında 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, dal tahmincisi, rastgele verileri tahmin edemediği için işe yaramaz hale gelir. Bu nedenle muhtemelen% 50 civarında yanlış tahmin olacaktır (rastgele tahmin etmekten daha iyi değildir).
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 istekliysen bazı hack’leri deneyebilirsin.
Değiştirin:
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 hackin, orijinal if-ifadesiyle tam olarak eşdeğer olmadığını unutmayın. Ancak 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:
- Dal ile: Sıralanmış ve sıralanmamış veriler arasında çok büyük bir fark vardır.
- Hack ile: Sıralanmış ve sıralanmamış veriler arasında hiçbir fark yoktur.
- C ++ durumunda, veri sıralandığında kesmek aslında daldan biraz daha yavaştır.
Genel bir pratik kural, kritik döngülerde (bu örnekte olduğu gibi) verilere bağlı dallanmadan kaçınmaktır.
Güncelleme:
- X64 ile
-O3veya-ftree-vectorizex64 üzerinde GCC 4.6.1 koşullu bir hareket oluşturabilir. Dolayısıyla, sıralı ve sıralanmamış veriler arasında hiçbir fark yoktur – her ikisi de hızlıdır.(Ya da biraz hızlı: önceden sıralanmış durum için,cmovözellikle GCC onu sadece 2 döngü gecikmesine sahipaddBroadwell’den önce Intel’de kritik yola koyarsa daha yavaş olabilircmov: gcc optimizasyon bayrağı -O3 kodu -O2’den daha yavaş hale getirir ) - VC ++ 2010, bu dal için koşullu hareketler oluşturamaz
/Ox. - Intel C ++ Compiler (ICC) 11 mucizevi bir şey yapar. Bu iki döngü alışverişini sağlar , böylece dış döngüye öngörülemeyen dalı kaldırma. Dolayısıyla, yalnızca yanlış tahminlere karşı bağışıklığı değil, aynı zamanda VC ++ ve GCC’nin üretebileceğinden iki kat daha hızlıdır! Başka bir deyişle, ICC, ölçütü yenmek için test döngüsünden yararlandı …
- Intel derleyicisine dalsız kodu verirseniz, onu sağ dışı vektörleştirir … ve dalda olduğu kadar hızlıdır (döngü değişimi ile).
Bu, olgun modern derleyicilerin bile kodu optimize etme yeteneklerinde çılgınca değişiklik gösterebileceğini gösteriyor