Memory performance when reading large files

Learn
5

Here is a modification of your program which is twice faster and twice less hungry for memory:

{-# LANGUAGE OverloadedStrings #-}

module Main where

import qualified Data.ByteString as BS
import qualified Data.ByteString.Unsafe as BS
import qualified Data.ByteString.Builder as BSB
import qualified Data.ByteString.Char8 as BS (lines, readInt)
import Data.List (sortOn)
import qualified Data.Map.Strict as Map

main :: IO ()
main = do
    mapFrequencies <- Map.fromList . parseFrequencies <$> BS.readFile fileFrequencies
    ls <- BS.lines <$> BS.readFile fileData
    let sorted = sortOn (\k -> Map.findWithDefault 0 k mapFrequencies) ls
    BSB.writeFile fileSorted $ foldMap ((<> "\n") . BSB.byteString) sorted

fileFrequencies :: FilePath
fileFrequencies = "deu_news_2020_freq.txt"

fileData :: FilePath
fileData = "german.utf8.dic"

fileSorted :: FilePath
fileSorted = "german.utf8.sorted.dic"

parseFrequencies :: BS.ByteString -> [(BS.ByteString, Int)]
parseFrequencies bs = case BS.uncons bs of
    Nothing -> []
    -- this is admittedly brittle, just to demonstrate single-pass parsing with readInt
    Just (35, _) -> parseFrequencies (BS.unsafeTail (BS.dropWhile (/= 10) bs))
    _ -> let (w, f) = BS.break (== 9) bs in
         case BS.readInt (BS.unsafeTail f) of
                Just (i, bs') -> (w, i) : parseFrequencies (BS.unsafeTail bs')
                Nothing -> []

Key insights:

  1. Your data is UTF8, but all parsing-sensitive characters (which are #, \t and \n) are ASCII. This suggests to use ByteString instead Text, immediately halving memory requirements.
  2. Both files must be loaded in full before sorting. So no point in lazy ByteString: in fact it will degrade performance by increasing heap fragmentation.
  3. Since keys are short strings, there is unlikely to be much benefit from HashMap, we can use Map and do not waste space for hashes.
  4. No need to involve Vector only for the purpose of sorting, plain old Data.List.sortOn is good enough.
  5. Use findWithDefault instead of fromMaybe / lookup, because it allocates less.
  6. Use readInt to parse integers from ByteString, do not resort to read . unpack.
  7. Use Builder for output, avoiding constructing it in memory in full.