Satır içi genişletme - Inline expansion

Gelen bilgi işlem , satır içi genişletme veya inlining , manuel veya derleyici optimizasyon bir işlev yerine çağrı sitesini denilen fonksiyonun vücuduyla. Satır içi genişletme makro genişletmeye benzer , ancak derleme sırasında kaynak kodu (metin) değiştirmeden gerçekleşir, makro genişletme ise derlemeden önce gerçekleşir ve daha sonra derleyici tarafından işlenen farklı metinlerle sonuçlanır.

Satır içi oluşturma önemli bir optimizasyondur, ancak performans üzerinde karmaşık etkileri vardır. Genel bir kural olarak , bazı satır içi işlemleri, çok küçük alan maliyetiyle hızı artıracaktır, ancak satır içi kodun talimat önbelleğini çok fazla tüketmesi ve aynı zamanda önemli bir alana mal olması nedeniyle fazla satır içi yapmak hıza zarar verecektir . Peyton Jones & Marlow 1999'da 1980'lerden ve 1990'lardan inlineing üzerine mütevazı bir akademik literatür incelemesi verilmiştir.

Genel Bakış

Satır içi genişletme, derleyici işlevin yeni bir kopyasını çağrıldığı her yere yerleştirdiği için makro genişletmeye benzer. Satır içi işlevler, işlev çağırma genel giderleri kaydedildiği için normal işlevlerden biraz daha hızlı çalışır, ancak bir bellek cezası vardır. Bir işlev 10 kez satır içine alınmışsa, koda eklenen işlevin 10 kopyası olacaktır. Bu nedenle satır içi yapmak, sıklıkla çağrılan küçük işlevler için en iyisidir. C ++ 'da, bir sınıfın üye işlevleri, sınıf tanımında tanımlanmışsa, varsayılan olarak satır içine alınır ( satır içi anahtar sözcüğünü kullanmaya gerek yoktur ); aksi takdirde anahtar kelimeye ihtiyaç vardır. Derleyici, programcının bir işlevi satır içi yapma girişimini, özellikle özellikle büyükse, göz ardı edebilir.

Satır içi genişletme, bir işlev çağrıldığında zaman ek yükünü (fazla süre) ortadan kaldırmak için kullanılır. Genellikle sık çalışan işlevler için kullanılır. Ayrıca, çok küçük işlevler için alan avantajına sahiptir ve diğer optimizasyonlar için olanak sağlayan bir dönüşümdür .

Satır içi işlevler olmadan, derleyici hangi işlevlerin satır içi olacağına karar verir. Programcının hangi fonksiyonların satır içi olduğu ve hangilerinin olmadığı üzerinde çok az kontrolü vardır veya hiç kontrolü yoktur. Programcıya bu kontrol derecesinin verilmesi, hangi fonksiyonların satır içi yapılacağını seçerken uygulamaya özel bilginin kullanılmasına izin verir.

Normalde, bir fonksiyon çağrıldığında, kontrol bir şube veya çağrı talimatı tarafından tanımına aktarılır . Satır içi ile kontrol, bir şube veya çağrı talimatı olmadan doğrudan işlev koduna geçer.

Derleyiciler genellikle satır içi içeren ifadeler uygular . Döngü koşulları ve döngü gövdeleri tembel bir değerlendirmeye ihtiyaç duyar . Bu özellik, döngü koşullarını ve döngü gövdelerini hesaplama kodu satır içi olduğunda yerine getirilir. Satır içi ifadelerin başka bir nedeni de performansla ilgili hususlardır.

İşlevsel programlama dilleri bağlamında , satır içi genişletmeyi genellikle beta azaltma dönüşümü izler .

Bir programcı , kaynak kodda tek seferlik bir işlem olarak, kopyalama ve yapıştırma programlama yoluyla bir işlevi manuel olarak satır içi yapabilir . Bununla birlikte, satır içi kontrol etmenin diğer yöntemleri (aşağıya bakın) tercih edilir, çünkü programcı, satır içi işlevdeki bir hatayı düzeltirken, orijinal işlev gövdesinin (muhtemelen değiştirilmiş) çoğaltılmış bir sürümünü gözden kaçırdığında ortaya çıkan hataları hızlandırmazlar.

Performansa etkisi

Bu optimizasyonun doğrudan etkisi, alan kullanımını kötüleştirme pahasına ( işlev gövdesinin kopyalanması nedeniyle) zaman performansını iyileştirmektir (çağrı ek yükünü ortadan kaldırarak ). Basit durumlar haricinde, işlev gövdesinin kopyalanmasından kaynaklanan kod genişlemesi hakimdir ve bu nedenle satır içi genişletmenin doğrudan etkisi, yer pahasına zamanı iyileştirmektir.

Bununla birlikte, satır içi genişletmenin birincil faydası, daha büyük işlevlerde daha iyi optimizasyon mümkün olduğundan, işlev gövdesinin boyutunun artması nedeniyle daha fazla optimizasyona ve iyileştirilmiş programlamaya izin vermektir. Satır içi genişletmenin hız üzerindeki nihai etkisi, modern işlemcilerde performansa hakim olan bellek sisteminin performansı üzerindeki birden çok etkiden dolayı karmaşıktır (öncelikle talimat önbelleği ): belirli programa ve önbelleğe bağlı olarak, belirli işlevlerin sıralanması performansı artırabilir veya azaltabilir. .

Satır içi oluşturmanın etkisi, farklı soyutlama dereceleri nedeniyle programlama diline ve programa göre değişir. C ve Fortran gibi daha düşük seviyeli zorunlu dillerde, kod boyutu üzerinde küçük bir etki ile tipik olarak% 10-20 hız artışı sağlarken, daha soyut dillerde kaldırılan satır içi katman sayısı nedeniyle önemli ölçüde daha önemli olabilir. Ekstrem bir örnek Self'tir , burada bir derleyici satır içi olarak 4 ila 55 arasında iyileştirme faktörleri görmüştür.

Bir işlev çağrısını ortadan kaldırmanın doğrudan faydaları şunlardır:

Satır içi yapmanın birincil yararı, izin verdiği diğer optimizasyonlardır. İşlev sınırlarını aşan optimizasyonlar , prosedürler arası optimizasyon (IPO) gerektirmeden yapılabilir : satır içi bir kez gerçekleştirildikten sonra, genişletilmiş fonksiyon gövdesinde ek prosedür içi optimizasyonlar ("global optimizasyonlar") mümkün hale gelir. Örneğin:

  • Bağımsız değişken olarak iletilen bir sabit , genellikle eşleşen parametrenin tüm örneklerine yayılabilir veya işlevin bir kısmı bir döngüden ( döngü-değişmez kod hareketi yoluyla) "kaldırılabilir" .
  • Kayıt tahsisi , daha büyük işlev gövdesinde yapılabilir.
  • Kaçış analizi ve kuyruk tekrarı gibi üst düzey optimizasyonlar, daha geniş bir kapsamda gerçekleştirilebilir ve özellikle bu optimizasyonları uygulayan derleyici esas olarak prosedür içi analize dayanıyorsa daha etkili olabilir.

Bunlar satır içi olmadan yapılabilir, ancak önemli ölçüde daha karmaşık bir derleyici ve bağlayıcı gerektirir (arayan ve aranan uçların ayrı derleme birimlerinde olması durumunda).

Tersine, bazı durumlarda, bir dil belirtimi, bir programın, bazı optimizasyonları önleyerek, yordamın satır içi halindeyken artık yapamayacağı yordamlara ilişkin argümanlar hakkında ek varsayımlar yapmasına izin verebilir. Daha akıllı derleyiciler ( Glasgow Haskell Compiler gibi ) bunu izler, ancak saf satır içi bu bilgiyi kaybeder.

Bellek sistemi için satır içi yapmanın bir başka yararı da şudur:

  • Dalları ortadan kaldırmak ve bellekte birbirine yakın çalıştırılan kodu tutmak , referansın yerelliğini (uzamsal yerellik ve talimatların sıralılığı) iyileştirerek talimat önbelleği performansını iyileştirir . Bu, özellikle sıralılığı hedefleyen optimizasyonlardan daha küçüktür, ancak önemlidir.

