Low C performance for TSP heuristic

I've been recently doing classes on the traveling salesman problem. I've been tackling the nearest neighbor heuristic for the problem and seeing that the algorithm was simplistic, I've decided to see how fast would be solutions implemented in different languages. I've implemented several versions of the solution using different lua extensions, of those most importantly, luajit. I've also done the same algorithm in C.

What surprised me is that luajit solution using C data structures actually beats the pure C implementation significantly (5-6 times faster) C was compiled with gcc -o3 and the problem size was such that completion times were on the order of a few seconds.

I'm not very well versed in the ways of the language, so I wonder if I didn't do something right in C code:

#include 

typedef struct city {double x; double y; double ind;} city;

double tsp(city* cities, int N){
    city current=cities[0];
    double S=0;
    for (int i=N-1; i>0; i--){
        int pos=i;
        city  viewing= cities[i];
        double d2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
        double ind=viewing.ind;
        for (int j=1; j<i; j++){
            viewing=cities[j];
            double D2=pow((current.x-viewing.x),2)+pow((current.y-viewing.y),2);
            if ((D2 < d2)||((D2==d2)&&(viewing.ind<ind))){
                pos=j;
                d2=D2;
                ind=viewing.ind;
            }
        }
        S+=sqrt(d2);
        current=cities[pos];
        cities[pos]=cities[i];
    }
    return S+sqrt(pow((cities[0].x-cities[1].x),2)+pow((cities[0].y-cities[1].y),2));
}

The function implements the following algorithm: start at city[0], find nearest city, go there, find nearest unvisited city, go there, repeat until no cities left, go to city[0].

Well, the first thing to do is extracting the distance-calculation and replacing the costly call to pow():

inline static double distance2(city* a, city* b) {
    double dx = a->x - b->x;
    double dy = a->y - b->y;
    return dx * dx + dy * dy;
}

Next, let's stop always copying the cities when not really needed.

Optionally, use a sentinel value (INFINITY) so we don't need to single out any candidate for nearest city.

Another nearly gratuitious change I did was starting with the last city given.

I suggest you also invest in slightly more spaces, they make things more readable, especially around operators.

The changed function:

double tsp(city* cities, int N) {
    double S = 0;
    for (int i = N; --i > 0;) {
        double best_d2 = distance2(cities + i, cities + 0);
        int best_pos = 0;
        for(int j = i; --j > 0;) {
            double d2 = distance2(cities + i, cities + j);
            if(d2 < best_d2 || d2 == best_d2 && cities[j].ind < cities[best_pos].ind) {
                best_d2 = d2;
                best_pos = j;
            }
        }
        S += sqrt(best_d2);
        city temp = cities[best_pos];
        cities[best_pos] = cities[i - 1];
        cities[i - 1] = temp;
    }
    return S + sqrt(distance2(cities, cities + N - 1));
}

StackExchange Code Review Q#163283, answer score: 7