Optimize fibonacci heap allocations

Message ID 20191120112951.esx6px4dr5shm245@kam.mff.cuni.cz
State New
Headers show
Series
  • Optimize fibonacci heap allocations
Related show

Commit Message

Jan Hubicka Nov. 20, 2019, 11:29 a.m.
Hi,
since inliner got faster malloc overhead starts to show up in profiles.
This patch eliminates a lot of malloc/free traffic by putting fibonaci
heaps nodes into pool allocators.

It also fixes a silly issue with constant sized vector not being
allocated on stack (which actually seems most important problem here).

I went with pool_allocator rather than object_allocator because I do not
know how to call non-default constructor which of fibonnaci node which
is used by fibonacci_heap<K,V>::insert.

By default every heap has its own allocator.  We implement (but do not
use) union_with operation for which I needed to add a way to allocate
multiple heaps in one allocator.

Bootstrapped/regtested x86_64-linux, OK?

Honza

	* fibonacci_heap.h (fibonacci_heap<K,V>::fibonacci_heap):
	Add allocator parameter.
	(fibonacci_heap<K,V>::~fibonacci_heap): Optimize destruction.
	(fibonacci_heap<K,V>::m_allocator): New.
	(fibonacci_heap<K,V>::m_own_allocator): New.
	(fibonacci_heap<K,V>::insert): Use allocator.
	(fibonacci_heap<K,V>::extract_min): Likewise.
	(fibonacci_heap<K,V>::union_with): Assert that both heaps share
	allocator.
	(fibonacci_heap<K,V>::consolidate): Allocate constant sized vector
	on stack.
	* fibonacci_heap.c: Include alloc-pool
	(test_empty_heap): Initialize allocator.
	(test_union): Likewise.
	* bb-reorder.c: Include alloc-pool.h.
	* tracer.c: Inlclude alloc-pool.h.

Comments

Richard Biener Nov. 20, 2019, 11:47 a.m. | #1
On Wed, 20 Nov 2019, Jan Hubicka wrote:

> Hi,

> since inliner got faster malloc overhead starts to show up in profiles.

> This patch eliminates a lot of malloc/free traffic by putting fibonaci

> heaps nodes into pool allocators.

> 

> It also fixes a silly issue with constant sized vector not being

> allocated on stack (which actually seems most important problem here).

> 

> I went with pool_allocator rather than object_allocator because I do not

> know how to call non-default constructor which of fibonnaci node which

> is used by fibonacci_heap<K,V>::insert.

> 

> By default every heap has its own allocator.  We implement (but do not

> use) union_with operation for which I needed to add a way to allocate

> multiple heaps in one allocator.

> 

> Bootstrapped/regtested x86_64-linux, OK?

> 

> Honza

> 

> 	* fibonacci_heap.h (fibonacci_heap<K,V>::fibonacci_heap):

> 	Add allocator parameter.

> 	(fibonacci_heap<K,V>::~fibonacci_heap): Optimize destruction.

> 	(fibonacci_heap<K,V>::m_allocator): New.

> 	(fibonacci_heap<K,V>::m_own_allocator): New.

> 	(fibonacci_heap<K,V>::insert): Use allocator.

> 	(fibonacci_heap<K,V>::extract_min): Likewise.

> 	(fibonacci_heap<K,V>::union_with): Assert that both heaps share

> 	allocator.

> 	(fibonacci_heap<K,V>::consolidate): Allocate constant sized vector

> 	on stack.

> 	* fibonacci_heap.c: Include alloc-pool

> 	(test_empty_heap): Initialize allocator.

> 	(test_union): Likewise.

> 	* bb-reorder.c: Include alloc-pool.h.

> 	* tracer.c: Inlclude alloc-pool.h.

> Index: fibonacci_heap.h

> ===================================================================

> --- fibonacci_heap.h	(revision 278464)

> +++ fibonacci_heap.h	(working copy)

