User talk:Skilgannon/KDTree

From Robowiki
Jump to navigation Jump to search

Contents

Thread titleRepliesLast modified
Optimization found601:46, 31 July 2015
Weighted Tree602:45, 25 December 2013
Re: "pointer stack instead of object stack"208:23, 21 July 2013
Regarding PrioQueue1222:51, 19 July 2013

Optimization found

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

Tmservo (talk)00:51, 30 July 2015

Are you actually joking?

Voidious (talk)01:33, 30 July 2015

No I'm not.

Tmservo (talk)01:35, 30 July 2015

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.
Voidious (talk)01:40, 30 July 2015

Actually my dad Chris Reeves is the real Tmservo

Tmservo (talk)02:20, 30 July 2015
 

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.

AW (talk)10:03, 30 July 2015

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

Beaming (talk)01:46, 31 July 2015
 
 
 
 
 

Weighted Tree

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?

Straw (talk)10:20, 24 December 2013

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.

Skilgannon (talk)13:13, 24 December 2013

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

Straw (talk)22:51, 24 December 2013
Edited by author.
Last edit: 23:23, 24 December 2013

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

Tmservo (talk)22:53, 24 December 2013

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

Straw (talk)23:12, 24 December 2013
 

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

Straw (talk)02:45, 25 December 2013
 
 
 
 

Re: "pointer stack instead of object stack"

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))"

Rednaxela (talk)22:45, 20 July 2013

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.

MN (talk)03:00, 21 July 2013
 

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 =)

Skilgannon (talk)08:23, 21 July 2013
 

Regarding PrioQueue

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.

Rednaxela (talk)20:46, 17 July 2013

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?

Skilgannon (talk)21:03, 17 July 2013

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.

Rednaxela (talk)22:14, 17 July 2013

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.

Skilgannon (talk)02:50, 18 July 2013

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.

Rednaxela (talk)03:06, 18 July 2013

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;
   }
Skilgannon (talk)03:11, 18 July 2013