[PATCH]: Pool allocation of a few structures

[PATCH]: Pool allocation of a few structures

[Daniel Berlin]

This patch includes a pool based allocator for fixed size objects, and
uses it for et-forest things and basic blocks, to improve locality.
This does better than the patch i submitted yesterday, it knocks 12
seconds (out of 26) off branch prediction rather than 10, and improves
cache locality of basic block traversals.

The et-forest changes no longer depend on ggc-page behavior.

The basic blocks used to be obstack allocated, with a freelist. This is
close to what the pool does, except the pool doesn't have anything but
basic blocks to allocate.

I've not included a changelog (the changes to existing files are trivial
enough to look at and answer the question below), though this patch was
bootstrapped on i686-pc-linux-gnu and reg-tested.

I only wanted to know whether it *would* be acceptable to include a pool
allocator for fixed size objects and use it in gcc, and whether the
current one included is acceptable. If so, i'll split up the patch below
into a submission of the new files, and one patch each for the changes to
allocate et-forest.c and cfg.c.

Thus, the lack of a changelog since i just want people to look at the new
files and an example of how it's used.
--Dan


Index: alloc-pool.c
===================================================================
RCS file: alloc-pool.c
diff -N alloc-pool.c
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ alloc-pool.c	17 Dec 2002 20:26:42 -0000
@@ -0,0 +1,167 @@
+/* Functions to support a pool of allocatable objects.
+   Copyright (C) 1987, 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@cgsoftware.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "libiberty.h"
+#include "config.h"
+#include "system.h"
+#include "toplev.h"
+#include "alloc-pool.h"
+
+#define align_four(x) (((x+3) >> 2) << 2)
+#define align_eight(x) (((x+7) >> 3) << 3)
+
+/* Create a pool of things of size SIZE, with NUM in each block we
+   allocate.  */
+
+alloc_pool
+create_alloc_pool (name, size, num)
+     const char *name;
+     size_t size;
+     size_t num;
+{
+  alloc_pool pool;
+  size_t pool_size, header_size;
+
+  if (!name)
+    abort ();
+
+  /* Make size large enough to store the list header.  */
+  if (size < sizeof (alloc_pool_list))
+    size = sizeof (alloc_pool_list);
+
+  /* Now align the size to a multiple of 4.  */
+  size = align_four (size);
+
+  /* Um, we can't really allocate 0 elements per block.  */
+  if (num == 0)
+    abort ();
+
+  /* Find the size of the pool structure, and the name.  */
+  pool_size = sizeof (struct alloc_pool_def);
+
+  /* and allocate that much memory.  */
+  pool = (alloc_pool) xmalloc (pool_size);
+
+  /* Now init the various pieces of our pool structure.  */
+  pool->name = xstrdup (name);
+  pool->elt_size = size;
+  pool->elts_per_block = num;
+
+  /* List header size should be a multiple of 8 */
+  header_size = align_eight (sizeof (struct alloc_pool_list_def));
+
+  pool->block_size = (size * num) + header_size;
+  pool->free_list = NULL;
+  pool->elts_allocated = 0;
+  pool->elts_free = 0;
+  pool->blocks_allocated = 0;
+  pool->block_list = NULL;
+
+  return (pool);
+}
+
+/* Free all memory allocated for the given memory pool.  */
+void
+free_alloc_pool (pool)
+     alloc_pool pool;
+{
+  alloc_pool_list block, next_block;
+
+  if (!pool)
+    abort ();
+
+  /* Free each block allocated to the pool.  */
+  for (block = pool->block_list; block != NULL; block = next_block)
+    {
+      next_block = block->next;
+      free (block);
+    }
+  /* Lastly, free the pool and the name.  */
+  free (pool->name);
+  free (pool);
+}
+
+/* Allocates one element from the pool specified.  */
+void *
+pool_alloc (pool)
+     alloc_pool pool;
+{
+  alloc_pool_list header;
+  char *block;
+
+  if (!pool)
+    abort ();
+
+  /* If there are no more free elements, make some more!.  */
+  if (!pool->free_list)
+    {
+      size_t i;
+      alloc_pool_list block_header;
+
+      /* Make the block */
+      block = (char *) xmalloc (pool->block_size);
+      block_header = (alloc_pool_list) block;
+      block += align_eight (sizeof (struct alloc_pool_list_def));
+
+      /* Throw it on the block list */
+      block_header->next = pool->block_list;
+      pool->block_list = block_header;
+
+      /* Now put the actual block pieces onto the free list.  */
+      for (i = 0; i < pool->elts_per_block; i++, block += pool->elt_size)
+      {
+        header = (alloc_pool_list) block;
+        header->next = pool->free_list;
+        pool->free_list = header;
+      }
+      /* Also update the number of elements we have free/allocated, and
+         increment the allocated block count.  */
+      pool->elts_allocated += pool->elts_per_block;
+      pool->elts_free += pool->elts_per_block;
+      pool->blocks_allocated += 1;
+    }
+
+  /* Pull the first free element from the free list, and return it.  */
+  header = pool->free_list;
+  pool->free_list = header->next;
+  pool->elts_free--;
+  return ((void *) header);
+}
+
+/* Puts PTR back on POOL's free list.  */
+void
+pool_free (pool, ptr)
+     alloc_pool pool;
+     void *ptr;
+{
+  alloc_pool_list header;
+
+  if (!ptr)
+    abort ();
+
+  /* Check if we free more than we allocated, which is Bad (TM).  */
+  if (pool->elts_free + 1 > pool->elts_allocated)
+    abort ();
+  header = (alloc_pool_list) ptr;
+  header->next = pool->free_list;
+  pool->free_list = header;
+  pool->elts_free++;
+}
Index: alloc-pool.h
===================================================================
RCS file: alloc-pool.h
diff -N alloc-pool.h
--- /dev/null	1 Jan 1970 00:00:00 -0000
+++ alloc-pool.h	17 Dec 2002 20:26:42 -0000
@@ -0,0 +1,48 @@
+
+/* Functions to support a pool of allocatable objects
+   Copyright (C) 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin <dan@cgsoftware.com>
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GCC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA.  */
+#ifndef ALLOC_POOL_H
+#define ALLOC_POOL_H
+
+typedef struct alloc_pool_list_def
+{
+  struct alloc_pool_list_def *next;
+}
+ *alloc_pool_list;
+
+typedef struct alloc_pool_def
+{
+  char *name;
+  size_t elts_per_block;
+  alloc_pool_list free_list;
+  size_t elts_allocated;
+  size_t elts_free;
+  size_t blocks_allocated;
+  alloc_pool_list block_list;
+  size_t block_size;
+  size_t elt_size;
+}
+ *alloc_pool;
+
+extern alloc_pool create_alloc_pool PARAMS ((const char *, size_t, size_t));
+extern void free_alloc_pool PARAMS ((alloc_pool));
+extern void *pool_alloc PARAMS ((alloc_pool));
+extern void pool_free PARAMS ((alloc_pool, void *));
+#endif
Index: et-forest.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/et-forest.c,v
retrieving revision 1.1.6.2
diff -u -3 -p -r1.1.6.2 et-forest.c
--- et-forest.c	25 Sep 2002 19:16:05 -0000	1.1.6.2
+++ et-forest.c	17 Dec 2002 20:26:43 -0000
@@ -26,6 +26,7 @@ Boston, MA 02111-1307, USA.
 #include "config.h"
 #include "system.h"
 #include "et-forest.h"
