diff options
Diffstat (limited to 'open_issues/gnumach_memory_management.mdwn')
| -rw-r--r-- | open_issues/gnumach_memory_management.mdwn | 49 |
1 files changed, 49 insertions, 0 deletions
diff --git a/open_issues/gnumach_memory_management.mdwn b/open_issues/gnumach_memory_management.mdwn index 9feb30c8..e5e9d2c5 100644 --- a/open_issues/gnumach_memory_management.mdwn +++ b/open_issues/gnumach_memory_management.mdwn @@ -2133,3 +2133,52 @@ There is a [[!FF_project 266]][[!tag bounty]] on this task. <braunr> do you want to review ? <youpi> I don't think there is any need to <braunr> ok + + +# IRC, freenode, #hurd, 2012-12-08 + + <mcsim> braunr: hi. Do I understand correct that merely the same technique + is used in linux to determine the slab where, the object to be freed, + resides? + <braunr> yes but it's faster on linux since it uses a direct mapping of + physical memory + <braunr> it just has to shift the virtual address to obtain the physical + one, whereas x15 has to walk the pages tables + <braunr> of course it only works for kmalloc, vmalloc is entirely different + <mcsim> btw, is there sense to use some kind of B-tree instead of AVL to + decrease number of cache misses? AFAIK, in modern processors size of L1 + cache line is at least 64 bytes, so in one node we can put at least 4 + leafs (key + pointer to data) making search faster. + <braunr> that would be a b-tree + <braunr> and yes, red-black trees were actually developed based on + properties observed on b-trees + <braunr> but increasing the size of the nodes also increases memory + overhead + <braunr> and code complexity + <braunr> that's why i have a radix trees for cases where there are a large + number of entries with keys close to each other :) + <braunr> a radix-tree is basically a b-tree using the bits of the key as + indexes in the various arrays it walks instead of comparing keys to each + other + <braunr> the original avl tree used in my slab allocator was intended to + reduce the average height of the tree (avl is better for that) + <braunr> avl trees are more suited for cases where there are more lookups + than inserts/deletions + <braunr> they make the tree "flatter" but the maximum complexity of + operations that change the tree is 2log2(n), since rebalancing the tree + can make the algorithm reach back to the tree root + <braunr> red-black trees have slightly bigger heights but insertions are + limited to 2 rotations and deletions to 3 + <mcsim> there should be not much lookups in slab allocators + <braunr> which explains why they're more generally found in generic + containers + <mcsim> or do I misunderstand something? + <braunr> well, there is a lookup for each free() + <braunr> whereas there are insertions/deletions when a slab becomes + non-empty/empty + <mcsim> I see + <braunr> so it was very efficient for caches of small objects, where slabs + have many of them + <braunr> also, i wrote the implementation in userspace, without + functionality pmap provides (although i could have emulated it + afterwards) |