Bryan O'Sullivan avatar Bryan O'Sullivan committed 4e16641

Speed up the Ord instance for Text

Comments (0)

Files changed (2)

     {-# INLINE (==) #-}
 
 instance Ord Text where
-    compare t1 t2 = compare (stream t1) (stream t2)
-    {-# INLINE compare #-}
+    compare = compareText
 
 instance Show Text where
     showsPrec p ps r = showsPrec p (unpack ps) r
   dataTypeOf _   = mkNorepType "Data.Text.Text"
 #endif
 
+-- | /O(n)/ Compare two 'Text' values lexicographically.
+compareText :: Text -> Text -> Ordering
+compareText ta@(Text _arrA _offA lenA) tb@(Text _arrB _offB lenB)
+    | lenA == 0 && lenB == 0 = EQ
+    | otherwise              = go 0 0
+  where
+    go !i !j
+        | i >= lenA || j >= lenB = compare lenA lenB
+        | a < b                  = LT
+        | a > b                  = GT
+        | otherwise              = go (i+di) (j+dj)
+      where Iter a di = iter ta i
+            Iter b dj = iter tb j
+
 -- -----------------------------------------------------------------------------
 -- * Conversion to/from 'Text'
 

tests/benchmarks/Ordering.hs

+import System.Environment
+import qualified Data.ByteString.Char8 as B
+import qualified Data.ByteString.Lazy.Char8 as BL
+import qualified Data.Text as T
+import qualified Data.Text.Encoding as T
+import qualified Data.Text.Lazy as TL
+import qualified Data.Text.Lazy.Encoding as TL
+
+every :: Int -> [a] -> [a]
+every k = go k
+  where go n (x:xs)
+          | n < k     = go (n+1) xs
+          | otherwise = x : go 1 xs
+        go _ _        = []
+
+func :: (Ord a) => [a] -> IO ()
+func ls = print . sum . map f $ every 1000 ls
+    where f needle = length . filter ((==GT) . compare needle) $ ls
+
+bytestring haystack = func =<< B.lines `fmap` B.readFile haystack
+
+lazyBytestring haystack = func =<< BL.lines `fmap` BL.readFile haystack
+
+text haystack = func =<< (T.lines . T.decodeUtf8) `fmap` B.readFile haystack
+
+lazyText haystack = func =<<
+                    (TL.lines . TL.decodeUtf8) `fmap` BL.readFile haystack
+
+string haystack = func =<< lines `fmap` readFile haystack
+
+main = do
+  args <- getArgs
+  case args of
+    ["bs",h] -> bytestring h
+    ["lazybs",h] -> lazyBytestring h
+    ["text",h] -> text h
+    ["lazytext",h] -> lazyText h
+    ["string",h] -> string h
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.