Как долго может быть имя конструктора типа?

Ответ 1

Если мы проверим источник для ghc, мы найдем тип, используемый для определения конструкторов данных. Он называется DataCon и имеет следующее поле:

dcName    :: Name,  -- This is the name of the *source data con*

Спустившись по кроличьей дыре, Имя содержит OccName:

n_occ  :: !OccName,     -- Its occurrence name

An OccName содержит FastString для имени:

data OccName = OccName
    { occNameSpace :: !NameSpace
    , occNameFS :: !FastString
    }
    deriving Typeable

Наконец, FastString - всего лишь ByteString, также с предварительно рассчитанной длиной, а int - для его тега для быстрого сравнения

data FastString = FastString {
      uniq :: {-# UNPACK #-} !Int, -- unique id
      n_chars :: {-# UNPACK #-} !Int, -- number of chars
      fs_bs :: {-# UNPACK #-} !ByteString,
      fs_ref :: {-# UNPACK #-} !(IORef (Maybe FastZString))
  } deriving Typeable

Нет ограничений на размер строки с использованием этого типа данных (кроме, очевидно, maxBound :: Int). Однако это не исключает ошибки где-то еще в коде, который может вызвать проблемы.

Итак, нам нужна программа для проверки этого:

{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE TemplateHaskell #-}
module Main where
import Control.Applicative ((<$>))
import Control.Monad (forM_)
import System.IO (hPutStr, hFileSize, hClose)
import System.Exit (ExitCode(..))
import System.IO.Temp (withSystemTempFile)
import Data.Time.Clock.POSIX (getPOSIXTime)
import System.Process (readProcessWithExitCode)

-- timing functions (from criterion)
getTime :: IO Double
getTime = (fromRational . toRational) `fmap` getPOSIXTime

time :: IO a -> IO (Double, a)
time act = do
  start <- getTime
  result <- act
  end <- getTime
  let !delta = end - start
  return (delta, result)



-- make a constructor like
-- data C = FFFFFF
makeConstructor :: Int -> String
makeConstructor size = "data C = " ++ replicate size 'F'

wrapWithMainModule :: String -> String
wrapWithMainModule code = unlines ["module Main where", "main = return ()", code]

data CompileResults = CompileResults {
  timeTaken :: Double,
  success :: Bool,
  outputFileSize :: Integer
  } deriving (Show)



compileHsCode :: String -> IO CompileResults
compileHsCode sourceCode = withSystemTempFile "test.hs" $ \path handle -> do
  withSystemTempFile "output.o" $ \outputPath outputHandle -> do
    hPutStr handle $ wrapWithMainModule sourceCode
    hClose handle
    (timeTaken, (exitCode, _, _)) <- time $ readProcessWithExitCode "ghc" ["-c", "-o", outputPath, path] ""
    let success = exitCode == ExitSuccess

    size <- if success then hFileSize outputHandle else return 0
    return $ CompileResults {
      timeTaken = timeTaken
      , success = success
      , outputFileSize = size
      }


testConstructorSizes :: [Int] -> IO ()
testConstructorSizes sizes = forM_ sizes $ \size -> do
  info <- compileHsCode $ makeConstructor size
  putStrLn $ "For Size " ++ show size ++ "\t: " ++ show info



-- Up to 10 million
sizesToTest :: [Int]
sizesToTest = take 7 (iterate (*10) 10)

main = testConstructorSizes $ sizesToTest

Вот результат работы main:

For Size 10     : CompileResults {timeTaken = 0.1390078067779541, success = True, outputFileSize = 1818}
For Size 100    : CompileResults {timeTaken = 0.14700841903686523, success = True, outputFileSize = 2086}
For Size 1000   : CompileResults {timeTaken = 0.1390080451965332, success = True, outputFileSize = 4786}
For Size 10000  : CompileResults {timeTaken = 0.1520085334777832, success = True, outputFileSize = 31786}
For Size 100000 : CompileResults {timeTaken = 0.31201791763305664, success = True, outputFileSize = 301786}
For Size 1000000        : CompileResults {timeTaken = 2.26712965965271, success = True, outputFileSize = 3001786}
For Size 10000000       : CompileResults {timeTaken = 109.2182469367981, success = True, outputFileSize = 30001786}

Несколько интересных моментов:

• Обратите внимание на то, как время, затраченное на увеличение, превышает 1 миллион. Вы ожидали бы увеличения x10, если бы изменение было линейным, но это изменение x50. Это, вероятно, означало бы для конструктора с 100 миллионами символов, для компиляции потребовалось бы около 5000 секунд (что я не тестировал).
• Размер файла для всех записей был точно (1786 + (constructorSize * 3). Поэтому каждый char занимает три байта при использовании в конструкторе.