Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utcs!mnetor!seismo!caip!princeton!allegra!ulysses!mhuxr!mhuxt!houxm!ihnp4!inuxc!pur-ee!uiucdcs!ccvaxa!aglew
From: aglew@ccvaxa.UUCP
Newsgroups: net.lang.c
Subject: Re: Yet another ALIGN idea.  (some
Message-ID: <2600067@ccvaxa>
Date: Sun, 13-Jul-86 12:44:00 EDT
Article-I.D.: ccvaxa.2600067
Posted: Sun Jul 13 12:44:00 1986
Date-Received: Mon, 14-Jul-86 22:28:30 EDT
References: <21022@<1986Jul9>
Lines: 90
Nf-ID: #R:<1986Jul9:21022:ccvaxa:2600067:000:3968
Nf-From: ccvaxa.UUCP!aglew    Jul 13 11:44:00 1986


... > Chris Torek responds to my alignof() proposal (the shorter name is
... > better):

>I think this can still be implemented with a common header file, e.g.,
>
>	#define OFFSET_TO_ALIGN(ptr)	/*something*/
>	#define	IS_ALIGNED(ptr)	(OFFSET_TO_ALIGN(ptr) == 0)
>
>On your hypothetical [strictly aligned, power of two sized]
>machine, /*something*/ may be
>
>	#define	OFFSET_TO_ALIGN(ptr)	(_offset_to_align(sizeof *(ptr)))
>
>where _offset_to_align is a library function.

He's right - I don't care if something gets stuck in the language or in a
header file - but his macros have some weaknesses. (1) They can only be 
used to determine if a pointer is correctly aligned, not to generate a 
correctly aligned pointer. Ie. given an arena from which your malloc()
draws stuff, do you run through every hole looking for IS_ALIGNED(p) where
p is what you're allocating now? And what if you have a block beginning on
a misaligned address - do you run through every byte in the block looking
for a place to start?

(2) On my hypothetical, strictly aligned, power of two sized, machine using
sizeof as the sole criterion can lead to some inefficiencies. For example,
a character string of length 2n+1 need not be allocated on a 4n boundary,
if you know that indexing is never used into the string, or if you are
willing to have indexing be slow (through explicit pointer calculations)
when it is. So you don't need to waste those 2n-1 bytes. However, since
the fields of a structure of size 2n+1 are very frequently indexed, then you
are willing to waste the memory.

---

The discussion is useful, though. We can see two needs:

[A] a predicate IS_ALIGNED(ptr,type) which returns true or false if
    the ptr is correctly aligned for an object of type.

    The predicate can handle any machine's alignment restrictions, including
    multiple plus an offset type constraints (not my idea). On most machines
    it can be implemented by a macro in a header, something like

    #define IS_ALIGNED(ptr,type) ( sizeof(type) == 1 ? 1 \
				 : sizeof(type) == 2 ? ptr & 1 \
				 : ... \
				 : !(ptr & ((1<<(ALIGN-1))-1)) )

    but Ooops! note that even on a VAX struct {char a,b;} doesn't HAVE
    to be aligned like this.

[B] Constants that can be used in writing nearly machine independent
    memory allocators.

    For a large class of machines this can most simply be done by providing
    the sizeof() the largest data type that has alignment restrictions, eg.
	
    #define ALIGN sizeof(double)

    However, that doesn't cover my favorite architecture, strictly aligned 
    power of two sized; but a macro generating the alignment constant can
    handle all architectures with alignment constraints based on multiples
    without offsets

    #define ALIGN(type)	(1<<ceil_log(sizeof(type))

    where ceil_log would have to be a function executable by the
    preprocessor.

Of course, you can say "why bother going that extra little step just for one
of Krazy Glew's hypothetical architectures..." Well (1) Even on conventional
machines that have a single upper bound on alignment restrictions,
ALIGN(type) might permit more efficient memory allocators, particularly if
the upper bound on alignments is large. It may only be a 64 bit double now,
but it is quite reasonable to see it becoming 128 bits extended precision
floating point numbers, or even 256 bits, in the near future.

(2) Such an architecture may not be hypothetical much longer... I hope,
and I have reasons for hoping.

(3) Such an architecture already exists! Surprised? I've heard of somebody
who modified a 68000 compiler to use shifting and oring instead of mutiplying
and adding to access fields of structures. Hai presto! a strictly aligned
power of two sized system. And it ran faster than conventional code. Since
memory keeps getting cheaper...

Andy "Krazy" Glew. Gould CSD-Urbana.    USEnet:  ihnp4!uiucdcs!ccvaxa!aglew
1101 E. University, Urbana, IL 61801    ARPAnet: aglew@gswd-vms