Soru GCC neden bir * a * a * a * a * a'yı (a * a * a) * (a * a * a) olarak optimize etmiyor?


Bilimsel bir uygulamada sayısal optimizasyon yapıyorum. Fark ettiğim bir şey GCC'nin aramayı optimize edeceğidir. pow(a,2) onu derleyerek a*aama çağrı pow(a,6) optimize edilmez ve aslında kütüphane işlevini çağırır powperformansı büyük ölçüde yavaşlatır. (Tersine, Intel C ++ Derleyici, çalıştırılabilir icc, kütüphane çağrısını kaldıracak pow(a,6).)

Merak ettiğim şey, değiştirdiğimde pow(a,6) ile a*a*a*a*a*a GCC 4.5.1 ve seçeneklerinin kullanılması "-O3 -lm -funroll-loops -msse4", kullanır 5 mulsd Talimatlar:

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13

yazarsak (a*a*a)*(a*a*a)üretecek

movapd  %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm14, %xmm13
mulsd   %xmm13, %xmm13

Çarpma talimatlarının sayısını 3'e düşürür. icc benzer davranışa sahiptir.

Derleyiciler neden bu optimizasyon numarasını tanımıyor?


1965
2018-06-21 18:49


Menşei


"Tanıma gücü (a, 6)" ne anlama geliyor? - Varun Madiath
Um ... bunu biliyorsunbirbirbirbira ve (abira) * (aa * a) kayan noktalı sayılarla aynı değildir, değil mi? Bunun için -funsafe-math veya -ffast-math ya da bunun için bir şey kullanmanız gerekecek. - Damon
David Goldberg'in "Her Bilgisayar Bilimcinin Kayan Nokta Aritmetiği Hakkında Bilmesi Gereken" adlı kitabını okumanızı öneririm: download.oracle.com/docs/cd/E19957-01/806-3568/... Daha sonra içine girdiğiniz katran çukurunun daha kapsamlı bir anlayışına sahip olacaksınız! - Phil Armstrong
Mükemmel bir mantıklı soru. 20 yıl önce aynı genel soruyu sordum ve bu tek darboğazın ezilmesiyle, Monte Carlo simülasyonunun yürütme süresini 21 saatten 7 saate düşürdü. İç döngüdeki kod, süreçte 13 trilyon kez yürütüldü, ancak simülasyonu bir gece penceresine aldı. (aşağıdaki cevaba bakınız)
Belki atmak (a*a)*(a*a)*(a*a) karışıma da. Aynı sayıda çarpma, ama muhtemelen daha doğru. - Rok Kralj


Cevaplar:


Çünkü Kayan Nokta Matematik İlişkili Değildir. İşlenenleri kayan nokta çarpımında gruplama şekliniz, cevabın sayısal doğruluğu üzerinde bir etkiye sahiptir.

Sonuç olarak, çoğu derleyici, yanıtın aynı kalacağından emin olmadıkça veya sayısal doğruluğu önemsemediğiniz sürece, kayan nokta hesaplamalarını yeniden düzenlemek konusunda oldukça muhafazakardır. Örneğin: -fassociative-math seçenek gcc'nin kayan nokta işlemlerini yeniden kurmasına izin verir, hatta -ffast-math Hıza karşı daha hassas agresiflik avantajlarına izin veren seçenek.


2567
2018-06-22 15:32



