Java'da Object Layout Optimizasyonu

Java, diger bir suru dilde oldugu gibi, objelerin calisma zamaninda cache'e daha duzgun alinmasi ve VM'in bellek yonetimini daha duzgun yapabilmesi icin bazi object layout optimizasyonlari yapar.

Object layout optimizasyonu, objenin bellekteki yapisinin yukaridaki saydigim sebeplerden dolayi, bizim yazdigimiz halden biraz daha degisik olmasi demek :). Bu yapi temelde 3 kisimdan olusur;

  1. Header: Objeyle ilgili metadatanin tutuldugu alan. hashCode()'dan donen garip sayi, obje uzerindeki lock bilgisi gibi JVM'in isine yarayan bilgiler burada tutulur.
  2. Objenin icindeki alanlar: Bunlar datayi tutan kisimlar.
  3. Padding alanlari: Bunlar da JVM'in optimizasyon icin objenin sonuna ya da ortasina koydugu bos alanlar.

(Bunlari incelemek icin, bagimsiz bir proje olarak baslayip sonradan OpenJDK icine dahil edilmis JOL'u kullaniyorum)

Diyelim ki asagidaki gibi bir sinif var

Bunun bellekteki yapisina bakinca asagidaki gibi oldugu goruluyor;

Baslangic adresi boyut alan
0 12 (object header)
12 1 boolean A.a
13 3 (loss due to the next object alignment)

Kodu calistiran JVM'in tipine gore header alaninin buyuklugu ve objelerin kacar byte'lik bloklar seklinde tutulacagi (bu ornekte 8 byte) farklilik gosterebilir.

Yukaridaki ornek cok sacma gorunuyor. Yani biri neden tek boolean alani icin bir class olustursun diyoruz ama aslinda bu basit siniflar bizim surekli olarak kullandigimiz, hatta Java Generics ile birlikte daha da cok kullandigimiz (Stream, Optional gibi yapilar, Lombok vs.) Integer, Long gibi primitive wrapper siniflara denk geliyor.

Son olarak asagidaki gibi kodun ciktisinda aradaki fark gorulebilir.

arrayOfObjects  24M byte yer kaplarken arrayOfLongs  8M byte yer kapliyor.

Buraya kadar cok da olaganustu bir sey yok aslinda. Bir sonraki post'ta inheritance nasil calisiyor onu yazayim. JVM'in asil cuvalladigi kisim orasi :)

O Canada

Bugun Kanada'ya gocusumuzun 45. gunu. Sevgili gunluklu bir sey yazmadim hic simdiye kadar ama bugun bi sevincliyim; sonunda kendi evimizi kiraladik bugun :) Artik buraliyiz diyebilirim yani. Artik benim de burada her ay odeyecegim gul gibi faturalarim, kiralarim var.

Buraya not dusmus olayim :)

Project Euler 114

114 epey kısa ama güzel bir Project Euler sorusu; Elimizde n uzunluğunda bir sıra var. Bu sıradaki elemanları siyaha ya da ardışık olarak en az 3 hücre olacak şekilde kırmızıya boyamak istiyoruz, kaç farklı şekilde boyayabiliriz?

Ben şöyle bir yol izledim; \(F(n, k)\) şeklinde bir fonksiyon olsun ve bu fonksiyon \(n\) uzunluğunda ve son \(k\) hücresi kırmızı olan sıraların sayısını tutsun. Fonksiyon için aşağıdakileri yazabiliriz:

  • 3'ten daha kısa kırmızı alt sıra olamayacağından \(F(1, 0) = 1\) ve \(F(2, 0) = 1\). Ayrıca aynı mantıkla tüm \(n\) değerleri için \(F(n, 1) = 0\) ve \(F(n, 2) = 0\).
  • \(F(i, 0) = \sum\limits_{k=0}^{i-1} F(i-1, k)\). Yani, \(n-1\) uzunluktaki herhangi bir sıranın sonuna ancak 1 siyah hücre ekleyerek onu \(n\) uzunlukta ve sıfır kırmızı hücre ile biten bir sıra yapabiliriz.
  • \(n\) uzunlukta ve \(k\) tane kırmızı hücre ile biten sıra sayıları, \(n-k\) uzunlukta ve 0 kırmızı hücre ile biten sıra sayılarına eşittir. Çünkü 0'dan daha fazla kırmızı ile biten sıra sayılarını da dahil edersek, \(k\)'dan daha fazla kırmızı hücre ile biten sıraları da hesaplamış oluruz.

