User talk:Skilgannon/KDTree

I found a optimization, You can use 65536 + 2*_dimensions instead of 512 * 1024 / 8 + 2*_dimensions.

Are you actually joking?

No I'm not.

Two things - actually, three:

• That code executes once, because it's in the constructor. Clarity >> saving one multiplication and one division calculation during initialization.
• The Java compiler should optimize this, making it irrelevant anyway - that is, the compiled .class file will be the exact same bytecode.
• Please spend more time writing bots and less time posting on the wiki. I'm sorry for being blunt. I've never been in this situation, but your posts are mostly inane, to the point that I sometimes wonder if you're the most successful troll I've ever encountered.

Actually my dad Chris Reeves is the real Tmservo

I agree with Voidious (except that I don't mind being blunt as much as he seems to). Your questions/suggestions are usually poorly researched and annoying. IIRC, the time you joined the wiki was roughly the time activity here started to die off. I can't speak for others, but personally, the frequency of your questions and the ridiculousness of the subject matter made me stop frequenting the wiki as much as I had previously. (Though in fairness, college work also had some impact, that was more in the realm of coding and less in the realm of "robowiking"). I suggest that we implement some sort of warning system (say three consecutive "ridiculous questions/suggestions") and then a temporary ban.

I agree with AW and Voidious. All my attempts to understand motivation of Tmservo posts are failing.

Thanks for adding a weighted tree, It makes me feel safer to know that my implementation does the correct thing. Where are you using it in Wintermute?

Look at this.

In Wintermute I have a single tree for bullet hits, but I have 3 different weighting schemes that concentrate on different types of enemies. Since they all use the same tree I just set the different weights before pulling the KNN. It could be done just as well (and probably a bit faster) by keeping different trees, but I wanted the possibility of adjusting the weights as the battle went on, even though I never ended up using it.

Thanks, I see now you are using one tree to emulate having three different trees with weights.

is chebyshev norm better or worse than euclidean norm for knn for movement,gun

Without defining "better" or "worse", this is a meaningless question.

Still a meaningless question. Better against what? In what situations? With what weights? Its impossible to effectively answer the question without knowing those.

So that change had a positive effect when you benchmarked it? I'd tend to call "pointer stack instead of object stack" an inaccurate way of thinking about it, because object references in Java are pointers under-the-hood.

I have a feeling that perhaps the performance gain you may have saw actually came from avoiding a pointer deference in "if(results.peekPrio() > pointRectDist((2*_dimensions)*nodeIndex,searchLocation))" as compared to "if(results.peekPrio() > searchNode.pointRectDist(searchLocation))"

Calls to private methods are inlined. Calls to public methods aren't. Object references and polymorphism are a lot harder for compilers to optimize.

Polymorphism overhead can usually be detected with profiling.

Yeah, that's exactly where I was trying to speed things up. The way it is now, any path that I don't descend never has its Node contents examined, because I don't have to open up the Node to get the index when checking the bounds anymore. This means the Node contents (and the pointer to it) is never loaded unless it is determined that the Node needs to be searched.

Benchmarking says it's just a *tiny* bit quicker, and I like it so it stays =)

Out of curiosity, have you compared your PrioQueue impelementation that uses binary search, to the heap implementation that I use in my 3rd gen tree? Looking over it, I expect the heap to be faster.

Consider the heapsort algorithm. It is O(n log(n)) to perform the sort like most good sorting algorithms. Roughly half the effort of the heapsort is generating the heap-ordering, and half is generating the fully sorted order from the heap-ordering. This is not exactly what we're doing, but the general idea is that generating heap-ordering is lower cost than generating sorted-ordering, despite both having an O(n log(n)) cost.

With both the heap method and the binary search method, insertions are O(log(n)), except...

1. With the heap method, you only generate heap order for items that don't end up within the closest N points. This doesn't change the O(log(n)) characteristic, but it ought to be lower cost.
2. Your implementation also has some O(n) characeristics, because inserting in the middle of an ArrayList causes the ArrayList to copy everything after the insertion point. It's a fast O(n) operation when the number of points being returned is small, but I think it's still notable.

You're probably right that the binary search method get's through JIT faster, but I'm unsure if that pays off due to the two disadvantages I note above. In addition, I'd suspect your SearchResult container object probably adds some extra cost to your result queue. When I was doing my heap-based implementation I found it was faster to have an Object[] array for the results and double[] array for distances, and manage both in the heap, rather than using a container.

In the tests I did I found that the container didn't make any difference. I *did* try using the ResultHeap from your Gen2 tree, but it was quite a bit slower, the same speed as a linear-search ArrayList backed PrioQueue.

I think it isn't just a JIT issue, but also the fact that we generally only have ~50 elements in the queue. At these sizes something like an Insertion Sort is comparable in speed to a Heap Sort, so I thought I'd implement what I know first.

I'll give it another run, this time with your Gen3 heap.

Also, I tried using the PrioQueue as the stack for storing the tree nodes. I used the pointRectDist as the ordering factor, but it increased the number of points visited by ~30% so I'm not sure what I did wrong. I know you did something similar, how did you get it to work?

Regarding the stack of tree nodes, perhaps you had it sorting in the wrong direction or something? Based on my tests, when setting it up so it always visits the nearest unvisited node next, it pretty reliably decreased the number of points visisted. The overall performance gain was smaller than the reduction in points visited (due to the extra distance calculations Edit: not due to extra distance calculations, turns out I was calculating bounding box distances for unvisited paths before I implemented the stack of tree nodes), but it did did pay off slightly for me in any case.

OK, results are in. It turns out I still had some performance tucked away in my PrioQueue, like you thought. Odd that I didn't pick that up earlier.

Next, using your MaxHeap from Gen3 was faster than my old PrioQueue, but slower than the new one. Although it is really hard testing when you have shared dependencies without giving one a JIT advantage!

Using the PrioQueue (the fast one) instead of the ArrayDeque now reduces the number of nodes I visit by ~20%, but still takes longer than a stack - about the same amount longer as using the MaxHeap for the results. I skip pointRectDist checks on the chosen path when the results queue doesn't have any values, but beyond that it seems dead-end to me. It seems to me that the overhead from the PrioQueue instead of an ArrayDeque is more than I save by visiting less nodes. It also uses a few less pointRectDist calculations. I even tried trimming the stack occasionally when new data came in, thinking maybe it was growing and pushed out of the fast region. Maybe I'll try using the MinHeap, but otherwise I'm going to stick with my simple lazily-evaluate-pointRectDist ArrayDeque implementation.

So, new results without garbage-creation:

BEST RESULT: 
 - #1 Skilgannon's Cache-hit KDTree [0.0286]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0291]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0319]
 - #4 Voidious' Bucket PR k-d tree [0.1619]

New results with garbage-creation:

BEST RESULT: 
 - #1 Skilgannon's Cache-hit KDTree [0.0288]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0314]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0337]
 - #4 Voidious' Bucket PR k-d tree [0.1705]

Notice my Cache-hit tree isn't really affected by the garbage, while all the others are.

Ahh, nice stuff! Could you post both your current version of your tree and the code you're using for "garbage-creation"? I'm curious to do some tests with it.

Here is the garbage creation code:

 public TestResult doTest(KNNImplementation algorithm, int numNeighbours, SampleData[] data, KNNPoint[][] solution) {
      TestResult result = new TestResult(algorithm.getName(), data.length, numNeighbours, solution);
   
      ArrayList<KNNPoint[]> neighbourLists = new ArrayList<KNNPoint[]>();
      double sum = 0;//DEPENDENCY FOR GARBAGE
      int addCount = 0;
      for (SampleData sample : data) {
         if (sample.save) {
            long time = -System.nanoTime();
            algorithm.addDataPoint(sample.entry);
            time += System.nanoTime();
            result.recordAdd(time);
            addCount++;
         }
      
         if (sample.search) {
            long time = -System.nanoTime();
            KNNPoint[] neighbourList = algorithm.getNearestNeighbors(sample.data, Math.min(numNeighbours, addCount));
            time += System.nanoTime();
            result.recordSearch(neighbourList, time);
         }
         //GARBAGE - vary size of array to vary effect - 0 should have no effect
         double[] garbageD = new double[1000];
         int[] garbageI = new int[garbageD.length];
         for(int i = 0; i < garbageD.length; i++){
            garbageD[i] = Math.random();
            garbageI[i] = (int)(Integer.MAX_VALUE*Math.random());
         }
         for(int i = 0; i < garbageD.length; i++){
            garbageD[i] *= garbageI[garbageD.length-1-i];
            sum += garbageD[garbageD.length-1 - i];
            garbageI[i] -= sum;
         }
      }
      if(sum == -1.0)//DEPENDENCY FOR GARBAGE
         System.out.println("Unlikely event, but cannot be eliminated.");
   
      return result;
   }