1. Peter Shinners
  2. nrnr

Source

nrnr / test.c

Diff from to

File test.c

  • Ignore whitespace
 #include <stdio.h>
-#include "nrnr.h"
-
-
 #include <sys/time.h>
 #include <time.h>
+#include "nrnr.h"
 
 
-#define DOCHECKS 0
-
 
 float GetTime(void);
-void CheckSearch(struct NrNrHood* hood, size_t numResults, const size_t* results, const float* minimum, const float* maximum);
+void RunSearch(int repear, const struct NrNrHood* hood, const float* minimum, const float* maximum);
+void CheckSearch(const struct NrNrHood* hood, size_t numResults, const size_t* results, const float* minimum, const float* maximum);
 
 
 
     float start;
 
     // Create random points
-
     srand(1234);
-    size_t numPoints = 10000000;
+    size_t numPoints = 1000000; // million
     start = GetTime();
     float* points = (float*)malloc(sizeof(float) * 3 * numPoints);
 	for(size_t i=0; i<numPoints; i++) {
 		p[0] = ((float)rand() / RAND_MAX) * 200.0 - 100.0;
 		p[1] = ((float)rand() / RAND_MAX) * 200.0 - 100.0;
 		p[2] = ((float)rand() / RAND_MAX) * 200.0 - 100.0;
-        //printf("  pt %zu: %.1f %.1f %.1f\n",i, p[0], p[1], p[2]);
     }
-	//printf("Create random points (%zu): %.3f sec\n", numPoints, GetTime() - start);
 
     // Create neighborhood
-
     start = GetTime();
     struct NrNrHood* hood = NrNrCreateNeighborhood(numPoints, 3, points);
-	printf("Create neighborhood: %.3f sec\n", GetTime() - start);
+	printf("Create neighborhood: %.2f msec\n", GetTime() - start);
 
-    // Search block
-    start = GetTime();
-#if 0  // 10r
-    float minPos[3] = {-10.0f,10.0f,-30.0f};
-    float maxPos[3] = { 10.0,  30.0f, -10.0f};
-#elif 0 // 20r
-    float minPos[3] = {-20.0f, 0.0f, -40.0f};
-    float maxPos[3] = { 20.0,  40.0f, 00.0f};
-#elif 1 // 40r
-    float minPos[3] = {-40.0f,-20.0f,-60.0f};
-    float maxPos[3] = { 40.0,  60.0f, 20.0f};
-#elif 1 // 80r
-    float minPos[3] = {-80.0f,-60.0f,-100.0f};
-    float maxPos[3] = { 80.0,  100.0f, 60.0f};
-#endif
-
-    //printf("Searching: %.1f - %.1f,  %.1f - %.1f, %.1f - %.1f\n", minPos[0], maxPos[0], minPos[1], maxPos[1], minPos[2],maxPos[2]);
-
-    size_t* results;
-    size_t count = NrNrSearchBlock(hood, &results, minPos, maxPos);
-    printf("Search complete %zu: %.3f sec\n", count, GetTime() - start);
-
-#if 0
-for(size_t z = 0; z < count; ++z) {
-    float* pos = points + results[z] * 3;
-    printf("  found %zu: %.1f %.1f %.1f\n", results[z], pos[0], pos[1], pos[2]);
-}
-#endif
+    // Radius 1 search
+    float minPos1[3] = {-49.0f, -8.0f, 59.0f};
+    float maxPos1[3] = {-47.0f, -6.0f, 61.0f};
+    RunSearch(12000, hood, minPos1, maxPos1);
 
-#if DOCHECKS
-    CheckSearch(hood, count, results, minPos, maxPos);
-#endif
+    // Radius 10 search
+    float minPos10[3] = {-10.0f,10.0f,-30.0f};
+    float maxPos10[3] = { 10.0,  30.0f, -10.0f};
+    RunSearch(3000, hood, minPos10, maxPos10);
 
-    // Cleanup
+    float minPos20[3] = {-20.0f, 0.0f, -40.0f};
+    float maxPos20[3] = { 20.0,  40.0f, 00.0f};
+    RunSearch(1700, hood, minPos20, maxPos20);
 
-    start = GetTime();
-    results = NrNrFreeResults(results);
+    float minPos40[3] = {-40.0f,-20.0f,-60.0f};
+    float maxPos40[3] = { 40.0,  60.0f, 20.0f};
+    RunSearch(800, hood, minPos40, maxPos40);
 
+    float minPos80[3] = {-80.0f,-60.0f,-100.0f};
+    float maxPos80[3] = { 80.0,  100.0f, 60.0f};
+    RunSearch(500, hood, minPos80, maxPos80);
+
+    // Cleanup
+    start = GetTime();
     free(points);
     hood = NrNrFreeNeighborhood(hood);
-    printf("Cleanup: %.3f sec\n", GetTime() - start);
+    printf("Cleanup: %.2f msec\n", GetTime() - start);
 
 	return 0;
 }
 
 
 
