Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!snorkelwacker.mit.edu!bloom-beacon!eru!hagbard!sunic!dkuug!freja.diku.dk!njk From: njk@diku.dk (Niels J|rgen Kruse) Newsgroups: comp.lang.c Subject: Re: Dynamic Storage Allocator Pros and Cons Message-ID: <1990Nov25.162505.3445@diku.dk> Date: 25 Nov 90 16:25:05 GMT References: <241@smds.UUCP> <1990Nov21.212147.20783@diku.dk> <256@smds.UUCP> Organization: Department Of Computer Science, University Of Copenhagen Lines: 57 rh@smds.UUCP (Richard Harter) writes: rh >(A) All invalid size requests (zero, negative, too large) are trapped. njk>--------------------------------------------------^^^^^^^^^ njk> Try ``getsp (2147483646,0)''. ;-) rh > ??? What machine is this on? It worked fine on the rh > a couple of tests. Sorry, i should have given more details. It was a Vax-11/785 running MORE/Bsd 4.3, compiling with cc -g. You must have used a machine that zero-fill on signed right shift. Here is the relevant part of a gdb session: getsp (size=2147483646, reqno=0) (getsp.c line 150) 150 if (size<=0) { /* Bad size request */ (gdb) 155 size += 4; /* Allow for check words */ (gdb) 156 if (ninit) initsp(); /* Initialize if needful */ (gdb) p size $1 = -2147483646 (gdb) s (...) (gdb) 165 rx=(size-1)>>NSH; /* Get requested index */ (gdb) 166 rsz=(1+rx)<=MXSZ) fx=MXSZ; /* Big request, set fx for big */ (gdb) 172 if (px[rx]) fx=rx; /* Exact fit exists */ (gdb) Program received signal 11, Segmentation fault Authors of dynamic storage allocators almost never check for overflow, when rounding up requests. This is the first thing i look for, when i come across a new one. rh > Best fit gains rh > in two ways -- the percentage of fragments is smaller rh > because of exact fits and the fragment size distribution rh > is skewed to favor very small or very large blocks. rh > Both advantages are much less when the request sizes rh > are "large". This depends very much on the shape of the request size distribution. Consider what happens when you have request sizes, that are very large and very rare. With LIFO, the largest free blocks tend to get nibbled at by smaller requests, so when the very large request finally comes along, no block is large enough and you have to grow the heap. Best Fit on the other hand, tend to preserve the largest free blocks. -- Niels J|rgen Kruse DIKU Graduate njk@diku.dk