afc@mace.cc.purdue.edu (Greg Flint) (02/09/90)
I've been trying to use the "farmalloc" routine with Turbo C 2.0. I am trying to allocate numerous small units (e.g., 6 - 20 bytes with each call). I don't know the number or size of the units in advance -- it is data dependent -- so I can't use "farcalloc". The problem that I'm having is that when I request 1-8 bytes, I'm given 16. When I request 9-16, I'm given 32 bytes...and so on. This causes me to run out of memory long before I should. (This is determined by calling "farcoreleft" after each "farmalloc" call.) The manual says that I should get "n" bytes when I request "n" bytes, but I seem to be getting memory in paragraphs -- and 2x what I think I'd need even if it had to give them to me in 16 byte units. I called Bourland support -- what a waste of $'s that was -- and was told that "probably" memory was given out in paragraphs and that "probably" it was supposed to work that way -- regardless of what the manual says. In short, I got no info from Bourland. Does anyone have a patch or a code around for this problem? I know that I could do one big "farmalloc" and write my own "little malloc", but speed is important and I'd prefer not have to execute "C" code if assembler code (or a patch) is available. Besides, writing "little malloc" seems a lot like re-inventing the wheel. ------------------------------------------------------------------------------- Greg Flint Math G-169 (317) 494-1787 UUCP: purdue!klaatu.cc!afc Purdue Univ. Purdue University INTERNET: afc@klaatu.cc.purdue.edu Computing Ctr. West Lafayette, IN 47907 BITNET: flint@purccvm.bitnet
Ralf.Brown@B.GP.CS.CMU.EDU (02/09/90)
In article <4100@mace.cc.purdue.edu>, afc@mace.cc.purdue.edu (Greg Flint) wrote: }I've been trying to use the "farmalloc" routine with Turbo C 2.0. I am }trying to allocate numerous small units (e.g., 6 - 20 bytes with each }call). I don't know the number or size of the units in advance -- it is }data dependent -- so I can't use "farcalloc". } }The problem that I'm having is that when I request 1-8 bytes, I'm given }16. When I request 9-16, I'm given 32 bytes...and so on. This causes }me to run out of memory long before I should. (This is determined by }calling "farcoreleft" after each "farmalloc" call.) Depending on how farmalloc() is implemented, it may be calling DOS's memory allocation functions for each request. DOS allocates in multiples of one paragraph, with an additional paragraph of overhead for memory management. In addition, Turbo C will be taking 8 bytes off the top for its own memory allocation housekeeping info. As it turns out, TC 2.0 allocates in multiples of paragraphs anyway, unlike TC 1.x which allocated in multiples of two bytes (in both cases four to eight bytes of housekeeping info (depending on the memory model) are added before rounding up to the next multiple). }Does anyone have a patch or a code around for this problem? I know that I }could do one big "farmalloc" and write my own "little malloc", but speed }is important and I'd prefer not have to execute "C" code if assembler code }(or a patch) is available. Besides, writing "little malloc" seems a lot }like re-inventing the wheel. Depending on how it is done, it could be considerably faster than calling DOS for each request. Particularly if the allocation is permanent, i.e. you never intend to call free() on the block. Here is some code which I use for small permanent allocations, which virtually eliminates memory management overhead (16-32 bytes overhead for 8192 bytes of allocation, assuming 16-byte or smaller allocations). You may want to use farmalloc() instead of malloc() to allocate the blocks which get parceled out. #define PALLOC_SIZE 8192 /* increment in which palloc() gets memory */ typedef struct _palloc_rec { struct _palloc_rec *next ; int max_size ; int used ; char memblock[1] ; } PALLOC_REC ; static PALLOC_REC *palloc_chain = NULL ; #ifdef PROTOTYPES void *palloc(int n) ; #endif PROTOTYPES /************************************************************************/ /* palloc */ /* "permanent" version of malloc(). Items allocated with palloc() */ /* are not freed until the program terminates, providing a */ /* reduction in memory requirements because no allocation */ /* information needs to be kept */ /************************************************************************/ void *palloc(n) int n ; { PALLOC_REC *p = palloc_chain ; void *mem ; if (n > PALLOC_SIZE) return malloc(n) ; /* can't possibly fit into our blocks, so get a new mem block */ /* find a block with enough memory */ while (p && p->used + n >= p->max_size) p = p->next ; /* skip blocks with insufficient space */ if (p == NULL) /* block with enough space left? */ { /* no, allocate a new block */ if ((p = malloc(sizeof(PALLOC_REC) + PALLOC_SIZE)) == NULL) return NULL ; p->next = palloc_chain ; palloc_chain = p ; p->max_size = PALLOC_SIZE ; p->used = 0 ; } mem = (void *) (p->memblock + p->used) ; p->used += n ; return mem ; } -- UUCP: {ucbvax,harvard}!cs.cmu.edu!ralf -=- 412-268-3053 (school) -=- FAX: ask ARPA: ralf@cs.cmu.edu BIT: ralf%cs.cmu.edu@CMUCCVMA FIDO: Ralf Brown 1:129/46 "How to Prove It" by Dana Angluin Disclaimer? I claimed something? 14. proof by importance: A large body of useful consequences all follow from the proposition in question.
trier@shasta.scl.cwru.edu (Stephen Trier) (02/10/90)
In article <4100@mace.cc.purdue.edu> you write: >I've been trying to use the "farmalloc" routine with Turbo C 2.0. I am >trying to allocate numerous small units (e.g., 6 - 20 bytes with each >call). I don't know the number or size of the units in advance -- it is >data dependent -- so I can't use "farcalloc". > >The problem that I'm having is that when I request 1-8 bytes, I'm given >16. When I request 9-16, I'm given 32 bytes...and so on. This causes >me to run out of memory long before I should. (This is determined by >calling "farcoreleft" after each "farmalloc" call.) This is normal for most C compilers. In fact, K & R describe the need for rounded-up allocation units. (At least, they did in the first edition.) Paragraph-size allocation sounds a bit large, but not all that surprising. All that is guaranteed when using any malloc derivative is that you will get at least as many bytes as you need. Giving you more is up to the compiler. The most likely cause is the overhead involved in C's dynamic memory system. C uses a linked list of memory blocks, both allocated and free. This means that when you ask for 4 bytes of storage, you may get another 4 or 8 bytes of malloc-list data as part of the bargain. (Borland's example program on page 113 of the Reference Guide shows an 8-byte overhead for farmalloc.) If the overhead involved is too great, you will have to use your own allocator of some kind. Consider the possibilities of allocating from an array, or from a linked list of arrays. <=> Stephen Trier seldon!sct@skybridge.SCL.CWRU.Edu sct@po.CWRU.Edu {sun,att,decvax}!cwjcc!skybridge!trier
rds95@leah.Albany.Edu (Robert Seals) (02/10/90)
In article <25d2b215@ralf>, Ralf.Brown@B.GP.CS.CMU.EDU writes: > Here is some code which I use for small permanent allocations, which virtually > eliminates memory management overhead (16-32 bytes overhead for 8192 bytes of > allocation, assuming 16-byte or smaller allocations). You may want to use > farmalloc() instead of malloc() to allocate the blocks which get parceled > out. [ code deleted ] Ralf's code is probably terrific, but remember to #include <alloc.h> or you'll probably have problems in the larger memory models. rob
CMH117@psuvm.psu.edu (Charles Hannum) (02/10/90)
First off, farmalloc() calls DOS to allocate memory. This requires the memory
you allocate to be rounded up to the nearest paragraph. In addition, an extra
paragraph is added for the DOS "Memory Control Block". Together, this would
eat up a huge chunk of memory if you allocate heap in such small bits.
You could reduce this by using the more proper malloc() function, with the
Large, Compact, or Huge memory models. In this case, Turbo-C keeps track of
the allocation chain itself. However, each allocated segment would *still*
require at least 12 bytes of extra header information.
No matter what you do (even if you write your own), a generic malloc() routine
will always require chaining information. This simply cannot be avoided.
Perhaps you should take a better look at the problem you are trying to solve,
and the algorithm you are trying to use. Modifying it will probably eliminate
you malloc() woes altogether.
Virtually,
- Charles Martin Hannum II "Klein bottle for sale ... inquire within."
(That's Charles to you!) "To life immortal!"
cmh117@psuvm.{bitnet,psu.edu} "No noozzzz izzz netzzzsnoozzzzz..."
c9h@psuecl.{bitnet,psu.edu} "Mem'ry, all alone in the moonlight ..."jwbirdsa@phoenix.Princeton.EDU (James Webster Birdsall) (02/10/90)
In article <4100@mace.cc.purdue.edu> afc@mace.cc.purdue.edu (Greg Flint) writes: >The problem that I'm having is that when I request 1-8 bytes, I'm given >16. When I request 9-16, I'm given 32 bytes...and so on. This causes >me to run out of memory long before I should. (This is determined by >calling "farcoreleft" after each "farmalloc" call.) >------------------------------------------------------------------------------- >Greg Flint Math G-169 (317) 494-1787 UUCP: purdue!klaatu.cc!afc > Purdue Univ. Purdue University INTERNET: afc@klaatu.cc.purdue.edu > Computing Ctr. West Lafayette, IN 47907 BITNET: flint@purccvm.bitnet Since I'm not at my computer just now, I can't say for sure, but I think that farmalloc is just an interface to the DOS memory-allocation functions. These, of course, allocate memory in paragraphs. Since several bytes at the beginning of every memory block are reserved for system use, when you try for 9 bytes, it has to give you two paragraphs, etc. Worse, there have been the occasional rumors about bugs in DOS's memory handling functions, leading to system corruption if lots of small blocks are allocated and released frequently. Things you could try: you could try switching to a larger memory model (one with multiple data segments) and use malloc(). I've never gotten malloc() to work right in larger memory models, but I've never tried very hard. Otherwise I think you're going to have to write or find a library of memory-management functions. -- James W. Birdsall jwbirdsa@phoenix.Princeton.EDU jwbirdsa@pucc.BITNET ...allegra!princeton!phoenix!jwbirdsa Compu$erve: 71261,1731 "For it is the doom of men that they forget." -- Merlin
Ralf.Brown@B.GP.CS.CMU.EDU (02/11/90)
In article <2521@leah.Albany.Edu>, rds95@leah.Albany.Edu (Robert Seals) wrote: }In article <25d2b215@ralf>, Ralf.Brown@B.GP.CS.CMU.EDU writes: }> Here is some code which I use for small permanent allocations, which virtually }> eliminates memory management overhead (16-32 bytes overhead for 8192 bytes of }> allocation, assuming 16-byte or smaller allocations). You may want to use }> farmalloc() instead of malloc() to allocate the blocks which get parceled }> out. } }[ code deleted ] } }Ralf's code is probably terrific, but remember to } }#include <alloc.h> } }or you'll probably have problems in the larger memory models. <blush> I missed that line when I ripped the code out of another program.... -- UUCP: {ucbvax,harvard}!cs.cmu.edu!ralf -=- 412-268-3053 (school) -=- FAX: ask ARPA: ralf@cs.cmu.edu BIT: ralf%cs.cmu.edu@CMUCCVMA FIDO: Ralf Brown 1:129/46 "How to Prove It" by Dana Angluin Disclaimer? I claimed something? 14. proof by importance: A large body of useful consequences all follow from the proposition in question.
schaut@cat9.cs.wisc.edu (Rick Schaut) (02/13/90)
In article <4100@mace.cc.purdue.edu> afc@mace.cc.purdue.edu (Greg Flint) writes: | I've been trying to use the "farmalloc" routine with Turbo C 2.0. I am | trying to allocate numerous small units (e.g., 6 - 20 bytes with each | call). I don't know the number or size of the units in advance -- it is | data dependent -- so I can't use "farcalloc". | | The problem that I'm having is that when I request 1-8 bytes, I'm given | 16. When I request 9-16, I'm given 32 bytes...and so on. This causes | me to run out of memory long before I should. (This is determined by | calling "farcoreleft" after each "farmalloc" call.) Farmalloc, unlike malloc, needs to let DOS know that it is allocating a block of memory (the far heap is not allocated at load time). Thus it makes a call to function 48h of the DOS 21h interrupt. Quoting from Peter Norton's "Programmer's Guide to the IBM PC and PS/2": Function 48h (decimal 72) dynamically allocates memory. You request the number of paragraphs (16 byte units) you want allocated in BX. On return, AX contains the segment of the allocated memory block. p374 Remember also that TC needs to add 8 bytes of overhead (4 bytes for the size of the block + 4 bytes for a pointer to the next block) to enable garbage collection. | Does anyone have a patch or a code around for this problem? I know that I | could do one big "farmalloc" and write my own "little malloc", but speed | is important and I'd prefer not have to execute "C" code if assembler code | (or a patch) is available. Besides, writing "little malloc" seems a lot | like re-inventing the wheel. The only thing I can think of is compiling to the compact memory model, and using malloc. However, you may be subject to the same problem. -- Rick (schaut@garfield.cs.wisc.edu) Peace and Prejudice Don't Mix! (unknown add copy)