Evet. -Fast-math ile böyle bir optimizasyon yapıyor. İyi bir fikir! Ancak, kodumuz hızdan daha fazla doğrulukla ilgiliyse, geçmemesi daha iyi olabilir. - xis
IIRC C99, derleyicinin böyle "güvenli olmayan" FP optimizasyonlarını yapmasına izin verir, fakat GCC (x87'den başka herhangi bir şeyde) IEEE 754'ü takip etmek için makul bir girişimde bulunur - bu "hata sınırları" değildir; tek doğru cevap var. - tc.
Uygulama detayları pow ne burada ne de orada; bu cevap bile referans değil pow. - Stephen Canon
@nedR: ICC, yeniden ilişkilendirmeye izin verme varsayılanıdır. Standart uyumlu davranış almak istiyorsanız, ayarlamalısınız -fp-model precise ICC ile. clang ve gcc sıkı uyumluluk için varsayılan değer. Yeniden ilişkilendirme. - Stephen Canon
@xis, bu gerçekten değil -fassociative-math inaccurrate olurdu; sadece o a*a*a*a*a*a ve (a*a*a)*(a*a*a) farklıdır. Doğruluk ile ilgili değil; standartlara uygunluk ve kesinlikle tekrarlanabilir sonuçlar, ör. herhangi bir derleyicide aynı sonuçlar. Kayan nokta sayıları zaten kesin değil. Derlemek için nadiren uygunsuz -fassociative-math. - Paul Draper


Lambdageek doğru bir şekilde işaret eder çünkü ilişkilendirme kayan nokta sayıları için "optimizasyon" durmaz. a*a*a*a*a*a için (a*a*a)*(a*a*a) değeri değiştirebilir. Bu nedenle C99 tarafından izin verilmemektedir (kullanıcı tarafından özellikle derleyici bayrağı veya pragma ile izin verilmedikçe). Genel olarak, varsayım, programcının bir nedenden ötürü yaptığı şeyi yazması ve derleyicinin buna saygı göstermesidir. Eğer istersen (a*a*a)*(a*a*a)yaz bunu.

Bu olsa yazmak için bir acı olabilir; derleyici neden kullandığınız doğru şeyi yapmıyor? pow(a,6)? Çünkü o olurdu yanlış yapılacak şey. İyi bir matematik kütüphanesi olan bir platformda, pow(a,6) önemli ölçüde daha doğrudur a*a*a*a*a*a veya (a*a*a)*(a*a*a). Sadece bazı veriler sağlamak için, Mac Pro'mda küçük bir denemeyi yaptım ve [1 2] arasındaki tüm tek duyarlıklı kayan sayıların bir ^ 6'sını değerlendirirken en kötü hatayı ölçtüm:

worst relative error using    powf(a, 6.f): 5.96e-08
worst relative error using (a*a*a)*(a*a*a): 2.94e-07
worst relative error using     a*a*a*a*a*a: 2.58e-07

kullanma pow Bir çarpma ağacı yerine, bir 4 faktör. Derleyiciler, kullanıcı tarafından yetkilendirilmedikçe (örneğin, üzerinden) hata yapmayan "optimizasyon" yapmamalı (ve genellikle yapmamalıdır). -ffast-math).

GCC'nin sağladığını unutmayın __builtin_powi(x,n) alternatif olarak pow( )satır içi çoğaltma ağacı oluşturmalıdır. Performans için doğrulukla ticaret yapmak istiyorsanız, ancak hızlı-matematiği etkinleştirmek istemiyorsanız kullanın.


614
2018-06-22 22:39



Ayrıca Visual C ++ 'in' geliştirilmiş 'pow () sürümünü sağladığını unutmayın. Arayarak _set_SSE2_enable(<flag>) ile flag=1Mümkünse SSE2 kullanacaktır. Bu, hassasiyeti biraz azaltır, ancak hızları artırır (bazı durumlarda). MSDN: _set_SSE2_enable () ve pow () - TkTech
@TkTech: İndirgenmiş herhangi bir doğruluk, Microsoft'un uygulanmasından kaynaklanır, kullanılan kayıtların büyüklüğü değil. Bir teslim etmek mümkündür doğru yuvarlatılmış  pow Kütüphane yazarı çok motive ise, sadece 32-bit registerlar kullanarak. SSE tabanlı pow uygulamalar Daha x87 tabanlı uygulamaların çoğundan daha doğrudur ve ayrıca hız için bir miktar doğrulukla ticaret yapan uygulamalar da vardır. - Stephen Canon
@TkTech: Tabii ki, doğruluktaki azalmanın, SSE'nin kullanımı için değil, kütüphane yazarları tarafından yapılan seçimlerden kaynaklandığını açıkça belirtmek istedim. - Stephen Canon
Göreceli hataları hesaplamak için "altın standart" olarak ne kullandığınızı bilmek istiyorum - normalde beklerdim a*a*a*a*a*aama görünüşe göre durum böyle değil! :) - j_random_hacker
@j_random_hacker: tek duyarlıklı sonuçları karşılaştırdığım için, çift duyarlık bir altın standart için yeterlidir -birbirbirbirçifte hesaplanan bir hesaplama * büyük ölçüde Tek duyarlıklı hesaplamaların herhangi birinden daha küçük hata. - Stephen Canon


