git-gutter
git-gutter copied to clipboard
perf: optimize git-gutter:view-for-unchanged with range-based processing
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