-
-
-float GetTime(void)
-{
-	static struct timeval timeval, first_timeval;
-	gettimeofday(&timeval, 0);
-	if(first_timeval.tv_sec == 0) {
-		first_timeval = timeval;
-		return 0;
-	}
-	unsigned int s = (timeval.tv_sec - first_timeval.tv_sec) * 1000 + (timeval.tv_usec - first_timeval.tv_usec) / 1000.0;
-    return s / 1000.0f;
-}
-
-
-
-#if 0
-void CheckSorting(struct NrNrHood* hood) {
-    // Check value ordering
-    for (size_t d = 0; d < hood->dimensions; ++d) {
-        size_t* indices = hood->indices + hood->numPoints * d;
-        float val = hood->points[indices[0] * 3 + d];
-        for (size_t pt = 1; pt < hood->numPoints; ++pt) {
-            float nextVal = hood->points[indices[pt] * 3 + d];
-            if (nextVal < val) {
-                printf("Error sorting, values not in ascending order: axis=%zu, index=%zu\n", d, pt);
-                exit(1);
-            }
-            val = nextVal;
-        }
+void RunSearch(int repeat, const struct NrNrHood* hood, const float* minimum, const float* maximum) {
+    size_t count;
+    size_t* results = NULL;
+    float start = GetTime();
+    for (int r = 0; r < repeat; ++r) {
+        results = NrNrFreeResults(results);
+        count = NrNrSearchBlock(hood, &results, minimum, maximum);
     }
 
-    // Check repeated indices
-    for (size_t d = 0; d < hood->dimensions; ++d) {
-        size_t* indices = hood->indices + hood->numPoints * d;
-        for (size_t i = 0; i < hood->numPoints; ++i) {
-            size_t pt = indices[i];
-            if (pt >= hood->numPoints) {
-                printf("Error sorting, point number out of range: axis=%zu, index=%zu\n", d, i);
-                exit(1);
-            }
-            for (size_t j = i + 1; j < hood->numPoints; ++j) {
-                if (pt == indices[j]) {
-                    printf("Error sorting, point number used more than once: axis=%zu, index=%zu\n", d, i);
-                    exit(1);
-                }
-            }
-        }
-    }
-}
-
-
-void CheckNextIndices(struct NrNrHood* hood) {
-    // Check repeated indices
-    for (size_t d = 0; d < hood->dimensions; ++d) {
-        size_t* next = hood->nextIndices + hood->numPoints * d;
-        for (size_t i = 0; i < hood->numPoints; ++i) {
-            size_t pt = next[i];
-            if (pt >= hood->numPoints) {
-                printf("Error with nexts, point number out of range: axis=%zu, index=%zu\n", d, i);
-                exit(1);
-            }
-            for (size_t j = i + 1; j < hood->numPoints; ++j) {
-                if (pt == next[j]) {
-                    printf("Error with nexts, point number used more than once: axis=%zu, index=%zu\n", d, i);
-                    exit(1);
-                }
-            }
-        }
-    }
+    float radius = (maximum[0] - minimum[0]) / 2.0f;
+    printf("Search found %zu: %.2f msec per search  (repeat=%d radius=%.1f)\n",
+                count, (GetTime() - start) / repeat, repeat, radius);
 
-    // Check roundtrip through dimensions ends with the same
-    for (size_t d = 1; d < hood->dimensions; ++d) {
-        size_t* next = hood->nextIndices + hood->numPoints * d;
-        size_t* indices = hood->indices + hood->numPoints * d;
-        size_t* from;
-        if (d) {
-            from = hood->indices + hood->numPoints * (d - 1);
-        } else {
-            from = hood->indices + hood->numPoints * (hood->dimensions - 1);
-        }
-        for (size_t i = 0; i < hood->numPoints; ++i) {
-            size_t pt = from[i];
-            if (pt != indices[next[i]]) {
-                printf("Error with nexts, incorrect index: axis=%zu, index=%zu\n", d, i);
-                exit(1);
-            }
-        }
+    // Checking is too slow with big pools of matches
+    if (count < 10000) {
+        CheckSearch(hood, count, results, minimum, maximum);
     }
+    results = NrNrFreeResults(results);
 }
-#endif
 
 
-void CheckSearch(struct NrNrHood* hood, size_t numResults, const size_t* results, const float* minimum, const float* maximum) {
+
+void CheckSearch(const struct NrNrHood* hood, size_t numResults, const size_t* results, const float* minimum, const float* maximum) {
     int foundError = 0;
     for (size_t i = 0; i < hood->numPoints; ++i) {
         const float* pos = hood->points + i * hood->dimensions;
         int inside = 1;
+
         for (size_t d = 0; d < hood->dimensions; ++d) {
             if (pos[d] < minimum[d] || pos[d] > maximum[d]) {
                 inside = 0;
         exit(1);
     }
 }
+
+
+
+// Return time in milliseconds
+float GetTime(void)
+{
+	static struct timeval timeval, first_timeval;
+	gettimeofday(&timeval, 0);
+	if(first_timeval.tv_sec == 0) {
+		first_timeval = timeval;
+		return 0;
+	}
+	float s = (timeval.tv_sec - first_timeval.tv_sec) * 1000 + (timeval.tv_usec - first_timeval.tv_usec) / 1000.0;
+    return s;
+}
+
+
+