bug#48734: 28.0.50; Performance regression in `string-width`?

bug#48734: 28.0.50; Performance regression in `string-width`?

[Imran Khan]

A package I use (deft-mode) has been hanging for minutes with high cpu
use recently. Profiler says most time is spent in `string-width`, and
upon looking it seems to happen in files that have multibyte characters
in them.

I reproduced the problem by creating a file that has both single and
multi byte characters:

with open("/tmp/test", "w") as f:
    for i in range(50_000):
        print("1", file=f, end="")
    print("α", file=f, end="")

And now:

(benchmark-run 1
  (let ((str))
    (with-temp-buffer
      (insert-file-contents-literally "/tmp/test")
      (setq str (buffer-string)))
    (string-width str)))

This takes 20 seconds in my machine (if string is exclusively full of
either single or multibyte characters, weirdly it seems to finish
instantly).

--------

In GNU Emacs 28.0.50 (build 1, x86_64-unknown-linux-gnu, X toolkit, cairo version 1.16.0)
 of 2021-05-29 built on 9d4a5f294007
Windowing system distributor 'The X.Org Foundation', version 11.0.12011000
System Description: void

Configured using:
 'configure --with-x-toolkit=athena --without-toolkit-scroll-bars
 --without-ns --with-xft --without-dbus --without-gconf
 --without-gsettings --with-zlib --prefix=/usr --sysconfdir=/etc
 --sbindir=/usr/bin --bindir=/usr/bin --mandir=/usr/share/man
 --infodir=/usr/share/info --localstatedir=/var
 --host=x86_64-unknown-linux-gnu --build=x86_64-unknown-linux-gnu
 '--libdir=${exec_prefix}/lib64' --with-file-notification=inotify
 --with-modules --with-native-compilation --with-jpeg --with-tiff
 --with-gif --with-png --with-xpm --with-rsvg --with-imagemagick
 --with-json --with-xml2 --with-gnutls --with-sound --with-m17n-flt
 --with-harfbuzz --with-cairo --with-lcms --without-gmp 'CFLAGS=-fno-PIE
 -mtune=generic -O2 -pipe ' 'CPPFLAGS= ' 'LDFLAGS=-no-pie
 -Wl,--as-needed ''

Configured features:
ACL CAIRO FREETYPE GIF GLIB GMP GNUTLS HARFBUZZ IMAGEMAGICK JPEG JSON
LCMS2 LIBOTF LIBXML2 M17N_FLT MODULES NATIVE_COMP NOTIFY INOTIFY PDUMPER
PNG RSVG SECCOMP SOUND THREADS TIFF X11 XDBE XIM XPM LUCID ZLIB

Important settings:
  value of $LC_ALL: en_GB.UTF-8
  value of $LC_COLLATE: en_GB.UTF-8
  value of $LC_CTYPE: en_GB.UTF-8
  value of $LANG: en_GB.UTF-8
  value of $XMODIFIERS: @im=ibus
  locale-coding-system: utf-8-unix

Memory information:
((conses 16 677156 287115)
 (symbols 48 39801 7)
 (strings 32 181641 67878)
 (string-bytes 1 6097769)
 (vectors 16 66337)
 (vector-slots 8 1256518 570753)
 (floats 8 909 1141)
 (intervals 56 1260 531)
 (buffers 992 22))

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Imran Khan <contact@imrankhan.live>
> Date: Sun, 30 May 2021 02:45:57 +0600
> 
> A package I use (deft-mode) has been hanging for minutes with high cpu
> use recently. Profiler says most time is spent in `string-width`, and
> upon looking it seems to happen in files that have multibyte characters
> in them.
> 
> I reproduced the problem by creating a file that has both single and
> multi byte characters:
> 
> with open("/tmp/test", "w") as f:
>     for i in range(50_000):
>         print("1", file=f, end="")
>     print("α", file=f, end="")
> 
> And now:
> 
> (benchmark-run 1
>   (let ((str))
>     (with-temp-buffer
>       (insert-file-contents-literally "/tmp/test")
>       (setq str (buffer-string)))
>     (string-width str)))
> 
> This takes 20 seconds in my machine (if string is exclusively full of
> either single or multibyte characters, weirdly it seems to finish
> instantly).

