Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Uncle Steve <stevet810@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Malloc Query |
| Date | 2011-05-18 17:10 -0400 |
| Organization | Friends of the Galactic Collective |
| Message-ID | <a8b295514ba3fd1-1a35b@gmail.com> (permalink) |
| References | <iquit3$pl$1@speranza.aioe.org> <87aael3xw1.fsf@blp.benpfaff.org> <ir096a$6vd$1@dont-email.me> <0.9e954b297cf63735a997.20110518193428BST.87zkmjuabv.fsf@bsb.me.uk> |
On Wed, May 18, 2011 at 07:34:28PM +0100, Ben Bacarisse wrote:
> "BartC" <bc@freeuk.com> writes:
>
> > "Ben Pfaff" <blp@cs.stanford.edu> wrote in message
> > news:87aael3xw1.fsf@blp.benpfaff.org...
> <snip>
> >> According to an academic study I read some time ago, there is
> >> rarely any significant advantage to special-purpose memory
> >> allocators. In a quick online search, I didn't find a reference
> >> to this paper, but perhaps someone else here has a copy of it.
> >
> > I've just done a test where allocating and freeing large numbers of
> > 4-byte blocks took twenty times longer using malloc/free (and probably
> > took 2-4
> > times as much space) than using a special allocator.
>
> That's interesting, but of limited value unless you can give more
> details. Ideally, can you post the code? That way it can tried on
> different systems with different C libraries.
>
> At least say what the "special allocator" is. Relative speed up must be
> relative to something known, not something mysterious.
>
> > How significant this is depends on the application, but I don't think
> > you can just dismiss such an allocator.
>
> But no one else can consider it either since we don't know what it is.
It's probably something similar to what I use occasionally:
struct arena_head {
int obj_size;
int arena_size; /* obj_size count */
char * arena;
int free;
int free_list;
};
There's a function that mallocs the header and data area, and
initializes the free list, which in my case is a linked list of
integers stored in the first word of each arena slot. The allocator
comes in two varieties: one that will realloc() the arena
automatically when the free slots are exhausted, and one that just
returns -1 if the arena is exhausted.
#define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
arena_qa(struct arena_head *x)
{
int n;
n = x->free_list;
if(n != -1) {
x->free_list = *((int *) arena_obj_addr(x, n));
x->free--;
}
return(n);
}
void arena_free(struct arena_head *p, int n)
{
*((int *) arena_obj_addr(p, n)) = p->free_list;
p->free_list = n;
p->free++;
return;
}
I haven't measured it's performance against malloc() just yet, but it
must be something like an order of magnitude faster than malloc. I
spent some time to make it a little more flexible than the pared-down
version here, such as including an option to clear each slot when it
is freed automatically, and so on. In a debugger, it's fairly easy to
inspect the book-keeping and you can output a diagnostic message if
you destroy the arena while there are still allocated slots, which
identifies memory leaks.
When I read up on the malloc() implementation in glibc (a few years
ago), it stated that the length of the allocation was stored in the
32-bit word immediately prior to the pointer returned by malloc (on
x86) and there were additional padding bytes, probably a maximum of
three on x86 (not sure how true this is today). So, a four-byte object
size would require eight bytes minimum storage. When you're dealing
with many hundreds of thousands or even millions of allocations, that
might be the difference between keeping your data set in memory, or
going into swap space. For even 30% savings in memory, not to mention
speed, this is a real win.
I would propose that this is a simple example of a 'better algorithm'.
malloc() is designed to handle the general case of arbitrary
allocations occurring with arbitrary ordering. When you know you're
going to use many of the same size object it is easy to adapt the
algorithm to use this arrangement, and for this special case it is
fast and compact. What is the counterargument against using this kind
of structure?
Regards,
Uncle Steve
--
Should a professional politician be charged with molestation if he
kisses babies while attending political rallies?
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-17 19:39 +0000
Re: Malloc Query blp@cs.stanford.edu (Ben Pfaff) - 2011-05-17 12:55 -0700
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 12:05 +0100
Re: Malloc Query Pushpa <pushpa@nospam.invalid> - 2011-05-18 17:11 +0000
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:42 +0100
Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:10 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 19:34 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 17:10 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 00:26 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-18 21:25 -0400
Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-18 21:38 -0400
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:11 -0400
Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-19 22:55 -0400
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:14 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 03:22 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 14:20 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 23:51 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 20:01 -0400
Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-22 02:49 -0700
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:46 -0400
Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 12:37 -0500
Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-22 13:02 -0500
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 14:12 -0400
Re: Malloc Query Shao Miller <sha0.miller@gmail.com> - 2011-05-23 03:06 -0500
Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:42 -0700
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:10 -0400
Re: Malloc Query Keith Thompson <kst-u@mib.org> - 2011-05-23 09:06 -0700
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-22 23:18 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 19:18 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 11:22 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 01:57 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-23 19:24 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 14:20 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 07:41 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 16:24 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 09:20 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 18:05 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 10:37 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 19:34 -0400
Re: Malloc Query "robertwessel2@yahoo.com" <robertwessel2@yahoo.com> - 2011-05-23 17:48 -0700
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-24 12:56 +1200
Re: Malloc Query James Kuyper <jameskuyper@verizon.net> - 2011-05-24 07:19 -0400
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-24 11:32 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 01:04 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 02:36 -0400
Re: Malloc Query luser- -droog <mijoryx@yahoo.com> - 2011-05-23 00:39 -0700
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-23 14:44 +0100
Re: Malloc Query Seebs <usenet-nospam@seebs.net> - 2011-05-23 15:16 +0000
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-23 11:41 -0400
Re: Malloc Query David Thompson <dave.thompson2@verizon.net> - 2011-06-01 16:33 -0400
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-19 18:34 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 02:36 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 12:26 -0400
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-20 23:32 +0100
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-20 21:17 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-21 14:30 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 11:13 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 08:50 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-21 20:03 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-22 13:23 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-22 10:01 -0400
Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-26 08:12 +0200
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-26 19:16 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:03 -0400
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-27 09:16 +1200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 17:55 -0400
Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-27 05:47 +0200
Re: Malloc Query Uncle Steve <stevet810@gmail.com> - 2011-05-26 15:02 -0400
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:31 +0100
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-18 23:37 +0100
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 01:50 +0100
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 02:50 +0100
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 12:14 +0100
Re: Malloc Query Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-05-19 15:10 +0100
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-19 15:48 +0100
Re: Malloc Query cri@tiac.net (Richard Harter) - 2011-05-18 19:31 +0000
Re: Malloc Query Ike Naar <ike@iceland.freeshell.org> - 2011-05-18 21:43 +0000
Re: Malloc Query "BartC" <bc@freeuk.com> - 2011-05-18 22:58 +0100
Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-17 14:01 -0600
Re: Malloc Query Columbus sailed the ocean China Blue <chine.bleu@yahoo.com> - 2011-05-17 13:21 -0700
Re: Malloc Query BGB <cr88192@hotmail.com> - 2011-05-17 14:08 -0700
Re: Malloc Query Michael Press <rubrum@pacbell.net> - 2011-05-17 19:49 -0700
Re: Malloc Query Lauri Alanko <la@iki.fi> - 2011-05-18 00:50 +0000
Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-17 21:21 -0400
Re: Malloc Query "io_x" <a@b.c.invalid> - 2011-05-18 19:31 +0200
Re: Malloc Query Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-05-18 21:36 +0000
Re: Malloc Query Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-05-18 21:26 -0400
Re: Malloc Query Tim Rentsch <txr@alumni.caltech.edu> - 2011-05-19 02:07 -0700
Re: Malloc Query Ian Collins <ian-news@hotmail.com> - 2011-05-19 21:13 +1200
Re: Malloc Query Nobody <nobody@nowhere.com> - 2011-05-18 07:08 +0100
Re: Malloc Query David Resnick <lndresnick@gmail.com> - 2011-05-19 07:51 -0700
Re: Malloc Query Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2011-05-19 09:12 -0600
csiph-web