~scoopta/wofi#35: 
High CPU usage for long lists (~5000 lines)

Hi, I've noticed that for long lists (around 5000 lines) wofi have a high CPU usage for few seconds. In particular, when feeding wofi --dmenu (both with and without icons allowed) one of the CPUs bounce to 100% for around 7 seconds. For even longer lists, typing become not possible and wofi become soon irresponsive.

This do not seem to happen with rofi.

Status
REPORTED
Submitter
~cinghiopinghio
Assigned to
Submitted
5 years ago
Updated
3 years ago
Labels
bug

~scoopta 5 years ago

Might I ask what use case dealing with such large lists is needed for? Also performance on a 7K line file seems to be mostly fine. It's a bit slow towards the end of loading but quickly bounces back and regains full performance after everything loads. Searching appears to be perfectly fine for the contains search once everything is done loading. Fuzzy search is another matter entirely and is pretty painful. I can look into a faster fuzzy search algorithm however there's still the issue of actually loading all of this stuff which is much harder to solve. GTK requires all GUI tasks to be done on a single thread and that largely limits how quickly wofi can get stuff created. I can try to mitigate the lag however most of this is GTK. Wofi doesn't do anything during load that is sensitive to the number of items that have been inserted, this means that GTK is responsible for the progressive slow down during load.

~cinghiopinghio 5 years ago

I'm feeding all document/files/codes in my file-system to have a fast way to access them (through fd).

Just noob question: If the problem is gtk based, is it possible to build the gtk widgets only when they need to be displayed? I understand that re-implementing this would require quite a lot of refactoring.

~cloudninja 5 years ago

He basically already does this. The issue is when adding a new widget to the list, it takes increasingly more time, the more widgets there are. So say it takes N milliseconds to add the first widget, then it takes N+1 for the second, N+2 for the third, etc. etc.

Unfortunately your use case is a little niche. However, you may be able to make it faster by instead of giving it every single file, script it so that folders are their own entry that open a new wofi instance when selected. That should in theory cut down on time.

~scoopta 5 years ago

You bring up an interesting idea but again that would require significant rewriting to accomplish. Ultimately I'm not sure this is a super high priority for me to address. I'm not saying I won't mess with trying to find a faster way to get things loaded but it might take a bit for this to get solved, if ever.

~ernierasta 5 years ago

I also have 100% cpu usage. I do nothing special, just run wofi -S run. If I use wofi -S drun it is ok. Unfortunately this is unusable. I am not sure how many entries are there, but it is quite normal Void Linux system.

~ernierasta 5 years ago

I forgot to mention, that behavior is the same for packaged version and compiled current master.

~scoopta 5 years ago

Hmmm, alright I'll try to see where I can optimize the load code, I have an idea as to what causes this but I don't have an idea for fixing it yet

~scoopta 5 years ago

4d495941b8fe should fix most if not all performance issues, it should definitely fix run, in my testing it also significantly speeds up very large dmenu setups. Could you guys check and get back to me. I won't close this issue until I know it's good

~ernierasta 5 years ago

Thank you for improvements! From what I see on my ntb(previous test was on my desktop PC, will test it later), when I run wofi -S run:

  • it is responsive now, on my dt PC it was laggy (will test it there later),
  • I still see 100% CPU utilization of one CPU core. What is happening? I am even not searching, just opening wofi in run mode occupy CPU until wofi is closed.

~scoopta 5 years ago

It shouldn't be pinned until closed but it'll probably be pinned for a little bit. It has to crawl every directory in your $PATH searching for executables. Once it finds and adds every executable to the scroll area it should drop to basically nothing. drun is faster because it only looks for desktop files and there's always substantially less of those on your system. I'm not sure what kind of CPUs are in your PCs but I think you're the first person to have run pin something like this, on my system run mode pins a core for maybe 2-3 seconds after wofi is opened before dropping to 0. I can look to optimize further but I think I've sort of made all the easy "stop doing stupid stuff" optimizations.

