Choosing a data structure for cache of multiple fake cursors.

[Keith David Bershatsky <esq@lawlist.com>]

I am working on optimizing the drawing/erasing of multiple fake cursors in conjunction with the proposed implementation of feature requests #22873 (multiple fake cursors) and #17684 (crosshairs / visible fill-column).

The lines that need to potentially be updated can be extracted from update_window, which calls update_window_line, which calls update_text_area.  I have created modified versions of update_window_line / update_text_area and made a "dry run" that yields a list of lines that need to potentially be updated (before the updating actually occurs).  Let us assume for purposes of this example that the "dry run" tells us that we need to potentially update VPOS lines 5, 8 and 25.

The cache of multiple fake cursors is presently in the form of a Lisp_Object with 15 elements for each fake cursor.  From studying the Emacs code, it appears that a Lisp_Object may have been a poor choice for the cache data structure.  The reason I say that, is because now I am faced with the need to add/delete certain elements from the cache.

The elements of the cache are as follows:  x [int]; fx [frame x | int]; y [int]; fy [frame y | int]; hpos [int]; vpos [int]; h [height | int]; cursor_type [int]; cursor_width [int]; foreground [vector of 3 doubles]; background [vector of 3 doubles]; active_p [bool]; minimal_p [bool]; flavor [int]; posint [int].

In this example, we want to find all VPOS entries in the cache for 5, 8 and 25 and do two things:  (i) erase the fake cursors on the line; and, (2) recalculate/redraw the fake cursors on those lines based on the new layout.

Assuming that we are dealing with a potential of 200+ fake cursors on a visible window, what is the best data structure for performance and ease of add/removing elements (with 15 sub-elements)?

EXAMPLE:  Remove all lines from the cache that have a VPOS of 5, 8 and 25; and, add new entries to the cache with updated values for lines with a VPOS of 5, 8 and 25.

Thanks,

Keith