Message-ID: <3CE517CD.AD3D0617@yahoo.com> Date: Fri, 17 May 2002 10:46:37 -0400 From: CBFalconer Organization: Ched Research X-Mailer: Mozilla 4.75 [en] (Win98; U) X-Accept-Language: en MIME-Version: 1.0 To: djgpp-workers AT delorie DOT com Subject: Re: emacs under w2k and malloc effects References: <3CE3990C DOT 308C92EC AT yahoo DOT com> <1225-Thu16May2002182200+0300-eliz AT is DOT elta DOT co DOT il> <3CE3FF64 DOT E0F0D953 AT yahoo DOT com> <4331-Fri17May2002115908+0300-eliz AT is DOT elta DOT co DOT il> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Reply-To: djgpp-workers AT delorie DOT com Eli Zaretskii wrote: > > > Date: Thu, 16 May 2002 14:50:13 -0400 > > From: CBFalconer > > > > > > How do you overcome the problem of joining non-contiguous chunks? > > > > If the various sbrk calls returned something non-contiguous (the > > unexpected returns) nothing can join those. > > I didn't mean memory that was non-contiguous to begin with. I meant > memory that was returned as contiguous by sbrk, but was then > subdivided into chunks by malloc, and became non-contiguous after > several allocations and deallocations. > > > However everything in a contiguous sbrk chunk, whether created by > > one or several sbrk calls, will be rejoined when all components are > > freed. > > The problem is precisely that not everything is deallocated when you > suddenly need a large chunk of memory. Some Lisp objects are > short-lived, others tend to live for a long time before they die and > are freed by the garbage collector. That's the reason for > fragmentation. > > The only way to avoid the adverse effects of such fragmentation is to > relocate memory when you don't have a contiguous block large enough to > satisfy the request, but do have enough free memory in non-contiguous > chunks. That's what the Emacs relocating allocator does, but that > cannot be done in a C library. The problem should be eased (not avoided) in nmalloc, because it attempts to allocate from the smallest suitable free chunk. Reallocs of current space won't help, because nmalloc tries hard to avoid copying by attempting to extend the current block. As the system works large blocks will tend to either be in use or appear in large block free lists, while small blocks will either coalesce into large blocks or be available in small block free lists, where new small allocations will find them. I think the tendency will be to physically separate large and small blocks. My test sequences include long runs of random sized allocations intermixed with frees and reallocs. IIRC those runs bear out the above allegations. Probably a further test sequence in tnmalloc where the malloc/realloc/free cycle includes saving something in a growing list, to be freed only on test run termination, would be informative. That might simulate emacs gyrations to some extent. > > > nmalloc keeps track of adjacent allocations and rejoins them > > when freed. Adjacent free blocks are always joined into one larger > > block. It also attempts to do any new allocations from the free > > space list on something close to best fit, and avoids sbrk calls as > > far as possible. > > I think the current libc version also does that, at least within the > bucket. We are agreed on what can and cannot be done. The free space allocator/tracking in nmalloc was basically taken from the existing system. nmalloc tries harder to avoid sbrks during realloc calls, etc. However if something else effectively calls sbrk with a negative value, nmalloc may later think it has a new noncontiguous block, and may then very well allocate the same space twice!. This would NOT be good. It cannot be protected by insisting on monatonic increasing, since I found that the startup code does some wierd things and leaves things fragmented before the application starts. -- Chuck F (cbfalconer AT yahoo DOT com) (cbfalconer AT worldnet DOT att DOT net) Available for consulting/temporary embedded and systems. USE worldnet address!