Optimize fibonacci heap allocations

Wed Nov 20 12:14:00 GMT 2019

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)