Delay for certain dmenu scripts to appear about dmenu-flexipatch

[bakkeby]

Weird, this is slow even if you check out a bare dmenu from suckless.org.

Stepping backwards one commit at a time it looks like the delay introduced with this commit:
https://git.suckless.org/dmenu/commit/77526f756e23e362081ac807521f901f2e5cd5e6.html

[JimPix1]

Hah, ironic that the commit is meant to make startup fastup when it seem's to do the polar opposite here

[bakkeby]

Actually it is as fast if not faster than the original if I remove all the emoji characters from the file.

The reason it is slow (taking ~5 seconds to load) is because it detects that it is using a Xft font with color glyphs which will result in BadLength errors - hence it will open and close the font many times.

I'd assume the behaviour would be different if you use the COLOR_EMOJI_PATCH. I can test that tomorrow.

[JimPix1]

Oh I do use the color emoji patch! It wouldn't look great without it. I also have JoyPixels set as a secondary font to load them so I'm at a loss

[bakkeby]

In the meantime you could check out the latest version of dmenu-flexipatch and roll back that one commit.

$ git revert 761bc7939f7ff32a1a95d4c2150dc488806b9823

[JimPix1]

That command wouldn't work for me but I manually changed the code and it's perfect, thanks!

[bakkeby]

The aim of the game is to work out the width of the dmenu input prompt, which is at maximum a third of the available space. The input prompt width is determined by the longest / widest of the input options.

At the bottom of the comment for commit https://git.suckless.org/dmenu/commit/77526f756e23e362081ac807521f901f2e5cd5e6.html we have that:

additionally this will take fallback fonts into account compared to the previous version, so it's not only more performant but also more correct.

The way it worked before (and why it was faster in this particular case) was that for every line / item it would calculate the width of the string using the primary font only, regardless of whether that font had all the glyphs used in the string and as such the width could be wrong.

The changes that was introduced was that the width of each of the options will now be correctly calculated taking fallback fonts into account.

You said that you have JoyPixels as a fallback font so I would assume that you are using something sensible like Noto Color Emoji as your primary font (we are looking at emojis after all). So you might have a fonts config like this:

static const char *fonts[] =
{
	"Noto Color Emoji:size=10",
	"JoyPixels:size=10"
};

The emoji file has 1630 options / lines, and here is the first one:

😀 grinning face

When calculating the width of the this option it will check the first character 😀, find that this glyph exists in the primary font Noto Color Emoji and that the width of that is 18 (as an example).

Then it will check the next character which is a space character, find that hey this glyph does not exist in the Noto Color Emoji font, so it will try the JoyPixels font and find that hey this glyph does not exist here either, so it will ask the Xft library to find another font that has the space character. Let's say that it finds DejaVu Sans and it adds that to the list of available fonts. It finds that the width of this glyph is 12 and adds that to the width counter.

Then it will check the next character which is g, find that hey this glyph does not exist in the Noto Color Emoji font, so it will try the JoyPixels font and find that hey this glyph does not exist here either, so it will try the DejaVu Sans font and it finds the glyph and the width of that glyph is 12 and adds that to the width counter.

In total the emoji file has 31913 characters, 1630 of which are colour emoji characters. One of the reason it is slow (takes half a second to load on my system with the color emoji hack / patch) is that the primary font does not have general ASCII characters and it has to check two other fonts for every character checked.

So if you add a simple font like Sans or Serif that does not have any emojis then that improves on the speed but only by a margin.

static const char *fonts[] =
{
	"Sans:size=10",
	"Noto Color Emoji:size=10",
	"JoyPixels:size=10"
};

