[alsa-devel] [PATCH 2/2] ASoC: dapm: Add cache to speed up adding of routes

[Mike Looijmans]

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 at topicproducts.com
Website: www.topicproducts.com

Please consider the environment before printing this e-mail