Here's another one I threw together, tested here in src/keymap.c:
(defvar bench-run-times 10000)
...
However, if I ramp up bench-run-times to 100000 I start seeing GC hits,
and then nlinum--line-number-at-pos can be up to 10 times slower
Instead…
I got some speedup for free because I’m always interested in the line number at (point-max), and that remains fixed until the buffer changes. But otherwise, for random jumps that span a large fraction of a file’s length, I found “most recent line” caching doesn’t help you too much, as you might expect. But far more likely than jumping at random in a buffer is asking for many nearby line numbers in rapid succession (e.g. scrolling). I simulated that by skipping say 3000±1500 characters ahead at a time. For that access pattern, the speedup of “most recent” caching is tremendous, and increases linearly with position in a file.
I should point out that in my testing, format-mode-line %l performs even at worst case 10x better than line-number-at-pos, but both of them scale together with position in the file; i.e. both are counting lines from the beginning of the file (but one is doing it in C). When a file hasn’t changed, this is just tremendously inefficient. It does seem to have some kind of very nearby caching built in, since taking small steps (like a couple characters) leads to freakish speed in the 10µs range.
To support more random access patterns, it may pay to cache more than just the “last line”. E.g. if the distance from the closest last position is >20% of the (narrowed) buffer length, save another line on the cache (up to some fixed number of lines), in addition to the most recent. Finding the nearest cached point wouldn’t be free, and a deeper cache might slow down sequential (scrolling) cached line calculation a bit, but a modest amount of spread might be worth it to improve performance in the more general case. I’d personally favor `line-number-at-pos-cached' or perhaps a new optional CACHED argument, since there may be other caching strategies people have employed. |