Jump to content

LV OOP Kd-Tree much slower than .Net, brute force


Recommended Posts

I am writing a performance-sensitive application which requires the use of a nearest-neighbor lookup. Originally I used a brute-force method, but unfortunately this gets to be very slow as the data size increases . I have a point cloud of ~100k points in 2D, and need around 50k nearest neighbor lookups per second as a minimum performance requirement.

As a solution I wrote a kd-tree in .Net and used LabView to call the .Net dll. However, I discovered that each .Net transaction carries with it about a 0.5ms delay. I've tried bunching the data up into groups, but this only helps so much, as I am using an iterative process.

Armed with my new-found kd-tree knowledge, I then wrote the kd-tree in LV-OOP, using DVRs for both subtrees and leaf values. However, my LV implementation is still 100x slower than the .Net implementation, and 20x slower than brute force. And this is with just 10k points.

I'm fairly new to LV (about 6 months in an academic environment) and I'm fairly sure I've made a massive blunder somewhere, but I don't have any idea what it might be.

http://robowiki.net/...d-tree_Tutorial is the tutorial that I used for writing both trees - note that I've only implemented a 1-NN lookup method, so have no need for the priority queue.

Just some notes:

  • I found using in-place data structure unbundle-bundle was much faster than using normal unbundle-bundle for all of the read/writes.
  • The tree started out with pure by-value subtrees and data, so was even slower before I changed to DVRs.
  • The lookup uses a queue as a stack, rather than being recursive. Not sure if this is good or bad.
  • The add element uses recursion. Again, not sure if this is good or bad.

I've written speed tests for brute force, .Net and LV lookups with names like with test_...... .vi if you want to compare performance.

kd_tree Folder.zip

Thanks in advance for any help

Julian Kent

Link to post
Share on other sites

Depending on the size of your point data, does it make sense to use LVOOP? I have no benchmarks to point to, but I imagine for small data, the overhead of LVOOP will outweigh the performance of, say, a cluster of {prev, data, next} that you don't get the nice OOP-ness with. There will probably be more legwork with that route (and you may have to be more careful with memory allocations) but I think for the performance spec you're looking to hit, the simple route may be more effective.

Link to post
Share on other sites

Depending on Irrespective of the size of your point data, does it make sense to use LVOOP? I have no benchmarks to point to, but I imagine for small data, the overhead of LVOOP will outweigh the performance of, say, a cluster of {prev, data, next} for loop that you don't get the nice OOP-ness with. There will probably be more less legwork with that route (and you may won't have to be more careful with memory allocations) but I think for the performance spec you're looking to hit, the simple route may be more effective.

....and get rid of the queues.

Link to post
Share on other sites

just my 2¢: You can always do (translate) a recursive algorithm with a while loop. With above suggestion of clusters instead of Classes and while loop you should gain significant speeds.

Never mind my post, I looked at the code after I posted. and I don't see a Recursive implementation.

Edited by sam
Link to post
Share on other sites

Being a chemist rather than an engineer, I can't say I really know the finer details of what differentiates a k-d from a red-black or a spruce, but those are all very good tips which can take years of experience to learn. They are valuable to know in any context where performance matters.

I for one never thought of the ramifications of using the timed loop. Interesting.

Link to post
Share on other sites

asbo, ShaunR:

How would you suggest I place clusters within clusters within clusters within... (dynamically)? I'm desperate for speed, and if it means sacrificing OOP design I'm willing to try it, but as far as I can tell LV specifies cluster contents pretty rigidly. Doing a prev/next doesn't work in a kd tree because we have a large number of dimensions... and implicit kd trees will give this type of structure but use huge amounts of memory (curse of dimensionality and all that). As you'll see in my project, I've already tried a simple brute force method with a simple array subtract/square/sum/min for finding the nearest point, and if it isn't fast enough with raw arrays it definitely won't be fast enough with clusters. Unless I've completely misunderstood you...

sam:

The recursive implementation is simply because I can't think of any other way to move into a tree of unknown depth in a data-flow environment without doing a copy of each subtree as we go. Sure,i could use a while loop, but it would be really slow as it would require copying each subtree onto the stack as I go.

Aristos Queue

Thanks for the feedback. I've gone through and implemented the ideas you've given, excepting the parent_kdtree class, and I've almost doubled my performance, but it's still 50x slower than the .Net. As I'm not really concerned about concurrent access, would you then recommend getting rid of the DVR-on-a-stack technique and instead go for a recursive unbundle/bundle without any DVRs at all then?

I thought the casting might be slow so I tried changing the data type in the queue to just straight kdtree DVRs and it slowed me down about 4x. Not sure why, but it seems that is the wrong thing to do.

mje: A kd-tree is a tree that works in more than one dimension, ie. for a k-dimensional point cloud. It is typically used for fast nearest-neighbor lookup. Check out http://en.wikipedia.org/wiki/K-d_tree. The one described on Wikipedia isn't quite what I'm using, as I don't store points on lower parts of the tree, just the leaves, and at each leaf I keep an array of points. I also have some optimizations such as keeping track of the hyperrect containing each subtree and only traversing that tree if that hyperrect could contain a closer point. A bit abstract, I know :rolleyes:

I just tried profiling, and I spend more time in Exemplar:getSqDist than I do in the entire .Net lookup algorithm. So maybe I'll try a C++ .dll instead... sigh.