+#include "alloc-pool.h"

 struct et_forest_occurrence;
 typedef struct et_forest_occurrence* et_forest_occurrence_t;
@@ -35,6 +36,8 @@ struct et_forest
 {
   /* Linked list of nodes is used to destroy the structure.  */
   int nnodes;
+  alloc_pool node_pool;
+  alloc_pool occur_pool;
 };

 /* Single occurrence of node in ET-forest.
@@ -71,7 +74,7 @@ struct et_forest_node


 static et_forest_occurrence_t splay PARAMS ((et_forest_occurrence_t));
-static void remove_all_occurrences PARAMS ((et_forest_node_t));
+static void remove_all_occurrences PARAMS ((et_forest_t, et_forest_node_t));
 static inline et_forest_occurrence_t find_leftmost_node
                                PARAMS ((et_forest_occurrence_t));
 static inline et_forest_occurrence_t find_rightmost_node
@@ -334,7 +337,8 @@ splay (node)

 /* Remove all occurences of the given node before destroying the node.  */
 static void
-remove_all_occurrences (forest_node)
+remove_all_occurrences (forest, forest_node)
+     et_forest_t forest;
      et_forest_node_t forest_node;
 {
   et_forest_occurrence_t first = forest_node->first;
@@ -379,7 +383,7 @@ remove_all_occurrences (forest_node)
       if (prev_node->node->last == next_node)
 	prev_node->node->last = prev_node;

-      free (next_node);
+      pool_free (forest->occur_pool, next_node);
     }

   if (first != last)