> @@ -145,17 +145,36 @@ class fibonacci_heap

>    friend class fibonacci_node<K,V>;

>  

>  public:

> -  /* Default constructor.  */

> -  fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),

> -    m_global_min_key (global_min_key)

> +  /* Default constructor.  ALLOCATOR is optional and is primarily useful

> +     when heaps are going to be merged (in that case they need to be allocated

> +     in same alloc pool).  */

> +  fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):

> +    m_nodes (0), m_min (NULL), m_root (NULL),

> +    m_global_min_key (global_min_key),

> +    m_allocator (allocator), m_own_allocator (false)

>    {

> +    if (!m_allocator)

> +      {

> +        m_allocator = new pool_allocator ("Fibonacci heap",

> +					    sizeof (fibonacci_node_t));

> +	m_own_allocator = true;

> +      }

>    }

>  

>    /* Destructor.  */

>    ~fibonacci_heap ()

>    {

> -    while (m_min != NULL)

> -      delete (extract_minimum_node ());

> +    /* Actual memory will be released by the destructor of m_allocator.  */

> +    if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)

> +      while (m_min != NULL)

> +	{

> +          fibonacci_node_t *n = extract_minimum_node ();

> +	  n->~fibonacci_node_t ();

> +	  if (!m_own_allocator)

> +	    m_allocator->remove (n);

> +	}

> +    if (m_own_allocator)

> +      delete m_allocator;

>    }

>  

>    /* Insert new node given by KEY and DATA associated with the key.  */

> @@ -259,6 +278,11 @@ private:

>    fibonacci_node_t *m_root;

>    /* Global minimum given in the heap construction.  */

>    K m_global_min_key;

> +

> +  /* Allocator used to hold nodes.  */

> +  pool_allocator *m_allocator;

> +  /* True if alocator is owned by the current heap only.  */

> +  bool m_own_allocator;

>  };

>  

>  /* Remove fibonacci heap node.  */

> @@ -333,7 +357,8 @@ fibonacci_node<K,V>*

>  fibonacci_heap<K,V>::insert (K key, V *data)

>  {

>    /* Create the new node.  */

> -  fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);

> +  fibonacci_node<K,V> *node = new (m_allocator->allocate ())

> +				  fibonacci_node_t (key, data);

>  

>    return insert_node (node);

>  }

> @@ -438,7 +463,10 @@ fibonacci_heap<K,V>::extract_min (bool r

>        ret = z->m_data;

>  

>        if (release)

> -        delete (z);

> +	{

> +	  z->~fibonacci_node_t ();

> +          m_allocator->remove (z);

> +	}


tab/space mixup here

>      }

>  

>    return ret;

