[Bug preprocessor/118168] -Wmisleading-indentation causes 10x+ overhead or higher (visible on mypy-1.13.0)

[cvs-commit at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=118168

--- Comment #14 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andi Kleen <ak@gcc.gnu.org>:

https://gcc.gnu.org/g:4a992ecad0f302f69c4f6c42708c737eabaa60dc

commit r15-7327-g4a992ecad0f302f69c4f6c42708c737eabaa60dc
Author: Andi Kleen <ak@gcc.gnu.org>
Date:   Wed Dec 25 14:41:49 2024 -0800

    Rebalance file_cache input line cache dynamically

    The input context file_cache maintains an array of anchors
    to speed up accessing lines before the previous line.
    The array has a fixed upper size and the algorithm relies
    on the linemap reporting the maximum number of lines in the file
    in advance to compute the position of each anchor in the cache.

    This doesn't work for C which doesn't know the maximum number
    of lines before the files has finished parsing. The code
    has a fallback for this, but it is quite inefficient and
    effectively defeats the cache, so many accesses have to
    go through most of the input buffer to compute line
    boundaries. For large files this can be very costly
    as demonstrated in PR118168.

    Use a different algorithm to maintain the cache without
    needing the maximum number of lines in advance. When the cache
    runs out of entries and the gap to the last line anchor gets
    too large, prune every second entry in the cache. This maintains
    even spacing of the line anchors without requiring the maximum
    index.

    For the original PR this moves the overhead of enabling
    -Wmisleading-indentation to 32% with the default cache size.
    With a 10k entry cache it becomes noise.

      cc1 -O0 -fsyntax-only mypy.c   -quiet  ran
        1.03 ± 0.05 times faster than cc1 -O0 -fsyntax-only  mypy.c   -quiet
-Wmisleading-indentation --param=file-cache-lines=10000
        1.09 ± 0.08 times faster than cc1 -O0 -fsyntax-only  mypy.c   -quiet
-Wmisleading-indentation --param=file-cache-lines=1000
        1.32 ± 0.07 times faster than cc1 -O0 -fsyntax-only  mypy.c   -quiet
-Wmisleading-indentation

    The code could be further optimized, e.g. use the vectorized
    line search functions the preprocessor uses.

    Also it seems the input cache always reads the whole file into
    memory, so perhaps it should just be using file mmap if possible.

    gcc/ChangeLog:

            PR preprocessor/118168
            * input.cc (file_cache_slot::get_next_line): Use new algorithm
            to maintain
            (file_cache_slot::read_line_num): Use binary search for lookup.