`hourglass` Why use OS for `dateTimeFromUnixEpoch`?

hourglass has a function:

dateTimeFromUnixEpoch :: Elapsed -> DateTime

where Elapsed is the number of seconds from the start of the Unix epoch on 1970-01-01 00:00:00 UTC and DateTime is a date and time (YYYY-MM-DD hh:mm:ss).

It implements that by making use of gmtime_r (Unix-like operating systems) and FileTimeToSystemTime (Windows). Neither of those C functions take account of leap seconds, so the underlying algorithms must be straightforward.

This my question: why would it do that? Why not implement the straightforward algorithm only in Haskell? Am I missing something?

The question arises because there is a TODO from May 2014 “pure haskell backup for dateTimeFromUnixEpoch” but that is expressed in terms of a ‘backup’.

Are you sure? The glibc implementation of gmtime_r sure looks like it does. (__tz_convert, called from gmtime.c)

I will double check. ChatGPT assured me - with repeated prompting - that it did not.

I think I needed to be more precise:

hourglass-0.2.12 documents:

-- | A number of seconds elapsed since the unix epoch.
newtype Elapsed = Elapsed Seconds
    deriving (Read,Eq,Ord,Num,Data,Typeable,NFData)

but it likely does not mean that. It likely means “A number of non-leap seconds since the Unix epoch”.

That is because POSIX has:

A. Rationale for Base Definitions
A.4.19 Seconds Since the Epoch
Coordinated Universal Time (UTC) includes leap seconds. However, in POSIX time (seconds since the Epoch), leap seconds are ignored (not applied) to provide an easy and compatible method of computing time differences. Broken-down POSIX time is therefore not necessarily UTC, despite its appearance.
…it is inappropriate to require that a time represented as seconds since the Epoch precisely represent the number of seconds between the referenced time and the Epoch. …
The topic of whether seconds since the Epoch should account for leap seconds has been debated on a number of occasions, and each time consensus was reached (with acknowledged dissent each time) that the majority of users are best served by treating all days identically. (That is, the majority of applications were judged to assume a single length—as measured in seconds since the Epoch—for all days. Thus, leap seconds are not applied to seconds since the Epoch.).

As a consequence there are a few points in time, at the resolution of one second, (namely during leap seconds) that can’t be represented in POSIX time and a few UTC date and times (at that resolution) that don’t map to a unique number of non-leap seconds since the start of the Unix epoch.

I think I have answered my own question: “speed”. My pure Haskell alternative seems (based on tasty-bench output in GHCi 9.10.2 on x86_64/Windows) to be about 15 to 30 times slower than Haskell calling the equivalent C functions provided by the OS. However, perhaps I am missing a trick? My latest version of the Haskell alternative looks like this:

{-# LANGUAGE BangPatterns       #-}
{-# LANGUAGE NumericUnderscores #-}

{- |
Module      : Time.Calendar.FromElapsed
License     : BSD-style
Copyright   : (c) 2025 Mike Pilgrem <public@pilgrem.com>
Stability   : experimental
Portability : unknown

A native Haskell implementation of 'dateTimeFromUnixEpoch'.
-}

module Time.Calendar.FromElapsed
  ( dateTimeFromUnixEpoch
  ) where

import           Data.Int ( Int64 )
import           Time.Types
                   ( Date (..), DateTime (..), Elapsed (..), Hours (..)
                   , Minutes (..), Seconds (..), TimeOfDay (..)
                   )

dateTimeFromUnixEpoch :: Elapsed -> DateTime
dateTimeFromUnixEpoch (Elapsed (Seconds secs)) =
  if secs >= 0
    then afterUnixEpoch secs
    else beforeUnixEpoch (negate secs)
 where

  isleap :: Int -> Bool
  isleap !y =
    let isDivBy n = y `mod` n == 0
    in   isDivBy 4 && not (isDivBy 100 || isDivBy 400)
  {-# INLINE isleap #-}

  days :: Int -> Int64
  days !y = if isleap y then 366 else 365
  {-# INLINE days #-}

  monthDays :: Bool -> Int -> Int64
  monthDays !isLeap !m = months !! m
   where
    months = if isLeap then leapMonths else nonLeapMonths
    leapMonths = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    nonLeapMonths = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
  {-# INLINE monthDays #-}

  yearLoop :: Int -> Int -> Int64 -> (Int, Int64)
  yearLoop !dir !y !d =
    let yd = days y
    in  if d <= yd
          then (y, d)
          else yearLoop dir (y + dir) (d - yd)

  monthLoop :: Bool -> Int -> Int -> Int64 -> (Int,  Int64, Int64)
  monthLoop !isLeap !dir !m !d =
    let md = monthDays isLeap m
    in  if d <= md
          then (m, d, md)
          else monthLoop isLeap dir (m + dir) (d - md)

  afterUnixEpoch :: Int64 -> DateTime
  afterUnixEpoch secs1 =
    let (!y, !m, !d, _, !h, !mi, !s) = fromUnixEpoch 1970 0 1 secs1
        date = Date y (toEnum m) (fromIntegral d + 1)
        tod = TimeOfDay (Hours h) (Minutes mi) (Seconds s) 0
    in  DateTime date tod

  beforeUnixEpoch :: Int64 -> DateTime
  beforeUnixEpoch secs1 =
    let (!y, !m, !d, !md, !h, !mi, !s) = fromUnixEpoch 1969 11 (-1) secs1
        date = Date y (toEnum m) (fromIntegral $ md - d)
        tod = TimeOfDay (Hours (23 - h)) (Minutes (59 - mi)) (Seconds (60 - s)) 0
    in  DateTime date tod

  fromUnixEpoch ::
       Int
    -> Int
    -> Int
    -> Int64
    -> (Int, Int, Int64, Int64, Int64, Int64, Int64)
  fromUnixEpoch !baseYear !baseMonth !dir !secs1 =
    let (!d1, !s1) = secs1 `quotRem` 86_400
        (!y, !d2) = yearLoop dir baseYear d1
        (!m, !d, !md) = monthLoop (isleap y) dir baseMonth d2
        (!h, !s2) = s1 `quotRem` 3_600
        (!mi, !s) = s2 `quotRem` 60
    in  (y, m, md, d, h, mi, s)
  • Division is slow, use quote-quot: Divide without division as much as possible.
  • monthDays should be something like 28 + (if isLeap then magic1 else magic2) `shiftR (2 * m) .&. 3.

Thanks! On reading around, I have also discovered that my loop-based approach to years is naive. I should, apparently, be making use of the ‘Gregorian proleptic epoch’ (0000-03-01) and the pattern of leap days after that, in blocks of 400 years.

in blocks of 400 years.

in blocks of 100 and 400 years.
In Julian Calendar leap year is every 4th year.

And you also forget, that in Julian Calendar 0th year does not exists: if we count down years, we have: 5, 4, 3, 2, 1, -1, -2, -3,…

UPD: Hm… And maybe it is better to return to Gregorian Calendar for big negative years to match tropical years with calendar ones.

With a better algorithm and straight-forward Haskell, I am down to 3 times slower than making use of what the OS provides. (Perhaps I should be satisfied with that. ChatGPT may be hallucinating, but it tells me the OS functions may use hand-optimised assembly.)

However, I am not having much luck with eliminating division by apeing quote-quot; that seems to halve, not increase, the speed of the better algorithm.

My straight-forward code now looks like this:

module Time.Calendar.FromElapsed
  ( dateTimeFromUnixEpoch
  ) where

import           Data.Int ( Int64 )
import           Time.Types
                   ( Date (..), DateTime (..), Elapsed (..), Hours (..)
                   , Minutes (..), Seconds (..), TimeOfDay (..)
                   )

dateTimeFromUnixEpoch :: Elapsed -> DateTime
dateTimeFromUnixEpoch (Elapsed (Seconds secs)) =
  dateTimeFromGPEpoch (secs + 62_162_035_200)

-- | The \'Gregorian proleptic\' (GP) epoch (0000-03-01 00:00:00) follows a leap
-- day and starts a 400-year pattern of leap days.
dateTimeFromGPEpoch :: Int64 -> DateTime
dateTimeFromGPEpoch secs =
  let (!d1, !s1) = secs `quotRem` 86_400
      (!q400, !r400) = d1 `quotRem` 146_097
      (!q100, !r100) = r400 `minDivMod` 36_524
      (!q4, !r4) = r100 `quotRem` 1461
      (!q1, !r1) = r4 `minDivMod` 365
      !y' = fromIntegral $ 400 * q400 + 100 * q100 + 4 * q4 + q1
      !d2 = fromIntegral r1
      !isLeap = q1 == 0 && (q4 /= 0 || q100 == 0)
      (!m', !d) = monthDays isLeap d2
      (!h, !s2) = s1 `quotRem` 3_600
      (!mi, !s) = s2 `quotRem` 60
      (!y, !m) = if m' > 9 then (y' + 1, m' - 10) else (y', m' + 2)
      !date = Date y (toEnum m) d
      !tod = TimeOfDay (Hours h) (Minutes mi) (Seconds s) 0
  in  DateTime { dtDate = date, dtTime = tod }
 where

  minDivMod :: Int64 -> Int64 -> (Int64, Int64)
  minDivMod !n !d =
    let (q, r) = n `quotRem` d
    in  if q == 4 then (3, r + d) else (q, r)
  {-# INLINE minDivMod #-}

  -- | Month @0@ is March.
  monthDays :: Bool -> Int -> (Int, Int)
  monthDays !isLeap !doy = go 0 table
   where
    (table, febRef) = if isLeap then (leapTable, 337) else (nonLeapTable, 336)
    go !m (doy0 : doy1 : rest)
      | doy < doy1   = (m, doy - doy0 + 1)
      | otherwise = go (m + 1) (doy1 : rest)
    go _ _ = (11, doy - febRef) -- Fallback for February
    nonLeapTable = [0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337]
    leapTable   = [0, 31, 62, 93, 123, 154, 185, 215, 246, 276, 307, 338]
  {-# INLINE monthDays #-}

That gives me:

> stack ghci --bench
ghci> defaultMain $ [bench "fromEpoch" $ nf Time.Calendar.dateTimeFromUnixEpoch (Elapsed 1753988346)]
All
  fromEpoch: OK
    16.3 μs ± 868 ns, 8.0 KB allocated,   0 B  copied, 118 MB peak memory

My quote-quot inspired code (for example):

ghci> unType <$> (examineCode (quoteQuotRem (3600 :: Int64))) >>= putStrLn . pprint
\w_0 -> let q_1 = (\w_2 -> ((`GHC.Internal.Bits.shiftR` 10) GHC.Internal.Base.. ((`Numeric.QuoteQuot.mulHi` 5247073869855161349) GHC.Internal.Base.. GHC.Internal.Base.id)) w_2 GHC.Internal.Num.+ ((\w_3 -> GHC.Internal.Real.fromIntegral (GHC.Types.I# (GHC.Magic.dataToTag# (w_3 GHC.Classes.< 0)))) GHC.Internal.Base.. GHC.Internal.Base.id) w_2) w_0
         in (q_1, w_0 GHC.Internal.Num.- (3600 GHC.Internal.Num.* q_1))

looks like this:

dateTimeFromGPEpoch :: Int64 -> DateTime
dateTimeFromGPEpoch secs =
  let (!d1, !s1) = quotRem86400 secs
      (!q400, !r400) = quotRem146097 d1
      (!q100, !r100) = minDivMod 36_524 quotRem36524 r400
      (!q4, !r4) = quotRem1461 r100
      (!q1, !r1) =  minDivMod 365 quotRem365 r4
      !y' = fromIntegral $ 400 * q400 + 100 * q100 + 4 * q4 + q1
      !d2 = fromIntegral r1
      !isLeap = q1 == 0 && (q4 /= 0 || q100 == 0)
      (!m', !d) = monthDays isLeap d2
      (!h, !s2) = quotRem3600 s1
      (!mi, !s) = quotRem60 s2
      (!y, !m) = if m' > 9 then (y' + 1, m' - 10) else (y', m' + 2)
      !date = Date y (toEnum m) d
      !tod = TimeOfDay (Hours h) (Minutes mi) (Seconds s) 0
  in  DateTime { dtDate = date, dtTime = tod }
 where

  minDivMod :: Int64 -> (Int64 -> (Int64, Int64)) -> Int64 -> (Int64, Int64)
  minDivMod !d !quotRemD !n =
    let (q, r) = quotRemD n
    in  if q == 4 then (3, r + d) else (q, r)
  {-# INLINE minDivMod #-}

  monthDays :: Bool -> Int -> (Int, Int)
  monthDays !isLeap !doy = go 0 table
   where
    (table, febRef) = if isLeap then (leapTable, 337) else (nonLeapTable, 336)
    go !m (doy0 : doy1 : rest)
      | doy < doy1   = (m, doy - doy0 + 1)
      | otherwise = go (m + 1) (doy1 : rest)
    go _ _ = (11, doy - febRef)  -- Fallback for February
    nonLeapTable = [0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337]
    leapTable   = [0, 31, 62, 93, 123, 154, 185, 215, 246, 276, 307, 338]
  {-# INLINE monthDays #-}

  quotRem60 :: Int64 -> (Int64, Int64)
  quotRem60 = quotRemN2 60 5 (-8_608_480_567_731_124_087)
  {-# INLINE quotRem60 #-}

  quotRem365 :: Int64 -> (Int64, Int64)
  quotRem365 = quotRemN1 365 6 3_234_497_591_006_606_311
  {-# INLINE quotRem365 #-}

  quotRem1461 :: Int64 -> (Int64, Int64)
  quotRem1461 = quotRemN2 1_461 10 (-5_517_609_281_458_640_695)
  {-# INLINE quotRem1461 #-}

  quotRem3600 :: Int64 -> (Int64, Int64)
  quotRem3600 = quotRemN1 3_600 10 5_247_073_869_855_161_349
  {-# INLINE quotRem3600 #-}

  quotRem36524 :: Int64 -> (Int64, Int64)
  quotRem36524 = quotRemN2 36_524 15 (-1_896_998_432_287_073_591)
  {-# INLINE quotRem36524 #-}

  quotRem86400 :: Int64 -> (Int64, Int64)
  quotRem86400 = quotRemN1 86_400 13 1_749_024_623_285_053_783
  {-# INLINE quotRem86400 #-}

  quotRem146097 :: Int64 -> (Int64, Int64)
  quotRem146097 = quotRemN1 146_097 15 4_137_408_090_565_272_301
  {-# INLINE quotRem146097 #-}

  quotRemN1 :: Int64 -> Int -> Int64 -> Int64 -> (Int64, Int64)
  quotRemN1 !n !rShift !magic !w_0 =
    let q = w2 w_0
        w2 w_2 = ((`shiftR` rShift) . (`mulHiInt64` magic)) w_2 + w3 w_2
        w3 w_3 = fromIntegral (I# (dataToTag# (w_3 < 0)))
    in  (q, w_0 - (n * q))
  {-# INLINE quotRemN1 #-}

  quotRemN2 :: Int64 -> Int -> Int64 -> Int64 -> (Int64, Int64)
  quotRemN2 !n !rShift !magic !w_0 =
    let q = w2 w_0
        w2 w_2 = ((`shiftR` rShift) . w3) w_2 + w4 w_2
        w3 w_3 = w_3 + (`mulHiInt64` magic) w_3
        w4 w_4 = fromIntegral (I# (dataToTag# (w_4 < 0)))
    in  (q, w_0 - (n * q))
  {-# INLINE quotRemN2 #-}

  mulHiInt64 :: Int64 -> Int64 -> Int64
  mulHiInt64 x y = fromIntegral (fromIntegral x `mulHiInt` fromIntegral y :: Int)
  {-# INLINE mulHiInt64 #-}

  mulHiInt :: Int -> Int -> Int
  mulHiInt (I# x) (I# y) = let !(# _, hi, _ #) = timesInt2# x y in I# hi
  {-# INLINE mulHiInt #-}

That gives me (and I think it makes use of things not available on 32-bit machines):

ghci> defaultMain $ [bench "fromEpoch" $ nf Time.Calendar.dateTimeFromUnixEpoch (Elapsed 1753988346)]
All
  fromEpoch: OK
    37.2 μs ± 2.6 μs,  20 KB allocated,   1 B  copied, 119 MB peak memory

Why is using existing C functions a problem? :thinking:

The short answer is, it is not a problem. This started off as a ponder, and ended up as a voyage of discovery on my part.

Now I understand why hourglass is ‘performant’ (it cheats), I am not planning to change anything.

Some tricks to save calculations:

  • only those, which is not divisible by 4, are also not divisible by 100.
  • only those, which is not divisible by 100, are also not divisible by 400.

Efficient conversion of 64-bit Unix epoch time to proleptic Gregorian time (year 1 preceded by year 0 rather than -1):

import Data.Int (Int64)
import Data.Word (Word8)

data Date = Date 
    { year  :: !Int64
    , month :: !Word8
    , mday  :: !Word8
    , hour  :: !Word8
    , mins  :: !Word8
    , secs  :: !Word8
    }
  deriving (Eq, Ord, Show)

-- | 64-bit epoch to proleptic Gregorian date, based on
-- <http://howardhinnant.github.io/date_algorithms.html>
--
proleptic :: Int64 -> Date
proleptic t = Date { year = yr
                   , month = fromIntegral mn
                   , mday = fromIntegral dy
                   , hour = fromIntegral hh
                   , mins = fromIntegral mm
                   , secs = fromIntegral ss }
  where
    (!z0, !s) = t `divMod` 86400
    !z = z0 + 719468
    (!era, !doe) = z `divMod` 146097
    !yoe = (doe - doe `quot` 1460 + doe `quot` 36524
               - doe `quot` 146096) `quot` 365
    !y = yoe + era * 400
    !doy = doe - (365*yoe + yoe `quot` 4 - yoe `quot` 100)
    !mp = (5*doy + 2) `quot` 153
    !dy = doy - (153*mp + 2) `quot` 5 + 1
    !mn = 1 + (mp + 2) `rem` 12
    !yr = y + (12 - mn) `quot` 10
    (!hh, (!mm, !ss)) = flip divMod 60 <$> s `divMod` 3600

Am I reading it correct that you are benchmarking bytecode execution in ghci? This is unlikely to serve a good proxy for performance of compiled code.

Thanks! I see, first, that I made a mistake with my ‘better’ algorithm. Even on its own terms, it should have had:

  monthDays :: Int -> (Int, Int)
  monthDays !doy = go 0 [0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337]
   where
    go !i (a : b : rest)
      | doy < b   = (i, doy - a + 1)
      | otherwise = go (i + 1) (b : rest)
    go _ _ = (11, doy - 336) -- Fallback for February
  {-# INLINE monthDays #-}

Second, I see your alternative avoids a ‘look up’ by making use of the relationship:

> map (\m -> (153 * m + 2) `quot` 5) ([0 .. 11] :: [Int])
[0,31,61,92,122,153,184,214,245,275,306,337]

You are, of course, correct. I created a benchmark in the package (for 1 Mar 2024 (start of year) and 29 Feb 2024 (end of year)) and tried again, with very different results (ns, not μs):

Version Windows 11 Ubuntu 24.01.1 (via WSL 2)
Call out to OS 298/295 137/139
Haskell (lookup) 83/124 81/118
Haskell (all math; no lookup) 94/96 93/92
Haskell (quote-quot) 31/30 27/28

Are you willing to share a link to the benchmark code?

On sharing code, certainly:

There are four (temporary) branches at:

that build one upon the other. They are, in order:

  • fromEpoch-bench, that adds a bench-fromEpoch benchmark for the existing code
  • fromEpoch, that uses Haskell (lookup) and extends that benchmark;
  • fromEpoch-no-lookup, that uses Haskell (all math; no lookup); and
  • fromEpoch-quote-quot, that is inspired by quote-quot.

The benchmark looks like this:

{-# LANGUAGE NumericUnderscores #-}

module Main
  ( main
  ) where

import qualified Time.Calendar as C
import qualified Time.Calendar.FromElapsed as FE
import           Test.Tasty.Bench ( bench, bgroup, defaultMain, nf )

main :: IO ()
main = defaultMain
  [ bgroup  "fromEpoch (Time.Calendar)" $
      [ bench "2024-03-01" $ nf C.dateTimeFromUnixEpoch 1_709_337_599
      , bench "2024-02-29" $ nf C.dateTimeFromUnixEpoch 1_709_251_199
      ]
  , bgroup  "fromEpoch (Time.Calendar.FromElapsed)" $
      [ bench "2024-03-01" $ nf FE.dateTimeFromUnixEpoch 1_709_337_599
      , bench "2024-02-29" $ nf FE.dateTimeFromUnixEpoch 1_709_251_199
      ]
  ]

Just curious: is there a reason you avoid using quote-quot directly?

I have not been using quote-quot directly because I wanted to avoid a direct dependency on template-haskell and I was only substituting a small number of divisions.

EDIT: Testing, I found another reason: the quote-quot package does not provide a MulHi instance for Int64 before base-4.15.0.0 (GHC 9.0.1), so I handspun:

#if MIN_VERSION_base(4,15,0)
  mulHiInt :: Int -> Int -> Int
  mulHiInt (I# x) (I# y) = let !(# _, hi, _ #) = timesInt2# x y in I# hi
  {-# INLINE mulHiInt #-}
#else
  mulHiInt :: Int -> Int -> Int
  mulHiInt 0 _ = 0
  mulHiInt _ 0 = 0
  mulHiInt x y
    | x < 0, y > 0 = mulHiIntPos True (negate x) y
    | x > 0, y < 0 = mulHiIntPos True x (negate y)
    | otherwise = mulHiIntPos False x y
  {-# INLINE mulHiInt #-}

  -- | x# and y# are known to be positive.
  mulHiIntPos :: Bool -> Int -> Int -> Int
  mulHiIntPos isNeg (I# x#) (I# y#) =
    let wx# = int2Word# x#
        wy# = int2Word# y#
        !(# high#, low# #) = timesWord2# wx# wy#
        lowC# = plusWord# (not# low#) 1##
        highC# = plusWord# (not# high#) (int2Word# (lowC# `eqWord#` 0##))
    in  I# (word2Int# (if isNeg then highC# else high#))
  {-# INLINE mulHiIntPos #-}
#endif