Link to post
Share on other sites

You've now heard the position of the "OO is bad" crowd.

Wow. I'm a crowd? I really can be in two places at once (multiple salaries :) )

So maybe I'll try a C++ .dll instead... sigh.

For raw speed. It's the only way. Labview is fast (in comparison to, say Java), but not the fastest. A dll call will probably only add about 1-3 usecs of overhead.

Link to post
Share on other sites

asbo, ShaunR:

How would you suggest I place clusters within clusters within clusters within... (dynamically)? I'm desperate for speed, and if it means sacrificing OOP design I'm willing to try it, but as far as I can tell LV specifies cluster contents pretty rigidly. Doing a prev/next doesn't work in a kd tree because we have a large number of dimensions... and implicit kd trees will give this type of structure but use huge amounts of memory (curse of dimensionality and all that). As you'll see in my project, I've already tried a simple brute force method with a simple array subtract/square/sum/min for finding the nearest point, and if it isn't fast enough with raw arrays it definitely won't be fast enough with clusters. Unless I've completely misunderstood you...

Yes, I rather meant that prev/next would be indices in a parent array, where data would actually be the data cluster. The indices would be used for lookup, which could make traversal a little more work (thus my legwork comment). So, as a C programmer would write:

cluster data { ... };

cluster node {int prev, cluster data, int next}; (whatever metadata is appropriate, this is really more of a linked list)

cluster[] tree;

I should have warned in my first post, I didn't look at your implementation. I don't consider myself experienced enough to critique LVOOP methodologies, I was just throwing an idea in the ring. I'm not an OOP nay-sayer, but if you can't get the performance you need there may be other options. I'm certainly interested in what implementation reaches your goal for you.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Similar Content

    • By Marko Hakkarainen
      I had some time to learn about new interfaces and finally I could implement my collection class as I had envisioned. I didn’t want to use iterable and iterator names, because I thought that would have been too bold a claim.
      The original version of the collection class was (and is) used as a collection of sequence steps. Each element can be either a sequence command (send message, wait timer, wait complete etc.) or another collection of commands (sub-sequence). That’s the reasons for the labels and search method. Otherwise it is just a fancy (Rube Goldberg) array.
      Next method is recursive and it steps through all elements in the collection. Execute is only method, which requires override.
      For now, it’s at least an exercise in new interfaces. I don’t know if it’s useful enough to be in the code repository, but I can polish it up if needed.
       
      --
      Marko H
      Certified LabVIEW Architect
      www.optofidelity.com
      Iterable Collection LV2020.zip
    • By Zyl
      Hi everybody,
       
      I'm running into something I don't really understand. Maybe you can help me here !
      I've got a LVLIB that is used as an 'Interface': it exposes public VIs which wrap around public functions of a private class (see code attached) . The class is private because I want to force the users to use the 'interface' functions.
      In one of my interface VI, I create a DVR on the private class (Interface_init). The DVR is stored into a typedef (FClass_DVR.ctl) and this typedef is the 'reference' that link all the interface public functions.
      In TestCode.vi (which is not part of the lvlib and illustrates the standard code that a user can create to use my driver), I can call my public interface functions and link them without any problem.

      But as soon as I create an indicator on that reference (to create a state-machine-context-cluster for example), my TestCode VI breaks !

      The error returned is : This VI cannot use the LabVIEW class control because of library access scope. The LabVIEW class is a private library item and can only be accessed from inside the same library or libraries contained in that library.
      I understand that the class is private. But the DVR is contained into a public control. Using an In Place structure on that DVR into TestCode would not work, since the class is private. So why is the DVR control problematic at that point ? Creating it do not breaks any access protection...
      Am I missing something ?
      DVR Private POC.zip
    • By Brains
      Hi,
      Does anybody know the best way to make a copy of a byref object (open gds v4) at runtime and pass all the attributes values (including inherited attributes) to the new object?
      Thank you!
      Craig
    • By GregFreeman
      I currently have a project that I am refactoring. There is a lot of coupling that is not sitting well with me due to typedefs belonging to a class, then getting bundled into another class which is then fired off as event data.
      Effectively, I have class A with a public typedef, then class B contains ClassA.typedef and then class B gets fired off in an event to class C to be handled. Class C now has a dependency on class A which is causing a lot of coupling I don't want.
      For my real world example I query a bunch of data from our MES, which results in a bunch of typedef controls on the connector panes of those VIs. Those typedefs belong to the MES class. I then want to bundle all that data into a TestConfig class and send that via an event to our Tester class. But, now our tester has a dependency on the MES.
      I see a few ways to handle this. First is move the typedefs currently in the MES class, to the TestConfig class. The MES VIs will now have the typedefs from the TestConfig class on their connector panes, but at least the dependency is the correct "direction." Or, I can move the typedefs out of classes all together, but then I am not sure the best way to organize them. Looking for how others have handled these sorts of dependencies.
       
    • By Axelwlt
      Hi,
      In a Mouse Down? on a tree, I need to know if the user clicked on a expand/contract symbol, because I need to discard clicking on items but I still need the expand/contract mechanism.
      I would need something similar to the InSymbol from the Point To Row Column method, but for the expand/contract symbol.
      How can I do that?
×
×
  • Create New...

Important Information

By using this site, you agree to our Terms of Use.