unofficial mirror of emacs-devel@gnu.org 
 help / color / mirror / code / Atom feed
* Proposal: block-based vector allocator
@ 2011-12-06  5:22 Dmitry Antipov
  2011-12-06 13:35 ` Stefan Monnier
       [not found] ` <jwvaa1yjs21.fsf-monnier+emacs@gnu.org>
  0 siblings, 2 replies; 62+ messages in thread
From: Dmitry Antipov @ 2011-12-06  5:22 UTC (permalink / raw)
  To: emacs-devel

[-- Attachment #1: Type: text/plain, Size: 2178 bytes --]

I've tried a few designs of block-based vector allocation, and this is the first
one which looks good enough to be proposed here.

This vector allocator uses near-to-PAGE_SIZE blocks to allocate small vectors
and dedicated list for large vectors. Array of free lists is used to separately
hold free small vectors of all possible sizes. When an allocation request can't
be satisfied from exact-fit free list, best-fit is tried, and unused tail bytes
forms a free vector which is set up on an appropriate free list. If best-fit
allocation has failed too, and allocation request exceeds an amount of free bytes
in the current vector block, new block is allocated and this request is satisfied
from it; the rest of space from previous block forms a free vector which is set
up on appropriate free list. If allocation request may be satisfied from the
current vector block, it's just a simple bump pointer allocation.

At sweeping, all vector blocks are processed in reverse allocation order,
and pointers to unmarked vectors are collected on a per-block basic. If the
block contains no live vectors, it's freed. Otherwise, adjacent free vectors
are coalesced to form the largest possible free vectors, which are set up on
an appropriate free lists. Finally, dedicated list of large vector is processed,
and unmarked vectors are freed.

I didn't test it too much, but this code survives the bootstrap both in 32 and
64-bit variants and doesn't crash under usual daily editing workloads. Although
the whole stuff looks a bit complicated, the benefits are 4-5% faster speed and
7-8% less peak heap utilization with my favorite byte-force-recompile benchmark,
at the cost of 2% larger (64-bit) dumped executable.

As with the most general case algorithms, some special scenarios may hurt
an allocator. For example, allocating a lot of 3K vectors wastes ~25% of
vector block space; allocating a lot of mid-size vectors, followed by allocating
a lot of small vectors (or vice versa) will trigger an excessive splitting or
coalescing work. But I believe this code is balanced enough to have a measurable
advantage over current scheme for the most of average normal usage patterns.

Dmitry

[-- Attachment #2: vector_alloc.patch --]
[-- Type: text/plain, Size: 13435 bytes --]

=== modified file 'src/alloc.c'
--- src/alloc.c	2011-11-20 03:07:02 +0000
+++ src/alloc.c	2011-12-06 05:06:33 +0000
@@ -21,7 +21,7 @@
 #include <stdio.h>
 #include <limits.h>		/* For CHAR_BIT.  */
 #include <setjmp.h>
-
+#include <sys/param.h>		/* For roundup.  */
 #include <signal.h>
 
 #ifdef HAVE_PTHREAD
@@ -2896,9 +2896,12 @@
 			   Vector Allocation
  ***********************************************************************/
 
-/* Singly-linked list of all vectors.  */
+#ifndef PAGE_SIZE
+#define PAGE_SIZE 4096
+#endif
 
-static struct Lisp_Vector *all_vectors;
+#define VECTOR_BLOCK_SIZE (PAGE_SIZE - sizeof (void *))
+#define VECTOR_BLOCK_BYTES (VECTOR_BLOCK_SIZE - 2 * sizeof (void *))
 
 /* Handy constants for vectorlike objects.  */
 enum
@@ -2907,6 +2910,301 @@
     word_size = sizeof (Lisp_Object)
   };
 
+/* Free lists for all possible block-allocated vectors.  */
+
+#define VECTOR_FREE_LISTS (VECTOR_BLOCK_BYTES / word_size)
+
+/* Vector blocks are aligned to page size, so it's easy to
+   get vector block pointer from the vector pointer.  */
+
+#define VECTOR_BLOCK(v) (struct vector_block *) \
+  ((unsigned long)(v) & ~(PAGE_SIZE - 1))
+
+/* When the vector is on a free list, vectorlike_header.SIZE is set to
+   this special value ORed with vector's memory footprint size.  */
+
+#define VECTOR_FREE_LIST_SIZE \
+  (((EMACS_INT) ~0) & ~(ARRAY_MARK_FLAG | PSEUDOVECTOR_FLAG | (PAGE_SIZE - 1)))
+
+struct vector_block
+{
+  unsigned char data[VECTOR_BLOCK_BYTES];
+  unsigned char *bump;
+  struct vector_block *next;
+};
+
+/* Current vector block.  */
+
+static struct vector_block *vector_block;
+
+/* Vector free lists, where NTH item points to a chain
+   of free vectors of NTH * WORD_SIZE bytes.  */
+
+static struct Lisp_Vector *vector_free_lists[VECTOR_FREE_LISTS];
+
+/* Singly-linked list of large vectors.  */
+
+static struct Lisp_Vector *large_vectors;
+
+/* Get a new vector block.  */
+
+static struct vector_block *
+allocate_vector_block (void)
+{
+  struct vector_block *b;
+
+#ifdef DOUG_LEA_MALLOC
+  mallopt (M_MMAP_MAX, 0);
+#endif
+
+  /* Although lisp_align_malloc should be used, the default
+     1K granularity looks too small for vector allocation.  */
+  b = memalign (PAGE_SIZE, VECTOR_BLOCK_SIZE);
+  if (!b)
+    memory_full (VECTOR_BLOCK_SIZE);
+
+#ifdef DOUG_LEA_MALLOC
+  mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
+#endif
+
+  memset (b->data, 0, VECTOR_BLOCK_BYTES);
+  mem_insert (b->data, b->data + VECTOR_BLOCK_BYTES, MEM_TYPE_VECTORLIKE);
+
+  b->bump = b->data;
+  b->next = vector_block;
+  vector_block = b;
+  return b;
+}
+
+/* Called once to initialize vector allocation.  */
+
+static void
+init_vectors (void)
+{
+  int i;
+
+  large_vectors = NULL;
+  vector_block = allocate_vector_block ();
+
+  for (i = 0; i < VECTOR_FREE_LISTS; i++)
+    vector_free_lists[i] = NULL;
+}
+
+/* Allocate vector from the vector block.  */
+
+static struct Lisp_Vector *
+allocate_vector_from_block (size_t nbytes)
+{
+  struct Lisp_Vector *vector;
+  struct vector_block *block;
+  size_t index, restbytes;
+
+  /* Vector with 0 slots for Lisp_Objects is allowed.  */
+  eassert (nbytes >= sizeof (struct vectorlike_header) &&
+	   nbytes <= VECTOR_BLOCK_BYTES);
+  eassert (nbytes % word_size == 0);
+  eassert (vector_block != NULL);
+
+  /* First, try to allocate from a free list
+     contains vectors of the requested size.  */
+  index = nbytes / word_size;
+  if (vector_free_lists[index])
+    {
+      vector = vector_free_lists[index];
+      vector_free_lists[index] = vector->header.next.vector;
+      vector->header.next.nbytes = nbytes;
+      return vector;
+    }
+
+  /* Next, check free lists contains larger vectors.  */
+  for (index = (nbytes + sizeof (struct Lisp_Vector)) / word_size;
+       index < VECTOR_FREE_LISTS; index++)
+    if (vector_free_lists[index])
+      {
+	struct Lisp_Vector *rest;
+
+	/* This vector is larger than it was requested.  */
+	vector = vector_free_lists[index];
+	vector_free_lists[index] = vector->header.next.vector;
+	vector->header.next.nbytes = nbytes;
+
+	/* Excessive bytes are used for the smaller vector,
+	   which should be set on an appropriate free list.  */
+	restbytes = index * word_size - nbytes;
+	eassert (restbytes % word_size == 0);
+	rest = (struct Lisp_Vector *) ((char *) vector + nbytes);
+	rest->header.size = VECTOR_FREE_LIST_SIZE | restbytes;
+	index = restbytes / word_size;
+	eassert (index < VECTOR_FREE_LISTS);
+	rest->header.next.vector = vector_free_lists[index];
+	vector_free_lists[index] = rest;
+
+	return vector;
+      }
+
+  /* Next, try to allocate from current vector block.  */
+  restbytes = vector_block->data + VECTOR_BLOCK_BYTES - vector_block->bump;
+  if (nbytes > restbytes)
+    {
+      /* Current block's free space isn't enough...  */
+      if (restbytes >= sizeof (struct Lisp_Vector))
+	{
+	  /* ...but it's enough to allocate smaller vector,
+	     which should be set on an appropriate free list.  */
+	  eassert (restbytes % word_size == 0);
+	  vector = (struct Lisp_Vector *) vector_block->bump;
+	  vector_block->bump += restbytes;
+	  vector->header.size = VECTOR_FREE_LIST_SIZE | restbytes;
+	  index = restbytes / word_size;
+	  eassert (index < VECTOR_FREE_LISTS);
+	  vector->header.next.vector = vector_free_lists[index];
+	  vector_free_lists[index] = vector;
+	}
+      /* Anyway, need a new vector block.  */
+      block = allocate_vector_block ();
+    }
+  else
+    /* Allocate from current vector block.  */
+    block = vector_block;
+
+  /* Bump pointer allocation from current vector block.  */
+  vector = (struct Lisp_Vector *) block->bump;
+  block->bump += nbytes;
+  vector->header.next.nbytes = nbytes;
+  return vector;
+}
+
+/* Return amount of Lisp_Objects can be stored in that vector.  */
+
+#define VECTOR_SIZE(v) ((v)->header.size & PSEUDOVECTOR_FLAG ? \
+  (PSEUDOVECTOR_SIZE_MASK & (v)->header.size) :	(v)->header.size)
+
+/* Reclaim space used by unmarked vectors.  */
+
+static void
+sweep_vectors (void)
+{
+  struct vector_block *block = vector_block, *bprev = NULL, *bnext;
+  struct Lisp_Vector *vector, *prev, *next;
+  int index, nr;
+
+  total_vector_size = 0;
+  for (index = 0; index < VECTOR_FREE_LISTS; index++)
+    vector_free_lists[index] = NULL;
+
+  /* Looking through vector blocks first.  */
+
+  while (block)
+    {
+      struct Lisp_Vector *freearray
+	[VECTOR_BLOCK_BYTES / sizeof (struct Lisp_Vector)];
+
+      index = nr = 0;
+      vector = (struct Lisp_Vector *) block->data;
+      while ((unsigned char *) vector < block->bump)
+	{
+	  if ((vector->header.size & VECTOR_FREE_LIST_SIZE) == 
+	      VECTOR_FREE_LIST_SIZE)
+	    {
+	      /* This vector is on a free list already.  */
+	      freearray[index++] = vector;
+	      vector->header.next.nbytes = 
+		vector->header.size & (PAGE_SIZE - 1);
+	    }
+	  else
+	    {
+	      if (VECTOR_MARKED_P (vector))
+		{
+		  VECTOR_UNMARK (vector), nr++;
+		  total_vector_size += VECTOR_SIZE (vector);
+		}
+	      else
+		{
+		  /* This vector is not marked, and it's not on a free list. */
+		  freearray[index++] = vector;
+		  vector->header.size = 
+		    VECTOR_FREE_LIST_SIZE | vector->header.next.nbytes;
+		}
+	    }
+	  eassert (index < sizeof (freearray) / sizeof (freearray[0]));
+	  eassert (vector->header.next.nbytes != 0);
+	  vector = (struct Lisp_Vector *)
+	    ((unsigned char *) vector + vector->header.next.nbytes);
+	}
+
+      if (nr)
+	{
+	  /* This block has some used vectors, which are unmarked. Unused
+	     vectors are collected in FREEARRAY. Setup them on a free lists,
+	     coalescing adjacent free vectors if possible.  */
+	  int i, j;
+	  EMACS_INT nbytes;
+
+	  for (i = 0; i < index; i = j)
+	    {
+	      vector = freearray[i];
+	      nbytes = vector->header.next.nbytes;
+
+	      /* Try to form the largest possible free vector.  */
+	      for (j = i + 1; j < index; j++)
+		{
+		  next = freearray[j];
+		  if ((struct Lisp_Vector *)
+		       ((unsigned char *) vector + nbytes) == next)
+		    nbytes += next->header.next.nbytes;
+		  else
+		    break;
+		}
+	      vector->header.next.nbytes = nbytes;
+
+	      /* Setup resulting vector on a free list.  */
+	      eassert (vector->header.next.nbytes % word_size == 0);
+	      nr = vector->header.next.nbytes / word_size;
+	      eassert (nr < VECTOR_FREE_LISTS);
+	      vector->header.size =
+		VECTOR_FREE_LIST_SIZE | vector->header.next.nbytes;
+	      vector->header.next.vector = vector_free_lists[nr];
+	      vector_free_lists[nr] = vector;
+	    }
+	  bprev = block, block = block->next;
+	}
+      else
+	{
+	  /* This block is no longer used.  */
+	  if (bprev)
+	    bprev->next = block->next;
+	  else
+	    vector_block = block->next;
+	  bnext = block->next;
+	  mem_delete (mem_find (block->data));
+	  free (block);
+	  block = bnext;
+	}
+    }
+
+  /* Next, sweep large vectors.  */
+
+  vector = large_vectors, prev = NULL;
+
+  while (vector)
+    if (VECTOR_MARKED_P (vector))
+      {
+	VECTOR_UNMARK (vector);
+	total_vector_size += VECTOR_SIZE (vector);
+	prev = vector, vector = vector->header.next.vector;
+      }
+    else
+      {
+	if (prev)
+	  prev->header.next = vector->header.next;
+	else
+	  large_vectors = vector->header.next.vector;
+	next = vector->header.next.vector;
+	lisp_free (vector);
+	vector = next;
+      }
+}
+
 /* Value is a pointer to a newly allocated Lisp_Vector structure
    with room for LEN Lisp_Objects.  */
 
