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

[Eric Boesch]

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

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.  With 2 megabytes of data, the standard Mandrake 8.1
alloc()/free() slowed my program down by a factor of 10 as compared to
the same program linked with dlmalloc
(http://g.oswego.edu/dl/html/malloc.html).  (I observed the same
slowdown with Cygwin.)

The program was the Lua language, running a Lua script that
performed an XML transform.  Here's a chart of input size versus
performance.

Approx. input size (kB)   300  600  1200 2400

Runtime, normal (secs)    9.3   24   150  750

Runtime with dlmalloc     9.1   18    35   71

I can provide specifics, including a complete trace of memory
allocation, if need be, but since I'm guessing that this is
well-known behavior, I tried to keep it short.