How to quickly compare equality of structs ...

How to quickly compare equality of structs ...

[Keith David Bershatsky]

I am working on feature requests 22873 (multiple fake cursors) and 17684 (crosshairs that track the cursor position).

GOAL:  Reduce removal of fake cursors to the bare minimum and redraw only those fake cursors that are absolutely necessary.  [If done in an efficient manner, this might increase overall speed/performance and also reduce what the user sees when Emacs removes / draws fake cursors.]

Fake cursors come in two varieties:  (1) either they intersect a glyph; or, (2) they are floating (without any glyph intersection).  Think of a vertical/horizontal line that spans the entire window-body-height/width of a visible window -- parts of the line will intersect glyphs, and other parts of the line will be floating (not intersecting anything).

The floating fake cursors can only be erased with surgical precision by using cached data (screen relative coordinates, background color, dimensions of the rectangle).  The cached data becomes outdated when redisplay updates w->current_matrix, so removal of fake cursors must occur prior thereto.

mc_pre_scroll_clean is called _before_ redisplay updates w->current_matrix -- all fake cursors are removed and the caches are reset.  This happens _before_ the text is scrolled on the glass directly by try_window_reusing_current_matrix, try_window_id, and/or scrolling_window.

Fake cursors are created anew (and their data cached) immediately following calls to draw_glyphs within update_window => update_window_line => update_text_area.  Part of this happens when processing w->desired_matrix (if rows are enabled), and the remainder happens using w->current_matrix.

Whenever glyphs are redrawn during redisplay using w->current_matrix, fake cursors are likewise redrawn (only where needed) using cached data.  Essentially, any call to draw_glyphs using w->current_matrix is a cue for fake cursors to be redrawn immediately thereafter.

The cache of fake cursors is array of structs -- each fake cursors has approximately fifteen (15) elements of stored data.

TENTATIVE THINKING:  For each fake cursor, create a unique numeric representation of all cached elements combined; e.g., SHA1 (Secure Hash Algorithm).  That unique id can be stored as an additional element for each fake cursor cached.  Before the w->current_matrix (from the previous command loop) is altered, perform a dry-run to see what the new cache of fake cursors looks like.  Then, compare the old and tentative new cache to determine which fake cursors must be removed and which need to be drawn.

PROBLEM:  If the tentative plan makes good sense, then how can I programmatically turn a combination of int, enum, double and bool into one (1) unique numeric representation such as a SHA1 (Secure Hash Algorithm)?

Other ideas that are just as quick, or quicker would be greatly appreciated.

The latest proof concept patch of feature requests 17684 / 22873 is now at version 19.003:

https://debbugs.gnu.org/cgi/bugreport.cgi?bug=22873#137

Here is the structure of the cache of fake cursors:

struct multiple_cursors_cache
{
  ptrdiff_t allocated;
  ptrdiff_t used;
  enum type_of_cache
    {
      NO_CACHE,
      MC_CACHE,
      CH_CACHE,
      FC_CACHE
    } cache_type;
  struct items_in_cache
    {
      int x;
      int fx;
      int y;
      int fy;
      int hpos;
      int vpos;
      int wd;
      int h;
      enum type_of_cursor
        {
          /* NOTE:  The fringe bitmap framework relies upon MC_NO_FRINGE_BITMAP
          HAVING A VALUE OF ZERO (0). */
          MC_NO_FRINGE_BITMAP,
          MC_NO_CURSOR,
          MC_RIGHT_FRINGE_BITMAP,
          MC_LEFT_FRINGE_BITMAP,
          MC_FRAMED_BOX,
          MC_FILLED_BOX,
          MC_HOLLOW_BOX,
          MC_BAR,
          MC_HBAR
        } cursor_type;
      int cursor_width;
      struct RGB
        {
          double red;
          double green;
          double blue;
        } foreground, background;
      bool active_p;
      enum mc_flavor
        {
          NO_FLAVOR,
          MC_GLYPH,
          MC_GLYPHLESS,
          MC_OVERLAY_ARROW_BITMAP,
          MC_PILCROW,
          MC_HOLLOW_RECTANGLE_RIGHT_ARROW,
          MC_REVERSED_HOLLOW_RECTANGLE_RIGHT_ARROW,
          MC_HOLLOW_RECTANGLE,
          MC_VERTICAL_BAR_RIGHT_ARROW,
          MC_REVERSED_VERTICAL_BAR_RIGHT_ARROW,
          MC_VERTICAL_BAR,
          MC_REVERSED_VERTICAL_BAR,
          MC_VERTICAL_BAR_BACKSLASH
        } glyph_flavor;
      bool enabled_p;
    } *caches;
};