~cinghiopinghio 5 years ago

Great improovements.

as ~ernierasta say, the filtering is now responsive, I can write and erase chars without noticeable lags. I also notice that 1 core is running at 100% for 20+ seconds on lists with 5000+ lines (this is similar in size to the list of commands in wofi --show run). Notice that I'm using a quite powerful laptop with a i7-6700HQ (8) @ 3.5 GHz.

My guess is that during that time wofi is preparing the widgets to be shown, in fact some of them are asynchronously appended during this process. For example if I run wofi --show run and write right away gimp, at the beginning the list is short and does not contain gimp itself. After around 10 seconds I can see other items appearing and eventually even gimp will be appended.

~cinghiopinghio 5 years ago

I dont't think the crawl is the bottleneck since if I supply the content of a text file of around 5000 lines and search for last line, I got the same waiting time.

~scoopta 5 years ago

When wofi was first in development it originally generated the list all at once however this would cause unacceptable amounts of delay before the window even opened. To combat this wofi started async loading the list while the window was open and then caching was added to remove delay from things used frequently as they're added first. So yes, wofi is doing it async while the window is open and it's doing it on the GTK idle time. That is wofi's list insertion is done when the GTK thread has nothing better to do as determined by GTK. Wofi inserts one entry at a time before returning control to GTK, I might be able to further improve load times by batching inserts but I have to be careful with that as I could easily lag the UI.

~cinghiopinghio 5 years ago

I guess one could reorder the list of items being prepared by GTK given the user input at that time in order to get interesting results as soon as possible.

I don't know if this is a lot of work given wofi state, I don't know if this is even possible from the GTK point of view.

~scoopta 5 years ago

Hmm, that's an interesting idea, might have to shift some stuff around but it might be obtainable, not sure but it's an interesting idea. Also you were right in saying it's not the crawl, couldn't be. I forgot that with the new architecture the crawl is 100% finished by the time we add the first entry to the list, even the cache. That's definitely not the slow part. I'll have to use a different data structure for storing the list of entries to be added but if I were to use a map I might actually be able to search the entries and if none are found then search that map and do an immediate add of whatever the user is looking for at the time. I'll need a more efficient map than I've got but GLib has that, it honestly shouldn't even take a whole lot of redesign either. I'll play with this over the next few days, if I come up with something I like it'll probably be pushed some time this weekend assuming I can get it working.

~cinghiopinghio REPORTED FIXED 5 years ago

crazy idea:

Why not rendering (preparing the gtk widget) only for those few items that need to be shown?

~cinghiopinghio FIXED REPORTED 5 years ago

~cinghiopinghio 5 years ago

Sorry, accidentally clicked on solved

~scoopta 5 years ago

The problem with that is I get into the mess of trying to figure out what needs to be shown when the user is scrolling, it's easy for searching but for scrolling it gets more complicated than it might be worth. It might actually be easier to do once #41 is implemented but I feel like loading all of them ASAP and then loading search results as needed is a better solution. I'm also not too worried about pinning a core at 100% till everything is loaded as long as wofi stays responsive. Maybe I'll look into it but I think the other idea is better.

~mcoffin 5 years ago

I am also seeing this issue right now, but even on --show run, since my compgen -c | sort -u | wc -l list is ~5200 entries. I'll take a look around and see what I think could be done as well.

~scoopta 5 years ago

On your systems is /bin a symlink to /usr/bin? I forgot that run defaults to showing everything in your path including duplicates and I'm wondering if I should change that. It won't increase the performance of wofi as a whole but it will reduce the number of entries generated by run. It's not exactly a fix so much as a mitigation, there's always been an option to disable duplicates it's just off by default. On my system(debian sid) changing that option drops the run load time from 2.5s to under 1s. Again, not a fix but it might be worth while to change that default. I'm still trying to come up with a good way to load stuff as needed. My original idea won't work as it would only be feasible with contains matching and only if you searched for the beginning of the entry, not something in the middle which is admittedly most peoples use but I'm not sure it's a good fix if it's limited to that use.

