Re: pathfinding benchmark

[bearophile via Digitalmars-d]

Xiaoxi:

http://www.reddit.com/r/programming/comments/2pvf68/armv7_vs_x8664_pathfinding_benchmark_of_c_d_go/
didnt analyse the code, but D did quite well. :)

A little better D code:


import std.stdio, std.file, std.conv, std.string, std.datetime;

struct Route { uint dest, cost; }
alias Node = Route[];

Node[] readPlaces() {
    auto lines = "agraph".File.byLine;

    immutable numNodes = lines.front.to!uint;
    lines.popFront;
    auto nodes = new Node[numNodes];

    foreach (const line; lines) {
        immutable nums = line.split.to!(uint[]);
        if (nums.length < 3)
            break;
        nodes[nums[0]] ~= Route(nums[1], nums[2]);
    }

    return nodes;
}

uint getLongestPath(in Node[] nodes, in uint nodeID, bool[] 
visited)
pure nothrow @safe @nogc {
    visited[nodeID] = true;
    typeof(return) dMax = 0;

    foreach (immutable neighbour; nodes[nodeID])
        if (!visited[neighbour.dest]) {
            immutable dist = neighbour.cost +
                             getLongestPath(nodes, 
neighbour.dest, visited);
            if (dist > dMax)
                dMax = dist;
        }

    visited[nodeID] = false;
    return dMax;
}

void main() {
    const nodes = readPlaces;
    auto visited = new bool[nodes.length];

    StopWatch sw;
    sw.start;
    immutable len = getLongestPath(nodes, 0, visited);
    sw.stop;
    printf("%d language D %d\n", len, sw.peek.msecs);
}




I don't remember if the D entry gets faster with ldc2 if nodes is 
immutable, this is a version that keeps it immutable as in the 
original code:


import std.stdio, std.file, std.conv, std.string, std.datetime, 
std.exception;

struct Route { uint dest, cost; }
alias Node = Route[];

Node[] readPlaces() {
    auto lines = "agraph".File.byLine;

    immutable numNodes = lines.front.to!uint;
    lines.popFront;
    auto nodes = new Node[numNodes];

    foreach (const line; lines) {
        immutable nums = line.split.to!(uint[]);
        if (nums.length < 3)
            break;
        nodes[nums[0]] ~= Route(nums[1], nums[2]);
    }

    return nodes;
}

uint getLongestPath(immutable Node[] nodes, in uint nodeID, 
bool[] visited)
pure nothrow @safe @nogc {
    visited[nodeID] = true;
    typeof(return) dMax = 0;

    foreach (immutable neighbour; nodes[nodeID])
        if (!visited[neighbour.dest]) {
            immutable dist = neighbour.cost +
                             getLongestPath(nodes, 
neighbour.dest, visited);
            if (dist > dMax)
                dMax = dist;
        }

    visited[nodeID] = false;
    return dMax;
}

void main() {
    immutable nodes = readPlaces.assumeUnique;
    auto visited = new bool[nodes.length];

    StopWatch sw;
    sw.start;
    immutable len = getLongestPath(nodes, 0, visited);
    sw.stop;
    printf("%d language D %d\n", len, sw.peek.msecs);
}


But I think this is probably not necessary.

If you want you can submit the code to the original tester.

Bye,
bearophile