micro optimizations

[milahu]

hey, thanks for this : )

i have briefly used this library on my journey to write a terminal widget for pysimplegui
only to notice later, that i need a full terminal emulator → pyte

anyway, i made some small optimizations for your code
i hope you find this useful to make outta.parser faster

i did not do any benchmarks, but ... im feeling lucky ; )
in general ...

• for-loops are faster than while-loops
• function calls are expensive → return arrays, not class-instances
• loop unswitching
• arrays are the fastest data structure → combine positional and optional arguments
• consumers want numeric token types for faster switching (jump table)

#! /usr/bin/env python3

import outta.parser # outta.parser.Parser
outta_parser = outta.parser.Parser()

enable_debug = False

def _print(*args, **kwargs):
    if enable_debug:
        print(*args, **kwargs)

# just a workaround between old api and new api
outta_token_type_of_class = {
    outta.elements.Text: 0,
    outta.elements.LineFeed: 1, # type <= 1 == Text or Linefeed
    outta.elements.CarriageReturn: 2, # type <= 2 == Text or Linefeed or CarriageReturn
    # reserved: 3-15
    # TODO? add more "frequent" controls
    outta.elements.AlignmentDisplay: 16,
    outta.elements.Any: 17,
    outta.elements.Backspace: 18,
    outta.elements.Bell: 19,
    #outta.elements.CarriageReturn: 20,
    outta.elements.ClearTabStop: 21,
    outta.elements.CursorBack: 22,
    outta.elements.CursorDown: 23,
    outta.elements.CursorDown1: 24,
    outta.elements.CursorForward: 25,
    outta.elements.CursorPosition: 26,
    outta.elements.CursorToColumn: 27,
    outta.elements.CursorToLine: 28,
    outta.elements.CursorUp: 29,
    outta.elements.CursorUp1: 30,
    outta.elements.Debug: 31,
    outta.elements.DefineCharset: 32,
    outta.elements.DeleteCharacters: 33,
    outta.elements.DeleteLines: 34,
    outta.elements.DisableUTF8Mode: 35,
    outta.elements.Draw: 36,
    outta.elements.Element: 37,
    outta.elements.EnableUTF8Mode: 38,
    outta.elements.EraseCharacters: 39,
    outta.elements.EraseInDisplay: 40,
    outta.elements.EraseInLine: 41,
    outta.elements.Index: 42,
    outta.elements.InsertCharacters: 43,
    outta.elements.InsertLines: 44,
    outta.elements.Iterable: 45,
    #outta.elements.LineFeed: 46,
    outta.elements.Mapping: 47,
    outta.elements.ReportDeviceAttributes: 48,
    outta.elements.ReportDeviceStatus: 49,
    outta.elements.Reset: 50,
    outta.elements.ResetMode: 51,
    outta.elements.RestoreCursor: 52,
    outta.elements.ReverseIndex: 53,
    outta.elements.SaveCursor: 54,
    outta.elements.SelectGraphicRendition: 55,
    outta.elements.SetIconName: 56,
    outta.elements.SetMargins: 57,
    outta.elements.SetMode: 58,
    outta.elements.SetTabStop: 59,
    outta.elements.SetTitle: 60,
    outta.elements.SetTitleAndIconName: 61,
    outta.elements.ShiftIn: 62,
    outta.elements.ShiftOut: 63,
    outta.elements.Tab: 64,
    #outta.elements.Text: 65,
}

# patch the outta_parser.feed function
# avoid function calls
# use arrays
# dont build strings with +=
# unswitch loop
# https://github.com/abingham/outta/blob/0458723dd5012102ef7ea12cbb5c4d47e85ded39/source/outta/parser.py#L134
#def outta_parser_feed(self, input: str) -> Iterable[list]: # NameError: name 'Iterable' is not defined
def outta_parser_feed(self, input: str):
    """Consume some data and advances the state as necessary.
    Args:
        input: a blob of data to feed from.
    Returns:
        An iterable of list's.
    """
    parse_control_char = self._send_to_parser
    match_text = self._text_pattern.match
    taking_plain_text = self._taking_plain_text

    input_end = len(input)
    token_start = 0

    _print("input", repr(input)) # debug

    debug_counter = 0 # stop infinte loops

    while token_start < input_end:
        debug_counter += 1
        if debug_counter > 20:
            _print("debug break")
            break
        # loop tokens. cold code
        # token_start is variable
        _print(f"token_start={token_start} input_end={input_end} taking_plain_text={taking_plain_text}")
        if taking_plain_text:
            match = match_text(input, token_start)
            _print(f"match={match}")
            if match:
                # this token is text
                #start, token_start = match.span() # test
                #assert match.group(0) == input[start:token_start] # test
                # result[0]: token type. 0 = Text
                # result[1]: token value
                # result[2]: optional arguments [dict]
                token_start = match.end() # next token
                yield [0, match.group(0), None]
                continue # next token is text or control
            else:
                taking_plain_text = False
                _print("taking_plain_text = False")
                # this token is control
                # seek to token_end
        #else:
        # this token is control
        # seek to token_end
        # token_start <= char_index <= token_end
        _print(f"token_start {token_start}: loop chars")
        for char_index in range(token_start, input_end):
            ##_print(f"char_index {char_index}:", repr(input[char_index])) # verbose
            # loop chars. hot code
            # limitation: char_index is constant -> cannot seek in for loop
            #result = parse_control_char(input[char_index])
            try:
                result = self._parser.send(input[char_index]) # TODO sequence_buffer is never used
            except Exception:
                # Reset the parser state to make sure it is usable even
                # after receiving an exception. See PR #101 for details.
                self._initialize_parser()
                raise
            if result == None:
                #_print(f"char_index {char_index} next")
                continue # next char
            #if result != None:
            token_end = char_index
            #token_source = input[token_start:token_end] # too short
            #token_source = input[(token_start - 1):token_end] # wrong
            token_source = input[token_start:(token_end + 1)]
            _print(f"char_index {char_index}, token_start {token_start}, token_end {token_end}, token_source {repr(token_source)}, result", result)
            # token_class = result[0] [class] example: outta.elements.LineFeed
            # token_parameters = result[1] [tuple]
            # token_keywords = result[2] [dict]
            #yield result[0](result[1], result[2], token_source)
            token_class, token_args, token_kwargs = result
            token_type = outta_token_type_of_class[token_class] # workaround for new API
            if token_class == outta.elements.LineFeed:
                # FIXME token_source == ""
                _print("##########\nfound linefeed", repr(token_source), "\n##########")
            token_kwargs["args"] = token_args # TODO move all args to result[2]
            yield [token_type, token_source, token_kwargs]
            taking_plain_text = True # next token is text or control
            token_start = token_end + 1 # next token # FIXME token_start is off by one?
            #return # debug: token_start is 0
            _print("stop char loop")
            break # stop looping chars. return to the while loop

    self._taking_plain_text = taking_plain_text # save state for next call to feed

