Duff’s Device

İlk bakışta anlaşılması zor olan aşağıdaki kod Duff’s Device olarak anılıyor. Yaptığı iş bir adresten başka bir adrese kopyalama yapmaktan başka bir şey değil.

İsmini Tom Duff‘tan alan bu işlevi anlaşılması zor kılan taraflarından biri tanımının K&R biçimi (eski biçim) ile yapılmış olması. İşlevin argümanlarından biri memory mapped giriş-çıkış pini olduğu için kopyalama sırasında hedef göstericinin değeri artırılmıyor. Şimdilik bunları ve koddaki register anahtar sözcüğünü görmezden gelelim.

Yukarıdaki tanımda a değişkenin türü örtülü (implicit) olarak int kabul ediliyor. Örtülü int özelliği C99 standartları ile dilden çıkarıldı.

Şimdi yukarıdaki kodu adım adım anlamlandırmaya çalışalım:

Bir nedenden ötürü aşağıdakine benzer, bir adresten başka bir adrese kopyalama yapan bir işlev yazmamız gereksin:

mycopy işlevi çağırıldığında, argüman olarak n‘e geçilen değer kadar int türden nesne kaynak adresten başlayarak hedef adrese kopyalanıyor.

Bu süreçte döngü değişkeninin değeri n + 1 kez azaltılıyor ve döngü değişkeninin sıfırdan büyük olma durumu n + 1 kez kontrol ediliyor.

Şimdi de n‘in 10000, 50000 hatta 1000000 olduğunu düşünelim. n 1000000 olduğunda döngü değişkeni 1000001 defa azaltılacak, 1000001 defa değeri kontrol edilecek.

Aslında biraz hayal gücüyle, kendimizi, bu işlevin maliyetini azaltmak zorunda kalacağımız, sonuç olarak bu işlemleri azaltmak isteyeceğimiz bir duruma sokabiliriz.

Genel olarak döngünün maliyetini azaltmak için döngüyü açabiliriz. Yani döngünün her turunda bir adet kopyalama yapmak yerine aşağıdaki gibi bir kodla her turda 4 adet kopyalama yapabiliriz. (Aşağıdaki kod için döngü açma katsayısı 4 seçilmiş, Duff’s device için bu sayı 8.)

Bu şekilde n / 4 kez dönen bir döngü içinde, döngü değişkenini n / 4 kez azaltmış, döngü değişkeninin 0‘dan büyük olma durumunu n / 4 kez kontrol etmiş oluruz. Yine de n adet int‘i kopyalamış oluruz. (Döngüyü açmak için başka motivasyonlarımız da olabilir ama şimdilik buna da takılmayalım.)

Döngü açma (loop unrolling) tekniği hangi durumlarda uygulanabilir? 2016 yılında döngü açmak gerçekten maliyeti azaltır mı gibi soruları bir kenara bırakalım ve en son yazdığımız kodun neden hatalı olduğunu düşünelim.

n değişkeni 4’e tam bölünebilen bir sayı değilse ne olur? Yani işleve 3. argüman olarak 4’e tam bölünemeyen bir sayı geçilirse ne olur? Toplamda n adet int kopyalanması gerekirken, n – (n % 4) adet int kopyalanır. Yani n‘in 4’e bölümünden kalan gözardı edilecek.

Arta kalan kopyalama işlemlerini gerçekleştirmek için basit bir switch deyimi eklenebilir.

switch deyiminin gövdesinin break deyimi içermemesine ve deyimin gövdesinde n % 4 adet kopyalama gerçekleştiğine dikkat edin. Kodu bu şekilde de bırakabiliriz ama kodun boyutunu iyice artırmış olduk. Döngünün içindeki kopyalamadan sorumlu kodları switch deyiminin içinde tekrar yazdık. Belki bu kadar kod tekrarından kaçınabiliriz.

Aslında döngünün ilk turunda, döngü gövdesinin içinde istediğimiz yere sıçrayabilirsek, arta kalan kopyalama işlemlerini gerçekleştirebiliriz. Bu turda n % 4 adet kopyalama işlemi gerçekleşmeli ve n % 4 ‘ in değerine bağlı olarak tam bir tur olmayacak.

Döngünün içinde goto etiketleri tanımlayıp döngünün içinde istediğimiz yere sıçramamızı engelleyen bir kural yok. Aşağıdaki gibi bir kod, yazılması tavsiye edilmese de geçerli. C dilinin bu konuda bir kısıtlaması yok.

Program çıktısı: 11 12 13 14

O zaman kodumuzu aşağıdaki gibi düzenleyebiliriz:

Döngünün kontrol ifadesinin artık n_times– > 0 olmadığına dikkat edin. Bunun sebebi döngünün ilk turunda döngünün kontrol ifadesinin yürütülmeyecek olması. Yani ilk turda –n_times işlemi yürütülmeyecek çünkü doğrudan döngü gövdesinin içine sıçradık. n % 4 == 0 olması durumunda ilk tur tam tur olarak tamamlanacak (4 adet kopyalama gerçekleşecek) fakat döngü değişkeni azaltılmamış olacağı için ön ek -– operatörünü kullandık.

Kodda bir değişiklik daha oldu.