@@ -398,14 +402,14 @@ remove_all_occurrences (forest_node)
 	    node->right->parent = 0;

 	  next_node = node->next;
-	  free (node);
+	  pool_free (forest->occur_pool, node);
 	  node = next_node;
 	}
     }

-  free (first);
+  pool_free (forest->occur_pool, first);
   if (first != last)
-    free (last);
+    pool_free (forest->occur_pool, last);
 }

 /* Calculate ET value of the given node.  */
@@ -437,6 +441,8 @@ et_forest_create ()
   et_forest_t forest = xmalloc (sizeof (struct et_forest));

   forest->nnodes = 0;
+  forest->occur_pool = create_alloc_pool ("et_forest_occurrence pool", sizeof (struct et_forest_occurrence), 300);
+  forest->node_pool = create_alloc_pool ("et_forest_node pool", sizeof (struct et_forest_node), 300);
   return forest;
 }

@@ -449,7 +455,8 @@ et_forest_delete (forest)
 {
   if (forest->nnodes)
     abort ();
-
+  free_alloc_pool (forest->occur_pool);
+  free_alloc_pool (forest->node_pool);
   free (forest);
 }

@@ -464,8 +471,8 @@ et_forest_add_node (forest, value)
   et_forest_node_t node;
   et_forest_occurrence_t occ;

-  node = xmalloc (sizeof (struct et_forest_node));
-  occ = xmalloc (sizeof (struct et_forest_occurrence));
+  node = pool_alloc (forest->node_pool);
+  occ = pool_alloc (forest->occur_pool);

   node->first = node->last = occ;
   node->value = value;
@@ -503,7 +510,7 @@ et_forest_add_edge (forest, parent_node,
   if (child_occ->left)
     abort ();  /* child must be root of its containing tree.  */

-  new_occ = xmalloc (sizeof (struct et_forest_occurrence));
+  new_occ = pool_alloc (forest->occur_pool);

   new_occ->node = parent_node;
   new_occ->left = child_occ;
@@ -530,10 +537,10 @@ et_forest_remove_node (forest, node)
      et_forest_t forest;
      et_forest_node_t node;
 {
-  remove_all_occurrences (node);
+  remove_all_occurrences (forest, node);
   forest->nnodes--;

-  free (node);
+  pool_free (forest->node_pool, node);
 }

 /* Remove edge from the tree, return 1 if sucesfull,
@@ -573,7 +580,7 @@ et_forest_remove_edge (forest, parent_no
   if (parent_post_occ == parent_node->last)
     parent_node->last = parent_pre_occ;

-  free (parent_post_occ);
+  pool_free (forest->occur_pool, parent_post_occ);
   return 1;
 }

Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.18.6.5
diff -u -3 -p -r1.18.6.5 cfg.c
--- cfg.c	3 Sep 2002 23:04:51 -0000	1.18.6.5
+++ cfg.c	17 Dec 2002 20:26:43 -0000
@@ -55,12 +55,14 @@ Software Foundation, 59 Temple Place - S
 #include "toplev.h"
 #include "tm_p.h"
 #include "obstack.h"
+#include "alloc-pool.h"

 /* The obstack on which the flow graph components are allocated.  */

 struct obstack flow_obstack;
 static char *flow_firstobj;

+static alloc_pool bb_pool;
 /* Number of basic blocks in the current function.  */

 int n_basic_blocks;
@@ -76,7 +78,6 @@ int n_edges;
 /* First edge in the deleted edges chain.  */

 edge first_deleted_edge;
-static basic_block first_deleted_block;

 /* The basic block array.  */

@@ -139,7 +140,6 @@ init_flow ()
   static int initialized;

   first_deleted_edge = 0;
-  first_deleted_block = 0;
   n_edges = 0;

   if (!initialized)
@@ -150,9 +150,11 @@ init_flow ()
     }
   else
     {
+      free_alloc_pool (bb_pool);
       obstack_free (&flow_obstack, flow_firstobj);
       flow_firstobj = (char *) obstack_alloc (&flow_obstack, 0);
     }