Satır içi yazmanın doğrudan maliyeti, her arama sitesinde işlev gövdesinin çoğaltılması nedeniyle artan kod boyutudur. Bununla birlikte, önemsiz erişimci yöntemleri veya mutator gibi işlev gövdesinin bir işlev çağrısının boyutundan daha küçük olduğu (argüman ve dönüş değeri işleme dahil olmak üzere çağrıda bulunan) çok kısa işlevler söz konusu olduğunda bunu her zaman yapmaz. yöntemler (alıcılar ve ayarlayıcılar); veya yalnızca tek bir yerde kullanılan bir işlev için, bu durumda yinelenmez. Bu nedenle, gömülü sistemlerde sıklıkla olduğu gibi, kod boyutu için optimizasyon yapılırsa satır içi çizgi en aza indirilebilir veya ortadan kaldırılabilir .

Satır içi aynı zamanda, kod genişlemesinden dolayı (çoğaltma nedeniyle) talimat önbelleği performansına zarar verdiği için performansa bir maliyet getirir. Bu, genişletmeden önce , programın çalışma kümesi (veya kodun sıcak bölümü) bellek hiyerarşisinin bir düzeyine (örneğin, L1 önbelleği ) uyuyorsa , ancak genişletmeden sonra artık uymuyorsa, bu en önemlisidir. önbellek bu düzeyde ıskalı. Hiyerarşinin farklı seviyelerindeki önemli performans farkı nedeniyle bu, performansı önemli ölçüde düşürür. En üst düzeyde, bu, artan sayfa hatalarına , atma nedeniyle yıkıcı performans düşüşüne veya programın hiç çalışmamasına neden olabilir. Bu sonuncusu, kod boyutunun kullanılabilir belleğe göre küçük olduğu, ancak gömülü sistemler gibi kaynakları kısıtlı ortamlar için bir sorun olabileceği yaygın masaüstü ve sunucu uygulamalarında nadirdir. Bu sorunu hafifletmenin bir yolu, işlevleri daha küçük bir sıcak satır içi yola ( hızlı yol ) ve daha büyük bir soğuk satır içi olmayan yola (yavaş yol) bölmektir.

Hatalı performansın sıralanması, öncelikle birçok yerde kullanılan büyük işlevler için bir sorundur, ancak ötesine geçmenin performansı düşürdüğü başabaş noktasını belirlemek zordur ve genel olarak hassas yüke bağlıdır, bu nedenle manuel optimizasyona veya profile tabi olabilir. güdümlü optimizasyon . Bu, döngü açma gibi diğer kod genişletme optimizasyonlarına benzer bir sorundur , bu da işlenen talimatların sayısını azaltır, ancak daha düşük önbellek performansı nedeniyle performansı düşürebilir.

Satır içi yapmanın önbellek performansı üzerindeki kesin etkisi karmaşıktır. Küçük önbellek boyutları için (genişletmeden önceki çalışma kümesinden çok daha küçük), artan sıralılık baskındır ve satır içi önbellek performansını iyileştirir. Satır içi yazmanın çalışma kümesini artık önbelleğe sığmayacak şekilde genişlettiği çalışma kümesine yakın önbellek boyutları için, bu baskın hale gelir ve önbellek performansı düşer. Çalışma kümesinden daha büyük önbellek boyutları için satır içi oluşturma, önbellek performansı üzerinde ihmal edilebilir bir etkiye sahiptir. Ayrıca, yük iletme gibi önbellek tasarımındaki değişiklikler , önbellek kayıplarındaki artışı telafi edebilir.

Derleyici desteği

Derleyiciler, hangi işlev çağrılarının satır içine alınması gerektiğine karar vermek için çeşitli mekanizmalar kullanır; bunlar, komut satırı seçenekleri aracılığıyla genel kontrol ile birlikte belirli işlevler için programcılardan manuel ipuçları içerebilir . Diğer durumlarda el derleyici vasıtasıyla belirlenebilir ise, inlining yararlı olup olmadığı yargısına dayanan, birçok dilde birçok derleyici tarafından otomatik olarak yapılır inlining direktifler tipik bir anahtar kelime veya kullanarak derleyici yönergesini denilen inline . Tipik olarak bu, ipucunun gücü dile ve derleyiciye göre değişiklik göstererek satır içi yapmak yerine satır içi yazmanın istendiğini ima eder.

Tipik olarak, derleyici geliştiriciler akılda yukarıdaki performans sorunları ve anonim tutmak sezgisel tarama ziyade çoğu durumda, onu kötüleşen yerine, performansı geliştirmek amacıyla satır içi hangi işlevleri seçmek onların derleyicilerine.

Uygulama

Bir kez derleyici inlining işlemini kendisi gerçekleştirerek, belirli bir işlevi satır içi karar verdi genellikle basittir. Derleyicinin satır içi olarak farklı dillerde kodlar arasında çalışıp çalışmadığına bağlı olarak, derleyici ya yüksek seviyeli bir ara gösterime ( soyut sözdizimi ağaçları gibi ) ya da düşük seviyeli bir ara gösterime göre inlining yapabilir . Her iki durumda da, derleyici basitçe argümanları hesaplar, bunları fonksiyonun argümanlarına karşılık gelen değişkenlerde saklar ve ardından çağrı sitesine fonksiyon gövdesini ekler.

Bağlayıcılar ayrıca satır içi işlevi de yapabilir. Bir bağlayıcı işlevleri satır içi yaptığında, kütüphane işlevleri gibi kaynağı olmayan işlevleri satır içi yapabilir (bkz. Bağlantı zamanı optimizasyonu ). Bir çalışma zamanı sistemi de satır içi işlevi görebilir. Çalışma zamanı satır içi işlemi, Java Hotspot derleyicisinde olduğu gibi hangi işlevlerin satır içi yapılacağına ilişkin daha iyi kararlar vermek için dinamik profil oluşturma bilgilerini kullanabilir .

C programlama dilinde kaynak düzeyinde "elle" gerçekleştirilen satır içi genişletmenin basit bir örneği : 

int pred(int x)
{
    if (x == 0)
        return 0;
    else
        return x - 1;
}

Satır içi yapmadan önce: 

int func(int y) 
{
    return pred(y) + pred(0) + pred(y+1);
}

Satır içi yaptıktan sonra: 

int func(int y) 
{
    int tmp;
    if (y   == 0) tmp  = 0; else tmp  = y - 1;       /* (1) */
    if (0   == 0) tmp += 0; else tmp += 0 - 1;       /* (2) */
    if (y+1 == 0) tmp += 0; else tmp += (y + 1) - 1; /* (3) */
    return tmp;
}

Bunun yalnızca bir örnek olduğunu unutmayın. Gerçek bir C uygulamasında, derleyiciye kodu bu şekilde dönüştürmesini söylemek için parametreli makrolar veya satır içi işlevler gibi bir satır içi dil özelliğini kullanmak tercih edilebilir . Bir sonraki bölüm, bu kodu optimize etmenin yollarını listeler.

Montaj makro genişletmesi ile satır içi

Assembler makroları , satır içi yapmaya alternatif bir yaklaşım sağlar; bu sayede, bir dizi talimat normalde tek bir makro kaynak ifadesinden (sıfır veya daha fazla parametre ile) makro genişletme ile satır içi olarak üretilebilir. Parametrelerden biri, alternatif olarak diziyi içeren ve bunun yerine işleve yönelik satır içi bir çağrı ile işlenen tek seferlik ayrı bir alt rutin üretme seçeneği olabilir . Misal: 

MOVE FROM=array1,TO=array2,INLINE=NO

Sezgisel

Satır içi için bir dizi farklı sezgisel tarama araştırılmıştır. Genellikle, bir satır içi algoritmanın belirli bir kod bütçesi vardır (program boyutunda izin verilen bir artış) ve bu bütçeyi aşmadan en değerli çağrı sitelerini satır içi yapmayı hedefler. Bu anlamda, birçok satır içi algoritma genellikle Sırt Çantası probleminden sonra modellenir . Hangi çağrı yerlerinin daha değerli olduğuna karar vermek için, bir satır içi algoritması bunların faydasını, yani yürütme süresinde beklenen azalmayı tahmin etmelidir. Satır içi uzmanlar, faydaları tahmin etmek için genellikle farklı kod yollarının çalıştırılma sıklığı hakkında profil bilgilerini kullanır.

