X-Authentication-Warning: delorie.com: mailnull set sender to djgpp-bounces using -f
From: Ben Pfaff <blp AT cs DOT stanford DOT edu>
Newsgroups: comp.lang.c,comp.os.msdos.djgpp,comp.compilers.lcc
Subject: Re: hash library - interface criticisms
Date: 20 Jan 2002 10:58:21 -0800
Lines: 41
Sender: blp AT pfaff DOT stanford DOT edu
Message-ID: <87g050n92q.fsf@pfaff.stanford.edu>
References: <3C4ADB8E DOT 552CAE40 AT yahoo DOT com>
NNTP-Posting-Host: pfaff.stanford.edu
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
User-Agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.1
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp
Reply-To: djgpp AT delorie DOT com

CBFalconer <cbfalconer AT yahoo DOT com> writes:

> On my 486/80 65M system with gcc or lcc insertion of 10000 items
> or more has a serious pause during program exit, when hshkill is
> called, which in turn calls the hshfreefn and thence free for each
> item.  The pause becomes oppressive for larger amounts of
> insertions, and is **much** longer than the time to insert.  The
> items are freed in no particular order.
> 
> I suspect this has something to do with recombining free space
> when free is called.

Here's the results on my Debian GNU/Linux "sid" with Linux kernel
2.4.17 PIII/500 laptop with 192 MB RAM.  Free, no-free, and
difference times in seconds, time per free in microseconds:

        buckets free    no-free diff    time/free
        1e5       .33     .25     .08     .8
        5e5      2.44    1.80     .64    1.3
        1e6      5.64    3.75    1.89    1.9
        2e6     15.59    7.71    7.88    3.9
        5e6     82.7    17.7    65.0    13.

Ideally the time/free should stay constant, but in fact it
increases superlinearly: 13/3.9 == 3.33 > 2.5 == 5e6/2e6, same as
what you observed.

I also suspect that it has to do with recombining free space.
Examination of the glibc code for free() doesn't reveal any
obvious problems, but it also doesn't show that it's optimized
for many small (12-byte in this particular implementation)
blocks.  Maybe the Microsoft allocator is smart about such
allocations.  Have you looked at its code?  (Is its source code
available?)

I'd probably use a pool allocator, myself.
-- 
"The way I see it, an intelligent person who disagrees with me is
 probably the most important person I'll interact with on any given
 day."
--Billy Chambless