Choosing a data structure for cache of multiple fake cursors.

Choosing a data structure for cache of multiple fake cursors.

[Keith David Bershatsky]

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

Re: Choosing a data structure for cache of multiple fake cursors.

[Eli Zaretskii]

> Date: Mon, 24 Dec 2018 22:18:12 -0800
> From: Keith David Bershatsky <esq@lawlist.com>
> 
> 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].

You didn't describe what each element means.

> 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)?

If the number of elements is fixed, then a vector would be more
convenient, but other than that, I don't see why it would be a poor
choice to use a list.  We access and modify lists (and other Lisp
objects) from C code all the time, to say nothing of the fact that
these objects and the primitive operations on them are implemented in
C to begin with.

Re: Choosing a data structure for cache of multiple fake cursors.

[Keith David Bershatsky]

Thank you, Eli, for reading this particular thread.

My first thought was to remove elements from the cache, and add elements to the cache.  E.g., a Lisp equivalent would be:

  (setcar (nthcdr 17 the-list) my-variable)

or

  (setcar (nthcdr 17 the-list) my-variable)

and

  (defun remove-nth-element (nth list)
    (if (zerop nth) (cdr list)
      (let ((last (nthcdr (1- nth) list)))
        (setcdr last (cddr last))
        list)))

  (remove-nth-element 0 (list 1 2 3 4 5))

The replace/remove approach above appears to be somewhat daunting given the complexity of the cache described below.

Today, I thought of a different approach which is to create a new cache with the desired components.  E.g., Loop through the old cache and create a new one that includes new data and omits certain outdated data.  That would obviate the need to use the replace/remove approach above.

When the fake cursors are active for a particular buffer, each window has its own cache (a Lisp_Object).  The cache is a list with three elements:

1.  First element of the cache is another list containing lists of 15 elements -- one list of 15 elements is used for each fake cursor.

    x:  A window relative x-axis coordinate for a glyph.

    fx:  A frame relative x-axis coordinate for the vertical bar cursor, which can intersect any desired area of a glyph.  This is useful for vertically intersecting nonstandard width characters and also for buffers with variable pitch font.

    y:  A window relative y-axis coordinate for the glyph.

    fy:  A frame relative y-axis coordinate used to align all fake cursors along the horizontal ruler of the crosshairs.

    hpos:  The coordinate within a glyph row used to find a particular glyph of a particular display line.

    vpos:  A particular display line on the y-axis.

    h:  The height of a fake cursor, which is set to the glyph row->visible_height.

    cursor_type:  One of the text_cursor_kinds defined in dispextern.h, with a few additional possible types:  NO_FRINGE_BITMAP, LEFT_FRINGE_BITMAP, RIGHT_FRINGE_BITMAP, FRAMED_BOX_CURSOR.

    cursor_width:  The thickness of the horizontal / vertical bar cursors.

    foreground:  The color of a fake cursor in the form of an LSL color vector consisting of three doubles; e.g., a shade of grey is [0.75 0.75 0.75].  The API exposed to the Emacs user lets him/her specify the color in any one of three possible formats:  a string such as "grey", a hex format such as "#bfbfbf", or an LSL color vector.  If a user specified a string, then Emacs converts it to an LSL color vector.  Colors are treated differently on the various platforms, e.g., NS, NT and X11.  Depending upon the platform that Emacs was built, the LSL color vector is converted to whatever is needed.

    background:  An LSL color vector (like above), which is used for erasing a fake cursor with that has no glyph.  I think of these as floating fake cursors.

    active_p:  A boolean value to indicate whether the fake cursor appears in the active window.

    minimal_p:  A boolean value used to indicate whether the LEFT_FRINGE_BITMAP should be drawn in one of two possible colors.  E.g., when the crosshairs and/or the visible fill column are on an idle timer, a blue arrow indicates the timer is pending, and a red arrow is used when the timer fires and the Full Monty is drawn.

    flavor:  Enum values defined in dispextern.h:  NO_FLAVOR, MC_GLYPH, MC_GLYPHLESS, MC_OVERLAY_ARROW_BITMAP, MC_PILCROW, MC_HOLLOW_RECTANGLE_RIGHT_ARROW, MC_HOLLOW_RECTANGLE, MC_VERTICAL_BAR_RIGHT_ARROW, MC_VERTICAL_BAR, MC_VERTICAL_BAR_BACKSLASH.  These are used to know what type of fake cursor to draw, which may be over a glyph, or floating in thin air, or a particular left/right fringe bitmap.

    posint:  The buffer position of a fake cursor if it coincides with a glyph.

2.  The second element of the cache is the window that the cache corresponds to.

3.  The third element of the cache is the buffer that the cache corresponds to.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

> Date: [12-25-2018 05:36:26] <25 Dec 2018 15:36:26 +0200>
> From: Eli Zaretskii <eliz@gnu.org>
> 
> >
> > 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].
> 
> You didn't describe what each element means.
> 
> > 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)?
> 
> If the number of elements is fixed, then a vector would be more
> convenient, but other than that, I don't see why it would be a poor
> choice to use a list.  We access and modify lists (and other Lisp
> objects) from C code all the time, to say nothing of the fact that
> these objects and the primitive operations on them are implemented in
> C to begin with.