+  bb_pool = create_alloc_pool ("Basic block pool", sizeof (struct basic_block_def), 100);
 }

 /* Helper function for remove_edge and clear_edges.  Frees edge structure
@@ -214,18 +216,8 @@ basic_block
 alloc_block ()
 {
   basic_block bb;
-
-  if (first_deleted_block)
-    {
-      bb = first_deleted_block;
-      first_deleted_block = (basic_block) bb->succ;
-      bb->succ = NULL;
-    }
-  else
-    {
-      bb = (basic_block) obstack_alloc (&flow_obstack, sizeof *bb);
-      memset (bb, 0, sizeof *bb);
-    }
+  bb = pool_alloc (bb_pool);
+  memset (bb, 0, sizeof (*bb));
   return bb;
 }

@@ -270,7 +262,6 @@ compact_blocks ()
   last_basic_block = n_basic_blocks;
 }

-
 /* Remove block B from the basic block array.  */

 void
@@ -280,12 +271,7 @@ expunge_block (b)
   unlink_block (b);
   BASIC_BLOCK (b->index) = NULL;
   n_basic_blocks--;
-
-  /* Invalidate data to make bughunting easier.  */
-  memset (b, 0, sizeof *b);
-  b->index = -3;
-  b->succ = (edge) first_deleted_block;
-  first_deleted_block = (basic_block) b;
+  pool_free (bb_pool, b);
 }

 /* Create an edge connecting SRC and DST with FLAGS optionally using

Re: [PATCH]: Pool allocation of a few structures

[Zack Weinberg]

Daniel Berlin <dberlin@dberlin.org> writes:

> This patch includes a pool based allocator for fixed size objects, and
> uses it for et-forest things and basic blocks, to improve locality.
> This does better than the patch i submitted yesterday, it knocks 12
> seconds (out of 26) off branch prediction rather than 10, and improves
> cache locality of basic block traversals.

I think this is a fine idea.  I would suggest that you put
alloc-pool.c over in libiberty.  Also, you might want to think about
using a slab-like algorithm for even better data locality and
cacheline coloring (this would be an additional refinement).

zw

Re: [PATCH]: Pool allocation of a few structures

[Daniel Berlin]

On Tue, 17 Dec 2002, Zack Weinberg wrote:

> Daniel Berlin <dberlin@dberlin.org> writes:
>
> > This patch includes a pool based allocator for fixed size objects, and
> > uses it for et-forest things and basic blocks, to improve locality.
> > This does better than the patch i submitted yesterday, it knocks 12
> > seconds (out of 26) off branch prediction rather than 10, and improves
> > cache locality of basic block traversals.
>
> I think this is a fine idea.  I would suggest that you put
> alloc-pool.c over in libiberty.  Also, you might want to think about
> using a slab-like algorithm for even better data locality and
> cacheline coloring (this would be an additional refinement).

Actually, I forgot, but libbanshee (on the tree-ssa branch) includes
region stuff in it's libraries (which will compile without the rest of
libbanshee, it's 4 files). It was built for a recent (2001 or 2) thesis on
region based allocation, and does smart things like staggering subregions across
cache lines, etc.
I'll try it as the underlying allocator in the pool (rather than
malloc) and see how it does, since it will likely handle data locality
better than changing the pool itself would.



 > > zw >

Re: [PATCH]: Pool allocation of a few structures

[Zack Weinberg]

Daniel Berlin <dberlin@dberlin.org> writes:

> Actually, I forgot, but libbanshee (on the tree-ssa branch) includes
> region stuff in it's libraries (which will compile without the rest
> of libbanshee, it's 4 files). It was built for a recent (2001 or 2)
> thesis on region based allocation, and does smart things like
> staggering subregions across cache lines, etc.  I'll try it as the
> underlying allocator in the pool (rather than malloc) and see how it
> does, since it will likely handle data locality better than changing
> the pool itself would.

That sounds nifty.  The whole library's being linked into cc1 on the
tree-ssa branch, yes? Or is it just for a build utility?

>> FYI, I plan to address this particular issue after the New Year, by
>> picking up Dave Miller's suggestion from awhile back to avoid ever
>> allocating long-lived RTL, and then reverting RTL to obstacks -- but
>> just one obstack, data on which lives only during calls to expand_body
>> (or something like that).
> obstacks aren't something we should revert to.

I don't personally see anything wrong with them for RTL.  For RTL, we
want to allocate memory incrementally but with minimal padding and
with the content of each insn contiguous, and free it all in one go -
precisely what obstacks do.  Note I'd have just one, not the half a
dozen we used to use.

A potential issue is that some RTL optimizer passes might generate a
lot of garbage RTL that wouldn't be freed until we got to the end of
rest_of_compilation.  However, (a) my impression is that that's the
way it used to work before we got GC, and (b) arguably the optimizers
shouldn't allocate so much short-lived memory in the first place.

> It doesn't change the greater locality problem however.

Right, trees are going to be more and more important, and they have
the same problem.  Also all this other random data which is now
allocated under GC for PCH's benefit.

> I would think mark and sweep regions/pools (you can have subpools and
> whatnot, for per iteration things) per pass, one for rtl, and one for
> trees, would be a better idea.

Generational?

zw

Re: [PATCH]: Pool allocation of a few structures

[Daniel Berlin]

On Wed, 18 Dec 2002, Zack Weinberg wrote:

> Daniel Berlin <dberlin@dberlin.org> writes:
>
> > Actually, I forgot, but libbanshee (on the tree-ssa branch) includes
> > region stuff in it's libraries (which will compile without the rest
> > of libbanshee, it's 4 files). It was built for a recent (2001 or 2)
> > thesis on region based allocation, and does smart things like
> > staggering subregions across cache lines, etc.  I'll try it as the
> > underlying allocator in the pool (rather than malloc) and see how it
> > does, since it will likely handle data locality better than changing
> > the pool itself would.
>
> That sounds nifty.  The whole library's being linked into cc1 on the
> tree-ssa branch, yes?
Yes.
But all the stuff you need is in a separate subdir, and builds without the
rest of the library (it's all in the libcompat subdir).

 Or is it just for a build utility? >
> >> FYI, I plan to address this particular issue after the New Year, by
> >> picking up Dave Miller's suggestion from awhile back to avoid ever
> >> allocating long-lived RTL, and then reverting RTL to obstacks -- but
> >> just one obstack, data on which lives only during calls to expand_body
> >> (or something like that).
> > obstacks aren't something we should revert to.
>
> I don't personally see anything wrong with them for RTL.  For RTL, we
> want to allocate memory incrementally but with minimal padding and
> with the content of each insn contiguous, and free it all in one go -
> precisely what obstacks do.
Not quite.
When you replace existing RTL, you would want the new rtl to go where the
freed rtl just was.
Which is what the pool would do.
> Note I'd have just one, not the half a
> dozen we used to use.
>
> A potential issue is that some RTL optimizer passes might generate a
> lot of garbage RTL that wouldn't be freed until we got to the end of
> rest_of_compilation.  However, (a) my impression is that that's the
> way it used to work before we got GC, and (b) arguably the optimizers
> shouldn't allocate so much short-lived memory in the first place.
Sometimes this isn't possible.
The pools allow freeing (Technically the regions don't right now, but i
can change this. It's got the functions necessary, just no interface to
them).
 >
> > It doesn't change the greater locality problem however.
>
> Right, trees are going to be more and more important, and they have
> the same problem.  Also all this other random data which is now
> allocated under GC for PCH's benefit.
>
> > I would think mark and sweep regions/pools (you can have subpools and
> > whatnot, for per iteration things) per pass, one for rtl, and one for
> > trees, would be a better idea.
>
> Generational?
Yup.

Particularly because we really do have two types of objects only.
Short lived, and long lived. Either trees will die quickly, or they won't
die till the function ends.  Even those that the tree-ssa optimizers may
insert (IE SSAPRE) hold true to this.  All the insertions are "permanent".

>
> zw
>