Block-based vector allocation of small vectors.

* src/lisp.h (struct vectorlike_header): New field `nbytes',
adjust comment accordingly.
* src/alloc.c (enum mem_type): New type `MEM_TYPE_VECTOR_BLOCK'
to denote vector blocks. Adjust users (live_vector_p,
mark_maybe_pointer, valid_lisp_object_p) accordingly.
(COMMON_MULTIPLE): Move outside #if USE_LSB_TAG.
(VECTOR_BLOCK_SIZE, vroundup, VECTOR_BLOCK_BYTES),
(VBLOCK_BYTES_MIN, VBLOCK_BYTES_MAX, VECTOR_MAX_FREE_LIST_INDEX),
(VECTOR_FREE_LIST_FLAG, ADVANCE, VINDEX, SETUP_ON_FREE_LIST),
(VECTOR_SIZE, VECTOR_IN_BLOCK): New macros.
(roundup_size): New constant.
(struct vector_block): New data type.
(vector_blocks, vector_free_lists, zero_vector): New variables.
(all_vectors): Renamed to `large_vectors'.
(allocate_vector_from_block, init_vectors, allocate_vector_from_block)
(sweep_vectors): New functions.
(allocate_vectorlike): Return `zero_vector' as the only vector of
0 items. Allocate new vector from block if vector size is less than
or equal to VBLOCK_BYTES_MAX.
(Fgarbage_collect): Move all vector sweeping code to sweep_vectors.
(init_alloc_once): Add call to init_vectors.
* doc/lispref/internals.text (Garbage Collection): Document new
vector management code and vectorlike_header structure.

2 files changed, 28 insertions, 6 deletions

diff --git a/doc/lispref/ChangeLog b/doc/lispref/ChangeLog
index b774809feb9..1ef5595fa06 100644
--- a/doc/lispref/ChangeLog
+++ b/doc/lispref/ChangeLog
@@ -1,3 +1,8 @@
+2012-06-08  Dmitry Antipov  <dmantipov@yandex.ru>
+
+        * internals.text (Garbage Collection): Document new
+        vector management code and vectorlike_header structure.
+
 2012-06-03  Chong Yidong  <cyd@gnu.org>
 
         * modes.texi (Mode Line Data): Use "mode line construct"
diff --git a/doc/lispref/internals.texi b/doc/lispref/internals.texi
index 5d4a9c6a3af..1d0a7102a22 100644
--- a/doc/lispref/internals.texi
+++ b/doc/lispref/internals.texi
@@ -215,10 +215,23 @@ You should not change this flag in a running Emacs.
 (such as by loading a library), that data is placed in normal storage.
 If normal storage runs low, then Emacs asks the operating system to
 allocate more memory.  Different types of Lisp objects, such as
-symbols, cons cells, markers, etc., are segregated in distinct blocks
-in memory.  (Vectors, long strings, buffers and certain other editing
-types, which are fairly large, are allocated in individual blocks, one
-per object, while small strings are packed into blocks of 8k bytes.)
+symbols, cons cells, small vectors, markers, etc., are segregated in
+distinct blocks in memory.  (Large vectors, long strings, buffers and
+certain other editing types, which are fairly large, are allocated in
+individual blocks, one per object; small strings are packed into blocks
+of 8k bytes, and small vectors are packed into blocks of 4k bytes).
+
+@cindex vector-like objects, storage
+@cindex storage of vector-like Lisp objects
+  Beyond the basic vector, a lot of objects like window, buffer, and
+frame are managed as if they were vectors.  The corresponding C data
+structures include the @code{struct vectorlike_header} field whose
+@code{next} field points to the next object in the chain:
+@code{header.next.buffer} points to the next buffer (which could be
+a killed buffer), and @code{header.next.vector} points to the next
+vector in a free list.  If a vector is small (smaller than or equal to
+@code{VBLOCK_BYTES_MIN} bytes, see @file{alloc.c}), then
+@code{header.next.nbytes} contains the vector size in bytes.
 
 @cindex garbage collection
   It is quite common to use some storage for a while, then release it
@@ -243,8 +256,12 @@ might as well be reused, since no one will miss them.  The second
   The sweep phase puts unused cons cells onto a @dfn{free list}
 for future allocation; likewise for symbols and markers.  It compacts
 the accessible strings so they occupy fewer 8k blocks; then it frees the
-other 8k blocks.  Vectors, buffers, windows, and other large objects are
-individually allocated and freed using @code{malloc} and @code{free}.
+other 8k blocks.  Unreachable vectors from vector blocks are coalesced
+to create largest possible free areas; if a free area spans a complete
+4k block, that block is freed.  Otherwise, the free area is recorded
+in a free list array, where each entry corresponds to a free list
+of areas of the same size.  Large vectors, buffers, and other large
+objects are allocated and freed individually.
 
 @cindex CL note---allocate more storage
 @quotation