On 07-05-15 13:22, Lars-Peter Clausen wrote:
On 05/07/2015 12:33 PM, Charles Keepax wrote:
Some CODECs have a significant number of DAPM routes and for each route, when it is added to the card, the entire card widget list must be searched. When adding routes it is very likely, however, that adjacent routes will require adjacent widgets. For example all the routes for a mux are likely added in a block and the sink widget will be the same each time and it is also quite likely that the source widgets are sequential located in the widget list.
This patch adds an optional cache argument to snd_soc_dapm_add_route, if given, this argument will hold the source and sink widgets from the last call to snd_soc_dapm_add_route. A small search of the widget list will be made from those points for both the sink and source. Currently this search only checks both the last widget and the one adjacent to it.
On wm8280 which has approximately 500 widgets and 30000 routes (one of the largest CODECs in mainline), the number of paths that hit the cache is 24000, which significantly improves probe time.
That's crazy! ;)
I wonder if it makes sense to come up with a more machine readable blob format that can be pre-compiled where we don't have to search the widget list each time a route is added. Instead of having it reference the widgets by name use a index that points into an array of widgets. That makes the lookup time O(1).
Storing the names in a btree or similar structure should be a nice balance. That would make name lookups O(log(n)), meaning that it would find a name in 30000 items in about 5 steps.
A hashtable or precompiled "id" would only be viable if the whole table can be calculated at compile time. With many devices being hot-pluggable and creating multiple instances at runtime, I don't really think that'd be feasible - if it were, you might as well let the linker fill in the right pointer and skip the whole searching-on-name thing.
If new entries are being added in ascending order, inserting into the btree is a fast operation as well.
Drawback is that you'll need to store the btree graph in memory so it'll consume a bit more (something like two extra pointers per entry).
...
Kind regards,
Mike Looijmans System Expert
TOPIC Embedded Products Eindhovenseweg 32-C, NL-5683 KH Best Postbus 440, NL-5680 AK Best Telefoon: +31 (0) 499 33 69 79 Telefax: +31 (0) 499 33 69 70 E-mail: mike.looijmans@topicproducts.com Website: www.topicproducts.com
Please consider the environment before printing this e-mail