This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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;
  }


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]