Ali Çehreli
Posted in reply to Salih Dincer
| On 6/1/22 22:16, Salih Dincer wrote:f
>> Bir dinamik diziye `nextpow2()` algoritmasına göre bellek tahsis
>> edilir
Hem her zaman doğru değil hem de iyi bir algoritma değildir.
- Doğru değil çünkü D runtime, dizinin hemen sonrasındaki yer boşsa, hiç ikinin kuvvetini göz önüne almadan onu da kapasiteye ekleyiverir.
- Belki .dup ikinin kuvvetini kullanıyordur ama kendi başına büyüyen dizilerin %50 oranında büyümesinin bellek kullanımı açısından daha etkili olduğu gösterilmiştir. (D'de veya başka dilde.)
> öte yandan, dizeler böyle davranmıyor, yanlış mı anladım?
Dizeler de dizi olduğundan aynı olmasını beklerim. Denemek gerek... Aşağıda deneyince farklı bir algoritma kullanıldığını görüyorum. Ama bence bu elemanlar 1 bayt olduğundan olmalı. Yani, hizalama (alignment) işin içine giriyor olabilir. (Aşağıdaki programı byte için de deneyeceğim.)
>> Ayrıca .ptr en güncel ilk elemanın adresini tutuyor, öyle mi?
En güncel demeyelim de dizinin ilk elemanının adresidir. Eski .ptr değeri başka bir dizinin ilk adresi olarak yaşıyor olabilir. (Çöp toplayıcının emrinde.)
Aşağıdaki program kapasitenin değiştiği noktaları gösterir.
import std.stdio;
import std.range;
import std.format;
void main() {
dene!(int[])();
dene!string();
dene!(byte[])();
}
void dene(DiziTürü)() {
writefln!"\n--- %s ---"(DiziTürü.stringof);
DiziTürü dizi;
size_t kapasite;
enum sınır = 10_000_000;
while (kapasite < sınır) {
dizi ~= ElementType!DiziTürü.init;
if (dizi.capacity != kapasite) {
const fark = dizi.capacity - kapasite;
kapasite = dizi.capacity;
writefln!"%10,s %15s"(kapasite, format!"(+%,s)"(fark));
}
}
}
Satırlar hem kapasiteyi hem de ne kadar arttığını gösteriyor. Dikkat ederseniz, bu işin belirli bir mantığı yok; artış değerleri bazen azalabiliyor bile.
Görüldüğü gibi, farklı artış sanki string olduğundan değil de elemanların 1 bayt olduğundan. (int, immutable(char), ve byte dizileriyle deniyorum.)
--- int[] ---
3 (+3)
7 (+4)
11 (+4)
15 (+4)
23 (+8)
31 (+8)
43 (+12)
63 (+20)
91 (+28)
127 (+36)
203 (+76)
255 (+52)
339 (+84)
511 (+172)
1,019 (+508)
2,043 (+1,024)
4,091 (+2,048)
7,163 (+3,072)
12,283 (+5,120)
20,475 (+8,192)
32,763 (+12,288)
52,219 (+19,456)
81,915 (+29,696)
124,923 (+43,008)
190,459 (+65,536)
285,691 (+95,232)
420,859 (+135,168)
619,515 (+198,656)
899,067 (+279,552)
1,048,571 (+149,504)
1,520,635 (+472,064)
2,174,971 (+654,336)
2,280,443 (+105,472)
3,216,379 (+935,936)
4,535,291 (+1,318,912)
4,824,059 (+288,768)
6,754,299 (+1,930,240)
9,456,635 (+2,702,336)
10,131,451 (+674,816)
--- string ---
15 (+15)
31 (+16)
47 (+16)
63 (+16)
95 (+32)
127 (+32)
175 (+48)
255 (+80)
366 (+111)
510 (+144)
814 (+304)
1,022 (+208)
1,358 (+336)
2,046 (+688)
4,079 (+2,033)
8,175 (+4,096)
16,367 (+8,192)
28,655 (+12,288)
49,135 (+20,480)
81,903 (+32,768)
131,055 (+49,152)
208,879 (+77,824)
327,663 (+118,784)
499,695 (+172,032)
761,839 (+262,144)
1,142,767 (+380,928)
1,683,439 (+540,672)
2,478,063 (+794,624)
3,596,271 (+1,118,208)
4,194,287 (+598,016)
6,082,543 (+1,888,256)
8,699,887 (+2,617,344)
9,121,775 (+421,888)
12,865,519 (+3,743,744)
--- byte[] ---
15 (+15)
31 (+16)
47 (+16)
63 (+16)
95 (+32)
127 (+32)
175 (+48)
255 (+80)
366 (+111)
510 (+144)
814 (+304)
1,022 (+208)
1,358 (+336)
2,046 (+688)
4,079 (+2,033)
8,175 (+4,096)
16,367 (+8,192)
28,655 (+12,288)
49,135 (+20,480)
81,903 (+32,768)
131,055 (+49,152)
208,879 (+77,824)
327,663 (+118,784)
499,695 (+172,032)
761,839 (+262,144)
1,142,767 (+380,928)
1,683,439 (+540,672)
2,478,063 (+794,624)
3,596,271 (+1,118,208)
5,218,287 (+1,622,016)
6,430,703 (+1,212,416)
9,199,599 (+2,768,896)
12,865,519 (+3,665,920)
Ali
|