Re: How to quickly compare equality of structs ...

[Paul Eggert]

On 5/6/19 11:55 AM, Keith David Bershatsky wrote:
> PROBLEM:  If the tentative plan makes good sense, then how can I programmatically turn a combination of int, enum, double and bool into one (1) unique numeric representation such as a SHA1 (Secure Hash Algorithm)?

It's not clear to me that hashing is needed here; why not just use
memcmp? And if you do need hashing, why not just use an ordinary hash
table rather than messing with cryptographic hashing?

Re: How to quickly compare equality of structs ...

[Keith David Bershatsky]

Thank you, Paul, for having a look at this particular thread.

I had read on Stackoverflow that memcmp is not always reliable, and that is why I was trying to come up with a quick and guaranteed method of doing the comparison of data for each fake cursor in the new/old caches:

https://stackoverflow.com/a/141791/2112489

In the accepted answer, it says that C provides no method for comparing equality of structs ...

My only experience with a hash table has been in Lisp by setting up a unique key per each entry in the table; e.g., make-hash-table, gethash, puthash ....  The old cache and new cache will most likely have a different number of fake cursors and the order in which they appear will also be different; e.g., 200 fake cursors in the old cache and 250 fake cursors in the new cache.  Based on my limited experience with hash tables in Lisp, I am unable to visualize how I could use such a table in C to do my comparison for each fake cursor ....

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

> Date: [05-06-2019 12:00:11] <6 May 2019 12:00:11 -0700>
> From: Paul Eggert <eggert@cs.ucla.edu>
> To: Keith David Bershatsky <esq@lawlist.com>
> Cc: Emacs Devel <emacs-devel@gnu.org>
> Subject: Re: How to quickly compare equality of structs ...
> 
> On 5/6/19 11:55 AM, Keith David Bershatsky wrote:
> > PROBLEM:  If the tentative plan makes good sense, then how can I programmatically turn a combination of int, enum, double and bool into one (1) unique numeric representation such as a SHA1 (Secure Hash Algorithm)?
> 
> It's not clear to me that hashing is needed here; why not just use
> memcmp? And if you do need hashing, why not just use an ordinary hash
> table rather than messing with cryptographic hashing?

Re: How to quickly compare equality of structs ...

[Paul Eggert]

On 5/6/19 1:40 PM, Keith David Bershatsky wrote:
> C provides no method for comparing equality of structs

You can compare each member of the struct yourself. Or you can use
memset to clear all the bytes in the struct (including padding bytes)
before initializing the struct members, and then use memcmp on the result.

> Based on my limited experience with hash tables in Lisp, I am unable to visualize how I could use such a table in C to do my comparison for each fake cursor ....

I'm sure there's a way.

Re: How to quickly compare equality of structs ...

[Keith David Bershatsky]

Thank you, Paul, for the suggestions.

This afternoon, I came across the Cantor's Pairing Function that can be used to create a unique ID for each fake cursor.  With that unique ID, I can limit the quantity of comparisons ....

 n = ((x + y)*(x + y + 1)/2) + y

I'll keep working the outline/plan ...

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

> Date: [05-06-2019 14:22:37] <6 May 2019 14:22:37 -0700>
> From: Paul Eggert <eggert@cs.ucla.edu>
> To: Keith David Bershatsky <esq@lawlist.com>
> Cc: emacs-devel@gnu.org
> Subject: Re: How to quickly compare equality of structs ...
> 
> On 5/6/19 1:40 PM, Keith David Bershatsky wrote:
> > C provides no method for comparing equality of structs
> 
> You can compare each member of the struct yourself. Or you can use
> memset to clear all the bytes in the struct (including padding bytes)
> before initializing the struct members, and then use memcmp on the result.
> 
> > Based on my limited experience with hash tables in Lisp, I am unable to visualize how I could use such a table in C to do my comparison for each fake cursor ....
> 
> I'm sure there's a way.

Re: How to quickly compare equality of structs ...

[Stefan Monnier]

> This afternoon, I came across the Cantor's Pairing Function that can be used
> to create a unique ID for each fake cursor.  With that unique ID, I can
> limit the quantity of comparisons ....
>  n = ((x + y)*(x + y + 1)/2) + y

Not sure why you care about limiting the number of comparisons.
Replacing two comparisons with one-comparison-plus-two-mults (and
reducing the range of x and y to sqrt(MAXINT) along thre way) doesn't
sound like much of a win.


        Stefan

Re: How to quickly compare equality of structs ...

[Keith David Bershatsky]

Thank you, Stefan, for your insight regarding this issue.

I was thinking that if each fake cursor had a unique key based upon the x/y coordinates, then I could reduce my comparison for each fake cursor to just one (1) potential match.

If for example, the old cache contains a fake cursor with an x of 0 and a y of 3, then the key is 9.  I would search the new tentative cache for a key of 9 -- if none is found, then this fake cursor must be erased.  If a key of 9 is found in the new tentative cache, then proceed to do one of the methods suggested by Paul -- i.e., "compare each member of the struct" or use memcmp (provided that memset was used when initializing to remove padding).  Once that comparison is done, the fake cursor is deleted if there is no exact match; or, left right where it is if there is an exact match.

With an arbitrary estimated need of approximately 250 or so fake cursors for any live window, a "for" loop to search for a unique key in the new tentative cache is probably sufficiently effective.  I was; however, also thinking about the possibility of using a key in the context of a hash table if that would be more prudent.

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

> From:  Stefan Monnier
> Subject:  Re: How to quickly compare equality of structs ...
> Date:  Mon, 06 May 2019 20:49:23 -0400
> 
> > This afternoon, I came across the Cantor's Pairing Function that can be used
> > to create a unique ID for each fake cursor.  With that unique ID, I can
> > limit the quantity of comparisons ....
> >  n = ((x + y)*(x + y + 1)/2) + y
> 
> Not sure why you care about limiting the number of comparisons.
> Replacing two comparisons with one-comparison-plus-two-mults (and
> reducing the range of x and y to sqrt(MAXINT) along thre way) doesn't
> sound like much of a win.
> 
> 
>         Stefan

Re: How to quickly compare equality of structs ...

[Stefan Monnier]

> If for example, the old cache contains a fake cursor with an x of 0 and
> a y of 3, then the key is 9.  I would search the new tentative cache for
> a key of 9

That's a for-loop over the table with 1 int-comparison per iteration.

> -- if none is found, then this fake cursor must be erased.
> If a key of 9 is found in the new tentative cache, then proceed to do one of
> the methods suggested by Paul -- i.e., "compare each member of the struct"

That's a for-loop over the table with 2 int-comparisons per iteration.

The extra comparison per iteration is likely to be negligible.

> With an arbitrary estimated need of approximately 250 or so fake cursors for
> any live window, a "for" loop to search for a unique key in the new
> tentative cache is probably sufficiently effective.  I was; however, also
> thinking about the possibility of using a key in the context of a hash table
> if that would be more prudent.

I don't know how your fake-cursors are represented in the Elisp world,
but maybe you can add to the structs in the above table a pointer back
to the corresponding Elisp data, and then you can perform a single scan
of the table and for each such cursor, check the Elisp side to see if
it's still "live".  This would avoid the lookup altogether?

I'm probably not making sense, tho, since I have no idea how your
system is structured.  Don't mind me,


        Stefan