I did a test where going to from the end to the beginning of a 50 million length line happens instantly when using beginning-of-line. I wonder if this is because it is a C primitive or because Emacs implements this and related functions in an efficient way. For example, it could keep a mapping from line numbers to the positions of those lines within the buffer (this is just a guess). Why is it so fast? Does the runtime depend on the number of characters on the line, or is it constant?
The underlying function is
emacs/src/search.c. It uses a cache of sections of text that contain no newlines, so the function can skip over them quickly. The cache is controlled by the variable
cache-long-scans, whose doc string says:
Non-nil means that Emacs should use caches in attempt to speedup buffer scans.
There is no reason to set this to nil except for debugging purposes.
Normally, the line-motion functions work by scanning the buffer for newlines. Columnar operations (like ‘move-to-column’ and ‘compute-motion’) also work by scanning the buffer, summing character widths as they go. This works well for ordinary text, but if the buffer’s lines are very long (say, more than 500 characters), these motion functions will take longer to execute. Emacs may also take longer to update the display.
If ‘cache-long-scans’ is non-nil, these motion functions cache the results of their scans, and consult the cache to avoid rescanning regions of the buffer until the text is modified. The caches are most beneficial when they prevent the most searching---that is, when the buffer contains long lines and large regions of characters with the same, fixed screen width.
When ‘cache-long-scans’ is non-nil, processing short lines will become slightly slower (because of the overhead of consulting the cache), and the caches will use memory roughly proportional to the number of newlines and characters whose screen width varies.
Bidirectional editing also requires buffer scans to find paragraph separators. If you have large paragraphs or no paragraph separators at all, these scans may be slow. If ‘cache-long-scans’ is non-nil, results of these scans are cached. This doesn’t help too much if paragraphs are of the reasonable (few thousands of characters) size.
The caches require no explicit maintenance; their accuracy is maintained internally by the Emacs primitives. Enabling or disabling the cache should not affect the behavior of any of the motion functions; it should only affect their performance.