Bir başka benzer durum: çoğu derleyici optimize olmaz a + b + c + d için (a + b) + (c + d) (Bu, ikinci ifade, daha iyi bir şekilde pipele edilebildiğinden beri bir optimizasyondur) ve verilen değeri (örn. (((a + b) + c) + d)). Bu da köşe davaları yüzünden:

float a = 1e35, b = 1e-5, c = -1e35, d = 1e-5;
printf("%e %e\n", a + b + c + d, (a + b) + (c + d));

Bu çıkışlar 1.000000e-05 0.000000e+00


152
2018-06-23 11:44



Bu tam olarak aynı değil. Çoğaltımların / bölümlerin sırasını değiştirme (bölünme 0 ile hariç), toplam / çıkarma işleminin değişim sırasından daha güvenlidir. Benim düşünceme göre derleyici mults./divs'i ilişkilendirmeye çalışmalı. çünkü bu, toplam operasyon sayısını azaltır ve performans kazancının yanında hassas bir kazanç da sağlar. - GameDeveloper
@DarioOO: Bu daha güvenli değil. Çarpma ve bölme, üsün eklenmesi ve çıkarılması ile aynıdır ve siparişin değiştirilmesi, geçici konumların üssün olası aralığını aşmasına neden olabilir. (Tam olarak aynı değil, çünkü üs, hassaslık kaybına uğramaz ... ama temsil hala oldukça sınırlıdır ve yeniden sıralama, temsil edilemez değerlere yol açabilir) - Ben Voigt
Calculus arka planında eksik olduğunu düşünüyorum. Çoğaltma ve 2 sayı bölme aynı miktarda hata verir. Çıkarma / ekleme 2 rakamları özellikle 2 rakamı farklı büyüklük sırasına göre daha büyük bir hata verebilir, dolayısıyla son hatada küçük bir değişiklik getirdiğinden alt / add'ten daha güvenli yeniden düzenlemeler yapar. - GameDeveloper
@DarioOO: risk, mul / div ile farklıdır: Yeniden sıralama, ya son sonuçta önemsiz bir değişiklik yapar, ya da üs, bir noktada (daha önce olmadığı gibi) taşar ve sonuç büyük ölçüde farklıdır (potansiyel olarak + inf ya da 0). - Peter Cordes


Fortran (bilimsel hesaplama için tasarlanmış), yerleşik bir güç operatörüne sahiptir ve bildiğim kadarıyla Fortran derleyicileri, tam olarak tanımladığınızla aynı şekilde tamsayı güçlerine yükseltmeyi en iyi şekilde kullanacaktır. C / C ++ maalesef bir güç operatörüne sahip değil, sadece kütüphane işlevi pow(). Bu, akıllı derleyicilerin işlenmesini engellemez pow Özel durumlar için özel olarak ve daha hızlı bir şekilde hesaplamak, ancak daha az sıklıkta yaptıkları görünüyor ...

Birkaç yıl önce, tamsayı güçlerini en uygun şekilde hesaplamayı daha uygun hale getirmeye çalışıyordum ve aşağıdakileri buldum. C ++, C değil, yine de derleyicinin, bir şeyleri nasıl optimize edeceğine / inline edeceğine dair biraz zeki olmasına bağlı. Her neyse, umarım pratikte faydalı bulabilirsin:

template<unsigned N> struct power_impl;

template<unsigned N> struct power_impl {
    template<typename T>
    static T calc(const T &x) {
        if (N%2 == 0)
            return power_impl<N/2>::calc(x*x);
        else if (N%3 == 0)
            return power_impl<N/3>::calc(x*x*x);
        return power_impl<N-1>::calc(x)*x;
    }
};

template<> struct power_impl<0> {
    template<typename T>
    static T calc(const T &) { return 1; }
};

template<unsigned N, typename T>
inline T power(const T &x) {
    return power_impl<N>::calc(x);
}

