Re: a case of awful malloc/free performance in glibc2.2.4

[Wolfram Gloger]

> This is probably well known, and fixed for all I know, but just in
> case it isn't:

Sorry for the late reply, bug-glibc is hardly readable these days.

> I encountered a more-or-less real-life application (one that was never
> intended as an allocation benchmark) where the glibc alloc/free
> package appeared to be unboundedly slow.  That is, the larger my
> program's input, the slower the alloc/free package became -- I got
> apparently quadratic performance from a program that should have run
> in linear time.

It is known that such cases exist; malloc and or free can actually
perform linearly with heap size, although these cases should be rare
in practice.  glibc-2.3 will include a new malloc version that may (or
may not) work better in your case.

However, in general, the existence of such cases is unavoidable unless
you abandon the "best fit" allocation strategy completely.  There are
good arguments in the literature for at least trying hard to come
close to "best fit".

Basically, if you have an implementation that is _always_ faster than
linear in heap size, you can be sure it is _not_ best fit, so it is
tuned for speed rather than memory efficiency.  glibc's implementation
generally favours memory efficiency, although it is by no means slow
in the vast majority of cases.

Regards,
Wolfram.