Saturday, January 13, 2007

Analiz: Nasıl kod yazabiliriz?

Anladım ki benim yazılarım genel de yaşadığım güncel olaylar üzerine çıkıyor. Şimdi size geçenler de itü bilgisayar grubumuz da konustugumuz bir konuyu hararetli bicimde aktaricam hazir olun:) Yaziyi sonuna kadar takip etmenizi oneririm sonunda şaşırabilirsiniz...
Ozgur Macit arkadasimin deyimiyle;
Efendim gecen gun grubumuza bir mail geldi bi arkadasimiz tarafindan. Mail de herkesin bildiği bir swap islemi C/C++ dilinde farkli bir sekilde yazilmisti. Buyrun inceleyelim:

#include

int main(void)
{
int a = 3, b = 5;
a = a^b;
b = a^b;
a = a^b;

printf("%d\n", a);
printf("%d\n", b);

return 0;
}

// ^ XOR islemi bu arada :)
Alinti: Onur Dolu

Goruldugu gibi 3 tane XOR islemi yapilarak a ve b değiskenlerinin yeri değiştirimiş. Xor işlemi matematikte/programlamada çok işe yarıyor daha sonra başka örnekler yazmayı düşünüyorum da biz gelelim esas konuya: Bu kodu bilinen temp değişkeni üzerinden eski değeri saklayıp, daha sonra a ve b değişkenlerinin değerini değiştiren swap koduna tercih edilebilr mi?
Bu arada yukarıda yazılmış olan kod aşağıda ki şekilde de kısaltılabiliyor:

int a = 3, b = 5;
a ^= b ^=a ^=b;

Grupta bulunan sevdiğim bir arkadaşım bu koda doğal olarak karşı çıktı. Nedenini ise şu şekilde açıkladı:

"Okuması da oldukça zor oluyor..

Kod bir kere yazılır ama defalarca okunur..

Senden sonra programda değişlik yapması gereken bir programcı aşağıdaki satırı anlıyamıyabileceğ inden veya daha kötüsü yanlış anlıyabileceğinden saatler veya günler kaydebilir.. Proje başarızlığa uğrayabilir."...

Yukarıda aynen alıntısını aldığım yazı hakkında herhalde herkes fikir birliğine varmıştır. Bu kodu okumak matematik bilgisi çok iyi olmayan bir programcı için imkansıza yakın olduğu gibi, matematik bilgisi olan bir programci için de zaman alıcı ve can sıkıcıdır.

Bunun üzerine ne yapılabilir diye düşündüm. Kod daha efektif duruyordu. Yukardaki probleme bir çözüm üretmeden önce bunu teyid etmem gerekti ( Hazırsanız birazdan kendinizi sonu gelmeyen bir kaosun içinde bulacaksınız!! ) :

Test1 ( yeni swap )
#include //stdio gereksiz bu kodda ama printf koymustum kalmis oyle:)

int main(void)
{
int a = 3, b = 5;
int i;

for( i = 0; i < 100001; i++ ){
a ^= b ^= a ^= b;
}

return 0;
}

Bu kodun çalışması sonucunda şu değerler elde edildi:
Program Statistics
------------------
Command line at 2007 Jan 13 11:28: "D:\ITU\c++\fib\Debug\swap"
Total time: 17,024 millisecond
Time outside of functions: 15,794 millisecond
Call depth: 1
Total functions: 1
Total hits: 1
Function coverage: 100,0%
Overhead Calculated 3
Overhead Average 3

Module Statistics for swap.exe
------------------------------
Time in module: 1,231 millisecond
Percent of time in module: 100,0%
Functions in module: 1
Hits in module: 1
Module function coverage: 100,0%

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
1,231 100,0 1,231 100,0 1 _main (swap.obj)


Görüldüğü gibi döngü yaklaşık 1,231 milisaniye de tamamlandı.
Şimdi ikinci swap işlemini incelemeye geldi sıra. Bildiğmiz temp değişkeni üzerinden elde edilen swap....

