hello all ,
in the paper "engineering a sort function ", the author has used a
code fragment like:
typedef long WORD
Missing a semicolon here.
#define W sizeof(WORD)
#define SWAPINIT(a,es) swaptype= \
(a-(char*)0 | es) % W? 2 : es>W?: 1:0
They actually have an array a of objects of size es and what they do
with this code is determine what type of swapping they will be doing
depending upon the alignment of the object , 'a' is an array of. So if
'a' is not *appropriately aligned* they swap byte by byte else world
by word.
Now i had two questions on the above code .
1. How does it determine if the object is not appropriately aligned
( means the case when it sets swaptype=2)?
It's using a non-portable trick, not guaranteed by the
C language to work -- but in practice, it'll work "almost
everywhere." In the code, `a' is a char* pointer to the first
element of the array of items being sorted, and the expression
`a-(char*)0' is the "distance" from the "start of memory" to
the start of the array. C does not guarantee that this will
be a meaningful value, or even that it can be evaluated, but
in practice it turns out to be stated distance (except that it
might be negative if `a' points to "high memory").
This distance is ... what? Well, on most machines it's just
the address `a' itself, but converted to some kind of integer.
Why didn't the authors just write a cast and do the conversion
directly? Probably because they couldn't be sure what integer
type would be appropriate: the widths of integers and pointers
tend to vary from one implementation to the next. So `a-(char*)0'
is really just a sneaky way to convert the address `a' to an
integer, while being coy about exactly what kind of integer is
actually used.
Okay, so they've turned the address into an integer; now
what? The next not-strictly-portable-but-usually-reliable
assumption is that addresses are very much like numbers: Your
address space consists of byte 0, byte 1, ..., byte BIGNUMBER
(possibly with some gaps). The alignment requirement for a
type may limit which of these bytes an object of that type can
begin on: For example, a WORD might be constrained to begin on
a byte whose number is divisible by four, or maybe two, or maybe
something else. Whatever that divisibility condition is, we can
deduce (from the fact that arrays work) that the alignment divisor
is a divisor of the object's size: The alignment requirement for
a WORD is a divisor of sizeof(WORD). If sizeof(WORD) is 8, the
alignment divisor is either 1,2,4, or 8 itself. Certainly, a
byte whose number is divisible by sizeof(WORD) is a candidate
where a WORD could begin. So `(a-(char*)0) % W' would test
whether `a' points to a byte where a WORD could start: If the
remainder is 0 a WORD could begin there, if it's non-zero the
address might not be a good place for a WORD to start. (The
test is a little bit more stringent than it needs to be, since
an 8-byte WORD might need only 4-byte alignment. But even though
it might come up with a false negative, it will never come up
with a false positive.)
So far, we've figured out whether `a' points to a place
where a WORD could begin. If it does, we might be able to use
WORD pointers to access the elements. But the starting point
alone isn't enough; we must also consider the element size, `es'.
Let's stick with our 8-byte WORD for a moment; changing
to other sizes is straightforward. Suppose `es' is 16: Great!
We can swap a pair of elements by swapping two pairs of WORDS.
But suppose `es' is 14: What then? The first element starts
at a WORD-eligible place, but the second doesn't. We could
not use WORD pointers (safely) to access the second element,
or fourth, sixth, ... If `es' is not a multiple of sizeof(WORD),
we can't use WORD pointers on the data even if the very first
element looks like it might be WORD-eligible. So we can use
the WORD-based swaps only if `a' points to a WORD candidate and
if `es' is a multiple of sizeof(WORD). That would lead to two
tests: One for alignment of `a', and one for the size `es'.
Now comes another non-portable but nearly universal assumption:
The code squeezes two tests into one by assuming that sizeof(WORD)
is a power of two. Again, suppose it's 8: Then `a' is properly
aligned if `a-(char*)0' has three or more low-order zero bits,
and `es' is divisible by 8 if it, too, has three or more low-order
zeroes. If either has any ones among the three low-order bits,
one or the other test will fail. But if either has low-order ones,
then the expression `(a-(char*)0) | es' also has low-order ones,
so if we test that expression for divisibility by 8 we're checking
both conditions at once. This wouldn't work if sizeof(WORD) were
six, say.
That pretty much wraps it up. If the combined divisibility
test fails, we set swaptype=2 and use the byte-at-a-time swapping
code. If the divisibility test succeeds, one more check is made:
Whether to swap single WORDs (if `es==sizeof(WORD)') or to swap
multiple WORDs. That's the `es>W' piece: it sets swaptype=1 for
multi-WORD elements, or swaptype=0 for single-WORD swaps.
2. Isn't it illegal to subtract pointers belonging to two different
areas (and also two different types here as 'a' is not a (char*) its
actually a array of type 'object') as 'a' and (char*)0 doesn't point
to the same memory area (as we normally would do for two pointers
pointing inside the same array)?
Yes, `a-(char*)0' is undefined behavior. Even so, it will
almost always work as intended; a footnote in the paper says it
works even on some out-of-the-mainstream architectures.
As for the type of `a', in the paper's code it is a `char*'.
This makes the paper's qsort() implementation not quite kosher,
since qsort() as defined by the C Standard takes a `void*' rather
than a `char*'. (The paper's qsort() breaks another rule, too:
When the Standard qsort() calls the comparison function, both
arguments point to elements of the array being sorted. The paper's
version sometimes points to a copy outside the array.)