Since you use insert-file-contents-literally, why don't you also make
the temporary buffer unibyte?  That is:

  (benchmark-run 1
    (let ((str))
      (with-temp-buffer
	(set-buffer-multibyte nil)  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
	(insert-file-contents-literally "/tmp/test")
	(setq str (buffer-string)))
      (string-width str)))

Or maybe I don't understand your real-life use case?  Because if you
treat the file as a raw bytestream, why do you need to compute the
width of its text?

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Imran Khan <contact@imrankhan.live>
> Date: Sun, 30 May 2021 15:32:16 +0600
> 
> > Since you use insert-file-contents-literally, why don't you also make
> > the temporary buffer unibyte?  That is:
> >
> >   (benchmark-run 1
> >     (let ((str))
> >       (with-temp-buffer
> > 	(set-buffer-multibyte nil)  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
> > 	(insert-file-contents-literally "/tmp/test")
> > 	(setq str (buffer-string)))
> >       (string-width str)))
> >
> > Or maybe I don't understand your real-life use case?  Because if you
> > treat the file as a raw bytestream, why do you need to compute the
> > width of its text?
> 
> I would agree, my example was pointlessly contrived. For what it's
> worth, `insert-file-contents` exhibits same poor performance, and that's
> used by code in the wild (e.g. deft-mode, though I am sceptical if they
> should be needing to call `string-width` on entire buffer text either).
> 
> Personally I am now going to use your `(set-buffer-multibyte nil)`
> suggestion to patch their code for myself (so thanks for this). Since
> I have no idea about the internal complexity of `string-width` or what
> should be justified performance expectation, I would let you decide if
> this is a bug or not.

I'm not yet sure whether this is a real problem, because I don't
really understand the relation between your example code and what you
really need to do in deft-mode.  Specifically, generating random
characters isn't something that usually happens in real life.

So could you perhaps explain what you are using string-width for in
deft-mode, and what kind of text are you measuring there in your
real-life situations?

Thanks.

P.S. Please use Reply All to keep the bug address on the CC list.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Imran Khan]

Eli Zaretskii <eliz@gnu.org> writes:

>> From: Imran Khan <contact@imrankhan.live>
>> Date: Sun, 30 May 2021 15:32:16 +0600
>> 
>> > Since you use insert-file-contents-literally, why don't you also make
>> > the temporary buffer unibyte?  That is:
>> >
>> >   (benchmark-run 1
>> >     (let ((str))
>> >       (with-temp-buffer
>> > 	(set-buffer-multibyte nil)  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
>> > 	(insert-file-contents-literally "/tmp/test")
>> > 	(setq str (buffer-string)))
>> >       (string-width str)))
>> >
>> > Or maybe I don't understand your real-life use case?  Because if you
>> > treat the file as a raw bytestream, why do you need to compute the
>> > width of its text?
>> 
>> I would agree, my example was pointlessly contrived. For what it's
>> worth, `insert-file-contents` exhibits same poor performance, and that's
>> used by code in the wild (e.g. deft-mode, though I am sceptical if they
>> should be needing to call `string-width` on entire buffer text either).
>> 
>> Personally I am now going to use your `(set-buffer-multibyte nil)`
>> suggestion to patch their code for myself (so thanks for this). Since
>> I have no idea about the internal complexity of `string-width` or what
>> should be justified performance expectation, I would let you decide if
>> this is a bug or not.
>
> I'm not yet sure whether this is a real problem, because I don't
> really understand the relation between your example code and what you
> really need to do in deft-mode.  Specifically, generating random
> characters isn't something that usually happens in real life.
>
> So could you perhaps explain what you are using string-width for in
> deft-mode, and what kind of text are you measuring there in your
> real-life situations?
>
> Thanks.
>
> P.S. Please use Reply All to keep the bug address on the CC list.

Basically deft-mode takes a folder full of normal org-mode files, and
constructs a pretty "dashboard" view of the folder where you can browse,
search, filter the files in said folder (and many other features).

The dashboard UI uses `string-width` to calculate how much space is to
be allocated relative to window width to display metadata like file
title, file content summary, mtime etc for each file per line. This is
dynamic, the components size adjusts to window width change. Perhaps the
screenshot they have in their project page would be more descriptive:

https://github.com/jrblevin/deft

Org-mode files typically have unicode chars in them. So when deft-mode
uses `string-width` to construct view of file content part, it
hangs. I think the performance problem here is exacerbated because
deft-mode is stripping all vertical whitespace to squash the content to
show in a single line summary view, before calling `string-width`.

P.S. I am not involved with deft-mode, merely a user with moderately
sized utf-8 org-mode files. But if you think it's their UI
implementation ought be reworked, I can forward it to them.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Imran Khan <contact@imrankhan.live>
> Cc: 48734@debbugs.gnu.org
> Date: Sun, 30 May 2021 17:23:15 +0600
> 
> Basically deft-mode takes a folder full of normal org-mode files, and
> constructs a pretty "dashboard" view of the folder where you can browse,
> search, filter the files in said folder (and many other features).
> 
> The dashboard UI uses `string-width` to calculate how much space is to
> be allocated relative to window width to display metadata like file
> title, file content summary, mtime etc for each file per line. This is
> dynamic, the components size adjusts to window width change. Perhaps the
> screenshot they have in their project page would be more descriptive:
> 
> https://github.com/jrblevin/deft
> 
> Org-mode files typically have unicode chars in them. So when deft-mode
> uses `string-width` to construct view of file content part, it
> hangs. I think the performance problem here is exacerbated because
> deft-mode is stripping all vertical whitespace to squash the content to
> show in a single line summary view, before calling `string-width`.

If deft-mode wants to allocate space on display, then they really do
need to use string-width, but then the changes which make them "hang"
are really important, because before that string-width would compute
the result incorrectly when characters are composed on display.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> If deft-mode wants to allocate space on display, then they really do
> need to use string-width, but then the changes which make them "hang"
> are really important, because before that string-width would compute
> the result incorrectly when characters are composed on display.

string-width has always been approximate (but fast), hasn't it?  And to
determine the actual display width you've had to use
window-text-pixel-size or the like.

Perhaps string-width should get an extra parameter to get the new, more
accurate computation, and get the old, fast computation without this
parameter.

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: Imran Khan <contact@imrankhan.live>,  48734@debbugs.gnu.org
> Date: Sun, 30 May 2021 14:18:44 +0200
> 
> Eli Zaretskii <eliz@gnu.org> writes:
> 
> > If deft-mode wants to allocate space on display, then they really do
> > need to use string-width, but then the changes which make them "hang"
> > are really important, because before that string-width would compute
> > the result incorrectly when characters are composed on display.
> 
> string-width has always been approximate (but fast), hasn't it?  And to
> determine the actual display width you've had to use
> window-text-pixel-size or the like.

That should still be the case, although string-width will now be a bit
slower when the string includes characters which need to be composed
on display.

> Perhaps string-width should get an extra parameter to get the new, more
> accurate computation, and get the old, fast computation without this
> parameter.

That's really easy with the last change I made: the option to do that
exists on the C level.  So if there are significant use cases where
people report slowdown, we could expose the option to Lisp.

FWIW, I did measure the speed after the change, and saw only something
like 10% slowdown for strings with composable characters.  Maybe my
tests were skewed, or maybe there are other use cases I didn't think
about.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Lars Ingebrigtsen]

Eli Zaretskii <eliz@gnu.org> writes:

> FWIW, I did measure the speed after the change, and saw only something
> like 10% slowdown for strings with composable characters.  Maybe my
> tests were skewed, or maybe there are other use cases I didn't think
> about.

Yes, Imran's test case here was very synthetic -- Imran, what does the
actual strings in deft where you see these slowdowns look like?  Do you
have some examples you can share?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#48734: 28.0.50; Performance regression in `string-width`?

[Imran Khan]

Lars Ingebrigtsen <larsi@gnus.org> writes:

> Eli Zaretskii <eliz@gnu.org> writes:
>
>> FWIW, I did measure the speed after the change, and saw only something
>> like 10% slowdown for strings with composable characters.  Maybe my
>> tests were skewed, or maybe there are other use cases I didn't think
>> about.
>
> Yes, Imran's test case here was very synthetic -- Imran, what does the
> actual strings in deft where you see these slowdowns look like?  Do you
> have some examples you can share?
>
> -- 
> (domestic pets only, the antidote for overdose, milk.)
>    bloggy blog: http://lars.ingebrigtsen.no

I can't share my personal files for privacy reasons, but I don't think
there is anything remarkable about them, it's just prose so any utf-8
file would do. Let's go with Grimm's Fairy Tales from Project Gutenberg.

https://www.gutenberg.org/files/2591/2591-0.txt

I find that, this is actually fine:

(benchmark-run 1
  (let ((str))
    (with-temp-buffer
      (insert-file-contents "~/2591-0.txt")
      (setq str (buffer-string)))
    (print (string-width str)))) ;;;; 0.5s here, fast enough

But I believe what triggers the hanging behaviour for deft-mode is that
they are doing (among other things) a text transformation of stripping
all vertical whitespace in string to make it look flat:

https://github.com/jrblevin/deft/blob/c4af44827f4257e7619e63abfd22094a29a9ab52/deft.el#L678

Which we can replicate with string-replace:

(benchmark-run 1
  (let ((str))
    (with-temp-buffer
      (insert-file-contents "~/2591-0.txt")
      (setq str (string-replace "\n" " " (buffer-string))))
    (print (string-width str)))) ;;;; beware this now hangs

I waited a minute for it to finish before killing Emacs.

Hope that helps.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Imran Khan <contact@imrankhan.live>
> Cc: 48734@debbugs.gnu.org
> Date: Mon, 31 May 2021 18:36:40 +0600
> 
> But I believe what triggers the hanging behaviour for deft-mode is that
> they are doing (among other things) a text transformation of stripping
> all vertical whitespace in string to make it look flat:
> 
> https://github.com/jrblevin/deft/blob/c4af44827f4257e7619e63abfd22094a29a9ab52/deft.el#L678
> 
> Which we can replicate with string-replace:
> 
> (benchmark-run 1
>   (let ((str))
>     (with-temp-buffer
>       (insert-file-contents "~/2591-0.txt")
>       (setq str (string-replace "\n" " " (buffer-string))))
>     (print (string-width str)))) ;;;; beware this now hangs
> 
> I waited a minute for it to finish before killing Emacs.

Why would someone want to measure the visible width of a 550KB string?
Is that a real-life use case?

But I think I see the reason, and will try to improve this.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> Date: Mon, 31 May 2021 17:28:44 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: larsi@gnus.org, 48734@debbugs.gnu.org
> 
> > (benchmark-run 1
> >   (let ((str))
> >     (with-temp-buffer
> >       (insert-file-contents "~/2591-0.txt")
> >       (setq str (string-replace "\n" " " (buffer-string))))
> >     (print (string-width str)))) ;;;; beware this now hangs
> > 
> > I waited a minute for it to finish before killing Emacs.
> 
> Why would someone want to measure the visible width of a 550KB string?
> Is that a real-life use case?
> 
> But I think I see the reason, and will try to improve this.

