This module provides the types of fixed-size and bounded-size encodings, which are the basic building blocks for constructing Builders. They are used for application specific performance tuning of Builders. For example, libraries such as blaze-html or aeson use the functions provided by this module to implement efficient encodings that combine escaping and character encoding. We explain fixed-size and bounded-size encodings in three steps. First, we define them formally. Then, we explain how they can improve the performance of a Builder. Finally, we give two examples to illustrate their use.

Fixed(-size) encodings are encodings that always result in a sequence of bytes of a predetermined, fixed length. An example for a fixed encoding is the big-endian encoding of a Word64, which always results in exactly 8 bytes. Bounded(-size) encodings are encodings that always result in a sequence of bytes that is no larger than a predetermined bound. An example for a bounded encoding is the UTF-8 encoding of a Char, which results always in less or equal to 4 bytes.

Note that every fixed encoding is also a bounded encoding. This module does not expose functions that exploit the special properties of fixed-size encodings. However, they are exploited in the functions encodeSizePrefixed and encodeChunked from Data.ByteString.Lazy.Builder.Extras, which prefix a Builder with its (chunk) size. In the following, we therefore only refer to bounded encodings.

The goal of bounded encodings is to improve the performance of Builders. These improvements stem from making the two most common steps performed by a Builder more efficient.

The first most common step is the concatentation of two Builders. Internally, concatentation corresponds to function composition. (Note that Builders can be seen as difference-lists of buffer-filling functions; cf. http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist. ) Function composition is a fast O(1) operation. However, we can use bounded encodings to remove some of these function compositions altoghether, which is obviously more efficient.

The second most common step performed by a Builder is to fill a buffer using a bounded encoding, which works as follows. The Builder checks whether there is enough space left to execute the bounded encoding. If there is, then the Builder executes the bounded encoding and calls the next Builder with the updated buffer. Otherwise, the Builder signals its driver that it requires a new buffer. This buffer must be at least as large as the bound of the encoding. We can use bounded encodings to reduce the number of buffer-free checks by fusing the buffer-free checks of consecutive Builders. We can also use bounded encodings to simplify the control flow for signalling that a buffer is full by ensuring that we check first that there is enough space left and only then decide on how to encode a given value.

Let us illustrate these improvements on the CSV-table rendering example from Data.ByteString.Lazy.Builder. Its "hot code" is the rendering of a table's cells, which we implement as follows using only the functions from the Builder API.

import           Data.ByteString.Lazy.Builder         as B
import           Data.ByteString.Lazy.Builder.ASCII   as B

renderCell :: Cell -> Builder
renderCell (StringC cs) = renderString cs
renderCell (IntC i)     = B.intDec i

renderString :: String -> Builder
renderString cs = B.charUtf8 '"' <> foldMap escape cs <> B.charUtf8 '"'
  where
    escape '\\' = B.charUtf8 '\\' <> B.charUtf8 '\\'
    escape '\"' = B.charUtf8 '\\' <> B.charUtf8 '\"'
    escape c    = B.charUtf8 c

Efficient encoding of Ints as decimal numbers is performed by intDec from Data.ByteString.Lazy.Builder.ASCII. Optimization potential exists for the escaping of Strings. The above implementation has two optimization opportunities. First, we can use a single buffer free check for 4 bytes before escaping a character and only then decide on how to escape the character. This simplifies the control flow and allows to avoid a closure construction, which improves the performance of the Builder. Second, the concatenations performed by foldMap can be eliminated. The following implementation exploits these optimizations.

import qualified Data.ByteString.Lazy.Builder.BasicEncoding  as E
import           Data.ByteString.Lazy.Builder.BasicEncoding
                 ( ifB, fromF, (>*<), (>$<) )

renderString :: String -> Builder
renderString cs =
    B.charUtf8 '"' <> E.encodeListWithB escape cs <> B.charUtf8 '"'
  where
    escape :: E.BoundedEncoding Char
    escape =
      ifB (== '\\') (fixed2 ('\\', '\\')) $
      ifB (== '\"') (fixed2 ('\\', '\"')) $
      E.charUtf8
     
    {-# INLINE fixed2 #-}
    fixed2 x = fromF $ const x >$< E.char7 >*< E.char7

The code should be mostly self-explanatory. The slightly awkward syntax is because the combinators are written such that the sizeBound of the resulting BoundedEncoding can be computed at compile time. We also explicitly inline the fixed2 encoding, which encodes a fixed tuple of characters, to ensure that the bound compuation happens at compile time. When encoding the following list of Strings, the optimized implementation of renderString is two times faster.

maxiStrings :: [String]
maxiStrings = take 1000 $ cycle ["hello", "\"1\"", "λ-wörld"]

Most of the performance gain stems from using encodeListWithB, which encodes a list of values from left-to-right with a BoundedEncoding. It exploits the Builder internals to avoid unnecessary function compositions (i.e., concatentations). In the future, we would expect the compiler to perform the optimizations implemented in encodeListWithB by himself. However, it seems that the code is currently to complicated for the compiler to see through. Therefore, we provide the BoundedEncoding escape hatch, which allows data structures to provide very efficient encoding traversals, like encodeListWithB for lists.

Note that BoundedEncodings are a bit verbose, but quite versatile. Here is an example of a BoundedEncoding for combined HTML escaping and UTF-8 encoding. It exploits that the escaped character with the maximal Unicode codepoint is '>'.

{-# INLINE charUtf8HtmlEscaped #-}
charUtf8HtmlEscaped :: E.BoundedEncoding Char
charUtf8HtmlEscaped =
    ifB (>  '>' ) E.charUtf8 $
    ifB (== '<' ) (fixed4 ('&',('l',('t',';')))) $        -- &lt;
    ifB (== '>' ) (fixed4 ('&',('g',('t',';')))) $        -- &gt;
    ifB (== '&' ) (fixed5 ('&',('a',('m',('p',';'))))) $  -- &amp;
    ifB (== '"' ) (fixed5 ('&',('#',('3',('4',';'))))) $  -- &#34;
    ifB (== '\'') (fixed5 ('&',('#',('3',('9',';'))))) $  -- &#39;
    (fromF E.char7)         -- fallback for Chars smaller than '>'
  where
    {-# INLINE fixed4 #-}
    fixed4 x = fromF $ const x >$<
      E.char7 >*< E.char7 >*< E.char7 >*< E.char7
     
    {-# INLINE fixed5 #-}
    fixed5 x = fromF $ const x >$<
      E.char7 >*< E.char7 >*< E.char7 >*< E.char7 >*< E.char7

The combinators for FixedEncodings are implemented such that the size of the resulting FixedEncoding is computed at compile time.

In terms of expressivity, the function encodeWithF would be sufficient for constructing Builders from FixedEncodings. The fused variants of this function are provided because they allow for more efficient implementations. Our compilers are just not smart enough yet; and for some of the employed optimizations (see the code of encodeByteStringWithF) they will very likely never be.

Note that functions marked with "Heavy inlining." are forced to be inlined because they must be specialized for concrete encodings, but are rather heavy in terms of code size. We recommend to define a top-level function for every concrete instantiation of such a function in order to share its code. A typical example is the function byteStringHexFixed from Data.ByteString.Lazy.Builder.ASCII, which is implemented as follows.

 {-# NOINLINE byteStringHexFixed #-}
 byteStringHexFixed :: S.ByteString -> Builder
 byteStringHexFixed = encodeByteStringWithF word8HexFixed

The combinators for BoundedEncodings are implemented such that the sizeBound of the resulting BoundedEncoding is computed at compile time.

We provide an overloaded operator for the contramapF and contramapB combinators to allow for a more convenient syntax. The operator is source-compatible with the one provided by the contravariant library. Once this library is part of the Haskell platform, we will make FixedEncoding and BoundedEncoding instances of its Contravariant type-class.

Decimal encoding of numbers using ASCII encoded characters.

Encoding positive integers as hexadecimal numbers using lower-case ASCII characters. The shortest possible representation is used. For example,

 showB word16Hex 0x0a10 = "a10"

Note that there is no support for using upper-case characters. Please contact the maintainer if your application cannot work without hexadecimal encodings that use upper-case characters.

Encoding the bytes of fixed-width types as hexadecimal numbers using lower-case ASCII characters. For example,

 showF word16HexFixed 0x0a10 = "0a10"

The ISO/IEC 8859-1 encoding is an 8-bit encoding often known as Latin-1. The Char8 encoding implemented here works by truncating the Unicode codepoint to 8-bits and encoding them as a single byte. For the codepoints 0-255 this corresponds to the ISO/IEC 8859-1 encoding. Note that the Char8 encoding is equivalent to the ASCII encoding on the Unicode codepoints 0-127. Hence, functions such as intDec can also be used for encoding Ints as a decimal number with Char8 encoded characters.

The UTF-8 encoding can encode all Unicode codepoints. It is equivalent to the ASCII encoding on the Unicode codepoints 0-127. Hence, functions such as intDec can also be used for encoding Ints as a decimal number with UTF-8 encoded characters.

The following four functions are intended for testing use only. They are not efficient. FixedEncodings and BoundedEncodings are efficently executed by creating Builders from them using the encodeXXX functions explained at the top of this module.