[DTrace-devel] [PATCH 6/7] htab reduction: symtab

[Eugene Loh]

On 10/13/21 10:06 AM, Nick Alcock wrote:
> On 11 Oct 2021, Eugene Loh uttered the following:
>
>> On 10/5/21 9:38 AM, Nick Alcock wrote:
>>> The symtab is a major performance sink.  The symtabs in a running DTrace
>>> vary from tiny (most modules) to huge (20,000+ entries in the vmlinux
>>> symtab), but all of them are stuffed into fixed-size htabs of size 211,
>>> leading to hash chains hundreds long.  Combine that with the exponential
>> I'm not familiar with this.  In what way is it exponential?
> We do a name lookup for every symbol extracted from the core kernel to
> figure out what module it's in: see dt_prov_fbt.c:populate(). Then, for
> each of those, we walk across every module and do a symtab lookup.
>
> That's O(n^2), or O(nm) if you prefer
Which is to say, "not exponential."  So strike or replace "exponential."