Patchwork graphds.[ch]: alloc_pool for edges

login
register
mail settings
Submitter Dimitrios Apostolou
Date Aug. 22, 2011, 7:37 a.m.
Message ID <alpine.LNX.2.02.1108221032460.1374@localhost.localdomain>
Download mbox | patch
Permalink /patch/110861/
State New
Headers show

Comments

Dimitrios Apostolou - Aug. 22, 2011, 7:37 a.m.
free() was called way too often before, this patch reduces it 
significantly. Minor speed-up here too, I don't mention it individually 
since numbers are within noise margins.


2011-08-22  Dimitrios Apostolou  <jimis@gmx.net>

 	* graphds.h (struct graph): Added edge_pool as a pool for
 	allocating edges.
 	* graphds.c (new_graph): Initialise edge_pool.
 	(add_edge): Allocate edge from edge_pool rather than with malloc.
 	(free_graph): Instead of iterating across the graph freeing edges,
 	just destroy the edge_pool.
Jakub Jelinek - Aug. 22, 2011, 7:52 a.m.
On Mon, Aug 22, 2011 at 10:37:58AM +0300, Dimitrios Apostolou wrote:
> --- gcc/graphds.h	2009-02-20 15:20:38 +0000
> +++ gcc/graphds.h	2011-08-19 16:44:41 +0000
> @@ -18,6 +18,10 @@ You should have received a copy of the G
>  along with GCC; see the file COPYING3.  If not see
>  <http://www.gnu.org/licenses/>.  */
>  
> +
> +#include "alloc-pool.h"
> +
> +

This needs to be reflected in Makefile.in, we unfortunately don't have
automatic dependency generation for gcc.
So, create
GRAPHDS_H = graphds.h alloc-pool.h
and use $(GRAPHDS_H) everywhere where graphds.h has been used so far.

	Jakub
Richard Guenther - Aug. 22, 2011, 9:52 a.m.
On Mon, Aug 22, 2011 at 9:37 AM, Dimitrios Apostolou <jimis@gmx.net> wrote:
> free() was called way too often before, this patch reduces it significantly.
> Minor speed-up here too, I don't mention it individually since numbers are
> within noise margins.

As there is no re-use in this pool the natural allocator to use is an
obstack which has even less overhead than a alloc_pool.

Richard.

>
> 2011-08-22  Dimitrios Apostolou  <jimis@gmx.net>
>
>        * graphds.h (struct graph): Added edge_pool as a pool for
>        allocating edges.
>        * graphds.c (new_graph): Initialise edge_pool.
>        (add_edge): Allocate edge from edge_pool rather than with malloc.
>        (free_graph): Instead of iterating across the graph freeing edges,
>        just destroy the edge_pool.
>

Patch

=== modified file 'gcc/graphds.c'
--- gcc/graphds.c	2009-11-25 10:55:54 +0000

+++ gcc/graphds.c	2011-08-19 16:44:41 +0000

@@ -62,7 +62,8 @@  new_graph (int n_vertices)

 
   g->n_vertices = n_vertices;
   g->vertices = XCNEWVEC (struct vertex, n_vertices);
-

+  g->edge_pool = create_alloc_pool ("edge_pool",

+				    sizeof (struct graph_edge), 32);

   return g;
 }
 
@@ -71,7 +72,7 @@  new_graph (int n_vertices)

 struct graph_edge *
 add_edge (struct graph *g, int f, int t)
 {
-  struct graph_edge *e = XNEW (struct graph_edge);

+  struct graph_edge *e = (struct graph_edge *) pool_alloc (g->edge_pool);

   struct vertex *vf = &g->vertices[f], *vt = &g->vertices[t];
 
 
@@ -326,19 +327,7 @@  for_each_edge (struct graph *g, graphds_

 void
 free_graph (struct graph *g)
 {
-  struct graph_edge *e, *n;

-  struct vertex *v;

-  int i;

-

-  for (i = 0; i < g->n_vertices; i++)

-    {

-      v = &g->vertices[i];

-      for (e = v->succ; e; e = n)

-	{

-	  n = e->succ_next;

-	  free (e);

-	}

-    }

+  free_alloc_pool (g->edge_pool);

   free (g->vertices);
   free (g);
 }

=== modified file 'gcc/graphds.h'
--- gcc/graphds.h	2009-02-20 15:20:38 +0000

+++ gcc/graphds.h	2011-08-19 16:44:41 +0000

@@ -18,6 +18,10 @@  You should have received a copy of the G

 along with GCC; see the file COPYING3.  If not see
 <http://www.gnu.org/licenses/>.  */
 
+

+#include "alloc-pool.h"

+

+

 /* Structure representing edge of a graph.  */
 
 struct graph_edge
@@ -44,10 +48,10 @@  struct vertex

 
 struct graph
 {
-  int n_vertices;	/* Number of vertices.  */

-  struct vertex *vertices;

-			/* The vertices.  */

-  htab_t indices;	/* Fast lookup for indices.  */

+  int n_vertices;		/* Number of vertices.  */

+  struct vertex *vertices;	/* The vertices.  */

+  htab_t indices;		/* Fast lookup for indices.  */

+  alloc_pool edge_pool;		/* Pool for allocating edges. */

 };
 
 struct graph *new_graph (int);