@@ -2929,7 +3227,15 @@
   /* eassert (!handling_signal); */
 
   nbytes = header_size + len * word_size;
-  p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE);
+  if (nbytes > VECTOR_BLOCK_BYTES)
+    {
+      p = (struct Lisp_Vector *) lisp_malloc (nbytes, MEM_TYPE_VECTORLIKE);
+      p->header.next.vector = large_vectors;
+      large_vectors = p;
+    }
+  else
+    /* Rounding is needed for 32-bit code to preserve 8-byte alignment.  */
+    p = allocate_vector_from_block (roundup (nbytes, 8));
 
 #ifdef DOUG_LEA_MALLOC
   /* Back to a reasonable maximum of mmap'ed areas.  */
@@ -2939,9 +3245,6 @@
   consing_since_gc += nbytes;
   vector_cells_consed += len;
 
-  p->header.next.vector = all_vectors;
-  all_vectors = p;
-
   MALLOC_UNBLOCK_INPUT;
 
   return p;
@@ -4016,7 +4319,38 @@
 static inline int
 live_vector_p (struct mem_node *m, void *p)
 {
-  return (p == m->start && m->type == MEM_TYPE_VECTORLIKE);
+  if (m->type == MEM_TYPE_VECTORLIKE)
+    {
+      if (m->end - m->start == VECTOR_BLOCK_BYTES)
+	{
+	  /* This memory node corresponds to a vector block.  */
+	  struct vector_block *block = VECTOR_BLOCK (p);
+	  struct Lisp_Vector *vector = (struct Lisp_Vector *) block->data;
+
+	  /* Scan the whole vector block and see whether P points to
+	     the start of some vector which is not on a free list.  */
+	  while ((unsigned char *) vector < block->bump)
+	    {
+	      if ((vector->header.size & VECTOR_FREE_LIST_SIZE)
+		  == VECTOR_FREE_LIST_SIZE)
+		vector = (struct Lisp_Vector *)
+		  ((unsigned char *) vector +
+		   (vector->header.size & (PAGE_SIZE - 1)));
+	      else if (vector == p)
+		return 1;
+	      else
+		vector = (struct Lisp_Vector *)
+		  ((unsigned char *) vector + vector->header.next.nbytes);
+	    }
+	}
+      else
+	{
+	  if (p == m->start)
+	    /* This memory node corresponds to a large vector.  */
+	    return 1;
+	}
+    }
+  return 0;
 }
 
 
