Search does not perform well with 65 million lines of input #714

awal commented 2025年12月07日 22:17:00 +01:00

Fuzzel Version

fuzzel version: 1.13.1 +cairo +png +svg(librsvg) -assertions

Compositor Version

sway version 1.11

Distribution

Arch Linux

Fuzzel config

default/empty

Description of Bug and Steps to Reproduce

$ wget 'https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles.gz'
$ gunzip enwiki-latest-all-titles.gz
$ fuzzel --dmenu < enwiki-latest-all-titles

Try to search for "simply the best".

Expectation:

fuzzel shows the following wiki titles (as of this writing):

0	Dutch_Idol_Simply_the_Best
0	Dutch_idol_simply_the_best
0	Simply_The_Best
0	Simply_The_Best_(Art_Garfunkel_album)
0	Simply_The_Best_(Crystal_Lewis_album)
0	Simply_The_Best_(disambiguation)
0	Simply_the_Best
0	Simply_the_Best_(Art_Garfunkel_album)
0	Simply_the_Best_(Black_Eyed_Peas,_Anitta,_and_El_Alfa_song)
0	Simply_the_Best_(Black_Eyed_Peas,_Anitta_and_El_Alfa_song)

Current result:

fuzzel gets stuck and doesn't show anything for a long time.

Behavior of other programs:

rofi -dmenu can sort of handle it, but not too well. fzf handles this almost perfectly. dmenu is a bit sluggish (specially to start) but also shows adequate results.

Relevant logs, stacktraces, etc.

No response

### Fuzzel Version fuzzel version: 1.13.1 +cairo +png +svg(librsvg) -assertions ### Compositor Version sway version 1.11 ### Distribution Arch Linux ### Fuzzel config ```ini default/empty ``` ### Description of Bug and Steps to Reproduce ``` $ wget 'https://dumps.wikimedia.org/enwiki/latest/enwiki-latest-all-titles.gz' $ gunzip enwiki-latest-all-titles.gz $ fuzzel --dmenu < enwiki-latest-all-titles ``` Try to search for "simply the best". Expectation: fuzzel shows the following wiki titles (as of this writing): ``` 0 Dutch_Idol_Simply_the_Best 0 Dutch_idol_simply_the_best 0 Simply_The_Best 0 Simply_The_Best_(Art_Garfunkel_album) 0 Simply_The_Best_(Crystal_Lewis_album) 0 Simply_The_Best_(disambiguation) 0 Simply_the_Best 0 Simply_the_Best_(Art_Garfunkel_album) 0 Simply_the_Best_(Black_Eyed_Peas,_Anitta,_and_El_Alfa_song) 0 Simply_the_Best_(Black_Eyed_Peas,_Anitta_and_El_Alfa_song) ``` Current result: fuzzel gets stuck and doesn't show anything for a long time. Behavior of other programs: `rofi -dmenu` can sort of handle it, but not too well. `fzf` handles this almost perfectly. `dmenu` is a bit sluggish (specially to start) but also shows adequate results. ### Relevant logs, stacktraces, etc. _No response_

markstos commented 2025年12月08日 14:10:56 +01:00

To add more context: This input file has about 65 million lines.

You can see how fast Fuzzel is loading them by adding the --counter option. Both fzf and Rofi have an option like that as well, for easier comparison. I reproduced the what the @awal said that fzf is the fastest, loading all 65 million rows in about 5 seconds, Rofi was next, then Fuzzel.

Although I think Fuzzel's rate of loading > 100,000 lines per second will good enough for >99% of use-cases, if @dnkl or someone else what's try to improve performance further to match Rofi or fzf-- enjoy!

Some observations:

• Fzf used more than 5 GB of memory to load this data set. Anyone wanting to live-filter 65 million data set quickly like this is going to need plenty of RAM.
• Fuzzel used ~5 GB of memory after loading "only" about 10 million rows, suggesting it's about 10x less efficient with memory than Fzf.
• Fuzzel was visibly slowing down with number of lines that were loaded. Fzf did not exhibit that behavior, zooming straight through the full 65m rows.

To add more context: This input file has about 65 million lines. You can see how fast Fuzzel is loading them by adding the --counter option. Both fzf and Rofi have an option like that as well, for easier comparison. I reproduced the what the @awal said that fzf is the fastest, loading all 65 million rows in about 5 seconds, Rofi was next, then Fuzzel. Although I think Fuzzel's rate of loading > 100,000 lines per second will good enough for >99% of use-cases, if @dnkl or someone else what's try to improve performance further to match Rofi or fzf-- enjoy! Some observations: * Fzf used more than 5 GB of memory to load this data set. Anyone wanting to live-filter 65 million data set quickly like this is going to need plenty of RAM. * Fuzzel used ~5 GB of memory after loading "only" about 10 million rows, suggesting it's about 10x less efficient with memory than Fzf. * Fuzzel was visibly slowing down with number of lines that were loaded. Fzf did not exhibit that behavior, zooming straight through the full 65m rows.

dnkl commented 2026年05月14日 08:05:26 +02:00

Since fuzzel is primarily a .desktop launcher, each loaded entry contains a lot more meta data than in fzf. Not everything in the .desktop file, but certainly more than "just" the name.

dmenu mode is built on top of this, and obviooiusly uses the same struct to store dmenu entries. While not all entries in the struct is used in dmenu mode, it still uses the same amount of memory as in desktop launcher mode. Because of this, fuzzel will always use more memory than fzf. Fuzzel also supports searching in things not visible in the list (things like keywords, comments etc from the .desktop file - see the --fields option). Because of this, fuzzel will likely always be somewhat slower than fzf.

Now, we do automatically disable all but the "name" field in dmenu mode, but a) the larger data memory footprint is likely making it slower to search due to more cache misses, compared to fzf.

And b) the search/match code is larger (again, since it can match more data/fields than fzf), meaning fuzzel's i-cache behavior is likely worse than fzf's.

Comparing fuzzel, a graphical application mainly intended to launch .desktop files, with fzf, a text-only, "dmenu" first application, isn't really fair. That said, we're always open to improving performance. But don't expect it to match fzf for extreme data sets.

Since fuzzel is primarily a `.desktop` launcher, each loaded entry contains **a lot** more meta data than in fzf. Not everything in the `.desktop` file, but certainly more than "just" the name. dmenu mode is built on top of this, and obviooiusly uses the same struct to store dmenu entries. While not all entries in the struct is used in dmenu mode, it still uses the same amount of memory as in desktop launcher mode. Because of this, fuzzel **will always** use more memory than fzf. Fuzzel also supports searching in things not visible in the list (things like keywords, comments etc from the `.desktop` file - see the `--fields` option). Because of this, fuzzel will likely always be somewhat slower than fzf. Now, we do automatically disable all but the "name" field in dmenu mode, but a) the larger data memory footprint is likely making it slower to search due to more cache misses, compared to fzf. And b) the search/match **code** is larger (again, since it _can_ match more data/fields than fzf), meaning fuzzel's i-cache behavior is likely worse than fzf's. Comparing fuzzel, a graphical application mainly intended to launch `.desktop` files, with fzf, a text-only, "dmenu" first application, isn't really fair. That said, we're always open to improving performance. But don't expect it to match fzf for extreme data sets.