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

Groups > comp.lang.c > #4562

Re: Malloc Query

Show all headers | View raw

On Mon, May 23, 2011 at 03:06:29AM -0500, Shao Miller wrote:
> On 5/22/2011 1:12 PM, Uncle Steve wrote:
> >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.
> 
> Heheheh.  I was suggesting that it's more than "philosophically" and 
> more than "in spirit."  I think you are implying that a user of your 
> allocator needn't be aware of the fact that the arena is an array, or 
> that there is an "arena" at all.

More like a willful suspension of disbelief.  There are a few gotchas
with this arrangement, but the organization of the data behind the API
is mostly immaterial to any algorithm using it.  realloc() can move
the array, so you have to account for that when using a pointer
calculated from arena_obj_pointer() macro/function, but that's about
it, modulo corner cases such as the situation that comes about with
co-processors or with DMA from external devices.
 
> >>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.
> 
> I fail to understand why any C implementation would not pad structures 
> in this way.  Suppose you have an implementation that doesn't.  Suppose 
> an 'int' has a size and alignment of 4 bytes.  Suppose you have:
> 
>   struct foo {
>       int i;       /* 0 through 3 */
>       char ca[3];  /* 4 through 6 */
>       /* No padding */
>     };
> 
>   struct foo bar[2];
> 
> It would seem that the C implementation would have the 'bar' array's 
> second element's 'i' member starting at offset 7, counting from 0 and 
> relative to the first byte of the array.  That would be misaligned. 
> Adding one byte of padding would do the trick.

The question is whether the padding is added at the structure
definition or if it is accounted for when the bar[2] array is used.
No idea what the standard says about that.  As gcc supplies a 'packed'
attribute to use, I can assume that it is safe in this regard.
 
> Now I can understand if an implementation has a documented extension 
> that allows you to override such sensible padding and pack a structure 
> or specify your own padding, but use of such an extension would, in my 
> opinion, put the onus on the user to know what they're doing...

__attribute__(( packed )) applied to struct foo {...} ought to
misalign the structure elements properly.
 
> If they really want the structure above to be 7 bytes and you allocate 
> the second slot in your arena for such a structure and they try to 
> access the 'i' member at offset 7 from the beginning of your arena and 
> their CPU is angry about it...  Too bad for the user, in my opinion. 
> They need to re-think using the "packing" extension for their scenario.

Yes, which translates to reading and understanding the API
documentation.  I realize that is a nearly unacceptable burden to put
on the user, but I see no reasonable substitute for informed literacy.
 
> I don't believe that your allocator should need to be concerned about 
> padding, but I could be mistaken.

I'm taking the easy way out and leaving that decision to the
programmer.  A sensible default aligns to machine-word boundaries, but
allows it to be overridden.
 
> >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.
> 
> Ok.  So if it works with a small cycle penalty, then the CPU won't be 
> angry about it and 'i' will be read at offset 7 (continuing my example 
> above) and your allocator still works without having been worried about 
> padding.  When they chose to pack, they opted for the small cycle 
> penalty.  Should your allocator be burdened to guess at and provide 
> additional padding in order to remove the small cycle penalty?

There are two choices: yes and no.  The allocator will do either one,
so the question becomes:  which would you choose?  MIPS users may have
a different preference from those who are using x86, but then they
have to know what they're doing.  The Linux kernel apparently traps
unaligned accesses and emulates them: 

http://bit.ly/mwGxRV

PowerPC has issues with unaligned floating-point access as well
according to IBM Developer Works documentation:

http://ibm.co/6OdYj  (I guess we know who runs bit.ly?)

That article goes into some detail on the issue.  One thing that stood
out is that atomic operations fail on unaligned access for PowerPC (If
I am reading it correctly), which could cause huge problems if that
were brought about by careless use of the allocator.

I think it's safe to say that there is no substitute for reading and
understanding the documentation for your system.

> >>>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.
> 
> Ok.
> 
> >>>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 your allocator uses padding in the arena, where are the savings?

It doesn't /have/ to use padding.  That's up to the programmer.
Therefore the savings in the example above are about 25% RAM, and
possibly reduced d-cache pollution.
 
> >>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.
> 
> Agreed.  So why attempt to pad on their behalf within the allocator?

It comes down to having a sensible default.  As alignment is an issue
for some platforms, and since it is impossible to know beforehand the
platform the allocator will run on, the safe way aligns the array
slots to minimize the artifacts of misalignment.  Aligning to VM page
boundaries is about the only way I can think of to avoid all possible
unwanted interactions, but then we are off into ludicrous territory.
 
> >>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.
> 
> I didn't mean to suggest any consideration for negative 'ptrdiff_t' 
> values.  It's a signed integer type just as 'int' is a signed integer 
> type.  But because a pointer to the top of your arena minus a pointer to 
> the bottom of it yields a 'ptrdiff_t', perhaps it could be enjoyable to 
> use 'ptrdiff_t' for the addition, just for the sake of symmetry. :)

I'm not sure how that will save me from the risks inherent in the use
of ints, but I'll look into it.



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