new floor(), better periodic recalc

4 files changed, 113 insertions, 31 deletions

diff --git a/Changes b/Changes
index d6fca2f..e6bb3cd 100644
--- a/Changes
+++ b/Changes
@@ -1,5 +1,13 @@
 Revision history for libev, a high-performance and full-featured event loop.
 
+TODO: ev_loop_prefork hint?
+
+	- change the default periodic reschedule function to hopefully be more
+          exact and correct.
+        - document reasonable ranges for interval and offset.
+        - do not rely on -lm anymore: use it when available but use our
+          own floor () if it is missing. This should make it easier to embed.
+
 4.04 Wed Feb 16 09:01:51 CET 2011
 	- fix two problems in the native win32 backend, where reuse of fd's
           with different underlying handles caused handles not to be removed
diff --git a/ev.c b/ev.c
index 4187b18..dc737b2 100644
--- a/ev.c
+++ b/ev.c
@@ -45,6 +45,12 @@
 #  include "config.h"
 # endif
 
+#if HAVE_FLOOR
+# ifndef EV_USE_FLOOR
+#  define EV_USE_FLOOR 1
+# endif
+#endif
+
 # if HAVE_CLOCK_SYSCALL
 #  ifndef EV_USE_CLOCK_SYSCALL
 #   define EV_USE_CLOCK_SYSCALL 1
@@ -158,7 +164,6 @@
  
 #endif
 
-#include <math.h>
 #include <stdlib.h>
 #include <string.h>
 #include <fcntl.h>