@@ -6169,33 +6503,7 @@
 	}
   }
 
-  /* Free all unmarked vectors */
-  {
-    register struct Lisp_Vector *vector = all_vectors, *prev = 0, *next;
-    total_vector_size = 0;
-
-    while (vector)
-      if (!VECTOR_MARKED_P (vector))
-	{
-	  if (prev)
-	    prev->header.next = vector->header.next;
-	  else
-	    all_vectors = vector->header.next.vector;
-	  next = vector->header.next.vector;
-	  lisp_free (vector);
-	  vector = next;
-
-	}
-      else
-	{
-	  VECTOR_UNMARK (vector);
-	  if (vector->header.size & PSEUDOVECTOR_FLAG)
-	    total_vector_size += PSEUDOVECTOR_SIZE_MASK & vector->header.size;
-	  else
-	    total_vector_size += vector->header.size;
-	  prev = vector, vector = vector->header.next.vector;
-	}
-  }
+  sweep_vectors ();
 
 #ifdef GC_CHECK_STRING_BYTES
   if (!noninteractive)
@@ -6331,7 +6639,6 @@
   Vdead = make_pure_string ("DEAD", 4, 4, 0);
 #endif
 
-  all_vectors = 0;
   ignore_warnings = 1;
 #ifdef DOUG_LEA_MALLOC
   mallopt (M_TRIM_THRESHOLD, 128*1024); /* trim threshold */
