Строки по-взрослому и производительность

Финал проекта. Весь генератор написан на String, и для учебного кода это правильно: String это просто [Char], всё прозрачно. Но в проде на String не пишут, и пора понять почему. Разберём три строковых типа (String, Text, ByteString), зачем нужен Builder, что включает OverloadedStrings, и как конвертировать без сюрпризов. А потом измерим: добавим второй путь рендера через Builder и сравним его со String-генератором через criterion. Говорить о скорости будем цифрами.

Идея

String в Haskell это синоним [Char], связный список символов. Это честный, ленивый, прозрачный тип: всё, что ты знаешь про списки из урока 3, работает и тут. Но у списка символов есть цена, и в горячем коде она кусается:

• каждый символ это отдельная cons-ячейка в куче, с указателем на следующий. Память на строку из N символов это N ячеек, а не N байт;
• конкатенация a <> b для списка это обход всего a, чтобы пришить b в хвост. Собираешь строку из M кусков наивной склейкой, и сложность ползёт к квадрату.

Поэтому экосистема стоит на двух специализированных типах:

• Text для человекочитаемого Unicode-текста. Хранится упакованным массивом (с версии 2.0 это UTF-8), занимает в разы меньше памяти, операции быстрее. Это дефолт для текста в проде.
• ByteString для сырых байтов: бинарные данные, сеть, ввод-вывод на уровне байтов. Это не текст: байты становятся символами только когда ты выбрал кодировку.

Правило выбора простое. Человекочитаемый текст это Text. Сырые байты (картинка, сетевой пакет) это ByteString. String это для маленьких объёмов, прототипов и учебного кода, где прозрачность важнее скорости. Наш генератор учебный, поэтому String тут уместен; но раз он про экосистему, мы обязаны показать, как было бы в проде.

OverloadedStrings: литералы для всех

Есть бытовая проблема: литерал "hello" по умолчанию имеет тип String, и присвоить его Text нельзя без конвертации. Расширение OverloadedStrings это чинит: с ним литерал получает свой тип через класс IsString, и "hello" годится и для String, и для Text, и для ByteString.

{-# LANGUAGE OverloadedStrings #-}

import Data.Text (Text)

greeting :: Text
greeting = "привет"   -- литерал стал Text, без pack

Без расширения пришлось бы писать pack "привет". С ним литералы становятся полиморфными. Почти любой проект на Text включает OverloadedStrings глобально в cabal-файле через default-extensions.

Builder: склейка без квадрата

Главная идея производительности этого урока. Когда строишь длинную строку из множества кусков, наивный <> плох: каждая склейка копирует левый аргумент. Builder решает это: добавление к Builder это O(1), а сериализуется он в строку один раз в самом конце.

Думай про Builder как про список отложенных кусков: ты накапливаешь “допиши это, потом то”, а реальная сборка в непрерывный буфер происходит при финальном toLazyText. Тот же приём, что строковый Builder в Java или StringBuilder в C#, только тут это обычный Monoid: куски склеиваются через <>, нейтральный элемент это mempty.

Напишем второй путь рендера нашего HTML, на Builder. Заведём Press.Render.Text:

{-# LANGUAGE OverloadedStrings #-}

module Press.Render.Text
  ( renderDocument, escapeText, escapeBuilder )
where

import Data.Text (Text)
import qualified Data.Text as T
import Data.Text.Lazy (toStrict)
import Data.Text.Lazy.Builder (Builder, toLazyText)
import qualified Data.Text.Lazy.Builder as B

import qualified Press.Markup as Markup

renderDocument :: Text -> Markup.Document -> Text
renderDocument title doc =
  toStrict . toLazyText $
    el "html" (el "head" (el "title" (escapeBuilder title)) <> el "body" body)
  where
    body = foldMap structure doc

structure :: Markup.Structure -> Builder
structure = \case
  Markup.Heading n txt ->
    el ("h" <> B.fromString (show n)) (escapeBuilder (T.pack txt))
  Markup.Paragraph p ->
    el "p" (escapeBuilder (T.pack p))
  Markup.UnorderedList items ->
    el "ul" (foldMap (el "li" . el "p" . escapeBuilder . T.pack) items)
  Markup.OrderedList items ->
    el "ol" (foldMap (el "li" . el "p" . escapeBuilder . T.pack) items)
  Markup.CodeBlock code ->
    el "pre" (escapeBuilder (T.pack (unlines code)))

el :: Builder -> Builder -> Builder
el tag content =
  "<" <> tag <> ">" <> content <> "</" <> tag <> ">"

Заметь: el тут собирает Builder, а <> это O(1) добавление, а не копирование. Литералы "<", ">" стали Builder благодаря OverloadedStrings. А foldMap structure doc склеивает все блоки тем же Monoid-приёмом, что и String-версия из урока 28, только теперь склейка дешёвая.

Сердце это экранирование на Builder:

escapeBuilder :: Text -> Builder
escapeBuilder = T.foldr (\c acc -> escapeChar c <> acc) mempty
  where
    escapeChar c = case c of
      '<' -> "&lt;"
      '>' -> "&gt;"
      '&' -> "&amp;"
      '"' -> "&quot;"
      '\'' -> "&#39;"
      _ -> B.singleton c

Для контраста оставим рядом наивную версию на Text, которая аллоцирует новый Text на каждый символ через T.concatMap:

escapeText :: Text -> Text
escapeText = T.concatMap $ \c -> case c of
  '<' -> "&lt;"
  '>' -> "&gt;"
  '&' -> "&amp;"
  '"' -> "&quot;"
  '\'' -> "&#39;"
  _ -> T.singleton c

Обе корректны и дают одинаковый результат. Разница только в аллокациях, и её мы сейчас измерим.