Test1 ( klasik swap )
#include

int main(void)
{
int a = 3, b = 5;
int i, temp;

for( i = 0; i < 100001; i++ ){
temp = a;
a = b;
b = a;
}

return 0;
}

Evet heycanla bu kodu yazdım ve sonucu gerçekten çok merak ediyordum. Eğer tahminlerim doğruysa bu kodun çalışması en az 2 kat yavaş olacaktı çünkü fazladan bir temp değişkenine erişim vardı. Belleğe erişimin registerlar üzerinde xor işleminden çok daha fazla sürmesi gerekirdi. Şimdi sonuca bakalım:

Program Statistics
------------------
Command line at 2007 Jan 13 11:35: "D:\ITU\c++\fib\Debug\swap"
Total time: 2,228 millisecond
Time outside of functions: 1,538 millisecond
Call depth: 1
Total functions: 1
Total hits: 1
Function coverage: 100,0%
Overhead Calculated 3
Overhead Average 3

Module Statistics for swap.exe
------------------------------
Time in module: 0,690 millisecond
Percent of time in module: 100,0%
Functions in module: 1
Hits in module: 1
Module function coverage: 100,0%

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
0,690 100,0 0,690 100,0 1 _main (swap.obj)

Evet herkes gördü sonucu, bende gördüm, gördüm sonra gözlerime inanamadım, inanamadım bir daha çalıştırdım, çalıştırdım yine aynı sonucu gördüm, gördüm gözlerime inanamadım...

Sonuç beni hem hayal kırıklığına uğratmıştı hem de heycanlandırmıştı. Bu sonucu beklemediğim açıktı. Demek ki ya ben bi yerlerde yanlış yaptım, ya da...
Evet ya da derleyici de bir sorun vardı:) Bu arada derleyici MSVS 6.0

Ve derleyiciden şüphe duydum! Daha önceki tecrübelerimden biliyordum ki derleyici assembly kodunu oluştururken arada geçici bellek atamaları yapıyordu. Kodu tekrar yazmalıydım ama bu sefer inline assembly kullanacaktım, kalp atışlarım hızlanmıştı.

Ama, evet ama önce söylediğim şeyin gerçek olduğunu size göstermeliydim. Test1 kodunun disassemblysine baktım işte size de göstereyim ( sadece for döngüsü içinde ki tek satır xor işlemleri) :
00401041 mov ecx,dword ptr [ebp-4] <- varan 1
00401044 xor ecx,dword ptr [ebp-8] <- varan 2
00401047 mov dword ptr [ebp-4],ecx <- varan 3
0040104A mov edx,dword ptr [ebp-8] ....
0040104D xor edx,dword ptr [ebp-4] ....
00401050 mov dword ptr [ebp-8],edx ....
00401053 mov eax,dword ptr [ebp-4] ....
00401056 xor eax,dword ptr [ebp-8] ....
00401059 mov dword ptr [ebp-4],eax <- varan 9

Evet kod gerçekten beni "in a horror" vaziyetine düşürmüştü! ben saf ve masum bir şekilde registerlar da xor işlemi yapiyordum. Ama derleyici her işlem sonucunu bir bellek gözünde saklıyordu!!! bu ise performansı inanılmaz bir şekilde düşürüyordu. Gerçekten vs 6.0 dan korkmaya başlamıştım...

ve test2 deki temp kullanarak gerçekleştirilen 3 atama işlemi ile swap yaptığım kodu disassembly ettim ve işte sonuc:
9: temp = a;
00401041 mov ecx,dword ptr [ebp-4]
00401044 mov dword ptr [ebp-10h],ecx
10: a = b;
00401047 mov edx,dword ptr [ebp-8]
0040104A mov dword ptr [ebp-4],edx
11: b = a;
0040104D mov eax,dword ptr [ebp-4]
00401050 mov dword ptr [ebp-8],eax

