gram@uctcs.uucp (Graham Wheeler) (06/19/91)
I am reposting this article as I never saw the original appear when using nn and have had no responses, so I assume that it got lost. I have an application in which I am allocating a number of variable sized records, of average size about 6 bytes. Whenever the size changes, I use farrealloc. I have over 300kb available at the time I start allocating these nodes. I also keep track of the number of allocated bytes. My problem is that I get a memory allocation failure at about 120kb of allocated memory. This must mean one of two things: i) either there is a bug in TC (actually TC++ v1.0) so that when realloc fails to resize a block and allocates a new one it doesn't free the old one; or ii) the allocated blocks are being held on a linked list with an overhead of (I would guess) 12 bytes per block (two far pointers and one long size). This would mean that my nodes are actually using up 3 times more memory than I am actually using for record storage. Personally, I think it is better to have the free blocks on a linked list as you get the maximum use from your memory that way. I don't know how TC does it. Does anyone know which of these two theories is correct? Or is there a different explanation? Graham Wheeler <gram@cs.uct.ac.za> | "That which is weak conquers the strong, Data Network Architectures Lab | that which is soft conquers the hard. Dept. of Computer Science | All men know this; none practise it" University of Cape Town | Lao Tzu - Tao Te Ching Ch.78
msmith%peruvian.utah.edu@cs.utah.edu (Matthew Smith) (06/20/91)
In article <1991Jun19.083945.8921@ucthpx.uct.ac.za> gram@uctcs.uucp (Graham Wheeler) writes: >I am reposting this article as I never saw the original appear when using nn >and have had no responses, so I assume that it got lost. > >I have an application in which I am allocating a number of variable sized >records, of average size about 6 bytes. Whenever the size changes, I use >farrealloc. I have over 300kb available at the time I start allocating these >nodes. I also keep track of the number of allocated bytes. My problem is that >I get a memory allocation failure at about 120kb of allocated memory. This >must mean one of two things: > >i) either there is a bug in TC (actually TC++ v1.0) so that when realloc > fails to resize a block and allocates a new one it doesn't free the > old one; or >ii) the allocated blocks are being held on a linked list with an overhead of >Graham Wheeler <gram@cs.uct.ac.za> | "That which is weak conquers the strong, >Data Network Architectures Lab | that which is soft conquers the hard. >Dept. of Computer Science | All men know this; none practise it" >University of Cape Town | Lao Tzu - Tao Te Ching Ch.78 I've run across a similar situation. I was using realloc as opposed to farrealloc, and the same thing happened there. My conclusion after looking at several examples in the manuals is that they DON'T delete the old block. This conclusion was achieved by the fact that in all examples, they had a dummy pointer pointing to the current block, called realloc with their usual pointer, and then called free() with their dummy pointer (which really pointed to their old block). That's the way they want you to do it. I know, it really sucks. Matt Smith msmith@peruvian.utah.edu
alexande@borland.com (Mark Alexander) (06/20/91)
(Email bounced yet again, sorry.) The far heap in BC++ has 16-byte granularity, and 4 bytes of overhead per block. What this means is that each block is allocated on a 16-byte boundary, and the first four bytes of each block are reserved. If you look at the pointers returned by farmalloc() and farrealloc(), you'll see that they're all in the form xxxx:0004. So if your program allocates a 6-byte block, you'll actually use up 16 bytes. A 12-byte allocation would also use 16 bytes, but a 13-byte allocation would use 32 bytes. One solution is allocate two of your 6-byte structures in one call to farmalloc(), but this may make your program ugly.
kooijman@duteca.et.tudelft.nl (Richard Kooijman) (06/20/91)
msmith%peruvian.utah.edu@cs.utah.edu (Matthew Smith) writes: >> >>i) either there is a bug in TC (actually TC++ v1.0) so that when realloc >> fails to resize a block and allocates a new one it doesn't free the >> old one; or >>ii) the allocated blocks are being held on a linked list with an overhead of >I've run across a similar situation. I was using realloc as opposed to >farrealloc, and the same thing happened there. My conclusion after looking >at several examples in the manuals is that they DON'T delete the old block. >This conclusion was achieved by the fact that in all examples, they had a >dummy pointer pointing to the current block, called realloc with their usual >pointer, and then called free() with their dummy pointer (which really >pointed to their old block). That's the way they want you to do it. I know, >it really sucks. I do not understand what you mean with this. In my opinion the problem is caused by overhead and memory fragmentation. The overhead isn't 12 bytes, I think, but 8 bytes as somebody mentioned here a while ago. Richard.
colburn@tessa (alex colburn) (06/20/91)
In article <1991Jun19.083945.8921@ucthpx.uct.ac.za> gram@uctcs.uucp (Graham Wheeler) writes: >I am reposting this article as I never saw the original appear when using nn >records, of average size about 6 bytes. Whenever the size changes, I use >farrealloc. I have over 300kb available at the time I start allocating these >nodes. I also keep track of the number of allocated bytes. My problem is that >I get a memory allocation failure at about 120kb of allocated memory. This I don't think your problem lies in Borland's internal memory management systems, it would kind of silly for them to write something that uses twice as much memory as it is managing. Is this error message something you get, and then its time for a reboot? If so, I bet you're referencing invalid addresses. How are you keeping track of your reallocated memory? If you have some sort of linked list data structure, when you farrealloc you just might be scrambling pointers. For debugging purposes try doing a farheapcheck() after each memory function so you can determine the exact point where things go buggy. If you have memory blocks greater than 64K the pointer must be explicity declared as huge (this one threw me for the last week and 1/2), otherwise address calculations are only done on the offset, and you get a neat little effect that usually locks up the system. Good Luck! Alex.
gram@uctcs.uucp (Graham Wheeler) (06/24/91)
Thanks to all those who sent replies. The following reply is the most explicit. From: proxima!quagga!m2xenix!uunet!dartvax!eleazar.dartmouth.edu!crystal@Daisy.EE.UND.AC.ZA Organization: Dartmouth College, Hanover, NH In article <1991Jun19.083945.8921@ucthpx.uct.ac.za> you write: >I have an application in which I am allocating a number of variable sized >records, of average size about 6 bytes. Whenever the size changes, I use >farrealloc. I have over 300kb available at the time I start allocating these >nodes. I also keep track of the number of allocated bytes. My problem is that >I get a memory allocation failure at about 120kb of allocated memory. This >must mean one of two things: > >i) either there is a bug in TC (actually TC++ v1.0) so that when realloc > fails to resize a block and allocates a new one it doesn't free the > old one; or >ii) the allocated blocks are being held on a linked list with an overhead of > (I would guess) 12 bytes per block (two far pointers and one long size). > This would mean that my nodes are actually using up 3 times more memory > than I am actually using for record storage. > >Personally, I think it is better to have the free blocks on a linked list as >you get the maximum use from your memory that way. I don't know how TC does >it. > >Does anyone know which of these two theories is correct? Or is there a >different explanation? > When you use farmalloc/farrealloc, each memory request is separately allocated from DOS, with a granulation of 16 bytes (1 paragraph), and an overhead of another 16 bytes per request. The granularity of 16 bytes is so that only 16-bit segment address are needed to track the memory blocks. If you have dos 4+, try doing a system("mem /debug") from your program after allocating a few of these, and you will see of the separate blocks listed. Richard Brittain richard@einstein.dartmouth.edu ========================================================================== Bearing in mind that my allocations are on average six bytes, I would be using 32 bytes for each node, ie over 80% of memory will be wasted. A suggestion I got to get around this was to use the large memory model with a plain old malloc instead of farmalloc. I haven't tried this yet, but it may help. Otherwise I think I will just allocate one massive memory block and do my own allocation from that, so that I have none of this excess overhead. Thanks again! Graham Wheeler <gram@cs.uct.ac.za> | "That which is weak conquers the strong, Data Network Architectures Lab | that which is soft conquers the hard. Dept. of Computer Science | All men know this; none practise it" University of Cape Town | Lao Tzu - Tao Te Ching Ch.78
grimlok@hubcap.clemson.edu (Mike Percy) (06/26/91)
gram@uctcs.uucp (Graham Wheeler) writes: >Thanks to all those who sent replies. The following reply is the most explicit. >From: > proxima!quagga!m2xenix!uunet!dartvax!eleazar.dartmouth.edu!crystal@Daisy.EE.UND.AC.ZA >Organization: Dartmouth College, Hanover, NH >In article <1991Jun19.083945.8921@ucthpx.uct.ac.za> you write: >>i) either there is a bug in TC (actually TC++ v1.0) so that when realloc >> fails to resize a block and allocates a new one it doesn't free the >> old one; or Not the case here...but >>ii) the allocated blocks are being held on a linked list with an overhead of >> (I would guess) 12 bytes per block (two far pointers and one long size). >> This would mean that my nodes are actually using up 3 times more memory >> than I am actually using for record storage. It's actually one far pointer (to previous block in list), and a long for size. The second far pointer (to the next block) is derived from the current block address + size, since the next block is immediately after the current block in memory. The granularity is 16-bytes; this is to simplify tehg overhead computations. If you are farmalloc()ing lots of small items, you can be hurt by this. If you need to allocate lots of small, smae-size objects, try managing the list yourself. Smae-size objects require less work/overhead than arbitrary sized objects. >> >>Personally, I think it is better to have the free blocks on a linked list as >>you get the maximum use from your memory that way. I don't know how TC does >>it. For a description see my letter to the editor in Nov. 1990 C Users Journal. I might be able to dig it up and post it here if anyone's interested. >Bearing in mind that my allocations are on average six bytes, I would be using >32 bytes for each node, ie over 80% of memory will be wasted. No, since the overhead is only 8 bytes, a siz byte request is satisfied by a 16-byte block. >A suggestion I got to get around this was to use the large memory model with >a plain old malloc instead of farmalloc. I haven't tried this yet, but it may >help. Otherwise I think I will just allocate one massive memory block and do my >own allocation from that, so that I have none of this excess overhead. Won't help -- malloc() in large data memory models (compact, large, huge) is simply coerced into a call to farmalloc(). These memory models do not maintain near and far heaps. It might help to use samll data memory models and malloc (overhead is 4 bytes, granularity is 8 bytes) but if your data size is 6 bytes (4+6 = 10, need two block == 16 bytes -- same as before!). >Thanks again! Sure thing. I'll send you the article or post it sometime in the very near future. "I don't know about your brain, but mine is really...bossy." Mike Percy grimlok@hubcap.clemson.edu ISD, Clemson University mspercy@clemson.BITNET (803)656-3780 mspercy@clemson.clemson.edu
alexande@borland.com (Mark Alexander) (06/28/91)
In article <1991Jun24.075451.20728@ucthpx.uct.ac.za> gram@uctcs.uucp (Graham Wheeler) writes: >When you use farmalloc/farrealloc, each memory request is separately >allocated from DOS, with a granulation of 16 bytes (1 paragraph), and an >overhead of another 16 bytes per request. This is only half correct. The granularity is indeed 16 bytes, but the overhead for each allocated block is 4 bytes, not 16 bytes. Here's a little table that may help: Requested Actual no. of block size bytes allocated ---------- --------------- 1-12 16 13-28 32 29-44 48 etc. etc. You can verify this by printing the pointers returned by farmalloc(); you'll find that they are all of the form xxxx:0004.
smiller@wet.UUCP (Gregory Shane Miller) (06/28/91)
I once wrote a program which did around 580 to 600K of farmallocs and too found out that I ran out memory long before I anticipated. I believe this is the answer to your question. First, when any of TC's malloc functions are called, it merely passes the malloc call to the DOS malloc functions. You will notice that the DOS malloc functions allocates INTEGER UNITS of PARAGRAPHS (16 bytes). So when you do malloc(6) DOS does malloc(16) or when you do malloc(12) it does malloc (32). Also, my program was very recursive and when in deep levels the stack gets so big it reduces the far heap space. That is the problem your running into. I should also point out that the function farcoreleft() is useless after the first malloc. It only reports the space between the highest allocated byte and the bottom of stack. When the heap becomes fragmented, this function returns useless numbers. The only thing it is good for is too find the maximum amount of heap available - remember this goes down when the stack pushes down into memory. In order to solve my problem, I calculated the entire amount of memory I needed and did one big malloc and then rewrote my recursive routine to be iterative (using as it turned out the harddisk to shuffle some data). Hope that helps -- BTW if you want the info from farcoreleft() use it as the first line of your main(), for even calls to scanf have an embedded malloc call that you don't see! smiller@wet.UUCP -- G. Shane Miller [ smiller@wet.UUCP (415) 453-4926 ]
trier@cwlim.INS.CWRU.Edu (Stephen C. Trier) (06/29/91)
If you are interested in seeing how a real malloc implementation works, I recommend _The C Programming Language_, by Kernighan and Ritchie. The authors illustrate memory allocation with "malloc" and "free" functions which could very well be from a C library. They also explain the mechanisms of the memory allocator quite thoroughly. Incidentally, the first edition of K&R called the function "alloc". The second edition, without changing the code itself, admits that the function is "malloc". Most malloc implementations are similar to the version in K&R. They may have additional optimizations, but the principles are the same. -- Stephen Trier "48 61 70 70 69 6e 65 73 73 20 69 73 20 61 Server Surgery Group 20 77 61 72 6d 20 68 65 78 20 64 75 6d 70 Information Network Services 21 20 20 3b 2d 29" - Me Case Western Reserve University Mail: trier@ins.cwru.edu
grimlok@hubcap.clemson.edu (Mike Percy) (06/30/91)
trier@cwlim.INS.CWRU.Edu (Stephen C. Trier) writes: >If you are interested in seeing how a real malloc implementation works, >I recommend _The C Programming Language_, by Kernighan and Ritchie. The >authors illustrate memory allocation with "malloc" and "free" functions >which could very well be from a C library. They also explain the >mechanisms of the memory allocator quite thoroughly. Also you might pop over to comp.lang.c where I've just posted a description of the internals of TC++ farmalloc, gleaned from reading the assembler source via the debugger. Watch there for some variations on farheapwalk, farheapfreechack, etc. I'm digging deep and working out the mechanisms, and will put my code samples up for display. "I don't know about your brain, but mine is really...bossy." Mike Percy grimlok@hubcap.clemson.edu ISD, Clemson University mspercy@clemson.BITNET (803)656-3780 mspercy@clemson.clemson.edu