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