Re: [MirageOS-devel] Timestamp representation and CLOCK

[Daniel BÃnzli <daniel.buenzli@xxxxxxxxxxxx>]

Justin's point that would you store a large number of timestamps you'd anyway 
devise your own representation achieved to convince me that using int64 * int 
as initially proposed seemed to be the right representation to me: it has ample 
range, nanosecond precision and we would not invent anything new.  

However while trying to implement this representation in ptime I realized that 
addition is more tricky that needed because the nanosecond count can overflow 
on 32-bit platforms. While it does overflow in a magnitude that makes it still 
usable to perform the carry on addition â e.g. trying to add two [ns0] and 
[ns1] ranging from 0 to 999_999_999 in 32-bit yields the following on overflow: 
 

            1e9       max_int][min_int   (ns0+ns1)        0
     ... ----+---------------++--------------+------------+-- ...
             [-------------------------------]
                     (ns0+ns1) mod 1e9


I still find the resulting representation to be too tricky for OCaml 
programming. Here is how addition needs to be implemented:

let add (s0, ns0) (s1, ns1) =
  let s = Int64.add s0 s1 in
  let ns = ns0 + ns1 in
  if ns < 0 then (* 32-bit overflow *)
    Int64.(add s 1L), max_int - 1_000_000_000 + 1 + (ns - min_int)
  else if ns < 1_000_000_000 then
    s, ns
  else (* ns > 1_000_000_000 *)
    Int64.(add s 1L), ns mod 1_000_000_000


So I propose to use the following representation. Namely a signed count of days 
from the epoch and a pico precision timestamp in that day (another form of 
date-time value in some sense). So this is:

type posix_t = int * int64

with (d, ps) representing the point in time [d] * 86'400e12 + [ps] picoseconds 
from the epoch. [ps] in the range [0;86_399_999_999_999_999]. Incidentally this 
is the representation I would use internally for a calendar library as it 
conceptually similar the handy Julian Date "calendar" [1] in which a lot of 
calendar calculations become easier to perform.  

This has the same properties as my previous proposal except that we are 
inventing something (mildly) new, make better precision trade-off (the size of 
the range of days representable around the epoch is entirely sufficient, 
5'883'516 years on 32-bit platforms) and the representation is easier to use on 
both 32-bit and 64-bit platforms. Here's how 32-bit clean addition gets 
implemented:

let add (d0, ns0) (d1, ns1) =
  let d = d0 + d1 in
  let ns = Int64.add ns0 ns1 in
  let ns_clamp = Int64.rem ns 86_400_000_000_000_000L in
  let d = d + Int64.compare ns ns_clamp in
  d, ns_clamp


Having this and adding a function for accessing the clock period which was 
suggested by DavidS and Justin, this would bring us to the following CLOCK:  

module type CLOCK = sig

  val now_d_ps : unit -> int * int64
  (** [now_d_ps ()] is [(d, ps)] representing the time occuring at
      [d] * 86'400e12 + [ps] picoseconds from the epoch 1970-01-01
      00:00:00 UTC. [ps] is in the range \[[0];[86_399_999_999_999_999L]\]. *)

  val period_d_ps : unit -> (int * int64) option
  (** [period_d_ps ()] is if available [Some (d, ps)] representing the
      clock's picosecond period [d] * 86'400e12 + [ps]. [ps] is in the
      range \[[0];[86_399_999_999_999_999L]\]. *)

  val current_tz_offset_s : unit -> int
  (** [current_tz_offset_s ()] is the clock's current local time zone
      offset to UTC in seconds. *)
end


So what do people think of this ?

Daniel

P.S. Also note that on 64-bit platforms this could actually be represented by 
an int pair, as the calculations for pico seconds would fit in the 2^62-1 bits. 
 

[1] http://scienceworld.wolfram.com/astronomy/JulianDate.html



_______________________________________________
MirageOS-devel mailing list
MirageOS-devel@xxxxxxxxxxxxxxxxxxxx
http://lists.xenproject.org/cgi-bin/mailman/listinfo/mirageos-devel