~mcoffin 5 years ago

For me, yes. /bin is symlinked to /usr/bin.

It might be worth entirely skipping directories that are symlinked to another entry in $PATH.

On 1/28/20 2:48 PM, ~scoopta wrote:

On your systems is /bin a symlink to /usr/bin? I forgot that run defaults to showing everything in your path including duplicates and I'm wondering if I should change that. It won't increase the performance of wofi as a whole but it will reduce the number of entries generated by run. It's not exactly a fix so much as a mitigation, there's always been an option to disable duplicates it's just off by default. On my system(debian sid) changing that option drops the run load time from 2.5s to under 1s. Again, not a fix but it might be worth while to change that default. I'm still trying to come up with a good way to load stuff as needed. My original idea won't work as it would only be feasible with contains matching and only if you searched for the beginning of the entry, not something in the middle which is admittedly most peoples use but I'm not sure it's a good fix if it's limited to that use.

~scoopta 5 years ago

That's actually a much better idea

~scoopta 5 years ago

0fea34654a97 removes path duplication as a whole. Both symlinks and things like PATH=/usr/bin:/usr/bin if for some reason anyone has done that.

~cinghiopinghio 5 years ago

Also in my case bin is a symlink to /usr/bin. On top of that there are a lot of other symlinks such python -> python3 -> python3.8 or gimp -> gimp-2.10.

~mcoffin 5 years ago

On 1/28/20 6:47 PM, ~scoopta wrote:

0fea34654a97 removes path duplication as a whole.

This has largely resolved the issue for me, though I did have to submit a patch to fix a segfault in that particular changeset

~scoopta 5 years ago

Just making sure you got my reply to your patch, you have gmail and the gmail spam filter likes to drop mail.

~mcoffin 5 years ago

On 1/29/20 1:49 PM, ~scoopta wrote:

Just making sure you got my reply to your patch, you have gmail and the gmail spam filter likes to drop mail.

That it does. It was in my spam. I'll fix up the patch. Thanks!

I'm probably due for a new email account at some point, but that seems like a pain to update everywhere.

~ernierasta 5 years ago

Just wanted to confirm, that it looks much better now, than it was before. There is still 100% CPU load on one core (rofi doesn't do that), but on my notebook it is now only few seconds (2-3 seconds), which is completely ok.

Thank you for changes and great menu for my sway!

~scoopta 5 years ago

I'm honestly not too worried about the high CPU usage as long as wofi stays responsive. There's only two ways to lower the CPU usage, slow down load times or make them so fast it never gets noticed. I'm not going to do the former and I'm not sure I can accomplish the latter so as long as the CPU usage drops when loading is done I consider that to be the intended behavior. I do want to try to further optimize the load code but I'm happy it's at least in a state where everyone seems to get decent performance out of it.

~ernierasta 5 years ago

That is reasonable, thanks for elaborating.

~mcoffin 4 years ago

On 2/4/20 3:07 AM, ~ernierasta wrote:

That is reasonable

It's especially reasonable considering the other path to fixing this would be to manually rotate the items into and out of the GTK list as you scroll. (i.e. keep the full list in memory, but only tell GTK about part of it at any given time.

With the way the GTK flowbox and listbox are set up, the inserts are always going to get longer the more items you have.

~geo25rey closed duplicate ticket #131 4 years ago

~scoopta closed duplicate ticket #131 4 years ago

~scoopta referenced this from #149 4 years ago

~cab 3 years ago*

Up, still very much an issue. Using

wofi --show run,drun --matching=fuzzy

is quite painful

upd: Apparently, filter_rate doesn't work as a proper debounce, still executing update on a timer even if new updates occurred. That makes search execute more frequently, and it appears sluggish.

~mcoffin 3 years ago

Up, still very much an issue.

Sadly, I can confirm that despite that patch helping, I still do notice this quite frequently as well.

Register here or Log in to comment, or comment via email.