Re: Possible inline malloc alternatives: bitmap

[DJ Delorie <dj at redhat dot com>]

> These two are wasted work

Please do not refer to someone else's efforts as "wasted" until you
understand why those efforts were made, and how they're being used.  The
trace/simulate code allowed us to benchmark a customer's application
where we had no access to said application, it ran in an environment
where it interacted with many other applications and systems, and over
the course of a few days generated a few terabytes of trace.  We were
able to use that trace to reproduce the performance issue and solve it.
We've also used the trace/simulate code to validate tcache's
performance, which was confirmed in real-world tests later.  They are
not "wasted" work even if they aren't the right tool for your particular
needs.

Of course, you also need to understand what the benchmark benchmarks.
The trace simulator doesn't benchmark printf or strcpy, just the malloc
API.  Likewise, as we have no way of capturing actual memory
read/writes, we have no way of simulating them.  This is why we have
separate microbenchmarks in glibc, although microbenchmarks are poor
reasons to change a general-purpose system allocator.  People care about
things like compilers, browsers, and databases, not microbenchmarks.  So
while you can write a microbenchmark that shows a 400% improvement in
malloc speed, whether that translates to real-world performance
improvements or not still needs to be determined.

I'm not trying to discourage you from improving malloc here, of course.
A change that improves a microbenchmark has a good chance of improving
whole system performance also.  We just need a way to *prove it* by
reliably (and automatically) comparing "apples to apples" at a level and
scale that's appropriate for a general-purpose system allocator like
glibc's malloc, and the trace simulator is the best tool we can come up
with at this time, to serve that purpose.  So please do submit patches
that improve malloc, but understand that we'll expect statistically
robust comparisons with both microbenchmarks, and the simulator[*]
running available workloads, to demonstrate that your patch doesn't have
unexpected negative impacts in applications our users care about.

[*] All workloads, with and without your patch, showing both time and
    rss usage, averaged across many runs, etc...

> as any relation to actual performance is purely coincidental.

*Any* benchmarks are statistical in nature, and how well they correspond
to real-world performance needs to be understood before using said
benchmarks.  That in no way means they're "coincidental".  Even running
the real app once is only statistically related to its performance on
average.

> Running a program first with allocator A, then with allocator B and
> comparing total run time is the only way to get accurate results

Which we can do with the simulator, in as much as the workload is
representative of the application's performance.  Note I say
"representative".  Our experience with it is that it's quite close, so
we use it with some confidence that improvements seen in the simulator
will translate to improvements seen in the application.  But as I noted,
benchmarking a *real* program is also only "representative" of its
average performance.  And sometimes, it's not practical to run an
application with different allocators enough times, and consistently
enough, to get reliable numbers.

> Real problem with first two that current code is convoluted mess.

While I agree, its generally a bad idea to start a discussion with "your
code is a mess" when you're talking to the people who (1) wrote that
code, and (2) will ultimately be reviewing your changes to it.  We try
our best to be fair, but we're only human.

> For different representations of small allocations its easy to bound
> space usage with tunable of maximal number of pages for these. When no
> page is available it will just do allocation from heap. This would be
> easy to add with clean code.

I look forward to seeing your patch :-)