Re: [hackers] [dmenu] inputw: improve correctness and startup performance || NRK

From: Laslo Hunhold <dev_AT_frign.de>
Date: Fri, 29 Apr 2022 08:11:46 +0200

On Fri, 29 Apr 2022 08:53:38 +0600
NRK <nrk_AT_disroot.org> wrote:

Dear NRK,

> 2. (Incorrectly) assume `more bytes == wider string`, which is not
> correct thanks to unicode.
>
> 3. Try to get the width of the unicode code-point. I've attached a
> quick and dirty patch using `utf8proc_charwidth()` from libutf8-proc.
> The patch was just to confirm my hypothesis and not to be taken
> seriously.
>
> I'm not too well versed on unicode so I cannot tell how difficult
> rolling such a function ourself would be. But some quick searches
> seems to indicate it's not going to be trivial at all, specially if
> we take "grapheme clusters" into account.
>
> So this option is probably getting ruled out.

to keep a long story based on my experience with developing libgrapheme
and intensely working with Unicode short: The char-width-data from the
Unicode consortium cannot be relied on and said consortium has pretty
much given up on this matter and delegated this to font-rendering and
font-shaping implementations. While they still maintain the EAW-tables
(among others), they are nothing more than heuristics that break
horribly in many cases.

> My suggestion here is to just have a consistent input bar width which
> can be configured via config.h and cli arg. So for example:
>
> static float input_bar_percent = 0.24f;
>
> This would make the input bar width always 24% of the monitor width.
> I've attached a patch for this as well. It's simpler and gives a more
> static/predicable ui.

This is definitely the simplest solution in the context of the
following observation that might be a general aspect that could be
looked at:

If N is the number of "choices" passed to dmenu, getting the extent of
each choice pretty much makes the setup O(N). The Landau-constant is
pretty large in this case, especially for a lot of missing glyphs, as
you observed correctly, leading to a noticeable performance loss/delay.

Maybe the general goal should be to make dmenu O(1) in terms of passed
choices, at least until you actually enter any text (and run a search,
which is roughly O(N) for relatively small needle- and
haystack-strings, given each string-matching is of complexity O(n*h) ~
O(1), where n is the needle-length and h is the haystack-length).
In this context one could think of building a suffix-tree/-array for
faster searching, but that's probably overkill.

One solution that comes to mind is that the width is only calculated
"on the fly" using the current matches, so you always are O(1) in terms
of _all_ inputs.

One could also reflect on the necessity of the f-flag: Wouldn't it be
more reasonable to start up quickly, also allow the entering of text
even while dmenu is "waiting" for stdin. It could display a "waiting
for stdin" or something instead of blocking and being irresponsive.
Another way would be to allow searches on the partially-read input of
stdin, but this would be only half-honest. However, say you have a slow
network share and pass, among other things, an ls-output of a folder
in that share, you wouldn't have to wait for it to "load up". So when
there is a good way to indicate "business", a simple linear array of
all inputs could be built "event"-based (using select() or poll()) and
expanded dynamically.

Anyway, I don't have the time right now to cook up a patch, sorry, but
maybe it inspires someone to work on it. Project ideas for all skill
levels:

  1) come up with a good way to indicate "business", i.e. waiting for
     stdin. Given this is rare, it should at best be text, maybe
     displayed right next to the input prompt in a different colour.
  2) implement it, i.e. start up quickly, create the window. lock the
     keyboard before reading stdin and then have a select() or poll()
     on stdin reading in data, optionally indicating business and
     re-running searches when the string expands (but only on the added
     items of course).
  3) calculate width of the results on-the-fly only and use that for
     window dimensions.

_AT_Hiltjo: Before anybody puts time in this, any objections from you as
the maintainer?

With best regards

Laslo
Received on Fri Apr 29 2022 - 08:11:46 CEST