Meraklı için açıklama: Bu, güçleri hesaplamanın en iyi yolunu bulamaz, ancak En uygun çözümü bulmak NP-complete problemidir ve bu sadece küçük güçler için yapmaya değer. pow), detaylarla uğraşmak için bir sebep yok.

Sonra sadece olarak kullanın power<6>(a).

Bu, güçleri yazmayı kolaylaştırır (hecelemeye gerek yok 6 aparens ile s), ve bu tür bir optimizasyon olmadan -ffast-math gibi hassas bir şeye sahip olmanız durumunda telafi toplamı (operasyon sırasının gerekli olduğu bir örnek).

Muhtemelen bu C ++ olduğunu ve sadece C programında (eğer bir C ++ derleyicisi ile derlerse) olduğunu da unutabilirsiniz.

Umarım bu yararlı olabilir.

DÜZENLE:

Derleyicimden aldığım şey bu:

İçin a*a*a*a*a*a,

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0

İçin (a*a*a)*(a*a*a),

    movapd  %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm1, %xmm0
    mulsd   %xmm0, %xmm0

İçin power<6>(a),

    mulsd   %xmm0, %xmm0
    movapd  %xmm0, %xmm1
    mulsd   %xmm0, %xmm1
    mulsd   %xmm0, %xmm1

74
2018-06-23 10:07



