bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Ihor Radchenko]

[-- Attachment #1: Type: text/plain, Size: 980 bytes --]

Hi,

When investigating `re-search-forward' performance in
https://debbugs.gnu.org/cgi/bugreport.cgi?bug=58558 (bug#58558), I
noticed that buf_bytepos_to_charpos is taking most of the CPU time,
according to perf stats.

This was partially caused by `parse-sexp-lookup-properties', but even
after working around the text property issue, buf_bytepos_to_charpos
still shows up on top of the perf profile.

Since one of the apparent bottlenecks in buf_bytepos_to_charpos is

for (tail = BUF_MARKERS (b); tail; tail = tail->next)

which obviously scales with the number of markers in buffer, I decided
to add a cut-off parameter, as in the attached patch (number 50 has no
particular motivation underneath).

Surprisingly, this simple change reduced my Org agenda generation times
from 20 seconds down to 3-4 seconds!

I am sure that my dumb approach is not the best way to improve the
performance, but this place in buf_bytepos_to_charpos is clearly
something that can be optimized.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-src-marker.c-buf_bytepos_to_charpos-Limit-marker-sea.patch --]
[-- Type: text/x-patch, Size: 1180 bytes --]

From a6ff6268bdc42a7dfedc6729d4232a2ae149da56 Mon Sep 17 00:00:00 2001
Message-Id: <a6ff6268bdc42a7dfedc6729d4232a2ae149da56.1682278830.git.yantar92@posteo.net>
From: Ihor Radchenko <yantar92@posteo.net>
Date: Sun, 23 Apr 2023 21:31:46 +0200
Subject: [PATCH] * src/marker.c (buf_bytepos_to_charpos): Limit marker search

Limit searching across buffer markers to first 50 markers and thus
avoid performance scaling with the number of markers.

