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

Groups > comp.lang.c > #126321 > unrolled thread

Aligned Issue when malloc()

Back to article view | Back to comp.lang.c

Contents

  Aligned Issue when malloc() hwding <m@amastigote.com> - 2018-02-06 01:17 -0800
    Re: Aligned Issue when malloc() Ian Collins <ian-news@hotmail.com> - 2018-02-06 22:41 +1300
    Re: Aligned Issue when malloc() Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-06 11:52 +0000
      Re: Aligned Issue when malloc() hwding <m@amastigote.com> - 2018-02-06 04:35 -0800
        Re: Aligned Issue when malloc() Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-06 13:48 +0000
          Re: Aligned Issue when malloc() "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid> - 2018-02-06 12:55 -0800
        Re: Aligned Issue when malloc() Richard Damon <Richard@Damon-Family.org> - 2018-02-06 08:52 -0500
          Re: Aligned Issue when malloc() "James R. Kuyper" <jameskuyper@verizon.net> - 2018-02-06 09:59 -0500
            Re: Aligned Issue when malloc() supercat@casperkitty.com - 2018-02-06 07:20 -0800
              Re: Aligned Issue when malloc() Robert Wessel <robertwessel2@yahoo.com> - 2018-02-06 11:50 -0600
              Re: Aligned Issue when malloc() Keith Thompson <kst-u@mib.org> - 2018-02-06 11:34 -0800
              Re: Aligned Issue when malloc() Egor <egor@ruby.local> - 2018-02-09 16:20 +0200
                Re: Aligned Issue when malloc() supercat@casperkitty.com - 2018-02-15 08:56 -0800
                  Re: Aligned Issue when malloc() Egor <egor@ruby.local> - 2018-02-15 19:35 +0200
                    Re: Aligned Issue when malloc() supercat@casperkitty.com - 2018-02-15 11:27 -0800
                      Re: Aligned Issue when malloc() Egor <egor@ruby.local> - 2018-02-16 02:48 +0200
                        Re: Aligned Issue when malloc() supercat@casperkitty.com - 2018-02-16 08:49 -0800
        Re: Aligned Issue when malloc() "James R. Kuyper" <jameskuyper@verizon.net> - 2018-02-06 09:41 -0500

#126321 — Aligned Issue when malloc()

In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions, 
before certain size of memory segment is allocated,
the custom allocater always ask for an extra space to record
the information(the size) of this piece of memory.

void *chunk = malloc(sz + ALIGNMENT);
if (!chunk) return chunk;
total_allocated += sz;
*(size_t*)chunk = sz; // size is written here

Then we use the macro function to return the real starting address
of that memory segment.

return OUTPTR(chunk);

The definitions:

/* This union's purpose is to be as big as the largest of all the
 * types it contains. */
union alignment {
    size_t sz;
    void *ptr;
    double dbl;
};
/* We need to make sure that everything we return is on the right
   alignment to hold anything, including a double. */
#define ALIGNMENT sizeof(union alignment)

/* We need to do this cast-to-char* trick on our pointers to adjust
   them; doing arithmetic on a void* is not standard. */
#define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
#define INPTR(ptr) (((char*)ptr)-ALIGNMENT)

Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
the void * and double type are claimed in the union alignment?

[toc] | [next] | [standalone]

#126323

On 02/06/2018 10:17 PM, hwding wrote:
> In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions,
> before certain size of memory segment is allocated,
> the custom allocater always ask for an extra space to record
> the information(the size) of this piece of memory.
> 
> void *chunk = malloc(sz + ALIGNMENT);
> if (!chunk) return chunk;
> total_allocated += sz;
> *(size_t*)chunk = sz; // size is written here
> 
> Then we use the macro function to return the real starting address
> of that memory segment.
> 
> return OUTPTR(chunk);
> 
> The definitions:
> 
> /* This union's purpose is to be as big as the largest of all the
>   * types it contains. */
> union alignment {
>      size_t sz;
>      void *ptr;
>      double dbl;
> };
> /* We need to make sure that everything we return is on the right
>     alignment to hold anything, including a double. */
> #define ALIGNMENT sizeof(union alignment)
> 
> /* We need to do this cast-to-char* trick on our pointers to adjust
>     them; doing arithmetic on a void* is not standard. */
> #define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
> #define INPTR(ptr) (((char*)ptr)-ALIGNMENT)
> 
> Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
> the void * and double type are claimed in the union alignment?

