Page MenuHomePhabricator

evas: Make clipee list removal O(1)
Needs ReviewPublic

Authored by ManMower on Jan 10 2019, 8:18 AM.

Details

Reviewers
cedric
raster
Summary

If we add clippees to the end of the list, we end up with a pointer to
their list entry. If we store that we can use it for O(1) list removal
later instead of a walk.

Diff Detail

Repository
rEFL core/efl
Branch
clipee_list_O1_remove
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 8748
ManMower created this revision.Jan 10 2019, 8:18 AM

It seems that this patch has no reviewers specified. If you are unsure who can review your patch, please check this wiki page and see if anyone can be added: https://phab.enlightenment.org/w/maintainers_reviewers/

ManMower requested review of this revision.Jan 10 2019, 8:18 AM
ManMower added reviewers: cedric, raster.

Ticket D7471 proposes a new list technique with some compelling cache efficiency and memory usage characteristics. However, one of the things it's not great at is removes, as it has no equivalent to eina_list_remove_list, which is an O(1) list removal.

Clippers were given as an example of a piece of code that needs eina_list_remove(), so I'm providing this as a counterpoint. This is an attempt at justifying my claim that eina_list_remove() shouldn't be in the benchmarks for b-list, since I think many calls can be reduced to eina_list_remove_list with similar code.

Note that the memory consumption for evas objects just increased by a pointer - I think that this could be mitigated by only storing the clipper list entry and getting its data to get the clipper. The clippee list is now the reverse of what it was previously - if this actually mattered then list walks could be performed in reverse. I think in this case it doesn't matter though.

Presented as RFC to see if people think this is reasonable or worthwhile to pursue. Please don't merge.
I haven't actually done much benchmarking to see if the list walks were long, just wanted to share this as a PoC. :)

This is really interesting. I am wondering what the memory impact will really be. We moved clipper into the COW part of Evas_Object as it wasn't used that much. So my guess is that it shouldn't impact memory consumption that much. Still I would be interested to get a memory profile of elementary_test, enlightenment and terminology and see what it says.

Performance wise, I am not sure we have any tests in expedite that would really change. Maybe the first and last frame of the many clip test would be impacted, not sure. Need to revive expedite.

zmike added a subscriber: zmike.EditedJan 10 2019, 11:41 AM

Oh this does indeed seem like it could relate to some of the performance improvements speculated on by @raster in D7471. I wonder how this might impact any potential gains which blist could have provided?

zmike added a subscriber: raster.Jan 10 2019, 11:42 AM