Max Nikulin <maniku...@gmail.com> writes: >> +;; the same purpose. Overlays are implemented with O(n) complexity in >> +;; Emacs (as for 2021-03-11). It means that any attempt to move >> +;; through hidden text in a file with many invisible overlays will >> +;; require time scaling with the number of folded regions (the problem >> +;; Overlays note of the manual warns about). For curious, historical >> +;; reasons why overlays are not efficient can be found in >> +;; https://www.jwz.org/doc/lemacs.html. > > The linked document consists of a lot of messages. Could you, please, > provide more specific location within the rather long page?
There is no specific location. That thread is an old drama unfolded when intervals were first implemented by a third-party company (they were called intervals that time). AFAIU, the fact that intervals are stored in a list and suffer from O(N) complexity originates from that time. Just history, as I pointed in the comment. FYI, a more optimal overlay data structure implementation has been attempted in feature/noverlay branch (for example, see https://git.savannah.gnu.org/cgit/emacs.git/commit/?h=feature/noverlay&id=8d7bdfa3fca076b34aaf86548d3243bee11872ad). But there is no activity on that branch for years. Best, Ihor
