Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Builder for Data.Fixed? #689

Open
matthewbauer opened this issue Aug 1, 2024 · 1 comment
Open

Builder for Data.Fixed? #689

matthewbauer opened this issue Aug 1, 2024 · 1 comment

Comments

@matthewbauer
Copy link

matthewbauer commented Aug 1, 2024

I wonder if there is a fast ByteString Builder for numbers from Data.Fixed?

I've written one myself, but don't think it's quite as fast as it could be:

-- | Encode a 'Fixed' resolution number using ASCII digits.
fixedDec :: HasResolution a => Fixed a -> BB.Builder
fixedDec fa@(MkFixed a) | a < 0 = P.primFixed P.char8 '-' <> fixedDec (asTypeOf (MkFixed (negate a)) fa)
fixedDec fa@(MkFixed a) = integerDec i <> P.primFixed P.char8 '.' <> stimesMonoid zeros (P.primFixed P.char8 '0') <> integerDec d
  where
    (i, d) = a `quotRem` resolution fa
    zeros :: Integer = if d == 0 then 0 else ceiling (logBase 10 (fromIntegral (resolution fa) / fromIntegral d / 10) :: Double)

Calculating logBase 10 gets expensive, so it doesn't seem to perform well with lots of Fixed numbers.

Ideally if there was an efficient builder of fixed, it could be included in bytestring. Anyone have ideas of how to make it more efficient?

@matthewbauer
Copy link
Author

matthewbauer commented Aug 2, 2024

I was able to get some pretty good results (sub 1ms for 10,000 calls based on benchmarks) with this version:

-- | Encode a 'Fixed' resolution number using ASCII digits.
fixedDec :: HasResolution a => Fixed a -> Builder
fixedDec fa@(MkFixed a) | a < 0 = P.primFixed P.char8 '-' <> fixedDec (asTypeOf (MkFixed (negate a)) fa)
fixedDec fa@(MkFixed a) = integerDec i <> P.primFixed P.char8 '.' <> P.primMapListFixed P.char8 (List.genericReplicate zeros '0') <> integerDec d
  where
    !(i, d) = a `quotRem` resolution fa
    zeros :: Integer = if d == 0 then 0 else ceiling (logBase 10 (fromIntegral (resolution fa) / fromIntegral d / 10) :: Double)

You can about half (like 500μs) that by approximating Fixed to "Word64" instead of Integer:

-- | Encode a 'Fixed' resolution number using ASCII digits, approximated to Word64.
fixedDecWord64 :: HasResolution a => Fixed a -> Builder
fixedDecWord64 fa@(MkFixed a) | a < 0 = P.primFixed P.char8 '-' <> fixedDecWord64 (asTypeOf (MkFixed (negate a)) fa)
fixedDecWord64 fa@(MkFixed a) = word64Dec i <> P.primFixed P.char8 '.' <> P.primMapListFixed P.char8 (List.replicate zeros '0') <> word64Dec d
  where
    !(i, d) = fromIntegral a `quotRem` fromIntegral (resolution fa)
    zeros :: Int = if d == 0 then 0 else ceiling (logBase 10 (fromIntegral (resolution fa) / fromIntegral d / 10) :: Double)

I have a branch available here: master...matthewbauer:bytestring:fixedDec

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant