En hızlı tamsayı bölme sıfıra bölme sonucu ne olursa olsun desteklemek nedir?

SORU

27 Mayıs 2013, PAZARTESİ

En hızlı tamsayı bölme sıfıra bölme sonucu ne olursa olsun desteklemek nedir?

Özet:

Hesaplamak için en hızlı yol arıyorum

(int) x / (int) y

y==0 için bir istisna olmadan. Bunun yerine sadece rastgele bir sonuç istiyorum.

Arka plan:

Görüntü işleme algoritmaları kodlama yaparken sık sık (birikmiş) bir alfa değeri tarafından bölmek gerekir. En basit değişken C kodu tamsayı aritmetiği ile düz. Benim sorunum genellikle alpha==0 ile sonuç piksel için sıfır hata ile bir bölüm olsun. Bu sonuçtan hiç önemi yok nerede tam olarak piksel ancak: piksellerin renk değerleri alpha==0 ile. umurumda değil

Ayrıntılar:

Gibi bir şey arıyorum:

result = (y==0)? 0 : x/y;

result = x / MAX( y, 1 );

x ve y pozitif tamsayılar. Kod bir şekilde koşullu dallanma kurtulmak için arıyorum o kadar iç içe geçmiş bir döngü süreleri Çok sayıda yürütüldü.

Y bayt aralığı aşıyor, çözüm memnunum

unsigned char kill_zero_table[256] = { 1, 1, 2, 3, 4, 5, 6, 7, [...] 255 };
[...]
result = x / kill_zero_table[y];

Ama bu tabii ki de daha büyük aralıkları için çalışmıyor.

Son soru sanırım en hızlı bit öldürmek diğer tüm değerler değişmeden bırakarak başka bir tamsayı değeri 0 ile değiştirme hack, Nedir?

Açıklamalar

Dallanma çok pahalı olduğundan 0 emin değilim. Ancak farklı Derleyiciler kullanılır, küçük iyileştirmeler ile gerçekten şüpheli olan) kıyaslama tercih ederim.

Elbette, Compiler büyük gelince bit öldürmek, ama yapamam express "umurumda değil" sonuç olarak C, derleyici asla kullanabilir tam kapsamlı iyileştirmeleri.

Kod C uyumlu, ana platformlar gcc & çınlama ve MacOS ile Linux 64 Bit tam olmalıdır.

CEVAP

27 Mayıs 2013, PAZARTESİ

Bazı yorumlar esinlenerek benim Pentium ve gcc derleyici kullanarak şube kurtuldum

int f (int x, int y)
{
        y  = y == 0;
        return x/y;
}

Derleyici temelde ayrıca test koşulu bir bayrak kullanabilirsiniz tanır.

Kurul isteği:

.globl f
    .type   f, @function
f:
    pushl   �p
    xorl    �x, �x
    movl    %esp, �p
    movl    12(�p), �x
    testl   �x, �x
    sete    %al
    addl    �x, �x
    movl    8(�p), �x
    movl    �x, �x
    popl    �p
    movl    �x, �x
    sarl    $31, �x
    idivl   �x
    ret

Bu gibi popüler bir soru ve cevap oldu, ayrıntılı edeceğim biraz daha. Yukarıdaki örnekte derleyici tanıdığı deyim programlama dayanır. Yukarıdaki durumda boolean bir ifade ayrılmaz aritmetik kullanılır ve koşul bayraklarını, bu amaçla donanım icat. Genel durum bayrakları deyim kullanarak C ile sadece erişilebilir. O kadar sert (satır içi) montaj başvurmaksızın C taşınabilir çok hassas tamsayı bir kütüphane yapmak için neden olur. Benim tahminim en iyi Derleyiciler yukarıdaki deyim anlamayacak.

Ayrıca yukarıdaki yorumların bazılarının söylediği gibi dalları kaçınmanın bir başka yolu, tahmin yürütme. Ben bu nedenle philipp ilk Kodu ve Şifremi aldı ve ARM derleyici ve esas yürütme özellikleri olan ARM mimarisi için GCC derleyici ve inceledim. Her iki Derleyiciler kod iki örnekte de şube kaçının

ARM derleyici ile Philipp versiyonu:

f PROC
        CMP      r1,#0
        BNE      __aeabi_idivmod
        MOVEQ    r0,#0
        BX       lr

GCC ile Philipp versiyonu:

f:
        subs    r3, r1, #0
        str     lr, [sp, #-4]!
        moveq   r0, r3
        ldreq   pc, [sp], #4
        bl      __divsi3
        ldr     pc, [sp], #4

ARM derleyici ile benim kod:

f PROC
        RSBS     r2,r1,#1
        MOVCC    r2,#0
        ADD      r1,r1,r2
        B        __aeabi_idivmod

GCC ile benim kod:

f:
        str     lr, [sp, #-4]!
        cmp     r1, #0
        addeq   r1, r1, #1
        bl      __divsi3
        ldr     pc, [sp], #4

Tüm sürümleri hala KOLU bu sürümü bir bölümü için donanım yok ama y == 0 test için tamamen tahmin yürütme yoluyla uygulanır, çünkü bölünme için bir şube rutin gerekir.

Bunu Paylaş: