請教伙伴算法的問題

ppcc800330

請問下我看資料說 伙伴算法的每次調(diào)用都會“弄臟”硬件高速緩存，一直不太明白，
請問是為什么呢？

謝謝

yjh777

啥資料？原話是怎么寫的？

ppcc800330

深入理解linux內(nèi)核 中講到slab分配器時寫到：

硬件高速緩存的高性能又是盡可能地限制對伙伴系統(tǒng)分配器調(diào)用的另一個理由，因為對伙伴系統(tǒng)函數(shù)的每次調(diào)用都“弄臟”硬件高速緩存，所以增加了對內(nèi)存的平均訪問時間。內(nèi)核函數(shù)對硬件高速緩存的影響就是所謂的函數(shù)“足跡（footprint）”，其定義為函數(shù)結(jié)束時重寫高速緩存的百分比。顯而易見，大的“足跡”導(dǎo)致內(nèi)核函數(shù)剛執(zhí)行之后較慢的代碼執(zhí)行，因為硬件高速緩存此時填滿了無用的信息

yjh777 發(fā)表于 2015-12-24 08:45
啥資料？原話是怎么寫的？

yjh777

哦，沒太明白具體原因；

不知道伙伴系統(tǒng)的函數(shù) 為什么會導(dǎo)致寫很多無用信息到 硬件高速緩存，，
上網(wǎng)查查去，，

nswcfd

是指每次分配一個page，并且需要清零的情況下zero掉整個page，會invalid掉整個hw cache么？
（相對的，slab每次只分配一個object，初始化最多invalid幾個cache line，或者通過批量初始化來抵消掉這種開銷？）

ppcc800330

你是假設(shè)要zero掉整個page，分配并不一定要zero吧？

nswcfd 發(fā)表于 2015-12-24 15:56
是指每次分配一個page，并且需要清零的情況下zero掉整個page，會invalid掉整個hw cache么？
（相對的，sla ...

瀚海書香

ppcc800330 發(fā)表于 2015-12-24 17:32
你是假設(shè)要zero掉整個page，分配并不一定要zero吧？

1、buddy system 是基于page的，相比于slab 每次操作的foot print過大，而且大部分情況下會導(dǎo)致TLB失效。
2、很多時候大家說的劣勢都是指最壞情況下的場景。

參考資料：
https://people.kth.se/~roand/half_fit.pdf
http://www.cs.uky.edu/~raphael/courses/CS585/chap07.refs.txt

ppcc800330

1：buddy system 是基于page的,但如果分配頁面，但只訪問很小一部分，應(yīng)該只會導(dǎo)致所操作的很小一部分數(shù)據(jù)cache失效。
2：TLB miss確實會增加。但描述好像跟這個無關(guān)。
3：這里的“foot print” 具體是什么含義，有點不太明白。

瀚海書香 發(fā)表于 2015-12-24 20:07
1、buddy system 是基于page的，相比于slab 每次操作的foot print過大，而且大部分情況下會導(dǎo)致TLB失 ...

nswcfd

foot print簡單的說就是touch的memory范圍的大小，一個page的footprint通常比一個object要大得多。（除非是page-size級別的大object）.

討論fooprint的潛臺詞就是對 cache/tlb的影響，這么大的memory range全部被cache起來需要消耗多少cache line/tlb entry等。

如果只訪問一個page的一小部分（當然是種嚴重浪費），那就跟只訪問一個object的開銷差不多，實際上slab object本身就是page的一部分。

yjh777

明白了，謝謝 @nswcfd 解釋！

    所以系統(tǒng)在伙伴基礎(chǔ)上又有了 slab slub  ... 來減輕副作用，，