Profil oluşturma bilgilerine ek olarak, daha yeni tam zamanında derleyiciler , aşağıdakiler gibi birkaç daha gelişmiş sezgisel tarama uygular:

  • Hangi kod yollarının yürütme süresinde en iyi azalmaya yol açacağını tahmin etmek (satır içi yapmanın bir sonucu olarak ek derleyici optimizasyonlarını etkinleştirerek) ve bu tür yolların algılanan faydasını artırmak.
  • Satır içi için maliyet başına fayda eşiğini, derleme biriminin boyutuna ve halihazırda yerleştirilmiş olan kod miktarına göre uyarlayıcı bir şekilde ayarlama.
  • Alt yordamları kümeler halinde gruplamak ve tekil alt yordamlar yerine tüm kümeleri satır içine almak. Burada, buluşsal yöntem, kümelerin sadece uygun bir alt kümesini satır içine almanın hiçbir şeyi satır içine almamaktan daha kötü bir performansa yol açtığı yöntemleri gruplayarak tahmin eder.

Faydaları

Satır içi genişletmenin kendisi bir optimizasyondur, çünkü çağrılardan kaynaklanan ek yükü ortadan kaldırır, ancak etkinleştirici bir dönüşüm olarak çok daha önemlidir . Yani, derleyici çağrı sitesi bağlamında bir işlev gövdesini genişlettiğinde - genellikle sabit sabitler olabilecek argümanlarla - daha önce mümkün olmayan çeşitli dönüşümler yapabilir. Örneğin, bu belirli arama sitesinde bir koşullu dal her zaman doğru veya her zaman yanlış olabilir. Bu da sonuçta ölü kodun ortadan kaldırılmasını , döngüde değişmeyen kod hareketini veya tümevarım değişkenlerinin ortadan kaldırılmasını sağlayabilir .

Önceki bölümdeki C örneğinde, optimizasyon fırsatları çoktur. Derleyici şu adımları izleyebilir:

  • tmp += 0 İşaretli hatlarında ifadeleri (2) ve (3) hiçbir şey. Derleyici bunları kaldırabilir.
  • Koşul 0 == 0 her zaman doğrudur, bu nedenle derleyici (2) işaretli satırı sonuç ile değiştirebilir tmp += 0 (hiçbir şey yapmaz).
  • Derleyici koşulu y+1 == 0 olarak yeniden yazabilir y == -1 .
  • Derleyici ifadesini azaltabilir (y + 1) - 1 için y .
  • İfadeler y ve y+1 her ikisi de sıfıra eşit olamaz. Bu, derleyicinin bir testi ortadan kaldırmasını sağlar.
  • Gibi ifadelerde if (y == 0) return y değeri y vücutta bilinmekte ve satır içine alınabilmektedir.

Yeni işlev şuna benzer: 

int func(int y) 
{
    if (y == 0)
        return 0;
    if (y == -1)
        return -2;
    return 2*y - 1;
}

Sınırlamalar