En uygun güç ağacını bulmak zor olabilir, ancak sadece küçük güçler için ilginç olduğu için, bariz cevap bir kez önceden (Knuth 100'e kadar bir tablo sağlar) ve bu sabit kodlu tabloyu kullanmaktır (gcc dahili olarak powi için) . - Marc Glisse
Modern işlemcilerde hız, gecikme ile sınırlıdır. Örneğin, bir çarpmanın sonucu beş döngüden sonra kullanılabilir. Bu durumda, biraz güç yaratmanın en hızlı yolunu bulmak daha zor olabilir. - gnasher729
Göreceli yuvarlama hatası için en düşük üst sınırı veren güç ağacını veya en düşük ortalama göreli yuvarlama hatasını da deneyebilirsiniz. - gnasher729
Destek, bunun için, örneğin, artırmak :: matematik :: pow <6> (n); Hatta ortak faktörleri çıkararak çoğaltma sayısını azaltmaya çalışıyorum. - gast128
İyi fikir ! Bunu zaten faktoriyel ön hesaplamalar için yaptım. - Caduchon


Çünkü 32 bit kayan nokta sayısı - 1.024 gibi - 1.024 değil. Bir bilgisayarda, 1.024 bir aralıktır: (1.024-e) ila (1.024 + e) ​​arasında, "e" bir hatayı temsil eder. Bazı insanlar bunu fark edemez ve aynı zamanda * a'da *, sayılara eklenmiş herhangi bir hata olmaksızın keyfi-hassas sayıların çarpımı anlamına gelir. Bazı insanların bunu gerçekleştirememesinin nedeni belki de ilkokullarda kullandıkları matematik hesaplamalarıdır: sadece hatasız ve hatasız sayılarla çalışmak ve çarpma yaparken “e” yi göz ardı etmenin doğru olduğuna inanmak. "Float a = 1.2", "a * a * a" ve benzeri C kodlarında "e" yi görmezler.

Programcıların çoğunluğu, C ifadesinin bir * a * a * a * a * a * a'nın gerçekten ideal sayılarla çalışmadığı fikrini fark etmesi (ve üzerinde çalışabilmesi) durumunda, GCC derleyicisinin “a * a'yı optimize etmek için ÜCRETSİZ olacaktır. * a * a * a * a "derken" t = (a * a); t * t * t "daha az sayıda çarpma gerektirir. Ama ne yazık ki, GCC derleyicisi, programcı kod yazarak "a" bir hata olsun veya olmasın bir sayı olduğunu düşünmez. Ve böylece GCC sadece kaynak kodun neye benzediğini yapacak - çünkü GCC'nin "çıplak gözü" ile gördüğü şey budur.

... bir kere ne tür bir programcı olduğunu biliyorsunuz sen GCC'ye "Hey, GCC, ne yaptığımı biliyorum!" diye anlatmak için "-sast-matematik" anahtarını kullanabilirsiniz. Bu, GCC'nin bir * a * a * a * a * a'yı farklı bir metin parçasına dönüştürmesine izin verir - bir * a * a * a * a * a'dan farklı görünür, ancak yine de hata aralığı içinde bir sayı hesaplar. a * a * a * a * a * a. Bu tamam, çünkü aralıklarla çalıştığınızı zaten biliyorsunuz, ideal sayılar değil.


49
2018-03-29 06:51



Kayan nokta sayıları kesin. Tam olarak beklediğiniz gibi değiller. Üstelik, epsilon tekniği, gerçekte olan şeylerin nasıl üstesinden gelineceğine dair bir yaklaşımdır, çünkü gerçek beklenen hata mantisin ölçeğiyle ilişkilidir, yani normalde yaklaşık 1 LSB'ye çıkmış olursunuz, ancak dikkatli olmamanız durumunda yapılan her işlem için kayan nokta ile önemsiz olmayan bir şey yapmadan önce bir sayısal analiste danışın. Mümkünse uygun bir kütüphane kullanın. - Donal Fellows
@DonalFellows: IEEE standardı, kayan nokta hesaplamalarının, kaynak işlenenlerin tam değerleri olması durumunda sonucun ne olacağıyla en doğru eşleşen sonucu vermesini gerektirir, ancak bunlar aslında temsil etmek kesin değerler. Pek çok durumda, 0.1f'yi bu belirsizliğin ima ettiği ondalık basamak sayısıyla birlikte gösterilmesi gereken (1,677,722 +/- 0,5) / 16,777,216 olarak kabul etmek daha yararlıdır (1,677,722 +/-). 0.5) / 16,777,216 (24 ondalık haneye görüntülenmelidir). - supercat
@supercat: IEEE-754, kayan noktalı veri noktasında oldukça açık yap kesin değerleri temsil eder; Madde 3.2 - 3.4 ilgili bölümlerdir. Elbette, onları yorumlayabildiğiniz gibi, bunları başka şekilde yorumlamayı seçebilirsiniz. int x = 3 anlam olarak x 3 +/- 0.5'dir. - Stephen Canon
@supercat: Tamamen katılıyorum, ama bu demek değil ki Distance sayısal değerine tam olarak eşit değildir; Bu, sayısal değerin, modellenen bazı fiziksel niceliğe sadece bir yaklaşım olduğu anlamına gelir. - Stephen Canon
Sayısal analizler için, kayan noktalı sayıları aralıklarla değil, kesin değerler olarak (tam olarak istediğiniz değerler değil) yorumlarsanız, beyniniz size teşekkür edecektir. Örneğin, x, 4,5'ten küçük bir hata ile 4.5'ın altında bir yerdeyse ve (x + 1) - x'i hesaplarsanız, "aralık" yorumlaması, "tam değer" yorumlamasını söylerken 0,8 ila 1,2 arasında bir aralık bırakmanızı sağlar. Sonuç, çift hassasiyette en fazla 2 ^ (- 50) hatasıyla 1 olacaktır. - gnasher729


GCC aslında bir tamsayı olduğunda * a * a * a * a * a (a * a * a) * (a * a * a) değerini optimize eder. Bu komutla denedim:

$ echo 'int f(int x) { return x*x*x*x*x*x; }' | gcc -o - -O2 -S -masm=intel -x c -

Gcc bayrakları bir sürü var ama hiçbir şey fantezi. Demek istedikleri: Stdin'den oku; O2 optimizasyon seviyesini kullanın; bir ikili yerine çıkış derleme dili listesi; listeleme, Intel derleme dili sözdizimini kullanmalıdır; giriş C dilinde (genellikle giriş dosya uzantısından dil çıkar, ancak stdin'den okurken dosya uzantısı yok); ve stdout'a yaz.

İşte çıktının önemli kısmı. Derleme dilinde neler olduğunu gösteren bazı yorumlar ekledim:

    ; x is in edi to begin with.  eax will be used as a temporary register.
    mov    eax, edi     ; temp1 = x
    imul    eax, edi    ; temp2 = x * temp1
    imul    eax, edi    ; temp3 = x * temp2
    imul    eax, eax    ; temp4 = temp3 * temp3

