[PATCH 7/7] Reduce memory waste due to non-power-of-2 allocs

[Dodji Seketeli <dodji@redhat.com>]

This patch basically arranges for the allocation size of line_map
buffers to be as close as possible to a power of two.  This
*significantly* decreases peak memory consumption as (macro) maps are
numerous and stay live during all the compilation.

Ideally, I'd prefer some parts of this patch to be integrated into the
memory allocator.  That is, I'd like to see the memory allocator have
an interface that returns the actual size of memory it has allocated.
This would help client code like this one to avoid requesting memory
unnecessarily.  I am proposing this patch as is for now, at least to
see if the approach would be acceptable.

Tested on x86_64-unknown-linux-gnu against trunk.

libcpp/

	* line-map.c (next_largest_power_of_two): New.
	(new_linemap): Use it.
---
 libcpp/line-map.c |   50 +++++++++++++++++++++++++++++++++++++++++++-------
 1 files changed, 43 insertions(+), 7 deletions(-)

diff --git a/libcpp/line-map.c b/libcpp/line-map.c
index d69160c..327ce85 100644
--- a/libcpp/line-map.c
+++ b/libcpp/line-map.c
@@ -95,6 +95,18 @@ linemap_tracks_macro_expansion_locs_p (struct line_maps *set)
   return LINEMAPS_MACRO_MAPS (set) != NULL;
 }
 
+/* Return the smallest power of two that is greater than N.   */
+static unsigned
+next_largest_power_of_two (unsigned n)
+{
+  n |= (n >> 1);
+  n |= (n >> 2);
+  n |= (n >> 4);
+  n |= (n >> 8);
+  n |= (n >> 16);
+  return n+1;
+}
+
 /* Create a new line map in the line map set SET, and return it.
    REASON is the reason of creating the map. It determines the type
    of map created (ordinary or macro map). Note that ordinary maps and
@@ -109,19 +121,43 @@ new_linemap (struct line_maps *set,
   bool macro_map_p = (reason == LC_ENTER_MACRO);
   struct line_map *result;
 
-  if (LINEMAPS_USED (set, macro_map_p) == LINEMAPS_ALLOCATED (set, macro_map_p))
+  if (LINEMAPS_USED (set, macro_map_p)
+      == LINEMAPS_ALLOCATED (set, macro_map_p))
     {
       /* We ran out of allocated line maps. Let's allocate more.  */
+      unsigned alloc_size;
 
       line_map_realloc reallocator
 	= set->reallocator ? set->reallocator : xrealloc;
+
+      /* We are going to execute some dance to try to reduce the
+	 overhead of the memory allocator, in case we are using the
+	 ggc-page.c one.
+	 
+	 The actual size of memory we are going to get back from the
+	 allocator is the smallest power of 2 that is greater than the
+	 size we requested.  So let's consider that size then.  */
+
+      alloc_size =
+	(2 * LINEMAPS_ALLOCATED (set, macro_map_p) +  256)
+	* sizeof (struct line_map);
+
+      alloc_size = next_largest_power_of_two (alloc_size);
+
+      /* Now alloc_size contains the exact memory size we would get if
+	 we have asked for the initial alloc_size amount of memory.
+	 Let's get back to the number of macro map that amounts
+	 to.  */
       LINEMAPS_ALLOCATED (set, macro_map_p) =
-	2 * LINEMAPS_ALLOCATED (set, macro_map_p) + 256;
-      LINEMAPS_MAPS (set, macro_map_p)
-	= (struct line_map *) (*reallocator) (LINEMAPS_MAPS (set, macro_map_p),
-					      LINEMAPS_ALLOCATED (set,
-								  macro_map_p)
-					      * sizeof (struct line_map));
+	alloc_size / (sizeof (struct line_map));
+
+      /* And now let's really do the re-allocation.  */
+      LINEMAPS_MAPS (set, macro_map_p) =
+	(struct line_map *) (*reallocator)
+	(LINEMAPS_MAPS (set, macro_map_p),
+	 (LINEMAPS_ALLOCATED (set, macro_map_p)
+	  * sizeof (struct line_map)));
+
       result =
 	&LINEMAPS_MAPS (set, macro_map_p)[LINEMAPS_USED (set, macro_map_p)];
       memset (result, 0,
-- 
1.7.6