- Bağlantı izleme sistemindeki ICMP Echo Request kayıt yapısı küçültülürken ring buffer bellek kullanımı 12KiB'den 4KiB'ye düştü
sent_ns ve received_ns değerlerini birlikte saklamak yerine, alımdan sonra yalnızca gecikme süresi bırakacak şekilde union kullanınca dizi boyutu 8KiB'ye indi- Nanosaniye hassasiyeti yerine 100 mikrosaniye birimi kullanıldı ve
received bir bit alanına çevrildi, ancak struct padding nedeniyle ek tasarruf sağlanmadı
- Kaynak adresi yerine ICMP
identifier alanının bir kısmı 4 bitlik sayaçla değiştirildi; böylece yapı 8 bayta indi ve 512 elemanlı dizi 4KiB oldu
- Uygulamanın bellek kısıtı olmadığı için bunun pratik bir zorunluluğu yoktu, ama alan yerleşimi ve bit erişim maliyetine kadar inen bir optimizasyon deneyi oldu
Sorunun kurulumu: ping kayıtlarını saklama yöntemi
- Bağlantı izleme sistemi, birden çok sunucuya ICMP Echo Request gönderiyor ve 1 dakika, 5 dakika, 15 dakika aralıklarında gecikme ile paket kaybı ortalamalarını gözlemliyor
- İlk düşünülen saklama yöntemi 512 girişli bir ring buffer'dı; her giriş gönderim zamanı, alım zamanı, kaynak adresi, sıra numarası ve alınıp alınmadığı bilgisini tutuyordu
- Başlangıçtaki
pings_rb[512] struct dizisinin boyutu 12KiB olarak ölçüldü
struct ping_timestamp {
uint64_t sent_ns;
uint64_t received_ns;
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
İlk tasarruf: gönderim zamanı ile geçen süreyi union içinde birleştirmek
- Aslında tutulmak istenen değer, alımdan sonraki
received - sent gecikmesidir; bu yüzden gönderim zamanı ile geçen süreyi aynı anda saklamaya gerek yoktur
sent_ts ile elapsed_ts değerlerini bir union içinde birleştiren yapı, aynı slotu gönderim öncesinde gönderim zamanı olarak, alım sonrasında ise geçen süre olarak kullanır- Bu değişiklikten sonra 512 elemanlı dizinin boyutu 12KiB'den 8KiB'ye düştü
struct ping_timestamp_2 {
union {
uint64_t sent_ts;
uint64_t elapsed_ts;
};
in_addr_t source_addr;
uint16_t seq_no;
bool received;
};
İkinci deneme: hassasiyeti azaltmak ve bit alanı kullanmak
- Ping süreleri onlarca, yüzlerce, binlerce milisaniye düzeyinde ölçüldüğü için nanosaniye hassasiyetinin tamamını saklamaya gerek yok
- Zaman birimini 100 mikrosaniye, yani 0.1ms olarak değiştirince 43 bit ile en fazla 20 yıl boyunca ping takibi yapmak mümkün oluyor
received için doğru/yanlış değerine 8 bit ayırmak fazla olduğundan bit alanı uygulandı- Ancak
ping_timestamp_3 dizisinin boyutu da 8KiB olarak kaldı ve ek bir tasarruf oluşmadı
struct ping_timestamp_3 {
uint64_t sent_or_elapsed_ts: 43;
uint64_t received: 1;
uint64_t seq_no: 16;
in_addr_t source_addr;
};
Struct padding yüzünden küçülmeyen boyut
ping_timestamp_2, sonda hizalama gereksinimini karşılamak için padding baytları içeriyorping_timestamp_3, ilk 8 bayta zaman, alım durumu ve sıra numarasını yerleştiriyor, ama sonrasında kaynak adresi ve padding kalıyor- Bit alanı uygulanmış olsa da 36 bitlik padding kaldığı için struct'ın toplam boyutu küçülmüyor
- Sadece bool değerini bite indirmek, bellek yerleşimi ve hizalama sorunlarını tek başına çözmüyor
Kaynak adresini kaldırmak ve 4 bitlik sayaç kullanmak
- Ürün mobil veri ağında çalışırken kaynak adresi sık değiştiği için mevcut yapı kaynak adresini saklıyordu
- Adres değiştiğinde sıra numarası da sıfırlanıyor ve geçmişte farklı kaynak adreslerine sahip ama aynı sıra numarasını taşıyan paketler aynı anda işlenmişti
- ICMP Echo Request içinde, uygulamanın kendi gönderdiği paketi tanıyabilmesini sağlayan 16 bitlik
identifier alanı bulunuyor
- 16 bitin tamamını kullanmaya gerek olmadığından, boşta kalan 4 bit kaynak adresi değiştiğinde artan döngüsel sayaç olarak kullanıldı
- Bu sayaç, uygulamanın başka bir yerinde izlenen kaynak adresi değişikliklerine göre artırılıyor
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t received : 1;
uint64_t counter: 4;
uint64_t seq_no: 16;
};
Nihai sonuç ve alan yerleşimi
- Nihai yapı kaynak adresi alanını kaldırıyor ve 64 bit içine zaman, alım durumu, sayaç ve sıra numarasını sığdırıyor
- 512 elemanlı ring buffer dizisinin boyutu 4KiB oluyor ve veri tek sayfaya düşüyor
- Başlangıçtaki 12KiB'ye kıyasla toplam 8KiB tasarruf sağlanıyor
- Alan sırası,
seq_no 16 bit sınırına hizalanacak şekilde ayarlanmış; böylece yükleme sırasında kaydırma olmadan tek bir ldrh komutuyla okunabiliyor
elapsed_or_sent_ts okunurken yalnızca maskeleme gerekiyor
Ek optimizasyon: alım biti erişim maliyetini azaltmak
struct ping_timestamp {
uint64_t elapsed_or_sent_ts : 43;
uint64_t counter: 4;
uint64_t not_received : 1;
uint64_t seq_no: 16;
};
Sonuç
- Optimizasyon sonucunda bellek kullanımı 12KiB'den 4KiB'ye indi, ancak uygulamanın kendisi bellek kısıtı altında değildi
- Gerçek ihtiyaçtan bağımsız olarak bu, struct layout, padding, bit alanları ve komut seviyesi erişim maliyetlerini inceleyen bir deney oldu
- Son notta, “sorun” ifadesinin de gevşek kullanıldığı ve hatta benchmark bile yapılmadığı belirtiliyor
1 yorum
Lobste.rs görüşleri
Böyle problemleri düşünmenin artık eğlenceli gelmediği gün gelirse, o günün programlamayı bırakacağım gün olduğunu düşünürüm
Erken optimizasyon her zaman eğlencelidir
Ama o optimizasyonun neden erken olduğunu fark ettikten sonra ortaya çıkan sonuçlarla uğraşmak genelde eğlenceli değildir
Zaman damgası için 43 bit kullanılması kısmı biraz kafa karıştırıcı. 24 bit yeterli gibi görünüyor
512 öğelik bir ring buffer’dan bahsettiğine göre her 2 saniyede bir yeni ping gönderiliyor ve son 17 dakika 4 saniyedeki ping’ler takip ediliyor gibi görünüyor
İlk adım olarak ideal zamanlayıcı/sıra numarasına karşı delta encoding kullanılabilir. Son gönderim zamanını 2’şer saniye artırıp ring buffer indeksine bakarsan paketin ne zaman gönderilmesi gerektiğini kolayca anlarsın; sonra da tam zamanında mı gönderildi, 0.1 ms mi gecikti, 2.3 ms mi gecikti gibi şeyleri kaydedebilirsin
Geçen sürenin de ping ondan sonra süresi dolacağı için 17 dakika 4 saniyeyi aşmasına gerek yok gibi duruyor. 512 × 2s = 10,240,000 × 100μs olduğundan, bu hassasiyette yaklaşık 23.3 bit yeterli; istenirse 24 bite yuvarlanabilir. Geriye kalan yaklaşık 6,536,216 geçersiz bit deseni de belki başka amaçlar için kullanılabilir
Ek olarak, 24 bit ile “gönderildi” hassasiyeti çok daha artırılarak kuantalama hatası azaltılabilir. Mikrosaniye hassasiyetinde bile ping en fazla 16 saniye geç gönderilebilir, bu da fazlasıyla yeterli görünüyor
Örnekleri 64 bitten 48 bite düşürmenin performansa yardımcı mı yoksa zararlı mı olacağını bilmiyorum. x86 ve ARM’in 32 bit/64 bit ortamlarında sonucun farklı çıkmasına şaşırmam
Ama özgün boyut zaten oldukça eski işlemcilerin veri önbelleğine bile çok rahat sığacak kadar küçük, bu yüzden bellek tasarrufunun fark yaratacağını sanmıyorum
Erken optimizasyonu yapmamızın sebebinin tam da bu olduğuna eminim. Bu, eğlence için yapılan bir spor
Sistem tasarlarken ya da düşük seviyeli sistem dilleriyle çalışırken erken optimizasyon dürüst olmak gerekirse en sevdiğim şeylerden biri
En azından sonradan zaman ve bellek kazandıracağına dair bir umut var. Orta karar sonuç, “bunu neden böyle yaptım?” diye anlamaya çalışırken biraz daha fazla baş ağrısı çekmek oluyor; en kötü durum, ama bazen daha iyi olanı da bu, tasarım sırasında optimizasyon işinin o kadar büyümesi ki projenin kendisini artık yapamamak. “Ah, bu fazla dolaştı, ben bunu neden yapıyorum ki?” deyip programı kapatıyorsun