@@ -6344,6 +6651,7 @@
   init_marker ();
   init_float ();
   init_intervals ();
+  init_vectors ();
   init_weak_hash_tables ();
 
 #ifdef REL_ALLOC

=== modified file 'src/lisp.h'
--- src/lisp.h	2011-12-05 00:15:15 +0000
+++ src/lisp.h	2011-12-06 05:04:46 +0000
@@ -868,12 +868,15 @@
 struct vectorlike_header
   {
     EMACS_INT size;
-
-    /* Pointer to the next vector-like object.  It is generally a buffer or a
+    /* When the vector is allocated from a vector block, NBYTES is used
+       if the vector is not on a free list, and VECTOR is used otherwise.
+       For large vector-like objects, BUFFER or VECTOR is used as a pointer
+       to the next vector-like object.  It is generally a buffer or a 
        Lisp_Vector alias, so for convenience it is a union instead of a
        pointer: this way, one can write P->next.vector instead of ((struct
        Lisp_Vector *) P->next).  */
     union {
+      EMACS_INT nbytes;
       struct buffer *buffer;
       struct Lisp_Vector *vector;
     } next;


^ permalink raw reply	[flat|nested] 62+ messages in thread
end of thread, other threads:[~2012-06-08 10:00 UTC | newest]

Thread overview: 62+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-12-06  5:22 Proposal: block-based vector allocator Dmitry Antipov
2011-12-06 13:35 ` Stefan Monnier
2011-12-06 15:14   ` Dmitry Antipov
2011-12-06 19:39     ` Stefan Monnier
2011-12-07  5:05       ` Dmitry Antipov
2011-12-07 12:27         ` Carsten Mattner
2011-12-07 13:52         ` Stefan Monnier
2011-12-07 16:08           ` Dmitry Antipov
2011-12-07 16:30             ` Stefan Monnier
2011-12-08  8:50               ` Dmitry Antipov
2011-12-08 13:52                 ` Stefan Monnier
2011-12-08  1:53             ` Stephen J. Turnbull
2011-12-08  4:41               ` Dmitry Antipov
2011-12-08 14:10                 ` Stefan Monnier
2011-12-08 16:48                   ` Dmitry Antipov
2011-12-08 19:58                     ` Stefan Monnier
2011-12-09  7:32                       ` Eli Zaretskii
2011-12-09  9:04                       ` Dmitry Antipov
2011-12-09 14:05                         ` Stefan Monnier
2011-12-09 16:15                           ` Dmitry Antipov
2011-12-09 21:04                             ` Stefan Monnier
2011-12-11 13:18                               ` Dmitry Antipov
2011-12-12  3:07                               ` Dmitry Antipov
2011-12-12 16:24                                 ` Stefan Monnier
2011-12-09  4:44                 ` Stephen J. Turnbull
     [not found] ` <jwvaa1yjs21.fsf-monnier+emacs@gnu.org>
2012-05-17  7:58   ` Dmitry Antipov
2012-05-18 17:40     ` Stefan Monnier
2012-05-21 12:19       ` Dmitry Antipov
2012-05-21 13:02         ` Andreas Schwab
2012-05-21 13:48           ` Dmitry Antipov
2012-05-21 15:07             ` Andreas Schwab
2012-05-22  5:23             ` Ken Raeburn
2012-05-21 20:12         ` Stefan Monnier
2012-05-22  8:24           ` Dmitry Antipov
2012-05-31 13:44           ` Dmitry Antipov
2012-05-31 15:43             ` Paul Eggert
2012-06-01  5:15               ` Dmitry Antipov
2012-06-01  5:44                 ` Paul Eggert
2012-06-01  9:06                   ` Dmitry Antipov
2012-06-01 17:36                     ` Stefan Monnier
2012-06-02  0:32                       ` Paul Eggert
2012-06-02  7:41                         ` Eli Zaretskii
2012-06-03  6:49                           ` Paul Eggert
2012-06-03 14:26                             ` Eli Zaretskii
2012-05-31 21:16             ` Stefan Monnier
2012-06-01  7:34               ` Dmitry Antipov
2012-06-01 17:40                 ` Stefan Monnier
2012-06-01 17:43                 ` Stefan Monnier
2012-06-06  7:02                   ` Dmitry Antipov
2012-06-06 13:13                     ` Stefan Monnier
2012-06-06 14:58                       ` Dmitry Antipov
2012-06-06 19:18                         ` Stefan Monnier
2012-06-07 10:03                           ` Dmitry Antipov
2012-06-07 14:07                             ` Stefan Monnier
2012-06-08  5:50                               ` Dmitry Antipov
2012-06-08  6:17                                 ` Stefan Monnier
2012-06-08  8:49                                   ` Dmitry Antipov
2012-06-08  8:53                                     ` Eli Zaretskii
2012-06-08  9:41                                       ` Eli Zaretskii
2012-06-08 10:00                                         ` Eli Zaretskii
2012-06-08  6:57                                 ` Eli Zaretskii
2012-06-08  6:38                             ` Paul Eggert

Code repositories for project(s) associated with this public inbox

	https://git.savannah.gnu.org/cgit/emacs.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).