I got 5x `re-search-forward' speed improvement in my setup with this
dumb change.
---
 src/marker.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/src/marker.c b/src/marker.c
index e42c49a5434..008a76c49e6 100644
--- a/src/marker.c
+++ b/src/marker.c
@@ -348,8 +348,10 @@ buf_bytepos_to_charpos (struct buffer *b, ptrdiff_t bytepos)
   if (b == cached_buffer && BUF_MODIFF (b) == cached_modiff)
     CONSIDER (cached_bytepos, cached_charpos);
 
-  for (tail = BUF_MARKERS (b); tail; tail = tail->next)
+  int i = 0;
+  for (tail = BUF_MARKERS (b); tail && i < 50; tail = tail->next)
     {
+      i++;
       CONSIDER (tail->bytepos, tail->charpos);
 
       /* If we are down to a range of 50 chars,
-- 
2.40.0


[-- Attachment #3: Type: text/plain, Size: 610 bytes --]


In GNU Emacs 30.0.50 (build 2, x86_64-pc-linux-gnu, GTK+ Version
 3.24.37, cairo version 1.17.8) of 2023-04-23 built on localhost
Repository revision: ca875e3947e29d222554a05583068c49a56ed8ca
Repository branch: master
Windowing system distributor 'The X.Org Foundation', version 11.0.12101008
System Description: Gentoo Linux

Configured using:
 'configure --with-native-compilation'


-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Date: Sun, 23 Apr 2023 19:41:40 +0000
> 
> When investigating `re-search-forward' performance in
> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=58558 (bug#58558), I
> noticed that buf_bytepos_to_charpos is taking most of the CPU time,
> according to perf stats.
> 
> This was partially caused by `parse-sexp-lookup-properties', but even
> after working around the text property issue, buf_bytepos_to_charpos
> still shows up on top of the perf profile.
> 
> Since one of the apparent bottlenecks in buf_bytepos_to_charpos is
> 
> for (tail = BUF_MARKERS (b); tail; tail = tail->next)
> 
> which obviously scales with the number of markers in buffer, I decided
> to add a cut-off parameter, as in the attached patch (number 50 has no
> particular motivation underneath).
> 
> Surprisingly, this simple change reduced my Org agenda generation times
> from 20 seconds down to 3-4 seconds!
> 
> I am sure that my dumb approach is not the best way to improve the
> performance, but this place in buf_bytepos_to_charpos is clearly
> something that can be optimized.

Interesting.  Would it be possible to show the effect of different
values of the cut-off on the performance, so we could decide which
value to use?

Thanks.

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> I am sure that my dumb approach is not the best way to improve the
>> performance, but this place in buf_bytepos_to_charpos is clearly
>> something that can be optimized.
>
> Interesting.  Would it be possible to show the effect of different
> values of the cut-off on the performance, so we could decide which
> value to use?

I can do such test, but I do not think that playing with cut off is the
best approach here.

The full code in question is below and there is already existing
condition to cut the marker loop early based on the distance from
best_above to the requested bytepos. So, another approach could be
playing with BYTECHAR_DISTANCE_INCREMENT. Now, it is clearly not
efficient enough for my large file. (Note that I expressed similar idea
in another discussion and was pointed exactly to this existing condition)

Further, the later code creates markers to cache recent results and
cutting too early may waste this cache. Another idea could be moving the
cache markers into a separate array, so that we can examine them without
mixing with all other buffer markers. I am not sure if it is feasible
though.

  int i = 0;
  for (tail = BUF_MARKERS (b); tail && i < 50; tail = tail->next)
    {
      i++;
      CONSIDER (tail->bytepos, tail->charpos);

      /* If we are down to a range of 50 chars,
	 don't bother checking any other markers;
	 scan the intervening chars directly now.  */
      if (best_above - bytepos < distance
          || bytepos - best_below < distance)
	break;
      else
        distance += BYTECHAR_DISTANCE_INCREMENT;
    }

  /* We get here if we did not exactly hit one of the known places.
     We have one known above and one known below.
     Scan, counting characters, from whichever one is closer.  */

  if (bytepos - best_below_byte < best_above_byte - bytepos)
    {
...
      /* If this position is quite far from the nearest known position,
	 cache the correspondence by creating a marker here.
	 It will last until the next GC.
	 But don't do it if BUF_MARKERS is nil;
	 that is a signal from Fset_buffer_multibyte.  */
      if (record && BUF_MARKERS (b))
	build_marker (b, best_below, best_below_byte);
...
      return best_below;
    }
  else
    {
...
      if (record && BUF_MARKERS (b))
	build_marker (b, best_above, best_above_byte);
...
      return best_above;
    }
}


-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Eli Zaretskii]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 63040@debbugs.gnu.org
> Date: Mon, 24 Apr 2023 06:36:07 +0000
> 
> > Interesting.  Would it be possible to show the effect of different
> > values of the cut-off on the performance, so we could decide which
> > value to use?
> 
> I can do such test, but I do not think that playing with cut off is the
> best approach here.
> 
> The full code in question is below and there is already existing
> condition to cut the marker loop early based on the distance from
> best_above to the requested bytepos. So, another approach could be
> playing with BYTECHAR_DISTANCE_INCREMENT.

Yes, that would be an even better idea, IMO.

> Now, it is clearly not efficient enough for my large file.

Why do you say that?  Did you try something and the results were
unsatisfactory?  And what is not efficient enough -- the cutoff based
on the number of markers tested or based on the distance?

> Further, the later code creates markers to cache recent results and
> cutting too early may waste this cache.

And the technique that you tried doesn't waste the cache?

> Another idea could be moving the cache markers into a separate
> array, so that we can examine them without mixing with all other
> buffer markers.

Why would that separation be useful?

Thanks.

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Eli Zaretskii]

[Resending with Stefan added.]

> From: Ihor Radchenko <yantar92@posteo.net>
> Cc: 63040@debbugs.gnu.org
> Date: Mon, 24 Apr 2023 06:36:07 +0000
> 
> > Interesting.  Would it be possible to show the effect of different
> > values of the cut-off on the performance, so we could decide which
> > value to use?
> 
> I can do such test, but I do not think that playing with cut off is the
> best approach here.
> 
> The full code in question is below and there is already existing
> condition to cut the marker loop early based on the distance from
> best_above to the requested bytepos. So, another approach could be
> playing with BYTECHAR_DISTANCE_INCREMENT.

Yes, that would be an even better idea, IMO.

> Now, it is clearly not efficient enough for my large file.

Why do you say that?  Did you try something and the results were
unsatisfactory?  And what is not efficient enough -- the cutoff based
on the number of markers tested or based on the distance?

> Further, the later code creates markers to cache recent results and
> cutting too early may waste this cache.

And the technique that you tried doesn't waste the cache?

> Another idea could be moving the cache markers into a separate
> array, so that we can examine them without mixing with all other
> buffer markers.

Why would that separation be useful?

Thanks.

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Ihor Radchenko]

Eli Zaretskii <eliz@gnu.org> writes:

>> Now, it is clearly not efficient enough for my large file.
>
> Why do you say that?  Did you try something and the results were
> unsatisfactory?  And what is not efficient enough -- the cutoff based
> on the number of markers tested or based on the distance?

Sorry for not being clear.

I was referring to the existing code.
"BYTECHAR_DISTANCE_INCREMENT" alone is clearly not efficient in my use
case because introducing an addition 50 cut-off improved the performance
significantly. Hence, there is some room for improvement in this area.

>> Further, the later code creates markers to cache recent results and
>> cutting too early may waste this cache.
>
> And the technique that you tried doesn't waste the cache?

I was talking about my technique. It is wasting the cache, and it is the
reason why I think that we should find a better approach; not the one I
used in the patch.

>> Another idea could be moving the cache markers into a separate
>> array, so that we can examine them without mixing with all other
>> buffer markers.
>
> Why would that separation be useful?

Because the markers created by buf_bytepos_to_charpos are at least 5000
bytes apart. There is no such guarantee for other buffer markers.

The while loops "while (best_below_byte < bytepos)" used as fallback
(when no nearby marker is found) traverse the buffer char-by-char
"("best_below_byte += buf_next_char_len (b, best_below_byte);" and
should be strictly inferior compared to well-spaced marker list.

However, when the marker list is not well-spaced, looping over all the
buffer markers can be a waste. And it looks like I hit exactly such
scenario in my setup.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Stefan Monnier]

Hi Ihor,

> When investigating `re-search-forward' performance in
> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=58558 (bug#58558), I
> noticed that buf_bytepos_to_charpos is taking most of the CPU time,
> according to perf stats.

I couldn't find a recipe to reproduce the problem.
Could you point me to it?


        Stefan

bug#63040: 30.0.50; Performance of buf_bytepos_to_charpos when a buffer has large number of markers

[Ihor Radchenko]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> Hi Ihor,
>
>> When investigating `re-search-forward' performance in
>> https://debbugs.gnu.org/cgi/bugreport.cgi?bug=58558 (bug#58558), I
>> noticed that buf_bytepos_to_charpos is taking most of the CPU time,
>> according to perf stats.
>
> I couldn't find a recipe to reproduce the problem.
> Could you point me to it?

The recipe is gone, because 0x0 has already deleted the reproducer I
managed to create (it was a large file). Although, I am still able to
reproduce with my private .org files. I am using the i < 50 hack as a
remedy.

-- 
Ihor Radchenko // yantar92,
Org mode contributor,
Learn more about Org mode at <https://orgmode.org/>.
Support Org development at <https://liberapay.com/org-mode>,
or support my work at <https://liberapay.com/yantar92>