Subject: Re: bug#73563: [Ben Simms] Performance bottleneck in ns_draw_fringe_bitmap

From: Alan Third <[email-masked]>
Date: Sat, 24 May 2025 17:10:55 +0100

On Tue, May 13, 2025 at 08:37:55PM +0900, Jordan Ellis Coppard wrote:
> Howdy,
> 
> 
> I've been using the following patch (bottom of this email) until my most
> recent rebuild of Emacs from master. Since the recent commit fixing stipple
> drawing the patch can be reduced to just: https://github.com/emacs-mirror/emacs/commit/7f2efe6503fdce2a4e552c14802644a05b581bc7
> (link to a diff authored by Ben Simms).
> 
> I've now noticed again extreme slowdown when fringe bitmaps are used. It
> appears to be proportional to the number of bits set in the bitmap. An
> 'empty' bitmap (all zeroes) doesn't yield any noticeable slowdown, a bitmap
> with 1 bit set yields a little, with 2 its noticeable and with all 8 bits
> set Emacs takes up to 1 second to respond to any input at all.
> 
> This has been the case since at least August of last year. I can get a
> minimal reproduction but it has happened on completely different
> configurations with the only common denominator being the NS build (on
> ARM-based macOS), and the use of fringe bitmaps.

I have no idea what's going on, but it looks from the trace like the
problem is in the transform to move it to the final position, or the
copy... Which are both odd as to my mind they should be fast
processes.

Since we can't really use Core Graphics code in the NS port, I've
tried improving the bitmap tracing a little. I have my doubts it will
improve things much, but can you please try it and see how it
compares? I tried it here and the difference between all three
versions of the code is within 0.2 of a second, and totally
inconsistent. I couldn't vouch for any of them being consistently
faster.

-- 
Alan Third
>From 553fc809fcb1ad6768a7b6058521fc45e79da661 Mon Sep 17 00:00:00 2001
From: Alan Third <[email-masked]>
Date: Sat, 24 May 2025 16:29:33 +0100
Subject: [PATCH] Simplified NS fringe vectors

---
 src/nsterm.m | 99 ++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 92 insertions(+), 7 deletions(-)

diff --git a/src/nsterm.m b/src/nsterm.m
index 5514a693c86..578e20d11ba 100644
--- a/src/nsterm.m
+++ b/src/nsterm.m
@@ -2904,16 +2904,101 @@ Hide the window (X11 semantics)
   if (!fringe_bmp)
     fringe_bmp = [[NSMutableDictionary alloc] initWithCapacity:25];
 
-  [p moveToPoint:NSMakePoint (0, 0)];
-
-  for (int y = 0 ; y < h ; y++)
-    for (int x = 0 ; x < w ; x++)
+  uint8_t *points = alloca((h + 1) * (w + 1) * 4);
+  uint8_t *cur = points;
+
+  /* Find all the outgoing edges in a clockwise path.  That is, we only
+     want to list the edges leaving a point, not the ones entering a
+     point, so we don't double count them.  */
+  for (int y = 0 ; y < h + 1 ; y++)
+    for (int x = 0 ; x < w + 1 ; x++)
       {
-        bool bit = bits[y] & (1 << (w - x - 1));
-        if (bit)
-          [p appendBezierPathWithRect:NSMakeRect (x, y, 1, 1)];
+        int nw=0, ne=0, se=0, sw=0;
+        if (x != 0 && y != 0)
+          nw = bits[y-1] & (1 << (w - x));
+
+        if (x != 0 && y < h)
+          sw = bits[y] & (1 << (w - x));
+
+        if (x < w && y < h)
+          se = bits[y] & (1 << (w - x - 1));
+
+        if (x < w && y != 0)
+          ne = bits[y-1] & (1 << (w - x - 1));
+
+        cur[0] = !nw && ne; /* north */
+        cur[1] = !ne && se; /* east */
+        cur[2] = !se && sw; /* south */
+        cur[3] = !sw && nw; /* west */
+        cur += 4;
       }
 
+  /* Find all the points with edges and trace them out.  */
+  int v = 0;
+  char last = 0;
+  while (v < (h + 1) * (w + 1) * 4)
+    {
+      char this = 0;
+      int x = (v/4) % (w+1);
+      int y = (v/4) / (w+1);
+
+      if (points[v+3])
+        {
+          /* west */
+          points[v+3] = 0;
+          v = v - 4;
+          this = 'w';
+        }
+      else if (points[v+1])
+        {
+          /* east */
+          points[v+1] = 0;
+          v = v + 4;
+          this = 'e';
+        }
+      else if (points[v+2])
+        {
+          /* south */
+          points[v+2] = 0;
+          v = ((y+1)*(w+1) + x) * 4;
+          this = 's';
+        }
+      else if (points[v])
+        {
+          /* north */
+          points[v] = 0;
+          v = ((y-1)*(w+1) + x) * 4;
+          this = 'n';
+        }
+      else
+        {
+          /* no edge */
+          v = v + 4;
+
+          if (last)
+            {
+              /* If we reach here we were tracing a shape but have run
+                 out of edges, so we must be back to the start (or
+                 something's gone wrong).  */
+              [p closePath];
+              last = 0;
+            }
+        }
+
+      if (this)
+        {
+          /* If we've found an edge we now need to either move to that
+             point (if it's the start of a shape) or draw a line from
+             the last corner to this point, but only if it's a
+             corner.  */
+          if (!last)
+            [p moveToPoint:NSMakePoint (x, y)];
+          else if (last && last != this)
+              [p lineToPoint:NSMakePoint (x, y)];
+          last = this;
+        }
+    }
+
   [fringe_bmp setObject:p forKey:[NSNumber numberWithInt:which]];
 }
 
-- 
2.45.2