From bcfc058a332da0a2bd2e09e13619be3e2eb803a7 Mon Sep 17 00:00:00 2001 From: Thomas Schwinge Date: Tue, 11 Dec 2012 11:04:26 +0100 Subject: IRC. --- open_issues/gnumach_memory_management.mdwn | 49 ++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) (limited to 'open_issues/gnumach_memory_management.mdwn') 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. do you want to review ? I don't think there is any need to ok + + +# IRC, freenode, #hurd, 2012-12-08 + + 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? + yes but it's faster on linux since it uses a direct mapping of + physical memory + it just has to shift the virtual address to obtain the physical + one, whereas x15 has to walk the pages tables + of course it only works for kmalloc, vmalloc is entirely different + 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. + that would be a b-tree + and yes, red-black trees were actually developed based on + properties observed on b-trees + but increasing the size of the nodes also increases memory + overhead + and code complexity + that's why i have a radix trees for cases where there are a large + number of entries with keys close to each other :) + 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 + the original avl tree used in my slab allocator was intended to + reduce the average height of the tree (avl is better for that) + avl trees are more suited for cases where there are more lookups + than inserts/deletions + 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 + red-black trees have slightly bigger heights but insertions are + limited to 2 rotations and deletions to 3 + there should be not much lookups in slab allocators + which explains why they're more generally found in generic + containers + or do I misunderstand something? + well, there is a lookup for each free() + whereas there are insertions/deletions when a slab becomes + non-empty/empty + I see + so it was very efficient for caches of small objects, where slabs + have many of them + also, i wrote the implementation in userspace, without + functionality pmap provides (although i could have emulated it + afterwards) -- cgit v1.2.3