a*****1
发帖数: 314 | 1 why do we use circular link list in place of any balanced binary search tree
in storage allocator? One draw back is that to free() a chunk of memory
allocator has to search the link list and then if found that address then
release , so why not tree to reduce this search and merge?
请高手，给出简单解释。
谢谢 |
h****n
发帖数: 1093 | |
a*****1
发帖数: 314 | |
h****n
发帖数: 1093 | 4 我的理解就是内存分配器的目的是找到一块合适大小的空间，Tree你可以logn找到特定
节点，但是要找到合适大小的空间你依然需要遍历树中的节点，所以也是n，复杂度和
list比没啥优势，大概就这样子吧 |
d**********x
发帖数: 4083 | 5 我没用试过用bst来做allocator
我猜一个可能的原因是，circular link list只要单链表就行，搜索的时候首先可以分
bin，其次可以用next-fit，效率不会太差
而bst虽然效率高，但是它需要两个指针的overhead，这对于处理很多小对象的系统来
说是个严重负担
tree
【在 a*****1 的大作中提到】
: why do we use circular link list in place of any balanced binary search tree
: in storage allocator? One draw back is that to free() a chunk of memory
: allocator has to search the link list and then if found that address then
: release , so why not tree to reduce this search and merge?
: 请高手，给出简单解释。
: 谢谢
|
s********k
发帖数: 6180 | 6 tree还是有优势，比如所有节点都是不同大小的内存块，那么你知道了需要分配的内存
在这个内存树种就只需要logn找到合适的，链表要n，不过实际上大多数内存块都不是
完全任意大小，而是分别在几个不同大小的级别，Buddy system algorithm就是这样。
所以实际上应该是array加链表最合适，简单高效
【在 h****n 的大作中提到】
: 我的理解就是内存分配器的目的是找到一块合适大小的空间，Tree你可以logn找到特定
: 节点，但是要找到合适大小的空间你依然需要遍历树中的节点，所以也是n，复杂度和
: list比没啥优势，大概就这样子吧
|
d**********x
发帖数: 4083 | 7 exactly.
但是我的point是树的overhead太大，64位系统要两个8 byte指针，好可怕。
特定
度和
【在 s********k 的大作中提到】
: tree还是有优势，比如所有节点都是不同大小的内存块，那么你知道了需要分配的内存
: 在这个内存树种就只需要logn找到合适的，链表要n，不过实际上大多数内存块都不是
: 完全任意大小，而是分别在几个不同大小的级别，Buddy system algorithm就是这样。
: 所以实际上应该是array加链表最合适，简单高效
|
s********k
发帖数: 6180 | 8 其实我觉得内存分配最主要的overhead是速度，而不是内存大小，当然tree是有data
structure方面的overhead，但是其他简单的buddy system或者slab也有external,
internal fragementation的overhead。只是在实际系统中，对内存的要求满足tree形
式的太少了，几乎没有。
【在 d**********x 的大作中提到】
: exactly.
: 但是我的point是树的overhead太大，64位系统要两个8 byte指针，好可怕。
:
: 特定
: 度和
|
i****1
发帖数: 445 | 9 我的感觉是：
1. circular link list不需要额外的data structure,直接在block的前面留两个byte
or word表示状态，即可。而且是直接访问，不想tree，那样间接访问。
2. 当需要merge/de-fragmentation时，link list就很方便了直接merge毫无压力,O(1)
时间。但是tree就不一样了，tree要满足bst的性质，旋转子树是在所难免的。
当然通常的search for a proper size block,link list需要O(N)时间，而tree则只需
要O(logn).但是实际系统应该是用一个额外的list来链接free block的。
tree
【在 a*****1 的大作中提到】
: why do we use circular link list in place of any balanced binary search tree
: in storage allocator? One draw back is that to free() a chunk of memory
: allocator has to search the link list and then if found that address then
: release , so why not tree to reduce this search and merge?
: 请高手，给出简单解释。
: 谢谢
|