> @@ -474,6 +502,9 @@ fibonacci_heap<K,V>::union_with (fibonac

>  

>    fibonacci_node<K,V> *a_root, *b_root;

>  

> +  /* Both heaps must share allocator.  */

> +  gcc_checking_assert (m_allocator == heapb->m_allocator);

> +

>    /* If one of the heaps is empty, the union is just the other heap.  */

>    if ((a_root = heapa->m_root) == NULL)

>      {

> @@ -616,8 +647,8 @@ fibonacci_heap<K,V>::remove_root (fibona

>  template<class K, class V>

>  void fibonacci_heap<K,V>::consolidate ()

>  {

> -  int D = 1 + 8 * sizeof (long);

> -  auto_vec<fibonacci_node<K,V> *> a (D);

> +  const int D = 1 + 8 * sizeof (long);

> +  auto_vec<fibonacci_node<K,V> *, D> a;

>    a.safe_grow_cleared (D);


this can now use a.quick_grow_cleared (D)

Ok with those changes.

Thanks,
Richard.

>    fibonacci_node<K,V> *w, *x, *y;

>    int i, d;

> Index: fibonacci_heap.c

> ===================================================================

> --- fibonacci_heap.c	(revision 278464)

> +++ fibonacci_heap.c	(working copy)

> @@ -21,6 +21,7 @@ along with GCC; see the file COPYING3.

>  #include "config.h"

>  #include "system.h"

>  #include "coretypes.h"

> +#include "alloc-pool.h"

>  #include "fibonacci_heap.h"

>  #include "selftest.h"

>  

> @@ -38,13 +39,14 @@ typedef fibonacci_heap <int, int> int_he

>  static void

>  test_empty_heap ()

>  {

> -  int_heap_t *h1 = new int_heap_t (INT_MIN);

> +  pool_allocator allocator ("fibheap test");

> +  int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);

>  

>    ASSERT_TRUE (h1->empty ());

>    ASSERT_EQ (0, h1->nodes ());

>    ASSERT_EQ (NULL, h1->min ());

>  

> -  int_heap_t *h2 = new int_heap_t (INT_MIN);

> +  int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);

>  

>    int_heap_t *r = h1->union_with (h2);

>    ASSERT_TRUE (r->empty ());

> @@ -169,12 +171,13 @@ static void

>  test_union ()

>  {

>    int value = 777;

> +  pool_allocator allocator ("fibheap test");

>  

> -  int_heap_t *heap1 = new int_heap_t (INT_MIN);

> +  int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);

>    for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)

>      heap1->insert (i, &value);

>  

> -  int_heap_t *heap2 = new int_heap_t (INT_MIN);

> +  int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);

>    for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)

>      heap2->insert (i, &value);

>  

> Index: bb-reorder.c

> ===================================================================

> --- bb-reorder.c	(revision 278464)

> +++ bb-reorder.c	(working copy)

> @@ -112,6 +112,7 @@

>  #include "cfgcleanup.h"

>  #include "bb-reorder.h"

>  #include "except.h"

> +#include "alloc-pool.h"

>  #include "fibonacci_heap.h"

>  #include "stringpool.h"

>  #include "attribs.h"

> Index: tracer.c

> ===================================================================

> --- tracer.c	(revision 278464)

> +++ tracer.c	(working copy)

> @@ -49,6 +49,7 @@

>  #include "tree-ssa.h"

>  #include "tree-inline.h"

>  #include "cfgloop.h"

> +#include "alloc-pool.h"

>  #include "fibonacci_heap.h"

>  #include "tracer.h"

>  

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
Jan Hubicka Nov. 20, 2019, 3:29 p.m. | #2
Hi,
sadly this patch seems to trigger false positive 
../../gcc/vec.h:311:10: error: attempt to free a non-heap object �@Xa�@Y
[-Werror=free-nonheap-object]

which is about vec destructor freeing heap allocated memory if the
vector was ever resized from hits stack allocated place.  In this case
it never is.

I am testing the following workaround which turns it into simple array
(only benefit of auto_vec here is the bounds check that I implemented by
hand).

I will commit it once x86_64-linux boostrap finishes unless someone
comes with better alternative. Sorry for this - it did not show up with
LTO build for me.

Honza

	* fibonacci_heap.h (fibonacci_heap<K,V>::consolidate): Turn auto_vec
	to ordinary array.

