Najsporiji način sabiranja niza brojeva nije slučajan pristup. U nekim slučajevima, pažljivo konstruisan redosled čitanja podataka može da bude čak i više od 30% sporiji od random pristupa.
Suština problema nije u samom sabiranju. Problem je u tome kako CPU i Intel procesori upravljaju memorijom kroz cache, prefetcher, TLB i DRAM. Kada se ovi sistemi nateraju da rade protiv sopstvenog dizajna, performanse padaju ekstremno.
Kako cache i page struktura uništavaju performanse
Moderni CPU ne čita memoriju direktno iz RAM-a za svaki podatak. Umesto toga koristi L1, L2 i L3 cache kako bi ubrzao pristup.
Problem nastaje kada se podaci ne čitaju linearno. Linearni pristup omogućava prefetcher-u da unapred učita sledeće vrednosti. Random pristup to već otežava, ali i dalje ostavlja određene obrasce.
Kada se uvede pristup koji namerno razbija cache line lokalnost, CPU počinje da radi maksimalno neefikasno. Svaki pristup postaje novi ulazak u sporiju memorijsku hijerarhiju.
Još gore postaje kada se pristup organizuje tako da se stalno prelazi preko page granica. Tada u igru ulazi i page table i TLB mehanizam, što dodatno usporava svaki pojedinačni read.
Kada random više nije najgori scenario
Klasično se smatra da je random pristup memoriji najgori. Međutim, eksperimenti pokazuju da pažljivo konstruisan obrazac može biti još gori.
Kada se pristup dizajnira tako da stalno:
- razbija cache reuse
- poništava rad prefetcher-a
- forsira TLB i page walk operacije
- izaziva konflikte u DRAM bankama
dobija se scenario koji je sporiji od običnog random pristupa.
U merenjima, linearni pristup je imao oko 133 miliona ciklusa, random oko 1.57 milijardi, dok loše optimizovani obrasci idu i preko 2.08 milijardi ciklusa.
To znači da CPU ne pati samo od "nepredvidivosti", već i od načina na koji su podaci fizički raspoređeni u memoriji i kako se mapiraju kroz cache i DRAM hijerarhiju.
Ovaj primer jasno pokazuje da performanse ne zavise samo od algoritma, već i od toga kako algoritam "razmišlja" u odnosu na hardver.
Razumevanje cache sistema, page strukture i DRAM organizacije često ima veći uticaj na brzinu od same kompleksnosti koda.