Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Shao Miller <sha0.miller@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Malloc Query |
| Date | 2011-05-23 03:06 -0500 |
| Organization | A noiseless patient Spider |
| Message-ID | <ird11p$gra$1@dont-email.me> (permalink) |
| References | (6 earlier) <2b5874771e1859c-5f9fd@gmail.com> <22a91a32-b2c6-4ce1-bb2b-23c2455bc195@z13g2000yqg.googlegroups.com> <708913a057f3f9c-34aa7@gmail.com> <irbe4q$mi9$1@dont-email.me> <7d06059576d74e6-223c1@gmail.com> |
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.
>> 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.
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...
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.
I don't believe that your allocator should need to be concerned about
padding, but I could be mistaken.
> 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?
>
>>> 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?
>> 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?
>> 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. :)
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