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);
+ }
}
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"
