mc%miranda.uucp@moc.jpl.nasa.gov (Mike Caplinger) (02/09/89)
All versions of malloc from, I believe, 4.0 BSD on, have used a powers-of-two multiple free list allocation scheme instead of the simpler, less virtual-memory-efficient first-fit policy used in version 7 Unix. Simply, this means that if you ask for two chunks of size N, free both, and them ask for one chunk of size 2N, the system doesn't use the old space, because it groups allocated blocks into multiple spaces based on their size. Your test program actually *does* reuse the large block on the second big allocate (under 4.0 I verified that it returns the same address both times), it just sbrks for more space in preparation for extending its free list. I suspect that this, coupled with the N vs. 2N problem mentioned above, is the source of your difficulty. All this probably doesn't help you much. Two things: first, malloc is surprisingly complicated, probably more than I think you expect; second, I agree that this behavior is undesirable, but there are legitimate reasons for why it works this way. You could try using another version of malloc; I wrote one described in the Winter 1988 Usenix Proceedings, but it doesn't interact well with SunView, alas. If you have the old, old version 7 allocator handy, you could try that. It should be noted though, that SunView uses funny allocation (especially with space allocated with the valloc call.) Mike Caplinger, mc@moc.jpl.nasa.gov
djones@decwrl.dec.com (Dave Jones) (02/16/89)
For applications where memory-allocation is critical, I've quit using
malloc "raw". The algorithm the malloc-writers chose may not be at all
suited to your application. But if it is, they might change it next
release, anyway.
I am quite happy with the slow, first fit algorithm on my Sun-3, because
it is stingy with virtual memory. Sorry to hear they are changing it,
although I can understand the rationale.
I have a small collection of memory-allocation routines that I use instead
of using malloc directly. They get large chunks of memory from malloc,
(just as malloc typically gets large chunks from sbrk), and then they
apportion it. They have their own free-lists, etc..
One package allows you to allocate heaps which only dispense one size of
packet. It is a pretty simple package, and using it speeds some programs
up by a factor of 100 on my Sun 3/60. Another package is a virtual stack,
for deallocating memory in the reverse order from the order in which it
was allocated. You get a "mark", which is a virtual pointer to the top of
stack, and later release all memory above the mark. It dispenses
arbitrary size packets. It can show extremely large speed improvements
over regular malloc. Besides, there's the convenience of deallocating all
the packets in one go.
Of course, I also have a stacking package for fixed sized things.
Many of my utility packages, for lists, hash-tables, etc., have their own
specialized memory allocation and deallocation built into them.
I would be interested in trading with others who have similar
uncopyrighted packages.
Dave Jones
sun!megatest!djoneschuck@morgan.com (Chuck Ocheret) (03/09/89)
One thing worth noting... fprintf() may indirectly invoke malloc() (the stdio routines do this to allocate buffer space) which can skew the results of malloc() tests. If you wish to examine malloc() results directly use an sprintf() followed by write(). Or else use dbx. +------------------+ Chuck Ocheret, Sr. Staff Engineer +------------------+ | chuck@morgan.com | Morgan Stanley & Co., Inc. | (212)703-4474 | | Duty now ... |19th Floor, 1251 Avenue of the Americas| for the future. | +------------------+ New York, N.Y. 10020 +------------------+