Index: fibonacci_heap.h
===================================================================
--- fibonacci_heap.h	(revision 278501)
+++ fibonacci_heap.h	(working copy)
@@ -648,17 +648,18 @@ template<class K, class V>
 void fibonacci_heap<K,V>::consolidate ()
 {
   const int D = 1 + 8 * sizeof (long);
-  auto_vec<fibonacci_node<K,V> *, D> a;
+  fibonacci_node<K,V> *a[D];
   fibonacci_node<K,V> *w, *x, *y;
   int i, d;
 
-  a.quick_grow_cleared (D);
+  memset (a, 0, sizeof (a));
 
   while ((w = m_root) != NULL)
     {
       x = w;
       remove_root (w);
       d = x->m_degree;
+      gcc_checking_assert (d < D);
       while (a[d] != NULL)
 	{
 	  y = a[d];
Richard Biener Nov. 21, 2019, 2:13 p.m. | #3
On Wed, 20 Nov 2019, Jan Hubicka wrote:

> Hi,

> sadly this patch seems to trigger false positive 

> ../../gcc/vec.h:311:10: error: attempt to free a non-heap object ???@Xa???@Y

> [-Werror=free-nonheap-object]

> 

> which is about vec destructor freeing heap allocated memory if the

> vector was ever resized from hits stack allocated place.  In this case

> it never is.

> 

> I am testing the following workaround which turns it into simple array

> (only benefit of auto_vec here is the bounds check that I implemented by

> hand).

> 

> I will commit it once x86_64-linux boostrap finishes unless someone

> comes with better alternative. Sorry for this - it did not show up with

> LTO build for me.


I've committed a workaround for a similar issue to vec.h, so you
might want to re-check.

Richard.

> Honza

> 

> 	* fibonacci_heap.h (fibonacci_heap<K,V>::consolidate): Turn auto_vec

> 	to ordinary array.

> 

> Index: fibonacci_heap.h

> ===================================================================

> --- fibonacci_heap.h	(revision 278501)

> +++ fibonacci_heap.h	(working copy)

> @@ -648,17 +648,18 @@ template<class K, class V>

>  void fibonacci_heap<K,V>::consolidate ()

>  {

>    const int D = 1 + 8 * sizeof (long);

> -  auto_vec<fibonacci_node<K,V> *, D> a;

> +  fibonacci_node<K,V> *a[D];

>    fibonacci_node<K,V> *w, *x, *y;

>    int i, d;

>  

> -  a.quick_grow_cleared (D);

> +  memset (a, 0, sizeof (a));

>  

>    while ((w = m_root) != NULL)

>      {

>        x = w;

>        remove_root (w);

>        d = x->m_degree;

> +      gcc_checking_assert (d < D);

>        while (a[d] != NULL)

>  	{

>  	  y = a[d];

> 


-- 
Richard Biener <rguenther@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)

Patch

Index: fibonacci_heap.h
===================================================================
--- fibonacci_heap.h	(revision 278464)
+++ fibonacci_heap.h	(working copy)
@@ -145,17 +145,36 @@  class fibonacci_heap
   friend class fibonacci_node<K,V>;
 
 public:
-  /* Default constructor.  */
-  fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
-    m_global_min_key (global_min_key)
+  /* Default constructor.  ALLOCATOR is optional and is primarily useful
+     when heaps are going to be merged (in that case they need to be allocated
+     in same alloc pool).  */
+  fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
+    m_nodes (0), m_min (NULL), m_root (NULL),
+    m_global_min_key (global_min_key),
+    m_allocator (allocator), m_own_allocator (false)
   {
+    if (!m_allocator)
+      {
+        m_allocator = new pool_allocator ("Fibonacci heap",
+					    sizeof (fibonacci_node_t));
+	m_own_allocator = true;
+      }
   }
 
   /* Destructor.  */
   ~fibonacci_heap ()
   {
-    while (m_min != NULL)
-      delete (extract_minimum_node ());
+    /* Actual memory will be released by the destructor of m_allocator.  */
+    if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
+      while (m_min != NULL)
+	{
+          fibonacci_node_t *n = extract_minimum_node ();
+	  n->~fibonacci_node_t ();
+	  if (!m_own_allocator)
+	    m_allocator->remove (n);
+	}
+    if (m_own_allocator)
+      delete m_allocator;
   }
 
   /* Insert new node given by KEY and DATA associated with the key.  */
@@ -259,6 +278,11 @@  private:
   fibonacci_node_t *m_root;
   /* Global minimum given in the heap construction.  */
   K m_global_min_key;
+
+  /* Allocator used to hold nodes.  */
+  pool_allocator *m_allocator;
+  /* True if alocator is owned by the current heap only.  */
+  bool m_own_allocator;
 };
 
 /* Remove fibonacci heap node.  */
@@ -333,7 +357,8 @@  fibonacci_node<K,V>*
 fibonacci_heap<K,V>::insert (K key, V *data)
 {
   /* Create the new node.  */
-  fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
+  fibonacci_node<K,V> *node = new (m_allocator->allocate ())
+				  fibonacci_node_t (key, data);
 
   return insert_node (node);
 }
@@ -438,7 +463,10 @@  fibonacci_heap<K,V>::extract_min (bool r
       ret = z->m_data;
 
       if (release)
-        delete (z);
+	{
+	  z->~fibonacci_node_t ();
+          m_allocator->remove (z);
+	}
     }
 
   return ret;
@@ -474,6 +502,9 @@  fibonacci_heap<K,V>::union_with (fibonac
 
   fibonacci_node<K,V> *a_root, *b_root;
 
+  /* Both heaps must share allocator.  */
+  gcc_checking_assert (m_allocator == heapb->m_allocator);
+
   /* If one of the heaps is empty, the union is just the other heap.  */
   if ((a_root = heapa->m_root) == NULL)
     {
@@ -616,8 +647,8 @@  fibonacci_heap<K,V>::remove_root (fibona
 template<class K, class V>
 void fibonacci_heap<K,V>::consolidate ()
 {
-  int D = 1 + 8 * sizeof (long);
-  auto_vec<fibonacci_node<K,V> *> a (D);
+  const int D = 1 + 8 * sizeof (long);
+  auto_vec<fibonacci_node<K,V> *, D> a;
   a.safe_grow_cleared (D);
   fibonacci_node<K,V> *w, *x, *y;
   int i, d;
Index: fibonacci_heap.c
===================================================================
--- fibonacci_heap.c	(revision 278464)
+++ fibonacci_heap.c	(working copy)
@@ -21,6 +21,7 @@  along with GCC; see the file COPYING3.
 #include "config.h"
 #include "system.h"
 #include "coretypes.h"
+#include "alloc-pool.h"
 #include "fibonacci_heap.h"
 #include "selftest.h"
 
@@ -38,13 +39,14 @@  typedef fibonacci_heap <int, int> int_he
 static void
 test_empty_heap ()
 {
-  int_heap_t *h1 = new int_heap_t (INT_MIN);
+  pool_allocator allocator ("fibheap test");
+  int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);
 
   ASSERT_TRUE (h1->empty ());
   ASSERT_EQ (0, h1->nodes ());
   ASSERT_EQ (NULL, h1->min ());
 
-  int_heap_t *h2 = new int_heap_t (INT_MIN);
+  int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);
 
   int_heap_t *r = h1->union_with (h2);
   ASSERT_TRUE (r->empty ());
@@ -169,12 +171,13 @@  static void
 test_union ()
 {
   int value = 777;
+  pool_allocator allocator ("fibheap test");
 
-  int_heap_t *heap1 = new int_heap_t (INT_MIN);
+  int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
   for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
     heap1->insert (i, &value);
 
-  int_heap_t *heap2 = new int_heap_t (INT_MIN);
+  int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
   for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
     heap2->insert (i, &value);
 
Index: bb-reorder.c
===================================================================
--- bb-reorder.c	(revision 278464)
+++ bb-reorder.c	(working copy)
@@ -112,6 +112,7 @@ 
 #include "cfgcleanup.h"
 #include "bb-reorder.h"
 #include "except.h"
+#include "alloc-pool.h"
 #include "fibonacci_heap.h"
 #include "stringpool.h"
 #include "attribs.h"
Index: tracer.c
===================================================================
--- tracer.c	(revision 278464)
+++ tracer.c	(working copy)
@@ -49,6 +49,7 @@ 
 #include "tree-ssa.h"
 #include "tree-inline.h"
 #include "cfgloop.h"
+#include "alloc-pool.h"
 #include "fibonacci_heap.h"
 #include "tracer.h"