Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #4346

Re: Malloc Query

Show all headers | View raw

On Thu, May 19, 2011 at 03:22:18AM +0100, Ben Bacarisse wrote:
> Uncle Steve <stevet810@gmail.com> writes:
> 
> > On Thu, May 19, 2011 at 12:26:15AM +0100, Ben Bacarisse wrote:
> >> Uncle Steve <stevet810@gmail.com> writes:
> >> 
> >> > 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:
> >> 
> >> Yes, similar but even simpler.
> >> 
> >> <snip code>
> >> > 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 am guessing you don't have a background in the sciences!
> >
> > Not really.  Science fiction doesn't really count.  Real science is
> > time-consuming, and I just don't have enough free leisure hours in the
> > day.
> >  
> >> <snip>
> >> > I would propose that this is a simple example of a 'better algorithm'.
> >> 
> >> I am glad that's in 'scare quotes'.  I don't really want to get into a
> >> discussion of whether a special-case algorithm is better than a general
> >> one.  It depends on your metrics, no doubt.  What I'd really like is
> >> some data, and even better than that would be some code I could try to
> >> see how general the benefit is (across systems) for some specific
> >> special-purpose allocator.
> >
> > Hey, the code I wrote there is almost trivial to test.  I don't know
> > why you're so keen to get numbers on it, part of my reason for not
> > having those numbers is that it's more meaningful to measure the
> > performance of real code that's using the allocator.  Besides, what
> > I've done here has probably been studied to death some time way back
> > in the sixties or seventies.  I don't have convenient access to a
> > university library account, so an abstract search is problematic for
> > me.  You'll probably get buried in citations if you try this route.
> 
> I think this sort of thing has to be done every generation.  I doubt
> that conclusions drawn on a PDP-11 or an IBM 360 relate to my multi-core
> multi-level cache machine.  I've seen the situation change.  At one
> point I took out a freelist allocator like yours from a function
> language implementation of mine because it added very little to the
> performance.  Maybe I would be changing that ifdef macro now.  Only
> measurements can tell, and I can't test that code any more -- I seem to
> have lost it into the big bit bucket in the sky.
> 
> Even if the general rules are the same (specific-case allocation being
> cheaper than general-case) the thing that prompted my reply was a
> number: 20 times.  I'd like to check that out on my system.
> 
> <snip>
> >> > What is the counterargument against using this kind
> >> > of structure?
> >> 
> >> (a) You have to write it and debug it.  The code you posted had bugs,
> >> but that's probably because it was pulled out of context to illustrate
> >> the idea.  (BTW, I've been around the block long enough that you could
> >> just have said that it's a free list of fixed size objects).
> >
> > Probably, but people with less experience might not have appreciated the
> > simplicity of the algorithm if it was full of object padding
> > calculations, and all the little bits that go along with it.  Of
> > course I edited for brevity.
> 
> You edited in some bugs too:
> 
> | #define arena_obj_addr(x, n) ((void *) *(&p->arena[n * x->obj_size]))
> 
> 'p' can't be right here.  It must be 'x', yes?  The result of the
> expression is a char converted to void *.  That can't be right either.
> presumably the '*' in front of the '(&' should not be there.  (And I'd
> add parentheses round all the macro arguments in the body.)

You're correct.  The original function definitions have extra
convenience macros, and the macro variables are protected from
side-effects, etc.  Of course it should be:

| #define arena_obj_addr(x, n) ((void *) *(&x->arena[n * x->obj_size]))
 
> <snip>
> >> (c) Other people might have to learn about the interface (and maybe
> >> persuade themselves of the implementation) if they come to maintain code
> >> that uses it.  Every C programmer know malloc(...).  You code, for
> >> example, does not allocate and free using pointers -- the functions take
> >> and return an int.  This is perfectly logical, but it will take some
> >> getting used for the maintainer.
> >
> > Oh, absolutely.  Using integers as a sort of offset from a base is
> > the kind of thing more common to assembly language programmers, but
> > even in C it's a common idiom to use an array index, this is instead a
> > base + offset arrangement.  Stated that way, it is easy to understand
> > what is going on in the code.  Not much of an intellectual burden.
> 
> I don't thinks it's a common idiom at all and I've see a lot of C over
> the years.  The last time I saw it was in Gregory Chaitin's tiny Lisp
> interpreter that he's used in his books and courses.  It's not exactly
> idiomatic C, but then he has bigger fish to fry.

I take it you're refering to hiding the integer in the body of the
arena object for the free list via a slightly clever cast?  One of the
strengths of C, although it is a weakness as well since the conversion
of pointer types introduces complexities that can easily trip you up.



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

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