Özyinelemeden dolayı tam satır içi genişletme her zaman mümkün değildir : çağrıları yinelemeli olarak satır içi genişletme sona ermez. Sınırlı bir miktarı genişletmek veya çağrı grafiğini analiz etmek ve belirli düğümlerde döngüleri kırmak (yani özyinelemeli bir döngüde bazı kenarları genişletmemek) gibi çeşitli çözümler vardır . Özyinelemeli genişletme sona ermediğinden ve genellikle özyinelemeli makroların yasaklanmasıyla (C ve C ++ 'da olduğu gibi) çözüldüğünden, makro genişletmede de aynı sorun ortaya çıkar.

Makrolarla karşılaştırma

Geleneksel olarak, C gibi dillerde satır içi genişletme, parametreleştirilmiş makrolar kullanılarak kaynak düzeyinde gerçekleştiriliyordu . C99'da mevcut olduğu gibi gerçek satır içi işlevlerin kullanılması, bu yaklaşıma göre çeşitli avantajlar sağlar:

  • C'de, makro çağrıları tür denetimi yapmaz , hatta argümanların iyi biçimlendirildiğini kontrol etmez, oysa işlev çağrıları genellikle yapar.
  • C'de bir makro, return anahtar sözcüğünü bir işlevin yapacağı anlamla kullanamaz (bu, makro yerine genişletmeyi sonlandırmasını isteyen işlevi yapar). Başka bir deyişle, bir makro, içinde çağrılan son ifadenin sonucu olmayan hiçbir şeyi döndüremez.
  • C makroları yalnızca metin ikamesi kullandığından, bu, argümanların ve işlem sırasının yeniden değerlendirilmesi nedeniyle istenmeyen yan etkilere ve verimsizliğe neden olabilir .
  • Makrolar içindeki derleyici hatalarının anlaşılması genellikle zordur, çünkü bunlar programcının yazdığı kod yerine genişletilmiş koda atıfta bulunur. Bu nedenle, satır içi kod için hata ayıklama bilgileri genellikle makro genişletilmiş koddan daha yararlıdır.
  • Birçok yapının makrolar kullanılarak ifade edilmesi garip veya imkansızdır veya önemli ölçüde farklı bir sözdizimi kullanır. Satır içi işlevler, sıradan işlevlerle aynı sözdizimini kullanır ve kolaylıkla isteğe bağlı olarak satır içi ve satır içi olmayabilir.

Birçok derleyici, bazı özyinelemeli işlevleri satır içi olarak genişletebilir ; yinelemeli makrolar genellikle yasa dışıdır.

C ++ tasarımcısı Bjarne Stroustrup , makrolardan mümkün olduğunca kaçınılması gerektiğini vurgulamayı seviyor ve satır içi işlevlerin kapsamlı kullanımını savunuyor.

Seçim yöntemleri

Pek çok derleyici, yararlı olduğu her yerde işlevleri agresif bir şekilde satır içi yapar. Daha büyük yürütülebilir dosyalara yol açabilse de, bellek kapasitesi CPU hızından daha hızlı arttığı için agresif satır içi oluşturma yine de giderek daha cazip hale geldi. Satır içi, işlevsel dillerde ve nesneye yönelik programlama dillerinde kritik bir optimizasyondur ve klasik optimizasyonları etkili kılmak için tipik olarak küçük işlevleri için yeterli bağlam sağlamak üzere ona güvenir.

Dil desteği

Java ve işlevsel diller dahil birçok dil, satır içi işlevler için dil yapıları sağlamaz, ancak bunların derleyicileri veya yorumlayıcıları genellikle agresif satır içi genişletme gerçekleştirir. Diğer diller, genellikle derleyici yönergeleri (pragmalar) olarak açık ipuçları için yapılar sağlar .

In Ada programlama dili , satır içi işlevleri için bir pragma vardır.

Common Lisp'teki işlevler aşağıdaki gibi inline bildirime göre satır içi olarak tanımlanabilir : 

 (declaim (inline dispatch))
 (defun dispatch (x)
   (funcall
     (get (car x) 'dispatch) x))

Haskell derleyicisi GHC satır içi işlevler veya yeterince küçük ama dil pragma kullanarak açıkça not edilebilir inlining değerlere çalışır: 

key_function :: Int -> String -> (Bool, Double)
{-# INLINE key_function #-}

C ve C ++

Ana madde: Satır içi işlevi

C ve C ++ inline , hem bir derleyici yönergesi olarak işlev gören - satır içi yazmanın istendiğini ancak gerekli olmadığını belirten - hem de görünürlüğü ve bağlanma davranışını değiştiren bir anahtar sözcüğe sahiptir . Görünürlük değişikliği, işlevin standart C araç zinciri aracılığıyla satır içine alınmasına izin vermek için gereklidir; burada tek tek dosyaların derlenmesinin ( çeviri birimlerinin yerine ) ardından bağlanması gelir: bağlayıcının satır içi işlevler yapabilmesi için, başlık (görünür olacak) ve işaretli inline (çoklu tanımlardan kaynaklanan belirsizliği önlemek için).

Ayrıca bakınız

Notlar

Referanslar

Dış bağlantılar