diff mbox

graphds.[ch]: alloc_pool for edges

Message ID alpine.LNX.2.02.1108221032460.1374@localhost.localdomain
State New
Headers show

Commit Message

Dimitrios Apostolou Aug. 22, 2011, 7:37 a.m. UTC 
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.

Comments

Jakub Jelinek Aug. 22, 2011, 7:52 a.m. UTC | #1 
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 Biener Aug. 22, 2011, 9:52 a.m. UTC | #2 
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.
>
diff mbox

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);