@@ -234,6 +239,10 @@ EV_CPP(extern "C" {)
 # define EV_NSIG 65
 #endif
 
+#ifndef EV_USE_FLOOR
+# define EV_USE_FLOOR 0
+#endif
+
 #ifndef EV_USE_CLOCK_SYSCALL
 # if __linux && __GLIBC__ >= 2
 #  define EV_USE_CLOCK_SYSCALL EV_FEATURE_OS
@@ -445,14 +454,11 @@ struct signalfd_siginfo
 #endif
 
 /*
- * This is used to avoid floating point rounding problems.
- * It is added to ev_rt_now when scheduling periodics
- * to ensure progress, time-wise, even when rounding
- * errors are against us.
+ * This is used to work around floating point rounding problems.
  * This value is good at least till the year 4000.
- * Better solutions welcome.
  */
-#define TIME_EPSILON  0.0001220703125 /* 1/8192 */
+#define MIN_INTERVAL  0.0001220703125 /* 1/2**13, good till 4000 */
+/*#define MIN_INTERVAL  0.00000095367431640625 /* 1/2**20, good till 2200 */
 
 #define MIN_TIMEJUMP  1. /* minimum timejump that gets detected (if monotonic clock available) */
 #define MAX_BLOCKTIME 59.743 /* never wait longer than this time (to detect time jumps) */
@@ -525,6 +531,54 @@ static EV_ATOMIC_T have_monotonic; /* did clock_gettime (CLOCK_MONOTONIC) work?
 
 /*****************************************************************************/
 
+/* define a suitable floor function (only used by periodics atm) */
+
+#if EV_USE_FLOOR
+# include <math.h>
+# define ev_floor(v) floor (v)
+#else
+
+#include <float.h>
+
+/* a floor() replacement function, should be independent of ev_tstamp type */
+static ev_tstamp noinline
+ev_floor (ev_tstamp v)
+{
+  /* the choice of shift factor is not terribly important */
+#if FLT_RADIX != 2 /* assume FLT_RADIX == 10 */
+  const ev_tstamp shift = sizeof (unsigned long) >= 8 ? 10000000000000000000. : 1000000000.;
+#else
+  const ev_tstamp shift = sizeof (unsigned long) >= 8 ? 18446744073709551616. : 4294967296.;
+#endif
+
+  /* argument too large for an unsigned long? */
+  if (expect_false (v >= shift))
+    {
+      ev_tstamp f;
+
+      if (v == v - 1.)
+        return v; /* very large number */
+
+      f = shift * ev_floor (v * (1. / shift));
+      return f + ev_floor (v - f);
+    }
+
+  /* special treatment for negative args? */
+  if (expect_false (v < 0.))
+    {
+      ev_tstamp f = -ev_floor (-v);
+
+      return f - (f == v ? 0 : 1);
+    }
+
+  /* fits into an unsigned long */
+  return (unsigned long)v;
+}
+
+#endif
+
+/*****************************************************************************/
+
 #ifdef __linux
 # include <sys/utsname.h>
 #endif
@@ -2210,12 +2264,28 @@ timers_reify (EV_P)
 
 #if EV_PERIODIC_ENABLE
 
-inline_speed void
+static void noinline
 periodic_recalc (EV_P_ ev_periodic *w)
 {
-  /* TODO: use slow but potentially more correct incremental algo, */
-  /* also do not rely on ceil */
-  ev_at (w) = w->offset + ceil ((ev_rt_now - w->offset) / w->interval) * w->interval;
+  ev_tstamp interval = w->interval > MIN_INTERVAL ? w->interval : MIN_INTERVAL;
+  ev_tstamp at = w->offset + interval * ev_floor ((ev_rt_now - w->offset) / interval);
+
+  /* the above almost always errs on the low side */
+  while (at <= ev_rt_now)
+    {
+      ev_tstamp nat = at + w->interval;
+
+      /* when resolution fails us, we use ev_rt_now */
+      if (expect_false (nat == at))
+        {
+          at = ev_rt_now;
+          break;
+        }
+
+      at = nat;
+    }
+
+  ev_at (w) = at;
 }
 
 /* make periodics pending */
@@ -2247,20 +2317,6 @@ periodics_reify (EV_P)
           else if (w->interval)
             {
               periodic_recalc (EV_A_ w);
-
-              /* if next trigger time is not sufficiently in the future, put it there */
-              /* this might happen because of floating point inexactness */
-              if (ev_at (w) - ev_rt_now < TIME_EPSILON)
-                {
-                  ev_at (w) += w->interval;
-
-                  /* if interval is unreasonably low we might still have a time in the past */
-                  /* so correct this. this will make the periodic very inexact, but the user */
-                  /* has effectively asked to get triggered more often than possible */
-                  if (ev_at (w) < ev_rt_now)
-                    ev_at (w) = ev_rt_now;
-                }
-
               ANHE_at_cache (periodics [HEAP0]);
               downheap (periodics, periodiccnt, HEAP0);
             }
@@ -2348,9 +2404,12 @@ time_update (EV_P_ ev_tstamp max_block)
        */
       for (i = 4; --i; )
         {
+          ev_tstamp diff;
           rtmn_diff = ev_rt_now - mn_now;
 
-          if (expect_true (fabs (odiff - rtmn_diff) < MIN_TIMEJUMP))
+          diff = odiff - rtmn_diff;
+
+          if (expect_true ((diff < 0. ? -diff : diff) < MIN_TIMEJUMP))
             return; /* all is well */
 
           ev_rt_now = ev_time ();
diff --git a/ev.pod b/ev.pod
index 4bbef1f..0bbbf4a 100644
--- a/ev.pod
+++ b/ev.pod
@@ -2153,9 +2153,12 @@ Another way to think about it (for the mathematically inclined) is that
 C<ev_periodic> will try to run the callback in this mode at the next possible
 time where C<time = offset (mod interval)>, regardless of any time jumps.
 
-For numerical stability it is preferable that the C<offset> value is near
-C<ev_now ()> (the current time), but there is no range requirement for
-this value, and in fact is often specified as zero.
+The C<interval> I<MUST> be positive, and for numerical stability, the
+interval value should be higher than C<1/8192> (which is around 100
+microseconds) and C<offset> should be higher than C<0> and should have
+at most a similar magnitude as the current time (say, within a factor of
+ten). Typical values for offset are, in fact, C<0> or something between
+C<0> and C<interval>, which is also the recommended range.
 
 Note also that there is an upper limit to how often a timer can fire (CPU
 speed for example), so if C<interval> is very small then timing stability
@@ -4206,6 +4209,15 @@ F<event.h> that are not directly supported by the libev core alone.
 In standalone mode, libev will still try to automatically deduce the
 configuration, but has to be more conservative.
 
+=item EV_USE_FLOOR
+
+If defined to be C<1>, libev will use the C<floor ()> function for its
+periodic reschedule calculations, otherwise libev will fall back on a
+portable (slower) implementation. If you enable this, you usually have to
+link against libm or something equivalent. Enabling this when the C<floor>
+function is not available will fail, so the safe default is to not enable
+this.
+
 =item EV_USE_MONOTONIC
 
 If defined to be C<1>, libev will try to detect the availability of the
diff --git a/libev.m4 b/libev.m4
index e3f4c81..6fdb13f 100644
--- a/libev.m4
+++ b/libev.m4
@@ -16,7 +16,7 @@ AC_CHECK_FUNCS(clock_gettime, [], [
                        #include <time.h>],
                       [struct timespec ts; int status = syscall (SYS_clock_gettime, CLOCK_REALTIME, &ts)])],
                      [ac_have_clock_syscall=1
-                      AC_DEFINE(HAVE_CLOCK_SYSCALL, 1, "use syscall interface for clock_gettime")
+                      AC_DEFINE(HAVE_CLOCK_SYSCALL, 1, Define to 1 to use the syscall interface for clock_gettime)
                       AC_MSG_RESULT(yes)],
                      [AC_MSG_RESULT(no)])
    fi
@@ -35,5 +35,8 @@ AC_CHECK_FUNCS(nanosleep, [], [
    fi
 ])
 
-AC_CHECK_LIB(m, ceil)
+if test -z "$LIBEV_M4_AVOID_LIBM"; then
+   LIBM=m
+fi
+AC_SEARCH_LIBS(floor, $LIBM, [AC_DEFINE(HAVE_FLOOR, 1, Define to 1 if the floor function is available)])