Bir Ubuntu türevi olan Linux Mint 16 Petra'daki GCC sistemini kullanıyorum. İşte gcc sürümü:

$ gcc --version
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Diğer posterlerin de belirttiği gibi, bu seçenek kayan noktalarda mümkün değildir, çünkü kayan nokta aritmetiği aslında ilişkilendirici değildir.


49
2018-06-27 21:03



Bu tamsayı çarpma için yasaldır çünkü iki tamamlayıcı taşması tanımlanmamış bir davranıştır. Bir taşma olacaksa, yeniden yapılanma işlemlerine bakılmaksızın bir yerlerde gerçekleşecektir. Bu nedenle, taşma olmayan ifadeler de aynıdır, taşmanın tanımlanamayan davranışları olduğu için, derleyicinin taşmanın gerçekleştiği noktayı değiştirmesi iyi olur. gcc bunu yapar unsigned intayrıca - Peter Cordes


Kayan ifadelerin kasılmasından henüz söz edilemez (ISO C standardı, 6.5p8 ve 7.12.2). Eğer FP_CONTRACT pragma ayarlandı ON, derleyici gibi bir ifadeyi kabul edebilir a*a*a*a*a*a Tek bir işlem olarak, tek bir yuvarlamayla tam olarak değerlendirilmiş gibi. Örneğin, bir derleyici onu daha hızlı ve daha doğru olan bir dahili güç işleviyle değiştirebilir. Bu davranış özellikle programcı tarafından doğrudan kaynak kodda kısmen kontrol edilirken, son kullanıcı tarafından sağlanan derleyici seçenekleri bazen yanlış olarak kullanıldıkça özellikle ilgi çekicidir.

Varsayılan durumu FP_CONTRACT pragma uygulama tanımlı olduğundan, bir derleyicinin varsayılan olarak bu optimizasyonları yapmasına izin verilir. Bu nedenle, IEEE 754 kurallarına sıkı sıkıya uyması gereken taşınabilir kod, açıkça OFF.

Bir derleyici bu pragmayı desteklemiyorsa, geliştiricinin bunu seçmeyi seçmesi durumunda, bu tür bir optimizasyondan kaçınarak muhafazakar olmalıdır. OFF.

GCC bu pragmayı desteklemez, ancak varsayılan seçeneklerle, ON; Bu nedenle, dönüşümün önlenmesi isteniyorsa, bir donanım FMA ile hedefler için a*b+c fma (a, b, c) için, gibi bir seçenek sağlamak gerekir -ffp-contract=off (pragmayı açıkça ayarlamak için OFF) veya -std=c99 (GCC'nin bazı C standart versiyonuna uymasını söylemek gerekirse, burada C99, böylece yukarıdaki paragrafı takip edin). Geçmişte, bu son seçenek dönüşümü önlemiyordu, yani GCC'nin bu noktaya uymadığı anlamına geliyordu: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37845


27
2018-06-23 12:44



Uzun ömürlü popüler sorular bazen yaşlarını gösterir. Bu soruya, 2011'de GCC'nin son zamanlardaki C99 standardına tam olarak uymadığı için mazur kaldığı soruldu ve yanıtlandı. Tabii şimdi de 2014, yani GCC… ahem. - Pascal Cuoq
Yine de, kabul edilmiş bir cevap olmaksızın, son zamanlarda kayan noktalı soruları yanıtlamaman gerekir mi? öksürük stackoverflow.com/questions/23703408 öksürük - Pascal Cuoq
Onu bulmak ... gcc'nin C99 kayan nokta pragmasını uygulamamasını rahatsız ediyor. - David Monniaux


Lambdageek şamandıra çoğaltmanın işaretli olmadığından ve daha az doğruluk elde edebileceğinizden, aynı zamanda daha iyi bir doğruluk elde edeceğinizde, optimizasyona karşı tartışabilir, çünkü deterministik bir uygulama istersiniz. Örneğin, her müşterinin aynı dünyayı simüle etmesi gereken oyun simülasyonu istemci / sunucusunda, kayan nokta hesaplamalarının deterministik olmasını istersiniz.


26
2018-06-21 18:52



Kayan nokta her zaman deterministtir. - Alice
@Alice Burada oldukça farklı görünüyor Bjorn burada aynı sonucu farklı platformlar ve farklı derleyici sürümleri vs (programcının kontrolünün ötesinde olabilir dış değişkenler) veren kod anlamında 'determinist' kullanıyor - aksine Çalışma zamanında gerçek sayısal rastgelelik. Bunun kelimenin doğru bir şekilde kullanılmadığına işaret ediyorsanız, bununla tartışmayacağım. - greggo
@greggo Söylediklerinin yorumlanmasından bile farklı olarak, hala yanlıştır; platformlar boyunca çoğu (tümü olmasa bile) işlem için özdeş özellikler sağlamak üzere IEEE 754'ün tüm noktası budur. Şimdi, herhangi bir uzak sunucu / istemcide her bir işlemin aynı olmasını istemeniz durumunda geçerli bir sorun olan platformlar veya derleyici sürümlerinden bahsetmedi .... ama bu onun açıklamasından açık değil. Daha iyi bir kelime "güvenilir şekilde benzer" veya bir şey olabilir. - Alice
@Alice, herkesin zamanını, sizin de dahil olmak üzere, tartışılan semantiklerle harcıyorsunuz. Anlamı açıktı. - Lanaru
@Lanaru Standartların tüm noktası semantiktir; Onun anlamı açıkça belli değildi. - Alice


Bu davanın en iyi şekilde olmasını beklemiyordum. Bir ifadenin tüm işlemleri kaldırmak için yeniden gruplandırılabilen alt ifadeler içerdiği çoğu zaman olamaz. Derleyici yazarların zamanlarını nadiren karşılaşılan bir uç vakayı kapsamaktan ziyade dikkat çekici geliştirmelerle sonuçlanma olasılığı olan alanlarda yatırım yapmalarını beklerdim.

Diğer ifadelerden, bu ifadenin doğru derleyici anahtarlarıyla gerçekten optimize edilebileceğini öğrenmek beni şaşırttı. Optimizasyon önemsizdir, ya da çok daha yaygın bir optimizasyonun bir kenar durumudur ya da derleyici yazarlar son derece kapsamlıydı.

Burada yaptığınız gibi derleyiciye ipuçları vermede yanlış bir şey yok. Hangi optimiziteleri getireceğini görmek için ifadeleri ve ifadeleri yeniden düzenlemek için mikro optimizasyon sürecinin normal ve beklenen bir parçası.

Derleyici, tutarsız sonuçların (uygun anahtarlar olmadan) sunulması için iki ifadeyi göz önünde bulundurarak haklı çıkarsa da, bu kısıtlamaya tabi olmanıza gerek yoktur. Fark inanılmaz derecede küçük olacak - öyle ki, fark sizin için önemliyse, ilk olarak standart kayan nokta aritmetiğini kullanmamalısınız.


26
2018-01-03 16:40



Başka bir yorumcu tarafından belirtildiği gibi, bu saçma noktası doğru değildir; Fark, maliyetin% 10'u kadar olabilir ve eğer sıkı bir döngüde çalışıyorsa, bu, önemsiz miktarda ek hassasiyet elde etmek için boşa harcanan birçok talimatı çevirecektir. Monte Carlo'yu yaparken standart FP'yi kullanmamanızı söylemek, ülke çapında bir uçak kullanmak için her zaman bir uçak kullanmanız gerektiğini söylüyor; birçok dışsallığı yok sayar. Son olarak, bu nadir bir optimizasyon DEĞİLDİR; ölü kod analizi ve kod azaltma / refactor çok yaygındır. - Alice


"Pow" gibi kütüphane fonksiyonları genellikle mümkün olan minimum hatayı (genel durumda) elde etmek için dikkatlice hazırlanmışlardır. Bu genellikle spline'larla yaklaşan fonksiyonlara ulaşır (Pascal'ın yorumuna göre en yaygın uygulama Remez algoritması)

temelde aşağıdaki işlem:

pow(x,y);

