ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/libev/ev.c
(Generate patch)

Comparing libev/ev.c (file contents):
Revision 1.235 by root, Wed May 7 14:45:17 2008 UTC vs.
Revision 1.238 by root, Thu May 8 20:49:12 2008 UTC

766 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap 766 * a small-code-size 2-heap one and a ~1.5kb larger 4-heap
767 * which is more cache-efficient. 767 * which is more cache-efficient.
768 * the difference is about 5% with 50000+ watchers. 768 * the difference is about 5% with 50000+ watchers.
769 */ 769 */
770#define USE_4HEAP !EV_MINIMAL 770#define USE_4HEAP !EV_MINIMAL
771#define USE_4HEAP 1/* they do not work corretcly */
771#if USE_4HEAP 772#if USE_4HEAP
772 773
774#define DHEAP 4
773#define HEAP0 3 /* index of first element in heap */ 775#define HEAP0 (DHEAP - 1) /* index of first element in heap */
774 776
775/* towards the root */ 777/* towards the root */
776void inline_speed 778void inline_speed
777upheap (WT *heap, int k) 779upheap (WT *heap, int k)
778{ 780{
779 WT w = heap [k]; 781 WT w = heap [k];
780 782
781 for (;;) 783 for (;;)
782 { 784 {
783 int p = ((k - HEAP0 - 1) / 4) + HEAP0; 785 int p = ((k - HEAP0 - 1) / DHEAP) + HEAP0;
784 786
785 if (p >= HEAP0 || heap [p]->at <= w->at) 787 if (p == k || heap [p]->at <= w->at)
786 break; 788 break;
787 789
788 heap [k] = heap [p]; 790 heap [k] = heap [p];
789 ev_active (heap [k]) = k; 791 ev_active (heap [k]) = k;
790 k = p; 792 k = p;
803 805
804 for (;;) 806 for (;;)
805 { 807 {
806 ev_tstamp minat; 808 ev_tstamp minat;
807 WT *minpos; 809 WT *minpos;
808 WT *pos = heap + 4 * (k - HEAP0) + HEAP0; 810 WT *pos = heap + DHEAP * (k - HEAP0) + HEAP0;
809 811
810 // find minimum child 812 // find minimum child
811 if (expect_true (pos +3 < E)) 813 if (expect_true (pos + DHEAP - 1 < E))
812 { 814 {
815 /* fast path */
813 (minpos = pos + 0), (minat = (*minpos)->at); 816 (minpos = pos + 0), (minat = (*minpos)->at);
814 if (pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at); 817 if (pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at);
815 if (pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at); 818 if (pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at);
816 if (pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at); 819 if (pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at);
817 } 820 }
818 else 821 else
819 { 822 {
823 /* slow path */
820 if (pos >= E) 824 if (pos >= E)
821 break; 825 break;
822
823 (minpos = pos + 0), (minat = (*minpos)->at); 826 (minpos = pos + 0), (minat = (*minpos)->at);
824 if (pos + 1 < E && pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at); 827 if (pos + 1 < E && pos [1]->at < minat) (minpos = pos + 1), (minat = (*minpos)->at);
825 if (pos + 2 < E && pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at); 828 if (pos + 2 < E && pos [2]->at < minat) (minpos = pos + 2), (minat = (*minpos)->at);
826 if (pos + 3 < E && pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at); 829 if (pos + 3 < E && pos [3]->at < minat) (minpos = pos + 3), (minat = (*minpos)->at);
827 } 830 }

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines