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