This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Unreviewed patches
Hello,
[snip references]
> I'm not near a computer i can get to the rest of the references easily,
> i'll get you other reliable sources when i get home.
>
> I *really* think it's an implementation problem. There are a few ways to
> do various operations on the fibheap, and i just chose the simplest one,
> rather than speed testing anything.
you insired me to do some more searching. My feelings after looking at
few papers:
Nobody really considers Fibonacci heaps for use as worklist, because
they have the extra overhead in order to support decrease_key operation
that is not needed. If we remove this from Fibonacci heaps, we end up
with lazy binomial heap. Unfortunately I have found no comparison that
would take lazy binomial heaps into account, but the (non-lazy) binomial
heaps indeed outperform ordinary heaps, especially on small sizes.
Anyway I have looked at your implementation of Fibonacci heaps and made
some improvements to it; it seems fast enough for my purposes with the
attached patch.
Zdenek
* fibheap.c (fibnode_insert_after, fibheap_ins_root, fibheap_rem_root,
fibheap_link): Made inline.
(fibheap_consolidate): Speed up.
Index: fibheap.c
===================================================================
RCS file: /cvs/gcc/gcc/libiberty/fibheap.c,v
retrieving revision 1.4.26.1
diff -c -3 -p -r1.4.26.1 fibheap.c
*** fibheap.c 16 Oct 2002 16:09:14 -0000 1.4.26.1
--- fibheap.c 8 Jun 2003 13:41:24 -0000
*************** fibheap_comp_data (heap, key, data, b)
*** 101,106 ****
--- 101,139 ----
return fibheap_compare (heap, &a, b);
}
+ /* Insert node B after node A. */
+ static inline void
+ fibnode_insert_after (a, b)
+ fibnode_t a;
+ fibnode_t b;
+ {
+ b->left = a;
+ b->right = a->right;
+ a->right->left = b;
+ a->right = b;
+ }
+
+ /* Insert NODE into the root list of HEAP. */
+ static inline void
+ fibheap_ins_root (heap, node)
+ fibheap_t heap;
+ fibnode_t node;
+ {
+ /* If the heap is currently empty, the new node becomes the singleton
+ circular root list. */
+ if (heap->root == NULL)
+ {
+ heap->root = node;
+ node->left = node;
+ node->right = node;
+ return;
+ }
+
+ /* Otherwise, insert it in the circular root list between the root
+ and it's right node. */
+ fibnode_insert_after (heap->root, node);
+ }
+
/* Insert DATA, with priority KEY, into HEAP. */
fibnode_t
fibheap_insert (heap, key, data)
*************** fibheap_empty (heap)
*** 307,312 ****
--- 340,362 ----
return heap->nodes == 0;
}
+ /* Remove NODE from the rootlist of HEAP. */
+ static inline void
+ fibheap_rem_root (heap, node)
+ fibheap_t heap;
+ fibnode_t node;
+ {
+ if (node->left == node)
+ heap->root = NULL;
+ else
+ {
+ node->right->left = node->left;
+ node->left->right = node->right;
+ heap->root = node->left;
+ }
+ }
+
+
/* Extract the minimum node of the heap. */
static fibnode_t
fibheap_extr_min_node (heap)
*************** fibheap_extr_min_node (heap)
*** 344,441 ****
return ret;
}
- /* Insert NODE into the root list of HEAP. */
- static void
- fibheap_ins_root (heap, node)
- fibheap_t heap;
- fibnode_t node;
- {
- /* If the heap is currently empty, the new node becomes the singleton
- circular root list. */
- if (heap->root == NULL)
- {
- heap->root = node;
- node->left = node;
- node->right = node;
- return;
- }
-
- /* Otherwise, insert it in the circular root list between the root
- and it's right node. */
- fibnode_insert_after (heap->root, node);
- }
-
- /* Remove NODE from the rootlist of HEAP. */
- static void
- fibheap_rem_root (heap, node)
- fibheap_t heap;
- fibnode_t node;
- {
- if (node->left == node)
- heap->root = NULL;
- else
- heap->root = fibnode_remove (node);
- }
-
- /* Consolidate the heap. */
- static void
- fibheap_consolidate (heap)
- fibheap_t heap;
- {
- fibnode_t a[1 + 8 * sizeof (long)];
- fibnode_t w;
- fibnode_t y;
- fibnode_t x;
- int i;
- int d;
- int D;
-
- D = 1 + 8 * sizeof (long);
-
- memset (a, 0, sizeof (fibnode_t) * D);
-
- while ((w = heap->root) != NULL)
- {
- x = w;
- fibheap_rem_root (heap, w);
- d = x->degree;
- while (a[d] != NULL)
- {
- y = a[d];
- if (fibheap_compare (heap, x, y) > 0)
- {
- fibnode_t temp;
- temp = x;
- x = y;
- y = temp;
- }
- fibheap_link (heap, y, x);
- a[d] = NULL;
- d++;
- }
- a[d] = x;
- }
- heap->min = NULL;
- for (i = 0; i < D; i++)
- if (a[i] != NULL)
- {
- fibheap_ins_root (heap, a[i]);
- if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
- heap->min = a[i];
- }
- }
-
/* Make NODE a child of PARENT. */
! static void
fibheap_link (heap, node, parent)
fibheap_t heap ATTRIBUTE_UNUSED;
fibnode_t node;
fibnode_t parent;
{
if (parent->child == NULL)
! parent->child = node;
else
! fibnode_insert_before (parent->child, node);
node->parent = parent;
parent->degree++;
node->mark = 0;
--- 394,413 ----
return ret;
}
/* Make NODE a child of PARENT. */
! static inline void
fibheap_link (heap, node, parent)
fibheap_t heap ATTRIBUTE_UNUSED;
fibnode_t node;
fibnode_t parent;
{
if (parent->child == NULL)
! {
! parent->child = node;
! node->left = node->right = node;
! }
else
! fibnode_insert_after (parent->child, node);
node->parent = parent;
parent->degree++;
node->mark = 0;
*************** fibheap_cascading_cut (heap, y)
*** 477,503 ****
}
}
- static void
- fibnode_insert_after (a, b)
- fibnode_t a;
- fibnode_t b;
- {
- if (a == a->right)
- {
- a->right = b;
- a->left = b;
- b->right = a;
- b->left = a;
- }
- else
- {
- b->right = a->right;
- a->right->left = b;
- a->right = b;
- b->left = a;
- }
- }
-
static fibnode_t
fibnode_remove (node)
fibnode_t node;
--- 449,454 ----
*************** fibnode_remove (node)
*** 520,523 ****
--- 471,531 ----
node->right = node;
return ret;
+ }
+
+ /* Consolidate the heap. */
+ static void
+ fibheap_consolidate (heap)
+ fibheap_t heap;
+ {
+ /* This array is always kept zeroed. */
+ static fibnode_t a[1 + 8 * sizeof (long)];
+ fibnode_t w;
+ fibnode_t y;
+ fibnode_t x;
+ fibnode_t minimal;
+ int i;
+ int d;
+ int D = 0; /* Last non-zero element in a. */
+
+ while ((w = heap->root) != NULL)
+ {
+ x = w;
+ fibheap_rem_root (heap, w);
+ d = x->degree;
+ while (a[d] != NULL)
+ {
+ y = a[d];
+ if (fibheap_compare (heap, x, y) > 0)
+ {
+ fibnode_t temp;
+ temp = x;
+ x = y;
+ y = temp;
+ }
+ fibheap_link (heap, y, x);
+ a[d] = NULL;
+ d++;
+ }
+ a[d] = x;
+ if (d >= D)
+ D = d + 1;
+ }
+
+ i = D - 1;
+ minimal = a[i];
+ fibheap_ins_root (heap, a[i]);
+ a[i] = NULL;
+ while (i--)
+ {
+ x = a[i];
+ if (x != NULL)
+ {
+ fibheap_ins_root (heap, x);
+ if (fibheap_compare (heap, x, minimal) < 0)
+ minimal = x;
+ a[i] = NULL;
+ }
+ }
+ heap->min = minimal;
}