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

Groups > comp.lang.c > #4267

Re: Malloc Query

Show key headers only | View raw

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.

Anyways, as I'm not an actual working scientist, measurement of every little
thing in my programs isn't much of a priority.  If it is for you,
actually implementing the arena_open() and arena_close() will take
less time than setting up your test bench.

> > 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?
> 
> (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.  In this newsgroup, when someone posts a
few screens full of code it takes time to read it.  I don't think it
would have been better if I had posted the entire source file in this
instance.
 
> (b) You might also have to port it (see the problem that BartC's code
> had on my machine for example).
> 
> (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.
 
> These all boil down to "more code".  The question remains, though, about
> the benefits.  It would be very helpful to have the speed benefit
> quantified.

I guess.  If your question bugs me enough I'll think about setting
aside a couple of hours on the weekend.



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