#outta_parser.feed = outta_parser_feed # TypeError: outta_parser_feed() missing 1 required positional argument: 'data'
# problem: outta_parser is instance, not class
import types
outta_parser.feed = types.MethodType(outta_parser_feed, outta_parser)

# just some silly example code
def strip_ansi_codes(string):
    """remove ansi control sequences from terminal output"""
    # patched api
    result = ""
    ansi_token_iter = outta_parser.feed(string)
    for ansi_token in ansi_token_iter:
        #if ansi_token[0] <= 2: # token_type is Text or Linefeed or CarriageReturn
        if ansi_token[0] <= 1: # token_type is Text or Linefeed
            result += ansi_token[1] # token_source
    return result

# test: byte chunks produced by bash
bytes_ = b"".join([
  b'\x1b]0;user@laptop1:/tmp/demo\x1b\\',
  b'\x1b]7;file://laptop1/tmp/demo\x1b\\',
  b'\x1b[?2004h',
  b'\r\r\n\x1b[1;32m[\x1b]0;user@laptop1: /tmp/demo\x07user@laptop1:/tmp/demo]$\x1b[0m ',
])
term_str = strip_ansi_codes(bytes_.decode("utf8"))
term_str_expected = '\n[user@laptop1:/tmp/demo]$ '
print(repr(term_str))
assert term_str == term_str_expected

[abingham]

If you can turn this into a PR and do some convincing performance comparison, I'll consider some or all of it. I suspect that things like e.g. "for loops are faster than while loops" are likely not really correct in any meaningful way...the example you link to shows a degenerate case where the body of the loops are insignificant (as the discussion therein points out).

consumers want numeric token types for faster switching (jump table)

This is an interesting point that may deserve independent discussion. Can you give an example or other motivation where the change will make a real difference in performance? Why can't they use class objects as keys in a dict? Are integers so much faster as keys that we should make the change?

[milahu]

do some convincing performance comparison

of course we need benchmarks

i need a full terminal emulator → pyte

so, technically, i dont need outta.parser, but ...

def _parser_fsm and def feed in pyte/streams.py look familiar ...
aka its exactly (or mostly) the same code as in outta.parser
which means yay, i actually have time to work on this : )

ideally we would have one "source of truth" for the ansi parser
so either pyte should use outta to parse ansi-escapes ...
or, we deprecate outta in favor of pyte, since the parser alone is rather useless
selectel/pyte#152

[milahu]

some convincing performance comparison

yepp. turns out, my solution is slower

pyte benchmark:

$ BENCHMARK=tests/captured/htop.input python benchmark.py
htop.input->Screen: Mean +- std dev: 147 ms +- 14 ms
htop.input->DiffScreen: Mean +- std dev: 148 ms +- 13 ms
htop.input->HistoryScreen: Mean +- std dev: 384 ms +- 17 ms

# add "optimizations"

$ BENCHMARK=tests/captured/htop.input python benchmark.py
htop.input->Screen: Mean +- std dev: 166 ms +- 9 ms
htop.input->DiffScreen: Mean +- std dev: 168 ms +- 8 ms
htop.input->HistoryScreen: Mean +- std dev: 514 ms +- 10 ms

probably its faster if the control tokens are longer ...
but control tokens are too short to outweigh the cost of the added for loop

closing

[abingham]

FWIW, I fully endorse combining my work with pyte. If I could get the information provided by outta from pyte, I would gladly get rid of outta. See selectel/pyte#147.