K-Nearest Neighbor

June 10, 2014
Re: K-Nearest Neighbor + pointger alignments
Posted by bearophile
in reply to Ali Çehreli
Permalink
bearophile
Posted in reply to Ali Çehreli
Permalink
Ali Cehreli:

> I wonder what bearophile's response will be. ;)

Despite looking like a silly sequence of optimizations, I do have some general comments on that text. Thanks to Kenji (https://github.com/D-Programming-Language/dmd/pull/3650 ) this code is now valid:

void foo(size_t N)(ref int[N] b) if (N == 4) {}
void main() {
    int[5] a;
    foo(a[1 .. $]);
}


The D type system is able to understand that if you slice away the first item of an an array of 5 items, you produce a pointer to an array of 4 items.

But the D static typing is not very strong (precise), D is not yet using all the fruits given by static typing.

D throws away the compile-time knowledge about pointer alignments, so if you write code like this without the 7 shorts of padding, the program crashes at run-time, because of misalignment:


uint distance(immutable ref short[nCols - 1] p1,
              immutable ref short[nCols - 1] p2)
pure nothrow @nogc {
    alias TV = short8;
    enum size_t Vlen = TV.init.array.length;
    assert(p1.length % Vlen == 0);
    immutable v1 = cast(immutable TV*)p1.ptr;
    immutable v2 = cast(immutable TV*)p2.ptr;

    TV totV = 0;
    foreach (immutable i; 0 .. p1.length / Vlen) {
        TV d = v1[i] - v2[i];
        totV += d * d;
    }

    uint tot = 0;
    foreach (immutable t; totV.array)
        tot += t;
    return tot;
}

TLabel classify(immutable short[nCols][] trainingSet,
                immutable ref short[nCols - 1] pixels)
pure nothrow @nogc {
    auto closestDistance = uint.max;
    auto closestLabel = TLabel.max;

    foreach (immutable ref s; trainingSet) {
        immutable dist = pixels.distance(s[1 .. $]);
        if (dist < closestDistance) {
            closestDistance = dist;
            closestLabel = s[labelIndex];
        }
    }

    return closestLabel;
}



In this program there is all the information necessary to compute simply at compile-time the alignment of v1 and v2 and generate a compile-time error if you try to perform SIMD operations using such unaligned pointers. I don't like D to throw away static information that can be used to avoid run-time crashes, this is the opposite of what is usually called a safe language.

D type system is able to keep the length of arrays at compile-time, allowing data types like ushort[N], but in a system language that allows such simple usage of SIMD with core.simd it's also useful to encode in the pointer/array type the alignment.


So this code should not compile:

uint distance(immutable ref short[nCols - 1] p1,
              immutable ref short[nCols - 1] p2)
pure nothrow @nogc {
    alias TV = short8;
    enum size_t Vlen = TV.init.array.length;
    assert(p1.length % Vlen == 0);
    immutable v1 = cast(immutable TV*)p1.ptr;
    immutable v2 = cast(immutable TV*)p2.ptr;

    TV totV = 0;
    foreach (immutable i; 0 .. p1.length / Vlen) {
        TV d = v1[i] - v2[i];
        totV += d * d;


While this should compile:

uint distance(immutable ref align(16) short[nCols - 1] p1,
              immutable ref align(16) short[nCols - 1] p2)
pure nothrow @nogc {
    alias TV = short8;
    enum size_t Vlen = TV.init.array.length;
    assert(p1.length % Vlen == 0);
    immutable v1 = cast(immutable TV*)p1.ptr;
    immutable v2 = cast(immutable TV*)p2.ptr;

    TV totV = 0;
    foreach (immutable i; 0 .. p1.length / Vlen) {
        TV d = v1[i] - v2[i];
        totV += d * d;


And now this function that calls distance should not compile:

TLabel classify(immutable short[nCols][] trainingSet,
                immutable ref short[nCols - 1] pixels)
pure nothrow @nogc {
    auto closestDistance = uint.max;
    auto closestLabel = TLabel.max;

    foreach (immutable ref s; trainingSet) {
        immutable dist = pixels.distance(s[1 .. $]); // error


And now this should compile:

TLabel classify(immutable align(16) short[nCols][] trainingSet,
                immutable ref align(16) short[nCols - 1] pixels)
pure nothrow @nogc {
    auto closestDistance = uint.max;
    auto closestLabel = TLabel.max;

    foreach (immutable ref s; trainingSet) {
        immutable dist = pixels.distance(s[8 .. $]);



And this should compile because std.file.read returns memory allocated by the GC that is align(16):

align(16) immutable(short[nCols])[] readData(size_t nCols)(in string fileName) {
    return cast(typeof(return))std.file.read(fileName);
}


Where the alignment is not known at compile-time the D compiler could add run-time alignment asserts in debug builds, to give nice run-time error messages.

The simpler int[4] or int[] types are still valid and usable, they could be align(1). If you think of them as align(16) you are writing faith-based code when you use SIMD instructions.


Automatic variables (stack-allocated) too could allow alignment annotations (perhaps ldc2 is already supporting this syntax):

void main() {
    align(16) ubyte[60] ubs;
}


I discussed this topic another time in past:
http://forum.dlang.org/thread/wldsugyllfpnzeksupku@forum.dlang.org

Bye,
bearophile
Forums
