Strict `Text` wrapper unnecessarily decodes to `Char` for `text-2.*`

[sol]

Looking at the code:

alex/data/AlexWrappers.hs

Lines 88 to 90 in e65958c

	type AlexInput = (Char, -- previous char
	[Byte], -- pending bytes on current char
	Data.Text.Text) -- current input string

This can be replaced by:

type AlexInput = (Int,            -- current offset
                  Data.Text.Text) -- input string

alex/data/AlexWrappers.hs

Lines 98 to 105 in e65958c

	alexGetByte :: AlexInput -> Maybe (Byte,AlexInput)
	alexGetByte (c,(b:bs),s) = Just (b,(c,bs,s))
	alexGetByte (_,[],s) = case Data.Text.uncons s of
	Just (c, cs) ->
	case utf8Encode' c of
	(b, bs) -> Just (b, (c, bs, cs))
	Nothing ->
	Nothing

This can be replaced by:

alexGetByte :: AlexInput -> Maybe (Byte,AlexInput)
alexGetByte (cur, input) = case input of
  Text arr off len
    | cur < len = Just (unsafeIndex arr (off + curr) (cur + 1, input))
    | otherwise = Nothing

The only thing "complicated" is alexInputPrevChar, basically you go back from cur one byte at a time until you have seen two character boundaries and then do a character decode at that position.

[sol]

alexScanTokens also needs to be adjusted:

alexScanTokens input@(Text arr off _) = go (0, input)
  where go cur@(start, _) =
          case alexScan cur 0 of
                AlexEOF -> []
                AlexError _ -> error "lexical error"
                AlexSkip  new _len  -> go new
                AlexToken new _len act -> act match : go new
                   where
                     match = Text arr (off + start) (end - start)
                     (end, _) = new

[sol]

Also note that the current code

alex/data/AlexWrappers.hs

Line 526 in e65958c

AlexToken inp__' len act -> act (Data.Text.take len s) : go inp__'

is O(len), while the the new code is O(1).

[sol]

I modified https://gitlab.com/FinnBender/haskell-parsing-benchmarks to gauge the impact and it roughly improved performance by 25%.

This includes reading the file from disk and parsing. If we would only look at lexing, then the performance difference should be more significant.

I noticed that I get performance close to strict-bytestring, but still somewhat worse. I expected them to be on par. I'm not sure where the additional cycles are spent, possibly it's in the IO part (IIRC, there is currently no way to read from disk directly into a byte array, so I think creating the Text value copies the input one additional time, not sure if this is enough to explain the discrepancy).

[Bodigrim]

I'm not sure where the additional cycles are spent, possibly it's in the IO part (IIRC, there is currently no way to read from disk directly into a byte array, so I think creating the Text value copies the input one additional time, not sure if this is enough to explain the discrepancy).

Did you try https://hackage-content.haskell.org/package/text-2.1.3/docs/Data-Text-IO-Utf8.html ?

[sol]

Did you try https://hackage-content.haskell.org/package/text-2.1.3/docs/Data-Text-IO-Utf8.html ?

Yes, of course. Otherwise I think the discrepancy would be more pronounced.

Taking a quick look at the code now:

1. It does a sequential scan over the input for UTF-8 validation.
2. It converts ByteString to StrictTextBuilder and then to Text which is basically copying the input one time.

I imagine that (1) + (2) may very well explain the discrepancy I saw between Text and ByteString.

Somehow yesterday I forgot about (1). Depending on what Alex does internally this may or may not be necessary. If it's not necessary then I guess you could read the input into a ShortByteString and then do an (unsafe) O(1) conversion to Text.

[sol]

Somehow yesterday I forgot about (1). Depending on what Alex does internally this may or may not be necessary. If it's not necessary then I guess you could read the input into a ShortByteString and then do an (unsafe) O(1) conversion to Text.

I guess if you are trying squeeze out every inch of performance and if your input is regularly coming from a file, then you could do the lexing on ByteString and construct Text values (and do UTF-8 validation, if necessary) in alexScanTokens on AlexToken.

• With this approach, the input is not copied one additional time as no Text value is constructed initially.
• Only the parts of the input that you retain in the AST are copied.

One nice property you're getting for free with this approach is that all retained values don't reference the original input anymore so that the input can be garbage collected.