Commits

Bryan O'Sullivan  committed 82b5938

Switch to a faster decimal algorithm

This is about 25% faster than its predecessor for large numbers.

  • Participants
  • Parent commits 9b1fc0c

Comments (0)

Files changed (4)

File Data/Text/Lazy/Builder/Int.hs

 
 import Data.Int (Int8, Int16, Int32, Int64)
 import Data.Monoid (mempty)
+import qualified Data.ByteString.Unsafe as B
 import Data.Text.Lazy.Builder.Functions ((<>), i2d)
 import Data.Text.Lazy.Builder.Internal
+import Data.Text.Lazy.Builder.Int.Digits (digits)
 import Data.Text.Array
 import Data.Word (Word, Word8, Word16, Word32, Word64)
 import GHC.Base (quotInt, remInt)
     | otherwise = let !n = countDigits i
                   in writeN n $ \marr off -> posDecimal marr off n i
 
-posDecimal :: Integral a => forall s. MArray s -> Int -> Int -> a -> ST s ()
+posDecimal :: (Integral a) =>
+              forall s. MArray s -> Int -> Int -> a -> ST s ()
 {-# INLINE posDecimal #-}
 posDecimal marr off0 ds v0 = go (off0 + ds - 1) v0
   where go off v
-           | v < 10 = unsafeWrite marr off (i2w v)
-           | otherwise = do
-          unsafeWrite marr off (i2w (v `rem` 10))
-          go (off-1) (v `quot` 10)
+           | v >= 100 = do
+               write2 off $ let u = v `rem` 100
+                            in u + u
+               go (off - 2) (v `quot` 100)
+           | v < 10    = unsafeWrite marr off (i2w v)
+           | otherwise = write2 off (v + v)
+        write2 off i = do
+          unsafeWrite marr off $ get (i + 1)
+          unsafeWrite marr (off - 1) $ get i
+        get i = fromIntegral $ B.unsafeIndex digits (fromIntegral i) :: Word16
 
 minus, zero :: Word16
 {-# INLINE minus #-}

File Data/Text/Lazy/Builder/Int/Digits.hs

+{-# LANGUAGE OverloadedStrings #-}
+
+-- Module:      Data.Text.Lazy.Builder.Int.Digits
+-- Copyright:   (c) 2013 Bryan O'Sullivan
+-- License:     BSD3
+-- Maintainer:  Bryan O'Sullivan <bos@serpentine.com>
+-- Stability:   experimental
+-- Portability: portable
+--
+-- This module exists because the C preprocessor does things that we
+-- shall not speak of when confronted with Haskell multiline strings.
+
+module Data.Text.Lazy.Builder.Int.Digits (digits) where
+
+import Data.ByteString.Char8 (ByteString)
+
+digits :: ByteString
+digits = "0001020304050607080910111213141516171819\
+         \2021222324252627282930313233343536373839\
+         \4041424344454647484950515253545556575859\
+         \6061626364656667686970717273747576777879\
+         \8081828384858687888990919293949596979899"

File tests/text-tests.cabal

     Data.Text.Lazy.Builder
     Data.Text.Lazy.Builder.Functions
     Data.Text.Lazy.Builder.Int
+    Data.Text.Lazy.Builder.Int.Digits
     Data.Text.Lazy.Builder.Internal
     Data.Text.Lazy.Builder.RealFloat
     Data.Text.Lazy.Builder.RealFloat.Functions
     Data.Text.Fusion.Size
     Data.Text.IO.Internal
     Data.Text.Lazy.Builder.Functions
+    Data.Text.Lazy.Builder.Int.Digits
     Data.Text.Lazy.Builder.Internal
     Data.Text.Lazy.Builder.RealFloat.Functions
     Data.Text.Lazy.Encoding.Fusion