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.