[patch] mem_node shrink

[Dmitry Antipov]

This patch reduces the size of struct mem_node, assuming that Emacs never
allocates an area which size can't be represented as Lisp integer. On i386,
mem_node can be reduced from 28 to 20 bytes, giving a substantial size benefit
which may be precisely evaluated by using malloc_usable_size function of
glibc malloc.

I've never seen more than 50K lived mem_nodes, but 20-30K is typical. For an
average run ends with 30K lived mem_nodes, currently ~7% requests to allocate
28-bytes mem_node are satisfied by allocating 36-bytes chunk, and the rest of
requests causes exact 28-bytes allocations. So, 30K mem_nodes occupies ~848K,
and ~840K of them are really used.

With this patch, ~3.5% requests to allocate 20-bytes mem_node are satisfied
by allocating 28-bytes chunk, and the rest of request causes exact 20-bytes
allocations. So, 30K mem_nodes occupies ~613K, and ~600K of them are really
used.

In this example, we're shaving 235K. Note very long runs may cause heap
fragmentation, and this advantage may degrade. As usual for benchmarks,
your mileage may vary.

Dmitry

Index: alloc.c
===================================================================
RCS file: /sources/emacs/emacs/src/alloc.c,v
retrieving revision 1.432
diff -u -r1.432 alloc.c
--- alloc.c     16 Nov 2007 21:24:59 -0000      1.432
+++ alloc.c     19 Nov 2007 10:17:21 -0000
@@ -365,7 +365,8 @@
 
 /* When scanning the C stack for live Lisp objects, Emacs keeps track
    of what memory allocated via lisp_malloc is intended for what
-   purpose.  This enumeration specifies the type of memory.  */
+   purpose.  This enumeration specifies the type of memory.  Values
+   should begins from 0 and fits into type field of struct mem_node.  */
 
 enum mem_type
 {
@@ -430,6 +431,10 @@
    description of red-black trees.  Any book worth its salt should
    describe them.  */
 
+/* Colors of the node below.  */
+#define MEM_BLACK 0
+#define MEM_RED   1
+
 struct mem_node
 {
   /* Children of this node.  These pointers are never NULL.  When there
@@ -439,14 +444,18 @@
   /* The parent of this node.  In the root node, this is NULL.  */
   struct mem_node *parent;
 
-  /* Start and end of allocated region.  */
-  void *start, *end;
+  /* Start of allocated region.  */
+  void *start;
+
+  /* Size of allocated region.  */
+  unsigned size : BITS_PER_EMACS_INT - 4;
 
   /* Node color.  */
-  enum {MEM_BLACK, MEM_RED} color;
+  unsigned color : 1;
 
-  /* Memory type.  */
-  enum mem_type type;
+  /* Memory type. The width of this bitfield should be
+     enough to hold all values of enum mem_type.  */
+  unsigned type : 3;
 };
 
 /* Base address of stack.  Set in main.  */
@@ -480,7 +489,7 @@
 static void mark_maybe_object P_ ((Lisp_Object));
 static void mark_memory P_ ((void *, void *, int));
 static void mem_init P_ ((void));
-static struct mem_node *mem_insert P_ ((void *, void *, enum mem_type));
+static struct mem_node *mem_insert P_ ((void *, size_t, enum mem_type));
 static void mem_insert_fixup P_ ((struct mem_node *));
 static void mem_rotate_left P_ ((struct mem_node *));
 static void mem_rotate_right P_ ((struct mem_node *));
@@ -880,7 +889,7 @@
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (val && type != MEM_TYPE_NON_LISP)
-    mem_insert (val, (char *) val + nbytes, type);
+    mem_insert (val, nbytes, type);
 #endif
 
   MALLOC_UNBLOCK_INPUT;
@@ -1090,7 +1099,7 @@
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (val && type != MEM_TYPE_NON_LISP)
-    mem_insert (val, (char *) val + nbytes, type);
+    mem_insert (val, nbytes, type);
 #endif
 
   MALLOC_UNBLOCK_INPUT;
@@ -1263,14 +1272,13 @@
        fprintf (stderr, "Malloc returned %p which is already in use\n",
                 value);
        fprintf (stderr, "Region in use is %p...%p, %u bytes, type %d\n",
-                m->start, m->end, (char *) m->end - (char *) m->start,
-                m->type);
+                m->start, m->start + m->size, m->size, m->type);
        abort ();
       }
 
     if (!dont_register_blocks)
       {
-       mem_insert (value, (char *) value + max (1, size), allocated_mem_type);
+       mem_insert (value, max (1, size), allocated_mem_type);
        allocated_mem_type = MEM_TYPE_NON_LISP;
       }
   }
@@ -1332,7 +1340,7 @@
       }
 
     /* Can't handle zero size regions in the red-black tree.  */
-    mem_insert (value, (char *) value + max (size, 1), MEM_TYPE_NON_LISP);
+    mem_insert (value, max (size, 1), MEM_TYPE_NON_LISP);
   }
 
   /* fprintf (stderr, "%p <- realloc\n", value); */
@@ -3543,7 +3551,8 @@
   mem_z.left = mem_z.right = MEM_NIL;
   mem_z.parent = NULL;
   mem_z.color = MEM_BLACK;
-  mem_z.start = mem_z.end = NULL;
+  mem_z.start = NULL;
+  mem_z.size = 0;
   mem_root = MEM_NIL;
 }
 
@@ -3562,10 +3571,10 @@
 
   /* Make the search always successful to speed up the loop below.  */
   mem_z.start = start;
-  mem_z.end = (char *) start + 1;
+  mem_z.size = 1;
 
   p = mem_root;
-  while (start < p->start || start >= p->end)
+  while (start < p->start || start >= p->start + p->size)
     p = start < p->start ? p->left : p->right;
   return p;
 }
@@ -3576,16 +3585,24 @@
    pointer to the node that was inserted.  */
 
 static struct mem_node *
-mem_insert (start, end, type)
-     void *start, *end;
+mem_insert (start, size, type)
+     void *start;
+     size_t size;
      enum mem_type type;
 {
   struct mem_node *c, *parent, *x;
 
+#ifdef ALLOC_DEBUG
+  /* Check if we can store requested size in bitfield. It's expected that Emacs
+     never allocates the area which size can't be represented as Lisp integer. 
 */
+  if (size > MOST_POSITIVE_FIXNUM)
+    abort ();
+#endif
+
   if (min_heap_address == NULL || start < min_heap_address)
     min_heap_address = start;
-  if (max_heap_address == NULL || end > max_heap_address)
-    max_heap_address = end;
+  if (max_heap_address == NULL || start + size > max_heap_address)
+    max_heap_address = start + size;
 
   /* See where in the tree a node for START belongs.  In this
      particular application, it shouldn't happen that a node is already
@@ -3597,7 +3614,7 @@
 
   while (c != MEM_NIL)
     {
-      if (start >= c->start && start < c->end)
+      if (start >= c->start && start < c->start + c->size)
        abort ();
       parent = c;
       c = start < c->start ? c->left : c->right;
@@ -3622,7 +3639,7 @@
   x = (struct mem_node *) xmalloc (sizeof *x);
 #endif
   x->start = start;
-  x->end = end;
+  x->size = size;
   x->type = type;
   x->parent = parent;
   x->left = x->right = MEM_NIL;
@@ -3835,7 +3852,7 @@
   if (y != z)
     {
       z->start = y->start;
-      z->end = y->end;
+      z->size = y->size;
       z->type = y->type;
     }