From patchwork Mon Aug 22 07:37:58 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dimitrios Apostolou X-Patchwork-Id: 110861 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 2837CB6F77 for ; Mon, 22 Aug 2011 17:39:53 +1000 (EST) Received: (qmail 11326 invoked by alias); 22 Aug 2011 07:39:50 -0000 Received: (qmail 11316 invoked by uid 22791); 22 Aug 2011 07:39:49 -0000 X-SWARE-Spam-Status: No, hits=-2.2 required=5.0 tests=AWL, BAYES_00, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mailout-de.gmx.net (HELO mailout-de.gmx.net) (213.165.64.22) by sourceware.org (qpsmtpd/0.43rc1) with SMTP; Mon, 22 Aug 2011 07:39:36 +0000 Received: (qmail invoked by alias); 22 Aug 2011 07:38:00 -0000 Received: from teras.ics.forth.gr (EHLO [139.91.70.93]) [139.91.70.93] by mail.gmx.net (mp060) with SMTP; 22 Aug 2011 09:38:00 +0200 Date: Mon, 22 Aug 2011 10:37:58 +0300 (EEST) From: Dimitrios Apostolou To: Dimitrios Apostolou cc: gcc-patches@gcc.gnu.org, Steven Bosscher Subject: graphds.[ch]: alloc_pool for edges In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (LNX 1266 2009-07-14) MIME-Version: 1.0 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 * 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. === 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 . */ + +#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);