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 <rguent...@suse.de>
SUSE Software Solutions Germany GmbH, Maxfeldstrasse 5, 90409 Nuernberg,
Germany; GF: Felix Imendörffer; HRB 36809 (AG Nuernberg)
