… | |
… | |
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 */ |
776 | void inline_speed |
778 | void inline_speed |
777 | upheap (WT *heap, int k) |
779 | upheap (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 | } |