Bu üç maddeye göre \(F(n, k)\) fonksiyonunun değerlerini hesapladığımızda cevap

\[\sum\limits_{i=0}^{50} F(50, i)\]

toplamının sonucu olacak.

Amcalar ve Şapkalar

Dün akşam bir tane soruya denk geldim. Bir tane şirket soruyu yazmış, bunu çözebiliyorsanız başvurun falan demiş. Soru şu şekilde;

8 tane amca var, kağıtlara kendi isimlerini yazıp bir kutuya atıyorlar. Sonra hepsi kutudan rastgele bir kağıt çekiyor. Bu da herkes kendi adından farkli bir kağıt çekene kadar devam ediyor. Herkesin kendi adından farklı kağıt çekme olasılığı kaçtır?

Brute force çözüm olarak düşününce elimizde toplam \({n!}\) tane olasılık var, yani isimleri \({n!}\) farklı şekilde atayabiliriz. Tüm permütasyonları oluşturup başarılı permütasyonlari sayarsak olasılığı da, çıkan toplamı \({n!}\)'e bölerek bulabiliriz. Yani aşağıdaki gibi.

Kodu en kısa nasıl olabilir diye yazdığım için performans olarak idealden uzak. Bu haliyle \(n=9\) için de hesaplayabildim ama \(n=10\) için epey zorlandı.

Peki \(n > 9\) gibi durumlar için ne yapabiliriz? Burada tüm olasılıkları hesaplamak artık biraz zorlaşıyor. Onun yerine bir fonksiyon tanımlayip soruyu daha kısa zamanda cözebiliriz.

Diyelim ki \(D\) matrisi, \(n\) elemanli bir durum için \(k\) elemanın kendi adını çektiği durumları içeren bir matris olsun. Burada şöyle ön çıkarımlar yapabiliriz;

- \(0\) elemanlı her durum için sonuç sıfırdır, yani \(D_{0, i} = 0, i = 0 .. n\)
- Herhangi bir durumda herkesin kendi ismini bulduğu durumlarin sayisi \(1\)'dir, yani \(D_{i, i} = 1, i = 1 .. n\).

Bu durumların dışında ise şunu söyleyebiliriz; \(D_{i, k}\) bize \(i\) elemanın olduğu durumda \(k\) elemanın kendi adını bulduğu, diğerlerinin yani \(i-k\) elemanın ise kendi adından farkli adları bulduğu durumların sayısını versin. Burada \(k\) elemanı\(\binom{i}{k}\) farklı şekilde seçebiliriz. Her bir seçenek icin geriye kalan \(i-k\) eleman ise kendi adından farklı bir adı seçecek. Bu da aslında bizim fonksiyonumuzdaki \(D_{i-k, 0}\) sonucuna denk geliyor. Yani formülünü yazarsak;

\[D_{i, k} =\binom{i}{k} * D_{i-k, 0}\]

Burada tek istisnai durum ise şu; \(k = 0\) durumunda ne yapacagiz? \(k = 0\) iken denklem

\[D_{i, 0} =\binom{i}{0} * D_{i, 0}\]

oluyor yani sonsuz döngüye giriyor. Bundan da şu şekilde kurtulabiliriz; daha öncesinde tüm olası \(D_{i, k}\) değerlerini hesaplamıştık. \(D_i\) satırındaki değerlerin toplamı, \(i\) elemanlı durum için permütasyon sayısını veriyor. \(D_{i, 0}\) değerini de bu mantığı kullanarak

\[D_{i, 0} ={i!} - \sum\limits_{k=1}^i D_{i, k}\]

formülüyle hesaplayabiliriz.

Bunun da kodunu kısa olsun diye uğraşarak aşağıdaki gibi yazdim

Kodlarda ya da mantığımda herhangi bir hata var mı sizce?

Git'te Commit Büyüklüğünü Kontrol Etme

Bugün hem kendim inceleyeyim, hem de bizim takımdaki arkadaşlara önereyim diye bir code review makalesi arıyordum ki şuna denk geldim.

İlk iki madde review'ın büyüklüğüyle alakalı. Yani diyor ki 1000 satır kodu incelemeye çalışmayın, yazılımcıysanız da bir commitiniz 1000 satır olmasın mümkünse. Bu kriter gayet basit bir şekilde kontrol edilebilir geldi. Kontrol için de github'da bir repo oluşturup yazdığım hooku oraya attım.

git diff --stat  gerçekten benim düşündüğüm gibi mi çıktı veriyordur bilmiyorum, hata çıkarsa değiştiririm. Kullanırım ben bunu :).