Re: [PATCH 1/8] lib/sort: Heapsort implementation of sort()

[Junio C Hamano]

>>>>> "AG" == Andreas Gruenbacher <agruen@xxxxxxx> writes:

AG> On Wed, 2005-02-02 at 11:50, Herbert Xu wrote:
>> What if a/b aren't aligned?

AG> If people sort arrays that are unaligned even though the
AG> element size is a multiple of sizeof(long) (or sizeof(u32)
AG> as Matt proposes), they are just begging for bad
AG> performance.

If the user of your sort routine is dealing with an array of
this shape:

    struct { char e[8]; } a[]

the alignment for the normal access (e.g. a[ix].e[iy]) would not
matter and they are not begging for bad performance, are they?
It is only this swap routine, which is internal to the
implementation of sort, that is begging for it, methinks.  

Is unaligned access inside of the kernel get fixed up on all
architectures?  If not, this would not just be a performance
issue but becomes a correctness issue.

How about something like this to be a bit more defensive:

static inline void swap(void *a, void *b, int size)
{
       if (((unsigned long)a | (unsigned long)b | size) % sizeof(long)) {
	       char t;
	       do {
		       t = *(char *)a;
		       *(char *)a++ = *(char *)b;
		       *(char *)b++ = t;
	       } while (--size > 0);
       } else {
	       long t;
	       do {
		       t = *(long *)a;
		       *(long *)a = *(long *)b;
		       *(long *)b = t;
		       size -= sizeof(long);
	       } while (size > sizeof(long));
       }
}

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/