Re: [PATCH userspace v2] libsepol: cache ebitmap cardinality value

[Ondrej Mosnacek <omosnace@redhat.com>]

On Fri, Feb 14, 2020 at 8:51 PM Ondrej Mosnacek <omosnace@redhat.com> wrote:
> On Fri, Feb 14, 2020 at 6:37 PM Stephen Smalley <sds@tycho.nsa.gov> wrote:
> > On 2/13/20 8:39 AM, Ondrej Mosnacek wrote:
> > > According to profiling of semodule -BN, ebitmap_cardinality() is called
> > > quite often and contributes a lot to the total runtime. Cache its result
> > > in the ebitmap struct to reduce this overhead. The cached value is
> > > invalidated on most modifying operations, but ebitmap_cardinality() is
> > > usually called once the ebitmap doesn't change any more.
> > >
> > > After this patch, the time to do 'semodule -BN' on Fedora Rawhide has
> > > decreased from ~14.6s to ~12.4s (2.2s saved).
> > >
> > > Signed-off-by: Ondrej Mosnacek <omosnace@redhat.com>
> >
> > This seems fine but I was wondering how many of the callers of
> > ebitmap_cardinality() actually need anything more than ebitmap_length()?
>
> The caller that calls it the most (>99%) during a 'semodule -B' is
> __cil_should_expand_attribute(), which logically needs the actual
> cardinality. It might be possible to cache the decision directly in
> 'struct cil_typeattribute', but I don't know the CIL code well enough
> to attempt that...

BTW, in case anyone is wondering how I'm getting these numbers/facts -
I use Callgrind [1] to profile a program's run and then analyze it
with KCachegrind [2]. It is a surprisingly nice and easy to use GUI
for analyzing where the program spends most of its time.

Collecting the profile data is as simple as:

LD_BIND_NOW=1 valgrind --tool=callgrind <your_command> <args>...

(The LD_BIND_NOW=1 is to prevent the dynamic linker's lazy binding
from messing with the results.)

Then you can just open the generated "callgrind.out.<pid>" file with
KCachegrind and click around... Note that to see the function names,
you need to compile the program with -g (but you should keep -O2 et
al. to get the same optimized code as an actual build). Alternatively,
Callgrind will also auto-detect and use debug symbols provided by
distributions in their -debug/-debuginfo packages.

Maybe this is common knowledge for most, but perhaps someone here will
be one of today's lucky 10000 :) [3]

[1] https://valgrind.org/docs/manual/cl-manual.html
[2] https://kcachegrind.github.io/html/Home.html
[3] https://xkcd.com/1053/

-- 
Ondrej Mosnacek <omosnace at redhat dot com>
Software Engineer, Security Technologies
Red Hat, Inc.