Batch malloc
in [General Programming]
|
Prev: hacking
Next: How get percentage of use of cpu
From: Jon Harrop on 20 Jan 2010 16:13 Willem wrote: > Jon Harrop wrote: > ) Sure. I want a function that accepts an array of sizes of blocks to > allocate ) and returns an array of pointers to allocated blocks. > ) > ) For example (assuming an array notation [.., ...]): > ) > ) mallocs[10, 20, 30] > ) > ) gives a similar result to: > ) > ) [malloc(10), malloc(20), malloc(30)] > ) > ) except that the whole block is allocated atomically, i.e. as > contiguously as ) possible for a given thread. > > How would free()ing work ? Same as normal for each individual allocated block: [x,y,z] = mallocs[10, 20, 30] ... free(x) ... free(y) ... free(z) > ) I can just take out a global lock of my own but I suspect it would be > far ) more efficient if malloc could handle bulk allocations all at the > same ) time. For example, it could just allocate a larger block and divvy > it up > ) internally so I could still call "free" to free each subblock > ) individually. > > Or you could do that yourself (0-terminated list): > > void * malloc_m(size_t *sizes) > { > size_t sz, psz; > size_t *sp; > void *vp, *tp, *ret; > for (sp = sizes, sz = psz = 0; *sp; sp++, psz += sizeof(void *)) { > sz += *sp; > } > ret = malloc(sz + psz); > tp = ret + psz; > for (sp = sizes, vp = ret; *sp; sp++, vp++) { > *vp = tp; tp += *sp; > } > *vp = NULL; > return ret; > } > > Off the top of my head, of course, and untested. Just wanted to get the > idea across. > This way, you obviously have to only free() the array of pointers. That means I have to wait until they're all free before freeing the whole block, which is too much overhead. I need to be able to free them individually, as normal. -- Dr Jon D Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?u
From: James Harris on 20 Jan 2010 17:58 On 20 Jan, 17:07, Jon Harrop <j...(a)ffconsultancy.com> wrote: .... > >>Anyone know of a memory allocator that allows blocks to be allocated in > >>batches? > > > Could you be more specific? > > Sure. I want a function that accepts an array of sizes of blocks to allocate > and returns an array of pointers to allocated blocks. > > For example (assuming an array notation [.., ...]): > > mallocs[10, 20, 30] > > gives a similar result to: > > [malloc(10), malloc(20), malloc(30)] > > except that the whole block is allocated atomically, i.e. as contiguously as > possible for a given thread. From a different point of view you could regard this as nothing to do with the allocator. Even if there was an allocator which accepted requests in groups what's to stop it being timesliced? .... > I can just take out a global lock of my own but I suspect it would be far > more efficient if malloc could handle bulk allocations all at the same > time. For example, it could just allocate a larger block and divvy it up > internally so I could still call "free" to free each subblock > individually. Rather than use locks a fix could be to have an allocator thread. Send it allocation requests in groups and have it finish one group before going on to the next. James
From: Richard Harter on 20 Jan 2010 18:22 On Wed, 20 Jan 2010 17:07:12 +0000, Jon Harrop <jon(a)ffconsultancy.com> wrote: >Richard Harter wrote: >> On Sun, 17 Jan 2010 16:33:22 +0000, Jon Harrop >> <jon(a)ffconsultancy.com> wrote: >>>Anyone know of a memory allocator that allows blocks to be allocated in >>>batches? >> >> Could you be more specific? > >Sure. I want a function that accepts an array of sizes of blocks to allocate >and returns an array of pointers to allocated blocks. > >For example (assuming an array notation [.., ...]): > > mallocs[10, 20, 30] > >gives a similar result to: > > [malloc(10), malloc(20), malloc(30)] > >except that the whole block is allocated atomically, i.e. as contiguously as >possible for a given thread. I take it that you want to do this for locality reasons. > >The problem with the latter (which is my current approach) is that the >atomic lock in malloc allows the allocations to get multiplexed: > > Thread Location > A 0 > B 10 > A 20 > B 40 > A 60 > B 90 > >That destroys locality and can even introduce false sharing. > >I can just take out a global lock of my own but I suspect it would be far >more efficient if malloc could handle bulk allocations all at the same >time. For example, it could just allocate a larger block and divvy it up >internally so I could still call "free" to free each subblock >individually. I guess the key question is: Can you use your own malloc or are you constrained to use the default malloc? If you must use the default (system) allocator you don't have any really nice solutions. If you can modify the system allocator (calling it my_malloc) the required mod should be easy. Sorry, no real help at the moment. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Infinity is one of those things that keep philosophers busy when they could be more profitably spending their time weeding their garden.
From: James Dow Allen on 21 Jan 2010 02:53 On Jan 21, 12:07 am, Jon Harrop <j...(a)ffconsultancy.com> wrote: > ... I want a function that accepts an array of sizes of blocks to allocate > and returns an array of pointers to allocated blocks. > > For example (assuming an array notation [.., ...]): > mallocs[10, 20, 30] > gives a similar result to: > [malloc(10), malloc(20), malloc(30)] Assuming you have malloc/free source already and are willing to modify it, with some such packages it *may* be straightforward to get what you want by allocating the single bigger block and then invoking a new function you write: /* adjust malloc's state so one of its allocated * blocks becomes several allocated blocks. */ adjmalloc(p, listofsizes) This assumes that the greater difficulty of satisfying malloc(10+20+30 + /* possibly */ OVERHEAD); is not an issue. For more on *that* see a recent rec.puzzles thread set, rather lewdly I thought, among men's urinal stalls. James Dow Allen
From: websnarf on 27 Jan 2010 23:59
On Jan 20, 1:13 pm, Jon Harrop <j...(a)ffconsultancy.com> wrote: > Willem wrote: > > Jon Harrop wrote: > > ) Sure. I want a function that accepts an array of sizes of blocks to > > allocate ) and returns an array of pointers to allocated blocks. > > ) > > ) For example (assuming an array notation [.., ...]): > > ) > > ) mallocs[10, 20, 30] > > ) > > ) gives a similar result to: > > ) > > ) [malloc(10), malloc(20), malloc(30)] > > ) > > ) except that the whole block is allocated atomically, i.e. as > > contiguously as ) possible for a given thread. > > > How would free()ing work ? > > Same as normal for each individual allocated block: > > [x,y,z] = mallocs[10, 20, 30] > ... > free(x) > ... > free(y) > ... > free(z) > > > ) I can just take out a global lock of my own but I suspect it would be > > far ) more efficient if malloc could handle bulk allocations all at the > > same ) time. For example, it could just allocate a larger block and divvy > > it up > > ) internally so I could still call "free" to free each subblock > > ) individually. > > > Or you could do that yourself (0-terminated list): > > > void * malloc_m(size_t *sizes) > > { > > size_t sz, psz; > > size_t *sp; > > void *vp, *tp, *ret; > > for (sp = sizes, sz = psz = 0; *sp; sp++, psz += sizeof(void *)) { > > sz += *sp; > > } > > ret = malloc(sz + psz); > > tp = ret + psz; > > for (sp = sizes, vp = ret; *sp; sp++, vp++) { > > *vp = tp; tp += *sp; > > } > > *vp = NULL; > > return ret; > > } > > > Off the top of my head, of course, and untested. Just wanted to get the > > idea across. > > This way, you obviously have to only free() the array of pointers. > > That means I have to wait until they're all free before freeing the whole > block, which is too much overhead. I need to be able to free them > individually, as normal. Your question is quite interesting. But it should be fairly obvious that such things do not exist (insert my standard old EMOing about how the C language standard committee is too dull to consider functionality improvements to the C library). To implement a malloc that does what you suggest indeed should be quite straight-forward, but would have to be some kind of implementation specific extension. That being said, I am fairly sure you can take an alternative approach which is better than it might seem to you at first. Implement your own layer on top of malloc just for the specific types that you are allocating. int blk_malloc (void * results[], size_t qty, size_t arrSz[]); blk_element_free (void * blk_element); The idea is to implement wrappers for your allocations that look like: struct blkAlloc_base { size_t nElements; intptr_t data[1]; }; /* There would be many of these packed in the data[] element from the above structure */ struct blkAlloc_elem { struct blkAlloc_base * parent; intptr_t realOffset[1]; }; So the each allocation would point to the &blkAlloc_elem.realOffset offset, and your base allocation would just be a big allocation with &blkAlloc_base.data being the start of the packed sequence of smaller elements. nElements would be initiailized in blk_malloc() with qty, and each time blk_element_free() was called, it would access the parent entry then decrease nElements. If nElements reached 0, then the blkAlloc_base would be freed by calling free() on it. This is not a complete explanation of all the details of course, but I am sure you can suss out exactly what I mean, and what details you need to cover. (Alignment might be unavoidably platform specific.) This, of course, requires that you know all such elements are being allocated by this wrapper allocation system and that you are only allocating and freeing with it in a single thread (other wise you will have to throw a lock around it, or more ideally use atomic increment/ decrement). But assuming you can satisfy such requirements, from a performance point of view, this is ideal, and would not perform in anyway worse than any custom allocator extension based solution. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ |