From c27e1efb61c545f36c450ef60862df9251d239a4 Mon Sep 17 00:00:00 2001 From: Takashi Iwai Date: Fri, 10 Jun 2022 08:45:37 +0200 Subject: ALSA: control: Use xarray for faster lookups The control elements are managed in a single linked list and we traverse the whole list for matching each numid or ctl id per every inquiry of a control element. This is OK-ish for a small number of elements but obviously it doesn't scale. Especially the matching with the ctl id takes time because it checks each field of the snd_ctl_id element, e.g. the name string is matched with strcmp(). This patch adds the hash tables with Xarray for improving the lookup speed of a control element. There are two xarray tables added to the card; one for numid and another for ctl id. For the numid, we use the numid as the index, while for the ctl id, we calculate a hash key. The lookup is done via a single xa_load() execution. As long as the given control element is found on the Xarray table, that's fine, we can give back a quick lookup result. The problem is when no entry hits on the table, and for this case, we have a slight optimization. Namely, the driver checks whether we had a collision on Xarray table, and do a fallback search (linear lookup of the full entries) only if a hash key collision happened beforehand. So, in theory, the inquiry for a non-existing element might take still time even with this patch in a worst case, but this must be pretty rare. The feature is enabled via CONFIG_SND_CTL_FAST_LOOKUP, which is turned on as default. For simplicity, the option can be turned off only when CONFIG_EXPERT is set ("You are expert? Then you manage 1000 knobs"). Link: https://lore.kernel.org/r/20211028130027.18764-1-tiwai@suse.de Link: https://lore.kernel.org/r/20220609180504.775-1-tiwai@suse.de Link: https://lore.kernel.org/all/cover.1653813866.git.quic_rbankapu@quicinc.com/ Link: https://lore.kernel.org/r/20220610064537.18660-1-tiwai@suse.de Signed-off-by: Takashi Iwai --- include/sound/core.h | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'include/sound') diff --git a/include/sound/core.h b/include/sound/core.h index 6d4cc49584c6..dd28de2343b8 100644 --- a/include/sound/core.h +++ b/include/sound/core.h @@ -14,6 +14,7 @@ #include /* pm_message_t */ #include #include +#include /* number of supported soundcards */ #ifdef CONFIG_SND_DYNAMIC_MINORS @@ -103,6 +104,11 @@ struct snd_card { size_t user_ctl_alloc_size; // current memory allocation by user controls. struct list_head controls; /* all controls for this card */ struct list_head ctl_files; /* active control files */ +#ifdef CONFIG_SND_CTL_FAST_LOOKUP + struct xarray ctl_numids; /* hash table for numids */ + struct xarray ctl_hash; /* hash table for ctl id matching */ + bool ctl_hash_collision; /* ctl_hash collision seen? */ +#endif struct snd_info_entry *proc_root; /* root for soundcard specific files */ struct proc_dir_entry *proc_root_link; /* number link to real id */ -- cgit v1.2.3