git-gutter icon indicating copy to clipboard operation
git-gutter copied to clipboard

perf: optimize git-gutter:view-for-unchanged with range-based processing

Open eval-exec opened this issue 3 months ago • 0 comments

Summary

  • Replace O(n×m) line-by-line checking with O(m) range-based algorithm
  • Pre-compute unchanged line ranges from diff hunks instead of checking each line individually

Performance Results

Before (profiler output):

git-gutter:unchanged-line-p: 44% CPU (561,222 samples)
git-gutter:view-for-unchanged: 48% CPU (615,209 samples)
        615408  48%            - funcall
        615408  48%             - git-gutter:view-diff-infos
        615408  48%              - if
        615408  48%               - progn
        615408  48%                - git-gutter:view-set-overlays
        615209  48%                 - if
        615209  48%                  - progn
        615209  48%                   - git-gutter:view-for-unchanged
        615209  48%                    - save-excursion
        615209  48%                     - let
        572935  45%                      - while
        562784  44%                       - if
        561222  44%                        - git-gutter:unchanged-line-p
         43839   3%                         - let*
         27120   2%                          - while
         24919   1%                           - and
         24119   1%                            - progn
         23519   1%                             - setq
         17748   1%                              - let*
         15551   1%                               - progn
         13755   1%                                - or
         13755   1%                                 - let*
          2984   0%                                  - progn
          2386   0%                                   - and
          1800   0%                                      memq
          2818   0%                              - not
          2197   0%                               - and
          1398   0%                                  >=
           599   0%                                  <=
           398   0%                                car
           200   0%                              consp

After (profiler output):

git-gutter:view-for-unchanged: 1% CPU (36,736 samples)
         36736   1%                        - git-gutter:view-for-unchanged
         36736   1%                         - if
         36736   1%                          - progn
         36736   1%                           - save-excursion
         36736   1%                            - let
         22445   1%                             - git-gutter:put-signs
         22445   1%                              - if
         22445   1%                               - let
         22445   1%                                - while
         21648   1%                                 - let
         19479   0%                                  - let
         10130   0%                                   - git-gutter:before-string
          9531   0%                                    - let
          3562   0%                                     - propertize
           600   0%                                        list
          2779   0%                                     - concat
          2177   0%                                      - git-gutter:gutter-seperator
          1778   0%                                       - if
          1183   0%                                        - progn
          1183   0%                                           propertize
          1770   0%                                     make-overlay
           600   0%                                     overlay-put

Performance improvement: ~97% reduction in CPU usage

eval-exec avatar Sep 05 '25 15:09 eval-exec