size_t n_times = (n + 3) / 4; //eski hali size_t n_times = n / 4;

Ön ek – – operatörünü kullandığımız için bu işleme gerek duyduk. Ön ek – – operatörü kullanılınca döngünün n_times – 1 defa döneceğine dikkat edin. Bu sayıya döngünün ilk turu dahil değil. Yani n 4’ün tam katı olursa ilk turda 4 adet kopyalama gerçekleşecek, ilk tur tam tur olarak tamamlanacak ve sonrasında döngü n_times – 1 defa dönecek. Toplamda n_times tur tamamlanmış olur(4 adet kopyalama gerçekleşmesi turu tam tur yapıyor) ve bütün int’lerin kopyalanması başarı ile gerçekleşmiş olur.

n % 4 == 0 doğru değilse ne olur? İlk turda arta kalan int’ler kopyalanır, ilk tur tam bir olarak tamamlanmaz  sonrasında döngü n_times – 1 defa döner. Fakat biz n_times kere dönmesini istiyoruz daha doğrusu n / 4 kez dönmesini istiyoruz.

(n + 3) / 4 işleminin sonucunun her iki durumda da döngünün istediğimiz kadar dönmesine neden olacağına dikkat edin.

n 4’e tam bölünüyorsa toplama işlemi sonucu etkilemiyor kod yukarıda açıklandığı gibi çalışıyor, n 4’e tam bölünmüyorsa toplamı işlemi, sonucun n / 4 + 1 olmasına neden oluyor. Böylece n‘in 4’e tam bölünememesi durumunda ilk turda arta kalan int’ler kopyalanıyor, sonrasında döngü n / 4 kez dönüyor. Bu değişikliğin daha iyi anlaşılması için n’e farklı değerler vererek işlemin sonucunun kontrol edilmesini okuyucuya bırakıyorum. Sonuç olarak burada yaptığımız n’in 4’e bölümünden kalanların da bölme işleminin sonucuna etki etmesini sağlamak.

Bu haliyle n‘in 0 olması durumunda kodun doğru çalışmayacağını not düşelim. (Acaba bu sıkıntıyı da giderebilir miydik?) Aynı sıkıntı Duff’s device için de geçerli.

Şu goto‘lardan kurtulabilseydik kod daha sade olurdu, hem de ekstra sıçramaların maliyetini ödememiş olurduk.

Burada switch deyiminin case‘leri bir aracı durumunda, ilgili case döngü içinde ilgili etikete sıçrama görevini üstlenmiş. Bunu doğrudan switch deyimi ile yapamaz mıydık? Yani goto‘lardan kurtulup switch‘in ilgili case‘lerini döngü içindeki goto etiketleri yerine yazabilseydik sorunlarımız çözülebilirdi. Bu durumda döngüyü switch deyiminin gövdesi içine almamız gerekirdi.

Şimdi bir de aşağıdaki koda bakın, Duff’s device burada devreye giriyor.

İlk bakışta böyle bir kodun derleme zamanında hata vermemesi mümkün görünmeyebilir ama kodda herhangi bir sentaks hatası yok.

Karışıklığa sebep olan switch deyiminin sentaksının aşağıdaki gibi olması gerektiği düşüncesi.

Halbuki standartlarda belirtilen sentaks aşağıdaki gibi:

Bu deyim tek bir deyim de olabilir, birden fazla deyim de olabilir, deyimlerin gövdesi de olabilir ve en önemlisi switch deyiminin case‘leri bu gövdelerin herhangi birinde olabilir. Bununla ilgili bir kısıtlama yok.

Aynı bilinirlik alanı içinde aynı case‘den birden fazla olamaz, farklı bilinirlik alanlarında fakat aynı kapsayan bloğun içinde aynı caseden birden fazla olması halinde en kapsayan bloktaki case dikkate alınır. Yani bir switch deyimi içinde başka bir switch deyimi bile olabilir.

Burda yazdığımız kodla Duff’s device arasında farklılıklar var fakat temel ilke aynı. Bunların bazılarını inceledik. Kalan farklılıkları incelemeyi egzersiz olarak okuyucuya bırakıyorum.

  • Bonus:

Bonus olarak C++ programcıları için algorithm başlık dosyasındaki find işlev şablonları için yazılan yardımcı bir işlev şablonunun koduna bakalım.

Aşağıdaki kod __find_if işlev şablonunun random access iteratör overload’ının basitleştirilmiş hali. (Yardımcı işlev olan __find_if‘den bahsediyoruz, std::find_if ile karıştırmayın. __find_if işlev şablonunun kodu libstdc++’a aittir.)

Döngü açma tekniği uygulanan bu kodu kodu Duff’s device‘laştırmaya çalışalım.

Yukarıdaki kod doğru çalışmayacaktır. Hatayı görebiliyor musunuz?

Peki şimdi doğru çalışır mı?

 

Kaynaklar:
C89, C99 Standartları
https://www.lysator.liu.se/c/duffs-device.html
http://www.azillionmonkeys.com/qed/case2.html
http://c-faq.com/misc/duffexpln.html
libstdc++

 

Bunlar da ilginizi çekebilir

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Kod Eklemek İçin Okuyun