Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!wasatch!cs.utexas.edu!uunet!mcvax!kth!sunic!dkuug!freja!njk
From: njk@freja.diku.dk (Niels J|rgen Kruse)
Newsgroups: comp.lang.c
Subject: Re^2: Memory Allocation
Message-ID: <4648@freja.diku.dk>
Date: 8 May 89 20:52:59 GMT
References: <10946@bloom-beacon.MIT.EDU> <12546@ut-emx.UUCP> <10202@smoke.BRL.MIL> <11486@ulysses.homer.nj.att.com>
Organization: DIKU, U of Copenhagen, DK
Lines: 27

kpv@ulysses.homer.nj.att.com (Phong Vo[drew]) writes:

>The old malloc was based on a simple first-fit strategy with a roving pointer.
>It is intolerably slow when a process needs to to many mallocs (say thousand

Don't write off roving pointer/rotating freelist allocators
just because of a poor implementation. Rotating freelist
allocators can be made to go *very* fast. That requires an
explicit freelist however.

Even the Bsd 4.1 malloc can be speeded up significantly by
simple means. If there is sufficient interest, i will post a
patch to the Bsd 4.1 malloc (as distributed with the JOVE
sources), that makes it 10 x faster (on my benchmark, your
mileage may vary).

>However, one can go a long way toward making a compromise between having good
>time behavior and good space behavior. Locally, we've been having good
>success with a modified version of the best-fit based algorithm presented
>in that paper.

Could you say how fast it is relative to the Bsd 4.3 malloc,
roughly, < 2 x slower ?, < 3 x slower ?, ...
-- 
         Niels J|rgen Kruse
Email    njk@diku.dk
Mail     Tustrupvej 7, 2 tv, 2720 Vanlose, Denmark