To ensure the returned pointer remains suitably aligned for any built-in 
type (assuming double has the strictest alignment requirement in this case).

-- 
Ian.

[toc] | [prev] | [next] | [standalone]

#126326

hwding <m@amastigote.com> writes:

> In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions, 
> before certain size of memory segment is allocated,
> the custom allocater always ask for an extra space to record
> the information(the size) of this piece of memory.
>
> void *chunk = malloc(sz + ALIGNMENT);
> if (!chunk) return chunk;
> total_allocated += sz;
> *(size_t*)chunk = sz; // size is written here
>
> Then we use the macro function to return the real starting address
> of that memory segment.
>
> return OUTPTR(chunk);
>
> The definitions:
>
> /* This union's purpose is to be as big as the largest of all the
>  * types it contains. */
> union alignment {
>     size_t sz;
>     void *ptr;
>     double dbl;
> };
> /* We need to make sure that everything we return is on the right
>    alignment to hold anything, including a double. */
> #define ALIGNMENT sizeof(union alignment)
>
> /* We need to do this cast-to-char* trick on our pointers to adjust
>    them; doing arithmetic on a void* is not standard. */
> #define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
> #define INPTR(ptr) (((char*)ptr)-ALIGNMENT)
>
> Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
> the void * and double type are claimed in the union alignment?

