Page MenuHomePhabricator

focus manager is list lookup heavy
Closed, ResolvedPublic


efl_ui_focus_manager_calc.c in dirty_add performs a lot of list searches that end in failure on potentially long lists. It's trying to remove list items that are frequently not there. Seems like this could made more efficient.

Mhmm do you have real performance numbers on that ? Not filtering out the doubles just makes the list bigger and bigger ...

zmike added a subscriber: zmike.Jun 20 2018, 1:01 PM

I think the point is that there are methods of speeding up the list operations, e.g., not using Eina_List when you need O(1) time.

Sure, in the pathologically gruesome example in T6580, in a run that generates 111 frames that code generates 5985 full list walks that fail to find an item. The lists being walked are generally between 50 and 100 items long.

If it's just something as simple as having a bool on_list = EINA_TRUE to track this instead of doing O(n) lookups, it would be worthwhile.

Similarly, line 260ish the eina_list_remove() in node_item_free() is doing long walks - can this be an inlist with its much cheaper removals?

Yeah, i can add such a field, or feel free to add it yourself :)

I'll give it a shot and add you as reviewer.

@bu5hm4n any reason to not just use a hash?

zmike edited projects, added Restricted Project; removed efl.Jun 22 2018, 2:26 PM
zmike triaged this task as High priority.

@ManMower is there anything else you want to do here ?

I'll run my checks again as soon as I can and see if this is still heavier than necessary. Suspect moving to an inlist or a hash will be quite beneficial.

The king of bogus list abuse is now efl_ui_focus_composition.c's _state_apply() which appears to be doing list searches on both line 45 and line 60 on potentially large lists.

Looks like in current runs of the previously mentioned test we're seeing 1276 calls to _state_apply() that hit the list walks, 110 of which take over 1ms in duration, and 1 outlier of 15+

The total time contribution of these list walks is about 195ms over 52 rendered frames. best case for 52 frames would be 832ms, so 195/832 is a pretty big deal.

Another thing to check into here, node_item_free() ends up doing long walks for pd->dirty= eina_list_remove(pd->dirty, item)

Feels like pd->dirty should be an inlist?

With the latest patches, pressure on the dirty stuff is reduced a lot. I think we can get rid of this one here :)

ManMower closed this task as Resolved.Nov 26 2018, 12:42 PM

Yep, looks waaaay better. elementary's list activity is a drop in the bucket now, as far as I can tell.