IRC.

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)