The question has been answered, so I'll just suggest out that this could
be written a bit more clearly using a flexible array member (or the
"struck hack" for older C.  Start with

  struct allocation {
       size_t size;
       union {
            size_t s;
            void *p;
            double d;
       } data[];
  };

and the allocation code becomes

   struct allocation *p = malloc(sizeof *p + size);
   p->size = size;
   return p->data;

The code to convert the data back to the struct pointer can be made more
general than the rather basic INPTR macro

  static inline struct allocation *inptr(void *p)
  {
       return (void *)((char *)p - offsetof(struct allocation, data));
  }

because this function allows simple access to the size data via

  inptr(p)->size;

but a macro

  #define INPTR(ptr) ((char *)(ptr) - offsetof(struct allocation, data))

will do if this extra convenience is not required.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#126327

在 2018年2月6日星期二 UTC+8下午7:52:27，Ben Bacarisse写道：
> hwding <m@amastigote.com> writes:
> 
> > In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions, 
> > before certain size of memory segment is allocated,
> > the custom allocater always ask for an extra space to record
> > the information(the size) of this piece of memory.
> >
> > void *chunk = malloc(sz + ALIGNMENT);
> > if (!chunk) return chunk;
> > total_allocated += sz;
> > *(size_t*)chunk = sz; // size is written here
> >
> > Then we use the macro function to return the real starting address
> > of that memory segment.
> >
> > return OUTPTR(chunk);
> >
> > The definitions:
> >
> > /* This union's purpose is to be as big as the largest of all the
> >  * types it contains. */
> > union alignment {
> >     size_t sz;
> >     void *ptr;
> >     double dbl;
> > };
> > /* We need to make sure that everything we return is on the right
> >    alignment to hold anything, including a double. */
> > #define ALIGNMENT sizeof(union alignment)
> >
> > /* We need to do this cast-to-char* trick on our pointers to adjust
> >    them; doing arithmetic on a void* is not standard. */
> > #define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
> > #define INPTR(ptr) (((char*)ptr)-ALIGNMENT)
> >
> > Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
> > the void * and double type are claimed in the union alignment?
> 
> The question has been answered, so I'll just suggest out that this could
> be written a bit more clearly using a flexible array member (or the
> "struck hack" for older C.  Start with
> 
>   struct allocation {
>        size_t size;
>        union {
>             size_t s;
>             void *p;
>             double d;
>        } data[];
>   };
> 
> and the allocation code becomes
> 
>    struct allocation *p = malloc(sizeof *p + size);
>    p->size = size;
>    return p->data;
> 
> The code to convert the data back to the struct pointer can be made more
> general than the rather basic INPTR macro
> 
>   static inline struct allocation *inptr(void *p)
>   {
>        return (void *)((char *)p - offsetof(struct allocation, data));
>   }
> 
> because this function allows simple access to the size data via
> 
>   inptr(p)->size;
> 
> but a macro
> 
>   #define INPTR(ptr) ((char *)(ptr) - offsetof(struct allocation, data))
> 
> will do if this extra convenience is not required.
> 
> -- 
> Ben.

Thanks for the answers, Ben & lan.
Now I think I'm clear with this "struct hack" stuff.
But I'm wondering why we choose void * and double
but not int, key_t or float?

What is "strictest alignment"?

[toc] | [prev] | [next] | [standalone]

#126329

hwding <m@amastigote.com> writes:
<snip>
> Thanks for the answers, Ben & lan.
> Now I think I'm clear with this "struct hack" stuff.
> But I'm wondering why we choose void * and double
> but not int, key_t or float?
>
> What is "strictest alignment"?

Someone chose those types in an attempt to get the strictest alignment,
but there is no reliable way to do that using a union.  A long double
may need more alignment, structs may need more, even arrays of int may
need more.

In modern C, there is an _Alignof operator, so the way to do this now is
to rely on the fact that malloc allocates storage aligned for any type,
and to put the size at the end, suitably aligned -- since you know the
type, you can make sure it is correctly aligned.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#126345

On 2/6/2018 5:48 AM, Ben Bacarisse wrote:
> hwding <m@amastigote.com> writes:
> <snip>
>> Thanks for the answers, Ben & lan.
>> Now I think I'm clear with this "struct hack" stuff.
>> But I'm wondering why we choose void * and double
>> but not int, key_t or float?
>>
>> What is "strictest alignment"?
> 
> Someone chose those types in an attempt to get the strictest alignment,
> but there is no reliable way to do that using a union.  A long double
> may need more alignment, structs may need more, even arrays of int may
> need more.
> 
> In modern C, there is an _Alignof operator, so the way to do this now is
> to rely on the fact that malloc allocates storage aligned for any type,
> and to put the size at the end, suitably aligned -- since you know the
> type, you can make sure it is correctly aligned.
> 

Fwiw, wrt _Alignof and older C, well, check this hack out:
________________________
#define RALLOC_ALIGN_OF(mp_type) \
   offsetof( \
     struct { \
       char pad_RALLOC_ALIGN_OF; \
       mp_type type_RALLOC_ALIGN_OF; \
     }, \
     type_RALLOC_ALIGN_OF \
   )
________________________

used in my old region allocator, try to look past the nasty hacks... ;^)

https://pastebin.com/raw/f37a23918

lol.

[toc] | [prev] | [next] | [standalone]

#126330

On 2/6/18 7:35 AM, hwding wrote:
> 在 2018年2月6日星期二 UTC+8下午7:52:27，Ben Bacarisse写道：
>> hwding <m@amastigote.com> writes:
>>
>>> In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions,
>>> before certain size of memory segment is allocated,
>>> the custom allocater always ask for an extra space to record
>>> the information(the size) of this piece of memory.
>>>
>>> void *chunk = malloc(sz + ALIGNMENT);
>>> if (!chunk) return chunk;
>>> total_allocated += sz;
>>> *(size_t*)chunk = sz; // size is written here
>>>
>>> Then we use the macro function to return the real starting address
>>> of that memory segment.
>>>
>>> return OUTPTR(chunk);
>>>
>>> The definitions:
>>>
>>> /* This union's purpose is to be as big as the largest of all the
>>>   * types it contains. */
>>> union alignment {
>>>      size_t sz;
>>>      void *ptr;
>>>      double dbl;
>>> };
>>> /* We need to make sure that everything we return is on the right
>>>     alignment to hold anything, including a double. */
>>> #define ALIGNMENT sizeof(union alignment)
>>>
>>> /* We need to do this cast-to-char* trick on our pointers to adjust
>>>     them; doing arithmetic on a void* is not standard. */
>>> #define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
>>> #define INPTR(ptr) (((char*)ptr)-ALIGNMENT)
>>>
>>> Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
>>> the void * and double type are claimed in the union alignment?
>>
>> The question has been answered, so I'll just suggest out that this could
>> be written a bit more clearly using a flexible array member (or the
>> "struck hack" for older C.  Start with
>>
>>    struct allocation {
>>         size_t size;
>>         union {
>>              size_t s;
>>              void *p;
>>              double d;
>>         } data[];
>>    };
>>
>> and the allocation code becomes
>>
>>     struct allocation *p = malloc(sizeof *p + size);
>>     p->size = size;
>>     return p->data;
>>
>> The code to convert the data back to the struct pointer can be made more
>> general than the rather basic INPTR macro
>>
>>    static inline struct allocation *inptr(void *p)
>>    {
>>         return (void *)((char *)p - offsetof(struct allocation, data));
>>    }
>>
>> because this function allows simple access to the size data via
>>
>>    inptr(p)->size;
>>
>> but a macro
>>
>>    #define INPTR(ptr) ((char *)(ptr) - offsetof(struct allocation, data))
>>
>> will do if this extra convenience is not required.
>>
>> -- 
>> Ben.
> 
> Thanks for the answers, Ben & lan.
> Now I think I'm clear with this "struct hack" stuff.
> But I'm wondering why we choose void * and double
> but not int, key_t or float?
> 
> What is "strictest alignment"?
> 

On many machines 'large' types need to be suitably aligned for the 
hardware to access them (or maybe just to access efficiently). 
Inevitably, the larger types need stricter alignment, void * will have 
the strictest alignment of any data pointer (to really be safe, you 
probably should add some generic function pointer here too). Double will 
have at least as strict alignment as float, since it will be at least as 
big.

I suspect this is old code, and predates newer standards, because today 
you would need to add long double which might have larger requirements 
than double, and uintmax_t which is the largest integer type. (from C99)

Even simpler would be to use max_align_t if you can insist on C11 support.

[toc] | [prev] | [next] | [standalone]

#126335

On 02/06/2018 08:52 AM, Richard Damon wrote:
...
> I suspect this is old code, and predates newer standards, because today
> you would need to add long double which might have larger requirements
> than double, ...

Many people incorrectly think that long double was added in C99. I 
couldn't be sure from your wording whether you shared that 
misconception. In fact, it has been a standard C type for as long as 
there has been a C standard.

[toc] | [prev] | [next] | [standalone]

#126336

On Tuesday, February 6, 2018 at 8:59:40 AM UTC-6, James R. Kuyper wrote:
> On 02/06/2018 08:52 AM, Richard Damon wrote:
> ...
> > I suspect this is old code, and predates newer standards, because today
> > you would need to add long double which might have larger requirements
> > than double, ...
> 
> Many people incorrectly think that long double was added in C99. I 
> couldn't be sure from your wording whether you shared that 
> misconception. In fact, it has been a standard C type for as long as 
> there has been a C standard.

So far as I can tell, the "long double" type was traditionally either a
synonym for "double", or else an IEEE 80-bit extended type; while there
may have been some platforms in 1989 that would store an 80-bit type
with 64-bit alignment (and 48 padding bits), I would expect that it was
far more often stored with 16-bit or 32-bit alignment (using zero or 16
padding bits).  Note that if a 64-bit platform supports 32-bit loads and
stores, there may be no advantage to forcing 64-bit alignment since each
value would require one 64-bit and one 32-bit operation.

[toc] | [prev] | [next] | [standalone]

#126338

On Tue, 6 Feb 2018 07:20:13 -0800 (PST), supercat@casperkitty.com
wrote:

>On Tuesday, February 6, 2018 at 8:59:40 AM UTC-6, James R. Kuyper wrote:
>> On 02/06/2018 08:52 AM, Richard Damon wrote:
>> ...
>> > I suspect this is old code, and predates newer standards, because today
>> > you would need to add long double which might have larger requirements
>> > than double, ...
>> 
>> Many people incorrectly think that long double was added in C99. I 
>> couldn't be sure from your wording whether you shared that 
>> misconception. In fact, it has been a standard C type for as long as 
>> there has been a C standard.
>
>So far as I can tell, the "long double" type was traditionally either a
>synonym for "double", or else an IEEE 80-bit extended type; while there
>may have been some platforms in 1989 that would store an 80-bit type
>with 64-bit alignment (and 48 padding bits), I would expect that it was
>far more often stored with 16-bit or 32-bit alignment (using zero or 16
>padding bits).  Note that if a 64-bit platform supports 32-bit loads and
>stores, there may be no advantage to forcing 64-bit alignment since each
>value would require one 64-bit and one 32-bit operation.


128-bit float has been a part of the S/360 line for a long time,
starting with the 360/67.  It became a part of the official ISA with
S/370 (as opposed to a model-specific extension), but was an optional
component.

There was a GCC port for S/370 in that era, although I really don't
know if they supported a long double type, or what its alignment
requirements were.

There is apparently some maintenance of that old GCC port (which is
totally unrelated to the current support for the platform in GCC),
although someone is still maintaining it for historical purposes
(based on GCC 3.2).

There was also an IBM C compiler in that era, and I can't find any
archived documentation, but it too would have used 128-bit long
doubles if it supported them.

The current IBM C/C++ compiler for the platform does, of course,
support 128-bit long doubles (in both IEEE and IBM hex FP forms), but
aligns to a 64-bit boundary.  I *think*, but am not sure, that the
current GCC follows that pattern as well.

[toc] | [prev] | [next] | [standalone]

#126340

supercat@casperkitty.com writes:
> On Tuesday, February 6, 2018 at 8:59:40 AM UTC-6, James R. Kuyper wrote:
>> On 02/06/2018 08:52 AM, Richard Damon wrote:
>> ...
>> > I suspect this is old code, and predates newer standards, because today
>> > you would need to add long double which might have larger requirements
>> > than double, ...
>> 
>> Many people incorrectly think that long double was added in C99. I 
>> couldn't be sure from your wording whether you shared that 
>> misconception. In fact, it has been a standard C type for as long as 
>> there has been a C standard.
>
> So far as I can tell, the "long double" type was traditionally either a
> synonym for "double", or else an IEEE 80-bit extended type; while there
> may have been some platforms in 1989 that would store an 80-bit type
> with 64-bit alignment (and 48 padding bits), I would expect that it was
> far more often stored with 16-bit or 32-bit alignment (using zero or 16
> padding bits).  Note that if a 64-bit platform supports 32-bit loads and
> stores, there may be no advantage to forcing 64-bit alignment since each
> value would require one 64-bit and one 32-bit operation.

To summarize, if you need to define a union with strictest alignment, it
makes sense to include both double and long double members, since it's
at least possible that double could require stricter alignment than long
double.  Even if it's unnecessary, it won't hurt.

As others have mentioned, C11 adds max_align_t in <stddef.h>, making all
this union stuff unnecessary.  Or you can use alignof (_Alignof) to
determine the actual alignment of the type you're using.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#126476

supercat@casperkitty.com wrote:
> So far as I can tell, the "long double" type was traditionally either a
> synonym for "double", or else an IEEE 80-bit extended type; while there
> may have been some platforms in 1989 that would store an 80-bit type
> with 64-bit alignment (and 48 padding bits), I would expect that it was
> far more often stored with 16-bit or 32-bit alignment (using zero or 16
> padding bits).  Note that if a 64-bit platform supports 32-bit loads and
> stores, there may be no advantage to forcing 64-bit alignment since each
> value would require one 64-bit and one 32-bit operation.
80-bit real type is not really intended for storage. It is even called
"temporary real" in some sources. The point is to be able to convert
to/from int64 without precission loss. (Also, in general, it improves
precision of computations which end up saved as double)

Say you want to multiply a big (from 53 bits in width) integer by a
small real, and save result as int. First you'd lose less significant
bits of the int by converting it to double, and then when converting it
back, you'd have an int with least significant bits zeroed out. Using
extended reals, this problem is avoided.

Least significan bits of mantissa are the most affected by precission
loss on complicated computations, which means that getting your results
in 80-bits will not nescessarely give more accurate results (precise,
yes, but not accurate,) as all fp computations are done internally in
80-bits (well, at least on x86 it's done this way,) so while doubles
stay accurate, because lower bits are thrown away, the extended reals
don't have those inaccure "slack" bits. This is why I think it's not
intended for storage outside of fpu registers.

By the way, on some systems (8088+8087) these can be 8-bit aligned :P

[toc] | [prev] | [next] | [standalone]

#126739

On Friday, February 9, 2018 at 8:21:35 AM UTC-6, Egor wrote:
> supercat@casperkitty.com wrote:
> > So far as I can tell, the "long double" type was traditionally either a
> > synonym for "double", or else an IEEE 80-bit extended type; while there
> > may have been some platforms in 1989 that would store an 80-bit type
> > with 64-bit alignment (and 48 padding bits), I would expect that it was
> > far more often stored with 16-bit or 32-bit alignment (using zero or 16
> > padding bits).  Note that if a 64-bit platform supports 32-bit loads and
> > stores, there may be no advantage to forcing 64-bit alignment since each
> > value would require one 64-bit and one 32-bit operation.
> 80-bit real type is not really intended for storage. It is even called
> "temporary real" in some sources. The point is to be able to convert
> to/from int64 without precission loss. (Also, in general, it improves
> precision of computations which end up saved as double)
> 
> Say you want to multiply a big (from 53 bits in width) integer by a
> small real, and save result as int. First you'd lose less significant
> bits of the int by converting it to double, and then when converting it
> back, you'd have an int with least significant bits zeroed out. Using
> extended reals, this problem is avoided.
> 
> Least significan bits of mantissa are the most affected by precission
> loss on complicated computations, which means that getting your results
> in 80-bits will not nescessarely give more accurate results (precise,
> yes, but not accurate,) as all fp computations are done internally in
> 80-bits (well, at least on x86 it's done this way,) so while doubles
> stay accurate, because lower bits are thrown away, the extended reals
> don't have those inaccure "slack" bits. This is why I think it's not
> intended for storage outside of fpu registers.
> 
> By the way, on some systems (8088+8087) these can be 8-bit aligned :P

The fact that an 80-bit type is large enough to hold all integer types is
certainly convenient, but a bigger issue is that if wants to evaluate
something like

   a = b+c+d;

using values of type "double" on a system without an FPU, the system will
waste a fair amount of time normalizing the mantissa of (b+c), then shifting
and packing the mantissa and exponent to cram everything into an 8-byte
"double", and then unpacking the value that it had just spent time packing.
Having a type that can hold (b+c) without a normalizing or packing step
before adding d will yield computations which are not only more accurate but
also *faster*.

A point which language designers and compiler writers miss, however, is that
extra-precision intermediate types are a good thing only if there is a type
in the language which can actually hold them.  Storage efficiency won't
usually matter, since most values should be stored using "double", but given
an expression like:

   (x-y)*(x-y);

it should be possible for the programmer to eliminate the redundant
expression (x-y) without affecting the computed result.  Platforms which
use 80-bit computations but make "long double" only 64 bits violate that
principle.

[toc] | [prev] | [next] | [standalone]

#126745

supercat@casperkitty.com wrote:
> The fact that an 80-bit type is large enough to hold all integer types is
> certainly convenient, but a bigger issue is that if wants to evaluate
> something like
> 
>    a = b+c+d;
> 
> using values of type "double" on a system without an FPU, the system will
> waste a fair amount of time normalizing the mantissa of (b+c), then shifting
> and packing the mantissa and exponent to cram everything into an 8-byte
> "double", and then unpacking the value that it had just spent time packing.
> Having a type that can hold (b+c) without a normalizing or packing step
> before adding d will yield computations which are not only more accurate but
> also *faster*.
> 
> A point which language designers and compiler writers miss, however, is that
> extra-precision intermediate types are a good thing only if there is a type
> in the language which can actually hold them.  Storage efficiency won't
> usually matter, since most values should be stored using "double", but given
> an expression like:
> 
>    (x-y)*(x-y);
> 
> it should be possible for the programmer to eliminate the redundant
> expression (x-y) without affecting the computed result.  Platforms which
> use 80-bit computations but make "long double" only 64 bits violate that
> principle.

It's okay to use long doubles for temp variables, but I can't imagine a
scenario where you'd need to store intermediate computation in an
aligned array allocated by malloc, hence why I think that proper
alignment of long doubles is not an important matter.

[toc] | [prev] | [next] | [standalone]

#126746

On Thursday, February 15, 2018 at 12:09:03 PM UTC-6, Egor wrote:
> It's okay to use long doubles for temp variables, but I can't imagine a
> scenario where you'd need to store intermediate computation in an
> aligned array allocated by malloc, hence why I think that proper
> alignment of long doubles is not an important matter.

How about an interpreter for a language which includes that data type, and
which might need to maintain a "stack" [seem by the interpreted code] which
includes that data type?

[toc] | [prev] | [next] | [standalone]

#126771

supercat@casperkitty.com wrote:
> How about an interpreter for a language which includes that data type, and
> which might need to maintain a "stack" [seem by the interpreted code] which
> includes that data type?
Any alignment would do, as I'd doubt there are any systems with 80-bit
reals *and* with strict alignment, so it will be only an issue of
performance, and even then it wouldn't be that bad.

There are two options:
- 64-bit alignment. Memory buses on modern PCs are 64-bit, so having a
  bigger alignment than that would be a waste.
- 40-byte alignment. Least common multiple between 64-bit and 80-bit.
  This is the generic approach that doesn't treat long double
  differently from other types.

[toc] | [prev] | [next] | [standalone]

#126805

On Thursday, February 15, 2018 at 6:58:25 PM UTC-6, Egor wrote:
> supercat@casperkitty.com wrote:
> > How about an interpreter for a language which includes that data type, and
> > which might need to maintain a "stack" [seem by the interpreted code] which
> > includes that data type?
> Any alignment would do, as I'd doubt there are any systems with 80-bit
> reals *and* with strict alignment, so it will be only an issue of
> performance, and even then it wouldn't be that bad.
> 
> There are two options:
> - 64-bit alignment. Memory buses on modern PCs are 64-bit, so having a
>   bigger alignment than that would be a waste.
> - 40-byte alignment. Least common multiple between 64-bit and 80-bit.
>   This is the generic approach that doesn't treat long double
>   differently from other types.

I don't think that alignment would pose a particular problem for such
interpreters, since platforms that have such types would likely store them
as 80-, 96-, or 128-bit types with proper alignment; my point was simply
that a language interpreter would be a real-world application that could
need to store extended-precision values in an array-type structure using
storage received from malloc().  Since malloc() must return storage that
satisfies the coarsest alignment requirement of any C data type, the only
issue would be assuring that a heterogeneous stack's pointer remains aligned
for all types that will be pushed.

[toc] | [prev] | [next] | [standalone]

#126333

On 02/06/2018 07:35 AM, hwding wrote:
> 在 2018年2月6日星期二 UTC+8下午7:52:27，Ben Bacarisse写道：
>> hwding <m@amastigote.com> writes:
>>
>>> In the libevent manual, memory management chapter(http://www.wangafu.net/%7Enickm/libevent-book/Ref1_libsetup.html), when we use our own allocating functions,
>>> before certain size of memory segment is allocated,
>>> the custom allocater always ask for an extra space to record
>>> the information(the size) of this piece of memory.
>>>
>>> void *chunk = malloc(sz + ALIGNMENT);
>>> if (!chunk) return chunk;
>>> total_allocated += sz;
>>> *(size_t*)chunk = sz; // size is written here
>>>
>>> Then we use the macro function to return the real starting address
>>> of that memory segment.
>>>
>>> return OUTPTR(chunk);
>>>
>>> The definitions:
>>>
>>> /* This union's purpose is to be as big as the largest of all the
>>>   * types it contains. */
>>> union alignment {
>>>      size_t sz;
>>>      void *ptr;
>>>      double dbl;
>>> };
>>> /* We need to make sure that everything we return is on the right
>>>     alignment to hold anything, including a double. */
>>> #define ALIGNMENT sizeof(union alignment)
>>>
>>> /* We need to do this cast-to-char* trick on our pointers to adjust
>>>     them; doing arithmetic on a void* is not standard. */
>>> #define OUTPTR(ptr) (((char*)ptr)+ALIGNMENT)
>>> #define INPTR(ptr) (((char*)ptr)-ALIGNMENT)
>>>
>>> Since only the size_t sz is used in my_malloc, my_realloc and my_free, why
>>> the void * and double type are claimed in the union alignment?
>>
>> The question has been answered, so I'll just suggest out that this could
>> be written a bit more clearly using a flexible array member (or the
>> "struck hack" for older C.  Start with
>>
>>    struct allocation {
>>         size_t size;
>>         union {
>>              size_t s;
>>              void *p;
>>              double d;
>>         } data[];
>>    };
>>
>> and the allocation code becomes
>>
>>     struct allocation *p = malloc(sizeof *p + size);
>>     p->size = size;
>>     return p->data;
>>
>> The code to convert the data back to the struct pointer can be made more
>> general than the rather basic INPTR macro
>>
>>    static inline struct allocation *inptr(void *p)
>>    {
>>         return (void *)((char *)p - offsetof(struct allocation, data));
>>    }
>>
>> because this function allows simple access to the size data via
>>
>>    inptr(p)->size;
>>
>> but a macro
>>
>>    #define INPTR(ptr) ((char *)(ptr) - offsetof(struct allocation, data))
>>
>> will do if this extra convenience is not required.
>>
>> -- 
>> Ben.
> 
> Thanks for the answers, Ben & lan.
> Now I think I'm clear with this "struct hack" stuff.
> But I'm wondering why we choose void * and double
> but not int, key_t or float?
> 
> What is "strictest alignment"?

On many (most? all?) computer systems, for particular data types there 
are particular evenly-spaced locations in memory where it is preferred 
to locate objects of that type. The spacing between those locations is 
referred to as the alignment requirement of that type. In some cases, 
being correctly aligned is an absolute requirement; the only way to 
perform operations on misaligned data is to first copy it, byte by byte, 
into correctly aligned memory, perform the operations, and then copy it 
back. On other systems, operations on mis-aligned objects are just 
slower than operations on correctly aligned data.

Each implementation of C can have different alignment requirements. An 
implementation of C will place objects in locations that are correctly 
aligned for the object's type, and a program has undefined behavior if 
it attempts to convert a pointer to one type into a pointer of another 
type if the original pointer points at memory not correctly aligned for 
the new pointed-at type.

Because of the way arrays work, the size of an object type must be an 
integer multiple of the alignment requirement for that type. In 
particular, this implies that char, signed char, and unsigned char must 
have alignment requirements of 1. If a two byte type has an alignment 
requirement of 4 bytes, then as far as C is concerned, the size of an 
object of that type must be at least 4 bytes, meaning that the 
implementation must add two bytes of padding.

Because of the way that arrays of structs work, and the fact that 
offsetof(struct_type,member) is a compile time constant, the alignment 
requirement for a struct type must be a multiple of each of the 
alignment requirements for the types stored in that struct. The smallest 
possible alignment requirement for a struct is therefore the Least 
Common Multiple (LCM) of those alignment requirements. Thus, if an int 
had an alignment requirement of 3, and a long had an alignment 
requirement of 5, then the alignment requirement for a struct containing 
both an int and a long would have to have to be an integer multiple of 15.

Since all members of a union start at the same location in memory, that 
location must be correctly aligned for all of the types in the union, so 
the union itself must also have an alignment requirement that is an 
integer multiple of the LCM of the alignment requirements of it's member 
types.

malloc(), calloc(), and realloc() are required to return a pointer 
suitably aligned for all data types, and the same is intended to be true 
of the custom allocator you're studying.

Prior to C2011, there was no direct way to know what the alignment 
requirement of an arbitrary type was. If you had the following struct type:

	struct align{char a; T t};

Then offsetof(struct align, t) was guaranteed to be a multiple of the 
alignment requirement for T, and on most implementations is likely to be 
the actual alignment for most types.

The custom allocator you're using attempts to determine the maximum 
alignment requirement for any type, by putting several different types 
in a union, and looking at the sizeof the union. It would be slightly 
better to use "union alignment" as T in the struct above, because 
sizeof(union alignment) might be an integer multiple, greater than 1, of 
the actual alignment requirement. The offsetof() approach is likely to 
give you the actual requirement.

However, prior to C2011, there was no finite list of types that could be 
put into "union alignment" to guarantee that it included the type that 
had the largest alignment requirement. The best you could do was choose 
a finite list that's likely to include one of the most strictly aligned 
types, and size_t, void* and double are good choices for that list; but 
I would have included a function pointer type, and I would have used 
long rather than size_t. For C99 I would have used intmax_t rather than 
long.

In C2011, many new features were added to make it easier to deal with 
alignment issues. _Alignof(type) now gives the alignment requirement for 
a given type. _Alignas(n) can be added to the declaration of an object, 
forcing it to be placed in a location suitable for an alignment 
requirement of n (this is only useful if n > _Alignof(type). 
_Alignas(type) is equivalent to _Alignas(_Alignof(type)). <stddef.h> now 
typedefs max_align_t as a type that has the maximum alignment 
requirement of any type supported by that implementation of C, so you 
would now use

     #define ALIGNMENT _Alignof(max_align_t)

Alignment requirements are now required to be powers of 2 - the 
committee made that decision only after reaching the conclusion that 
this was already the case for essentially every platform that ever had 
been or ever might plausibly be a target for an implementation of C. As 
a result, the LCM that I referred to above is now guaranteed to be the 
same as the largest alignment.

aligned_alloc() is a new function that works similarly to the other 
members of the malloc() family, except that it returns memory aligned to 
the specified requirement, which might be less strict than the maximum 
alignment requirement. If you look over your custom allocator code, I 
hope you can see that it's possible (though not guaranteed) for 
aligned_alloc(_Alignof(T), count*sizeof(T)) to waste less memory due to 
alignment requirements than the other members of the malloc() family 
would, if _Alignof(T) < _Alignof(max_align_t).

Note: _Alignas() and aligned_alloc() both have a requirement that the 
alignment they are given must a valid alignment supported by the 
implementation, and each implementation is allowed to have a different 
set of valid alignment requirements. Therefore, I strongly recommend 
never giving either of them any alignment requirement larger than 1 
unless that number has been obtained by using _Alignof(type).

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web