(of course most fonts that have common characters are likely to include the copyright (©) and registered (®) symbols so you wouldn't have these displayed with their emoji variants in the dmenu script unless you were to create a bespoke font that does not have the glyphs)

To test this I created an emoji file that was 10000 times bigger having 16300000 lines (options) and 319130000 characters.

This took about 7.5 seconds to load without the commit. With the commit it took a long time (close to 30 minutes).

Comparatively an emoji file that was 1000 times bigger having 1630000 lines (options) and 31913000 characters took:

• 0.80s without the commit and
• 159s with the commit

Comparatively an emoji file that was 100 times bigger having 163000 lines (options) and 3191300 characters took:

• 0.12s without the commit and
• 16s with the commit

Comparatively an emoji file that was 10 times bigger having 16300 lines (options) and 319130 characters took:

• 1.85s with the commit

and finally using the original file having 1630 lines (options) and 31913 characters took:

• 0.35s with the commit

Generally it does seem a lot slower than it was before.

That said the changes do make a lot of difference when the options / lines are so long that they exceed a third of the menu width.

If we don't take the exactness of the dmenu width so seriously then skipping menu items that have a string length (as in number of characters rather than their combined width) that is less than previously tested menu items (as they are likely going to be less wide anyway) then that speeds things up quite dramatically.

Example solution:

diff --git a/dmenu.c b/dmenu.c
index 839f6cc..ec7a6b4 100644
--- a/dmenu.c
+++ b/dmenu.c
@@ -610,6 +610,7 @@ static void
 setup(void)
 {
        int x, y, i, j;
+       int minstrlen = 0, curstrlen = 0;
        unsigned int du, tmp;
        XSetWindowAttributes swa;
        XIM xim;
@@ -675,6 +676,10 @@ setup(void)
        }
        promptw = (prompt && *prompt) ? TEXTW(prompt) - lrpad / 4 : 0;
        for (item = items; item && item->text; ++item) {
+               curstrlen = strlen(item->text);
+               if (curstrlen <= minstrlen)
+                       continue;
+               minstrlen = curstrlen;
                if ((tmp = textw_clamp(item->text, mw/3)) > inputw) {
                        if ((inputw = tmp) == mw/3)
                                break;

The above cuts the load time down to 0.35s for the 1000x test and to 2.80s for the 10000x test.

[bakkeby]

@N-R-K do you have any thoughts on the above? When all the menu items are shorter than a third of dmenu's width then we will inevitably be checking the text width for each and every one of them.

[JimPix1]

Wow, thanks for taking the time to analyze all of that. It must have taken a while.
I think I'll keep the commit reverted for now and wait for a more permanent solution

[bakkeby]

For comparison a similar optimisation for the original code shaved the time from 7.5s to 3s for the 10000x test (still slower than the above).

diff --git a/dmenu.c b/dmenu.c
index 62a9a60..a660311 100644
--- a/dmenu.c
+++ b/dmenu.c
@@ -552,6 +552,7 @@ readstdin(void)
        char buf[sizeof text], *p;
        size_t i, imax = 0, size = 0;
        unsigned int tmpmax = 0;
+       int minstrlen = 0, curstrlen = 0;

        /* read each line from stdin and add it to the item list */
        for (i = 0; fgets(buf, sizeof buf, stdin); i++) {
@@ -563,7 +564,11 @@ readstdin(void)
                if (!(items[i].text = strdup(buf)))
                        die("cannot strdup %zu bytes:", strlen(buf) + 1);
                items[i].out = 0;
-               drw_font_getexts(drw->fonts, buf, strlen(buf), &tmpmax, NULL);
+               curstrlen = strlen(buf);
+               if (curstrlen <= minstrlen)
+                       continue;
+               minstrlen = curstrlen;
+               drw_font_getexts(drw->fonts, buf, curstrlen, &tmpmax, NULL);
                if (tmpmax > inputw) {
                        inputw = tmpmax;
                        imax = i;

Another strategy of only determining the input width based on the first 100 items only made no difference (still above 3 seconds).

diff --git a/dmenu.c b/dmenu.c
index 62a9a60..ede6b6a 100644
--- a/dmenu.c
+++ b/dmenu.c
@@ -552,6 +552,7 @@ readstdin(void)
        char buf[sizeof text], *p;
        size_t i, imax = 0, size = 0;
        unsigned int tmpmax = 0;
+       int num_width_checks = 100;

        /* read each line from stdin and add it to the item list */
        for (i = 0; fgets(buf, sizeof buf, stdin); i++) {
@@ -563,6 +564,9 @@ readstdin(void)
                if (!(items[i].text = strdup(buf)))
                        die("cannot strdup %zu bytes:", strlen(buf) + 1);
                items[i].out = 0;
+               if (!num_width_checks)
+                       continue;
+               --num_width_checks;
                drw_font_getexts(drw->fonts, buf, strlen(buf), &tmpmax, NULL);
                if (tmpmax > inputw) {
                        inputw = tmpmax;

On the other hand simply not calculating the input width gave similar results (it still needs to read and parse 305M of data of course).

[N-R-K]

Hi, thanks for the ping.

diff --git a/dmenu.c b/dmenu.c
index 839f6cc..ec7a6b4 100644
--- a/dmenu.c
+++ b/dmenu.c
@@ -610,6 +610,7 @@ static void
 setup(void)
 {
        int x, y, i, j;
+       int minstrlen = 0, curstrlen = 0;
        unsigned int du, tmp;
        XSetWindowAttributes swa;
        XIM xim;
@@ -675,6 +676,10 @@ setup(void)
        }
        promptw = (prompt && *prompt) ? TEXTW(prompt) - lrpad / 4 : 0;
        for (item = items; item && item->text; ++item) {
+               curstrlen = strlen(item->text);
+               if (curstrlen <= minstrlen)
+                       continue;
+               minstrlen = curstrlen;
                if ((tmp = textw_clamp(item->text, mw/3)) > inputw) {
                        if ((inputw = tmp) == mw/3)
                                break;

This might be faster, but it's also not correct. Unicode has many 0-width chars as well as "control chars" (not sure if that's the official term for them).

So it's possible to have a string be 1000 bytes long but still only have a width of, lets say 12, while another string with 100 bytes has a higher width.

That's more or less why strlen was replaced in 44c7de3, it was incorrectly assuming more bytes == bigger width.

[N-R-K]

Actually it makes no sense to calculate inputw if we're using vertical menu. I've sent a patch that skips inputw calculation when using -l to the hackers list.

For regular menu, we'll have to think of something else.

[N-R-K]

about 97% of the time is spent on XftFontMatch in cases we can't find a glyph. If we can somehow get the width of a unicode codepoint, then we can defer calculating the actual pixel-width, which I think should be much faster than repeatedly calling XftFontMatch.

Attached a patch which uses libutf8-proc to get the width of a codepoint. It's quick and dirty patch just to confirm my hypothesis. It seems to working fine and fixes the performance issue.

But I don't think it's worth it to add a library dependency just for this. At the same time I'm not well versed on unicringe enough to know how difficult it would be to roll it ourselves. Quick search seems to indicate it's not going to be trivial :')

From 7b6d422a6d49bfa472822dfb292eefde78a346a2 Mon Sep 17 00:00:00 2001
From: NRK <[email protected]>
Date: Thu, 28 Apr 2022 13:04:16 +0600
Subject: [PATCH] utf8proc

---
 Makefile |  2 +-
 dmenu.c  | 21 ++++++++++++++++++---
 drw.c    |  2 +-
 3 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/Makefile b/Makefile
index a03a95c..89b5ac7 100644
--- a/Makefile
+++ b/Makefile
@@ -23,7 +23,7 @@ config.h:
 $(OBJ): arg.h config.h config.mk drw.h
 
 dmenu: dmenu.o drw.o util.o
-	$(CC) -o $@ dmenu.o drw.o util.o $(LDFLAGS)
+	$(CC) -o $@ dmenu.o drw.o util.o $(LDFLAGS) -lutf8proc
 
 stest: stest.o
 	$(CC) -o $@ stest.o $(LDFLAGS)
diff --git a/dmenu.c b/dmenu.c
index 8e1c670..f7646a7 100644
--- a/dmenu.c
+++ b/dmenu.c
@@ -606,6 +606,7 @@ run(void)
 	}
 }
 
+#include <utf8proc.h>
 static void
 setup(void)
 {
@@ -617,6 +618,7 @@ setup(void)
 	XWindowAttributes wa;
 	XClassHint ch = {"dmenu", "dmenu"};
 	struct item *item;
+	char *longest = NULL;
 #ifdef XINERAMA
 	XineramaScreenInfo *info;
 	Window pw;
@@ -675,11 +677,24 @@ setup(void)
 	}
 	promptw = (prompt && *prompt) ? TEXTW(prompt) - lrpad / 4 : 0;
 	for (item = items; !lines && item && item->text; ++item) {
-		if ((tmp = textw_clamp(item->text, mw/3)) > inputw) {
-			if ((inputw = tmp) == mw/3)
-				break;
+		extern size_t utf8decode(const char *c, long *u, size_t clen);
+		char *l;
+		int utf8charlen;
+		long utf8codepoint;
+
+		l = item->text; tmp = 0;
+		while (l && *l) {
+			utf8charlen = utf8decode(l, &utf8codepoint, 4);
+			l += utf8charlen;
+			tmp += utf8proc_charwidth(utf8codepoint);
+		}
+
+		if (tmp > inputw) {
+			longest = item->text;
+			inputw = tmp;
 		}
 	}
+	if (lines == 0 && longest) inputw = textw_clamp(longest, mw/3);
 	match();
 
 	/* create menu window */
diff --git a/drw.c b/drw.c
index ced7d37..3f5adc1 100644
--- a/drw.c
+++ b/drw.c
@@ -35,7 +35,7 @@ utf8validate(long *u, size_t i)
 	return i;
 }
 
-static size_t
+size_t
 utf8decode(const char *c, long *u, size_t clen)
 {
 	size_t i, j, len, type;
-- 
2.35.1

[bakkeby]

Yes I am aware that using strlen is not correct as you could have five euro symbols that has a longer bytestring than something else written with single-byte characters.

E.g. this would demonstrate the issue:

$ echo -e "€€€€€\nabracadabra" | dmenu

if you start writing abracadabra then at some point your input will be too long and get the ellipsis added.

I'd assume that whatever shortcut is taken there will always be some kind of edge case where the input width is not 100% accurate.

If you have a million items do you really need to check the length of each and every one of them just to determine the width of the input field? Even if you do random sampling or sampling the first 100 then you can have that the input width may be too small for some of the options (when you need to type them all out), but it may be a reasonable tradeoff that would work in most situations.

[N-R-K]

I personally hold the opinion that the dynamic input width should just be removed entirely and replaced with a config.h option such as

static float input_bar_percent = 0.24f;

which means the input bar will always take 24% of the monitor width no matter what. This could also be adjusted via a cli arg (which is why i didn't make it const).

The question is, is this going to be accepted upstream. I wouldn't be too optimistic about it, though it is probably worth a proposal.

---

Also now that i think about it, the earlier patch i sent with utf8-proc isn't entirely correct either, since I dont think it's taking "grapheme clusters" into account.

[bakkeby]

Yes I would agree with that. The dynamic input width could be offered as a patch for those that need it.

[N-R-K]

Should be fixed on latest dmenu master.¹

Footnotes

1. https://git.suckless.org/dmenu/commit/e1e1de7b3b8399cba90ddca9613f837b2dbef7b9.html. ↩

[JimPix1]

Great to hear
I'll let someone else (maybe Bakkeby) test this as I'll just keep using my current dmenu flexipatch that works fine.
Feel free to close when it's confirmed to be fixed :)

[bakkeby]

I did see that. To be honest I was rather surprised that they'd go for a plain hardcoded 1/3rd of the screen. Thought to wait and see if there was any outcry, but I guess nobody cares :)

[bakkeby]

I removed the input width calculation now leaving it as 1/3rd as per latest master. I'll mark this as closed but let me know if you have any issues.