Turns out I completely misunderstood how find_automatic_composition
works (because its API is deceptively similar to that of
find_composition, and the crucial differences aren't documented).  So
I will need to restructure the code in lisp_string_width to deal
correctly with automatic compositions; stay tuned.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> Date: Mon, 31 May 2021 21:51:13 +0300
> From: Eli Zaretskii <eliz@gnu.org>
> Cc: 48734@debbugs.gnu.org
> 
> > Date: Mon, 31 May 2021 17:28:44 +0300
> > From: Eli Zaretskii <eliz@gnu.org>
> > Cc: larsi@gnus.org, 48734@debbugs.gnu.org
> > 
> > > (benchmark-run 1
> > >   (let ((str))
> > >     (with-temp-buffer
> > >       (insert-file-contents "~/2591-0.txt")
> > >       (setq str (string-replace "\n" " " (buffer-string))))
> > >     (print (string-width str)))) ;;;; beware this now hangs
> > > 
> > > I waited a minute for it to finish before killing Emacs.
> > 
> > Why would someone want to measure the visible width of a 550KB string?
> > Is that a real-life use case?
> > 
> > But I think I see the reason, and will try to improve this.
> 
> Turns out I completely misunderstood how find_automatic_composition
> works (because its API is deceptively similar to that of
> find_composition, and the crucial differences aren't documented).  So
> I will need to restructure the code in lisp_string_width to deal
> correctly with automatic compositions; stay tuned.

Eventually, I found a way of fixing lisp_string_width without
restructuring, so the above test case, however unrealistic, now works
reasonably fast.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Imran Khan]

Eli Zaretskii <eliz@gnu.org> writes:

>> Date: Mon, 31 May 2021 21:51:13 +0300
>> From: Eli Zaretskii <eliz@gnu.org>
>> Cc: 48734@debbugs.gnu.org
>> 
>> > Date: Mon, 31 May 2021 17:28:44 +0300
>> > From: Eli Zaretskii <eliz@gnu.org>
>> > Cc: larsi@gnus.org, 48734@debbugs.gnu.org
>> > 
>> > > (benchmark-run 1
>> > >   (let ((str))
>> > >     (with-temp-buffer
>> > >       (insert-file-contents "~/2591-0.txt")
>> > >       (setq str (string-replace "\n" " " (buffer-string))))
>> > >     (print (string-width str)))) ;;;; beware this now hangs
>> > > 
>> > > I waited a minute for it to finish before killing Emacs.
>> > 
>> > Why would someone want to measure the visible width of a 550KB string?
>> > Is that a real-life use case?
>> > 
>> > But I think I see the reason, and will try to improve this.
>> 
>> Turns out I completely misunderstood how find_automatic_composition
>> works (because its API is deceptively similar to that of
>> find_composition, and the crucial differences aren't documented).  So
>> I will need to restructure the code in lisp_string_width to deal
>> correctly with automatic compositions; stay tuned.
>
> Eventually, I found a way of fixing lisp_string_width without
> restructuring, so the above test case, however unrealistic, now works
> reasonably fast.

I have tested and can confirm it works and solves my issues with
deft-mode. Thanks a lot Eli, I am grateful for all your work.

bug#48734: 28.0.50; Performance regression in `string-width`?

[Eli Zaretskii]

> From: Imran Khan <contact@imrankhan.live>
> Cc: larsi@gnus.org, 48734@debbugs.gnu.org
> Date: Sat, 05 Jun 2021 21:25:08 +0600
> 
> > Eventually, I found a way of fixing lisp_string_width without
> > restructuring, so the above test case, however unrealistic, now works
> > reasonably fast.
> 
> I have tested and can confirm it works and solves my issues with
> deft-mode. Thanks a lot Eli, I am grateful for all your work.

Thanks for testing, I'm therefore closing this bug.