[DTrace-devel] [PATCH REVIEW 0/7] hashtab cleanups and corresponding speedups

[Nick Alcock]

This series dumps a bunch of handrolled hash tables in favour of the
expanding dt_htab (though some handrolled hashtabs are still there: these
are mostly the easy ones).  All these hash tables are the same size,
_dtrace_strbuckets, i.e. 211 buckets: given that many of them store many
thousands of entries, this was not good for performance.

The symbol lookup machinery had worse performance problems: we were doing
linear searches over modules and hashtab lookups (in horribly mis-sized hash
tables) in each one, and because of the way fbt population works we were
doing this tens of thousands of times per dtrace invocation.  Fixing this to
do a single htab lookup per name lookup speeds things up really quite a lot
(DTrace startup time drops by about 66%, and make check runtime falls by
15--20 minutes). Plus the code is *much* easier to follow.

We throw out a lot of symtab-specific complexity: purging of duplicate
symbols (which was necessary because they'd disrupt the hash table, even
though they were very rare and doing the duplicate elimination was quite
expensive), separate tracking of names for packed and nonpacked symtabs
(adding complexity to every lookup for the sake of saving *one line* in
the symtab packing code), and more.

One facility is added that isn't yet used, dt_htab_insert_unique, simply
because I was using it in an earlier version of the patch series and it
feels like the sort of thing that's likely to be quite useful regardless
("add only if not already present").

The last (trivial) commit in this series is kind of unrelated but I needed
it to test the rest: a tiny fix to the module code that causes it to not
skip out-of-tree modules merely because they happen to be gz/xz-compressed.

Nick Alcock (7):
  htab reduction: kernpath
  htab reduction: providers
  htab: add dt_htab_insert_unique
  htab: add dt_htab_purge to purge an htab rapidly
  htab reduction: modules
  htab reduction: symtab
  modules: support .gz and .xz-compressed modules

 cmd/ctf_module_dump.c        |   6 +-
 libdtrace/dt_htab.c          |  45 ++++++-
 libdtrace/dt_htab.h          |   2 +
 libdtrace/dt_impl.h          |  15 +--
 libdtrace/dt_kernel_module.c |  87 ++++++++-----
 libdtrace/dt_module.c        | 129 +++++++++++++------
 libdtrace/dt_module.h        |   1 +
 libdtrace/dt_open.c          |  20 +--
 libdtrace/dt_provider.c      |  62 +++++----
 libdtrace/dt_provider.h      |   2 +-
 libdtrace/dt_symtab.c        | 241 +++++++++++++++--------------------
 libdtrace/dt_symtab.h        |  23 ++--
 12 files changed, 361 insertions(+), 272 deletions(-)

-- 
2.33.0.256.gb827f06fa9