yaklaşık olarak doğal bir hata var herhangi bir çarpma veya bölme hatası ile aynı büyüklükte.

Aşağıdaki işlem sırasında:

float a=someValue;
float b=a*a*a*a*a*a;

daha büyük daha doğal bir hata var Tek çarpmanın 5 katı hatası ya da bölme (çünkü 5 çarpanı birleştiriyorsunuz).

Derleyici, yaptığı optimizasyon türüne gerçekten dikkat etmelidir:

  1. eğer optimizasyon yapıyorsa pow(a,6) için a*a*a*a*a*a o Mayıs ayı performansı artırmak, ancak kayan nokta sayıları için hassasiyeti büyük ölçüde azaltır.
  2. eğer optimizasyon yapıyorsa a*a*a*a*a*a  için pow(a,6) doğruluk oranını azaltabilir çünkü "a", çarpmadan çoğullamaya izin veren özel bir değerdi (2 veya biraz küçük tamsayı sayısı)
  3. eğer optimizasyon yapıyorsa pow(a,6) için (a*a*a)*(a*a*a) veya (a*a)*(a*a)*(a*a) hala doğruluk kaybı olabilir pow işlevi.

Genel olarak biliyorsunuz ki, rasgele kayan nokta değerleri için "pow", sonunda yazabileceğiniz herhangi bir işleve göre daha iyi bir doğruluğa sahiptir, ancak bazı özel durumlarda çoklu çarpımlar daha iyi doğruluk ve performansa sahip olabilir, daha uygun olanı seçen geliştiriciye bağlıdır, En sonunda, hiç kimsenin bu kodu "optimize etmeyeceği" şekilde yorumlayarak kodu yorumlar.

Optimize edilecek tek bir şey (kişisel görüş ve görünüşte GCC'de herhangi bir özel optimizasyon veya derleyici bayrağının seçilmesi) “pow (a, 2)” ile “a * a” nın yerini almalıdır. Bir derleyici satıcısının yapması gereken tek şey bu olurdu.


22
2017-10-01 19:33



downvoters, bu cevabın mükemmel olduğunu fark etmelidir. Cevabımı desteklemek için düzinelerce kaynak ve belge alıntı yapabilirim ve muhtemelen herhangi bir düşüşçünün olacağından daha fazla kayan nokta hassasiyeti ile ilgilenirim. StackOverflow'ta diğer cevapların kapsamadığı eksik bilgileri ekleyerek mükemmel bir şekilde mantıklı olun ve bu nedenle nedenlerinizi açıklayın. - GameDeveloper
Bana öyle geliyor ki Stephen Canon'un cevabı, söyleyeceklerinizle ilgili. Libms'in spline'larla uygulandığı konusunda ısrar ediyorsunuz: daha tipik olarak argüman azaltma (uygulanmakta olan işleve bağlı olarak) artı katsayıları Remez algoritmasının daha fazla veya daha az karmaşık varyantları tarafından elde edilen tek bir polinom kullanmaktadır. Birleşme noktalarındaki düzgünlük, libm fonksiyonlarını takip etmek için objektif bir değer olarak düşünülmez (eğer yeterince doğru sonuçlanırsa, alanın kaç parçaya ayrıldığına bakılmaksızın otomatik olarak oldukça pürüzsüzdür). - Pascal Cuoq
Cevabınızın ikinci yarısı, derleyicilerin kaynak kodunun ne dediğini uygulayan kod üretmesi gerektiği noktasını tamamen kaybeder. Ayrıca “doğruluk” anlamına geldiğinde “hassas” kelimesini kullanırsınız. - Pascal Cuoq
Girdiğin için teşekkürler, cevabı biraz düzelttim, son 2 satırda yeni bir şey var hala ^^ - GameDeveloper


Bu soruya şimdiden birkaç tane iyi cevap var, fakat bütünlük açısından C standardının ilgili bölümünün 5.1.2.2.3 / 15 olduğunu belirtmek istedim. C ++ 11 standart). Bu bölüm, operatörlerin yalnızca gerçekten birleştirici veya değişkendirlerse yeniden gruplandırılabileceğini belirtir.


19
2018-06-16 18:44