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

Groups > comp.lang.c > #4516

Re: Malloc Query

Show all headers | View raw

On Sun, May 22, 2011 at 12:37:43PM -0500, Shao Miller wrote:
> On 5/22/2011 9:46 AM, Uncle Steve wrote:
> >On Sun, May 22, 2011 at 02:49:51AM -0700, luser- -droog wrote:
> >>
> >>I've been using integer offsets instead of pointers a lot lately and
> >>I think you might be better off using the array formula explicitly:
> >>
> >>  #define arena_obj_addr(x, n) ((void *) (x->arena + n * x->obj_size))
> >>
> >>It's harder to get wrong.
> >
> >Still, you're at the mercy of transcription errors.  Philosophically,
> >the arena is an array even though the program using it does not care.
> 
> I agree, but would also like to point out that it _is_ an array object. 
>  Your 'arena' member points to its first element, if I understand your 
> code correctly.

True in spirit, but the 'array' aspect is an implementation detail.
 
> >But it would be better still to define the x->arena structure element
> >with the proper type of object so accesses would be type constrained
> >by the compiler and you would therefore get a warning if you tried to
> >assign the address to the wrong pointer.  (The following is modified
> >more from the real version, and less from the quick hack I posted.)
> 
> Heheh.  Yes but that departs further from 'malloc()', which returns a 
> 'void *'.  It seems that you are suggesting that "better," in this case,
> would be an allocator for every type.

Can do with some macro magic, although there is room for debate as to
the value of forcing type constraints when your program logic already
carries with it the assumption that it will be working with objects
of a certain size as specified when you build the arena.
 
> >
> >So,
> >
> >#define ARENA_TYPE	struct foo
> >
> >
> >struct arena_s {
> >    size_t        arena_size;
> >    int           free_list;
> >    size_t        free;
> >    ARENA_TYPE *  arena;
> >};
> >
> >And your access macro becomes:
> >
> >#define arena_obj_addr(x, n)&x->arena[n]
> >
> >since the pointer will be of the expected type.
> >
> >Even simpler.  But if your ARENA_TYPE is an odd number of bytes, this
> >can create alignment issues on some platforms.
> 
> If 'ARENA_TYPE' is a structure, oughtn't the implementation to pad 
> _every_ struct such that it can be the element type of an array?  I 
> really think so, so I don't understand your concern, here.  My 
> impression is that the 'sizeof' any type must be an integer multiple of 
> the alignment requirement, to allow for arrays...  Even unions ought to 
> contain such trailing padding, when needed.

Well, if C implementations pad out structures this way automatically
that would be a big win, but I have no way of knowing ahead of time
whether this is true for any given C compiler.  And for platform
like x86 where unaligned access works with a small cycle penalty you
can choose to pack your nine-byte structures so they don't require an
extra three bytes of alignment.  That saves twenty percent or
thereabouts for each array slot, which adds up bigtime if you have
thousands or millions of data elements.
 
> >On x86 there is merely
> >a small penalty presumably because the processor has to access two
> >32-bit words to resolve a structure element that crosses alignment
> >boundaries.  I've read that some architectures trap with a bus error
> >when you do this, so the easy solution is unworkable in practice
> >unless you carefully pad out the structure to satisfy alignment
> >requirements.
> 
> Who does "you" refer to in this last sentence?  Isn't it the 
> implementation's job to worry about padding?

'You' is whomever is hypothetically padding out structures to satisfy
alignment concerns.

> >All I've done here is move the alignment calculations
> >into the arena allocator logic, looking something like this:
> >
> >     op->obj_pad_size = (op->obj_size % pad_factor) ?
> >           (op->obj_size + pad_factor - (op->obj_size % pad_factor)) :
> >           op->obj_size;
> >
> >And so we go back to something much more like what is in the
> >previously posted benchmarking code:
> >
> >struct arena_s {
> >     size_t    obj_size;      // Size in bytes of the object
> >     size_t    obj_pad_size;  // Oobject size inclusive of padding
> >     size_t    arena_size;    // Number of obj_pad_size slots in pool
> >     int       free_list;     // Pointer to head of free list
> >     int       free;          // Number of slots remaining
> >     unsigned char *
> >               arena;         //
> >};
> >
>  
> If you are using 'malloc()' to allocate the arena, and 'malloc()' 
> returns a pointer to memory suitably aligned for _any_ object, then that 
> would seem to include an _array_ object, so again, I don't understand 
> the padding concerns.

Well, if one is using a platform that requires four-byte alignment to
access ints (for instance), but you know the algorithm only needs 24
bits of data, you /can/ pack it in to three bytes and save 25% of the
nominal storage requirements of the array.
 
> If someone tries to use your allocator with a size of "3", they had 
> better not be lying and requiring an alignment of "4", of which "3" is 
> not an integer multiple.

Except on x86, which does not demand strict alignment.  I'm leaving
alignment constraints up to the application programmer to define.  If
someone wants to shoot themselves in the foot on a platform that
requires strict alignment, who am I to argue against it?  Bloody toes
might be part of the application spec., and would therefore represent
an administrative policy beyond the scope of the allocator proper.
 
> >typedef struct arena_s arena;
> >w
> >
> >I do in fact have a function to calculate arena_obj_addr(), and it
> >necessarily contains
> >
> >    &p->arena[n * p->obj_pad_size]
> 
> Or, equivalently:
> 
>   p->arena + n * p->obj_pad_size
> 
> >
> >which is of course necessary since we can't calculate obj_pad_size
> >before we know what the target object is and the run-time platform
> >constraints.  No real real reason it couldn't be "&p->arena + n *
> >p->obj_pad_size", but I didn't do it that way.
> 
> (Without the '&', else your element size is 'sizeof (ARENA_TYPE *)')

Yes, sorry.  The ampersand is superfluous in that usage.
 
> >I guess the pointer
> >conversions don't cause my brain to lock-up the way they used to.
> 
> Using an 'int' and macro/function?  Seems reasonable to me, though 
> perhaps a 'ptrdiff_t' could be pleasant, too. :)

I doubt it.  If you're careful not to do pointer arithmetic where you
might get a negative offset, life is good.  While I would not
disparage the utility of negative pointer offsets in certain
situations, it isn't completely necessary.  "ptr - unsigned int"
should do the right thing.  So far, I have not come across a situation
where I would need negative pointer offsets, making the use of
ptrdiff_t a moot issue, IMO.  YMMV.



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