Bu kod kesinlikle belleğe daha az erişiyordu. Aslında tam da yapması beklenen işlemi yapıyordu. önce a değişkenini ecx e atıyor sonra ecx i temp bellek gözüne atıyordu ve diğer a=b ve b=a içinde aynılarını yapıyordu.

test2 nin kodu bu kadar iyi çalıştığı halde test1 neden bukadar kötüydü? Şeytan beni iyice kodu inline assembly de yazmaya itiyordu...

Ama önce son bir kez daha brain storming yapmak istedim. Düşündüm... registerlar üzerinde xor işlemi yapmak istiyordum. Ama yazdığım kod registerlar üzerinde değil bellek üzerinde, bellekten değerleri registerlar a çekerek, daha sonra registerlar da gerçekleştirdiği xor işlemlerini tekrar belleğe yazarak gerçekleştiriyordu. Evet yazarken farkediyodum herşeyi, bir emreknlk nasil bu kadar dikkatsizce davranabilirdi, bir emreknlk bu hatayi nasil yapabilirdi!

VS 6.0.. O kadar günahını aldığım derleyici. Aslında ben ne söylüyorsam onu yapıyordu! Onun hiç bir suçu yoktu tek suçlu vardı o da emreknlk! Kodu yazarken dikkat ederseniz değişkenler int a ve int b olarak tanımlamıştım. Yani ben dedim ki: Git esp den ( stack pointer) 8 çıkar! Değişkenleri yığında oluşturuyordum!!! Yani bellekte! sonra nasıl olurda bütün işlemleri registerlar üzerinde yapmasını bekleyebilirdim ki... Bellekten a ve b yi alıp tekrar a ve b yi belleğe yazması gerekiyor derleyicinin çünkü ben ona öyle yap demiştim!

Peki şimdi İnline assembly de yazmama gerek varmıydı? İnline assembly de yazarsam kodun hızlanacağını biliyordum. Çünkü asm kodunu ben gömecektim C nin içine. Ama C nin de bana sunduğu yetenekleri göz ardı edemezdim.

Evet register anahtar sözcüğü ( keyword ) değişkenleri bellekte değil, eğer mümkünse registerlar da oluşturuyordu. hemen
int a, b; ifadesini register int a, b; ifadesi olarak değiştirdim.

Sonucu merak ediyor olmalısınız. Sonuç değişmedi... Bir kaos içinde kalmıştım. Düşündüğüm hiç bir şey çalışmıyordu. Başarısızlık ard arda geliyordu. Belki de beni C ye bu kadar bağlayan şey buydu.

Araştırmaya başladım. niye çalışmadı niye sonuç aynıydı. tekrar disassebly ye baktım sonuçta yine a ve b değişkeni registerlarda değil yığında oluşturulmuştu! peki bu nasıl olabilirdi? Oysa ben açıkça registerlarda oluştur demiştim değişkenleri. Sonunda kendimi msdn de buldum. işte açıklamaları:

"The compiler does not accept user requests for register variables; instead, it makes its own register choices when global register-allocation optimization (/Oe option) is on. However, all other semantics associated with the register keyword are honored."

Evet vs 6.0 register anahtar sözcüğü için bizi sallamıyordu. belki de güvenmiyordu. Bu C nin esnekliğinin bir yerde kaybolması demekti. Düşündüm, kodu linux de derlesem çalışacaktı. Bundan şüphem yoktu. register anahtar sözcüğü ile test1 de yazdığımız xor lu kod hızlı çalışacaktı.

Ama bir sorun vardı! Birden adil davranmadığımı anladım. test2 içinde temp, a ve b değişkenlerini register anahtar sözcüğü ile tanımlasam daha o daha da hızlı çalışacaktı. 3 register da sadece 3 atama işlemi. işte hız buydu...

Peki son bir çırpınış, bu yazıma başlarken hatırlarsanız kodun okunabilirliğini sağlamak için yapılması gerekenleri anlatmak ama önce o kodun hızlı çalışması gerektiğini ispatlamak istiyordum. hızlı çalıştığını ispatlamadan nasıl olurda bu kodu kullanın diyebilirdim ki size, üstelik daha da okunabilirliği azaltırken.

Evet iki koda da adil olarak davrandığım sürece her yola başvurmalıydım. register fikri çok iyi bir fikir değildi. Büyük programlarda bu yöntem patlayabilirdi. Şimdi geriye malesef tek bir çözüm kaldı. Bu çözüm de başarısızlığa uğrarsa... düşünmek bile istemiyorum.

Inline assembly
Evet heycan dorukta. Bu sefer vs60 var bir de ben varım...

işte test 1, xor işlemleri ile yapılan swap işlemi ( Not: bu kod main içinde tanımlanmış ama swap fonksyonu içerisinen alınabilir, testleri yapmak için bu şekilde yazdım) :

#include

int main(void)
{
int a = 3, b = 5;
int i;

for( i = 0; i < 100001; i++ ){

__asm{
mov eax, [a]
mov ebx, [b]
xor eax, ebx
xor ebx, eax
xor eax, ebx
mov [a], eax
mov [b], ebx
}

}

return 0;
}

Gördüğünüz gibi asm kodu visual studio 6.0 içinde main içinde duruyor. şimdi bakalım sonuca:

Profile: Function timing, sorted by time
Date: Sat Jan 13 12:50:05 2007


Program Statistics
------------------
Command line at 2007 Jan 13 12:50: "D:\ITU\c++\fib\Debug\swap"
Total time: 1,702 millisecond
Time outside of functions: 1,112 millisecond
Call depth: 1
Total functions: 1
Total hits: 1
Function coverage: 100,0%
Overhead Calculated 3
Overhead Average 3

Module Statistics for swap.exe
------------------------------
Time in module: 0,589 millisecond
Percent of time in module: 100,0%
Functions in module: 1
Hits in module: 1
Module function coverage: 100,0%

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
0,589 100,0 0,589 100,0 1 _main (swap.obj)

Evetttt, işte bu mudur? budur dedirten sonuç kendini gösterdi!!! 0.589 milisaniye şu ana kadar elde edilen en iyi süre. Şimdi biraz sevinç duyuyorum ama daha herşey bitmedi diğer kodu da bu şekilde yazıp sonuçları karşılaştırmam gerek.

işte temp kullanılarak gerçekleştirilen swap işleminin inline assembly li hali:
#include

int main(void)
{
int a = 3, b = 5;
int i,temp;

for( i = 0; i < 100001; i++ ){

__asm{
mov eax, [a]
mov [temp], eax ; a nin degeri temp de
mov ebx, [b]
mov [a], ebx ; b nin degeri a da
mov eax, [temp]
mov [b], eax ;temp in degeri b de
}

}

return 0;
}

ve sonuç geliyor:

Profile: Function timing, sorted by time
Date: Sat Jan 13 12:56:28 2007


Program Statistics
------------------
Command line at 2007 Jan 13 12:56: "D:\ITU\c++\fib\Debug\swap"
Total time: 21,834 millisecond
Time outside of functions: 21,197 millisecond
Call depth: 1
Total functions: 1
Total hits: 1
Function coverage: 100,0%
Overhead Calculated 3
Overhead Average 3

Module Statistics for swap.exe
------------------------------
Time in module: 0,637 millisecond
Percent of time in module: 100,0%
Functions in module: 1
Hits in module: 1
Module function coverage: 100,0%

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
0,637 100,0 0,637 100,0 1 _main (swap.obj)


Evet en sonunda istediğim sonuç... 0.637 milisaniye . Biraz acımasız davrandım ikinci swap a kabul ediyorum ama en iyiye ulaşmak kolay olmuyor tabi :))

Dahası var...
inline assembly kullanarak temp i de atabilirz! işte 3. yol:

#include

int main(void)
{
int a = 3, b = 5;
int i;

for( i = 0; i < 100001; i++ ){

__asm{
mov eax, [a]
mov ebx, [b]
mov [a], ebx ; b nin degeri a da
mov [b], eax ; a nin degeri b de
}

}

return 0;
}

ve işte en kısası şimdi geliyorrrr :)
Profile: Function timing, sorted by time
Date: Sat Jan 13 13:00:59 2007


Program Statistics
------------------
Command line at 2007 Jan 13 13:00: "D:\ITU\c++\fib\Debug\swap"
Total time: 1,597 millisecond
Time outside of functions: 1,095 millisecond
Call depth: 1
Total functions: 1
Total hits: 1
Function coverage: 100,0%
Overhead Calculated 4
Overhead Average 4

Module Statistics for swap.exe
------------------------------
Time in module: 0,501 millisecond
Percent of time in module: 100,0%
Functions in module: 1
Hits in module: 1
Module function coverage: 100,0%

Func Func+Child Hit
Time % Time % Count Function
---------------------------------------------------------
0,501 100,0 0,501 100,0 1 _main (swap.obj)

Yani bu yazıdan çıkaracağımız pek çok sonuç var, ama en önemlisi vazgeçememek bana sorarsanız...

Sonuç olarak gelmek istediğim, asıl anlatmak istediğin noktaya gelemedim aslında, yazımın amacı kodu okunabilir yapmaktı. Bu konu hakkında bir cümleyle şunu söyleyebilirim ki: eğer elinizde daha efektif bir kod varsa, ve bu kodun okunabilirliği diğer algoritmalara göre daha kötüyse, o kodu, isminden görevinin anlaşılacağı bir fonksyon içerisine gömmek ( tek satır olsa dahi kodunuz) ve programınızı yazarken o koda ihtiyacınız olduğu yerde yazdığınız fonksyonu çağırmaktır. Fonskyonun ismini güzelce belirlerseniz, kodunuzu okuyanın fonksyon içerisinde yazdığınız kodu okuması gerekmeyecektir. Black box olara düşünülebilir fonksyonunuz.

Bir başka önemli nokta da, burada kodu zamanlama bakımından değerlendirdik. Günümüz bilgisayarlarında bellek sorunu olmamaktadır. ANCAK, gömülü sistemlerde, gerçek zaman sistemlerinde ciddi bellek kısıtlamaları vardır. Bu durumda 4 byte lık bir temp değişkenini bile kullanmak istemeyebilirsiniz. Bu durumda xor ile swap işlemi yapmak gerçekten işinize gelebilir. Kodu da büyük ihtimalle assembly ile yazacağınız için bu yöntem daha efektif olacaktır.

Yazı biraz uzadı ama ben yazarken gerçtekten keyif aldım, umarım sizde sıkılmamışsınızdır. Sonraki yazılarımda görüşmek dileğiyle...

2 comments:

Unknown said...

Performansı daha iyi fakat okunması güç algoritmaları ayrı bir fonksiyon içinde yazıp kara kutular haline getirmek fikri, swap gibi işlevi kolay kolay değişmeyecek bir işlem için iyi bir yöntem olabilir, fakat ya bu algoritmamızı değiştirmemiz veya daha kötüsü başka bir yazılımcının değiştirmesi gerekirse, o zaman ne olur??

Fazla zorlama... Simple is the best...

blkn

emreknlk said...

Evet balkan bende görüşüne katılıyorum. Algoritmamız yeterince modüler tasarlanmışsa, swap gibi işlemler bu şekilde ele alınabilir, dahası, günümüz de yazılımcılık daha çok hazır kütüphane fonksyonlarının kullanılması şekline döndü, çoğu modülü parayla dışardan library ler halinde alıp kodumuz da kullanıyoruz. Burada da bir kara kutu yaklaşımı var aslında. projenin geleceğini iyi görmek gerek kod kullanırken/yazarken. yine de okunabilirlik ve performans arasında bir denge kurulması şart. Bir taraftan kazanırken diğer taraftan feragat ediyoruz...