Map, implemented with classes, for 8.5

[Jim Kring]

QUOTE (Aristos Queue @ Apr 9 2008, 11:40 AM)

QUOTE

At the end of the day, I don't know why NI won't prioritize adding a nice associative array function to the Queue and Notifier palette.

It might be because I've never heard of this idea before. What exactly would this be?

I think that Jason's referring to the possibility of having a new AssociativeArray by-reference sibling to the Queues and Notifiers types+functions that enjoys the same sort of edit-time type propogation (e.g., Queue and Notifier references contain the type of Queue/Notifier element data, which causes the Queue and Notifier functions to adapt to these types). Just as Queue and Notifier element/data types propogate to the primatives, it would be nice if the key and value types of an AssociativeArray could propogate to primitive Get/Set/Delete/etc. functions. Yes, we can do it with OOP and inheritance + dynamic methods, but it would be nice if AssociativeArray could be a LabVIEW primitive type+functions.

[jdunham]

QUOTE (Aristos Queue @ Apr 9 2008, 11:40 AM)

JD -- would you mind going to ni.com/labs and downloading the XNode Map implementation and adding it to your benchmarks?

OK.

QUOTE (Aristos Queue @ Apr 9 2008, 11:40 AM)

Oh, I'm pretty sure this solution will beat all others someday. From the theory side, it'll blow just about everything else out of the water. We're still in unexplored territory with this, and there may very well be some stupid implementation detail that is getting in the way. In school, I was once debugging a program that should've been blazing fast, only to find that in my delirium I had written code that instead of calculating a constant and storing it was recalculating a constant every time I needed it. It wasn't even relevant to the algorithm, just happened to be a needed constant. There is almost certainly something like that somewhere in the LVClass code. I'll grant that it may take a few years to iron out, and in the meantime, enjoy the acceleration of the variants.

Well the tree rebalance requires a few conversions between generic map nodes and branch nodes, and there is a buffer allocation at each of those. As far as I can tell that's killing performance, but I don't know enough about the inheritance implementation to know whether that conversion could be done without a copy. There are other branch class subvis that also show buffer allocation on bother input and output, and I don't know why, since a dynamic dispatch terminal is used on both input and output and the wire does not branch.

QUOTE (Aristos Queue @ Apr 9 2008, 11:40 AM)

It might be because I've never heard of this idea before. What exactly would this be?

Well I know various people have asked for a hash table. I asked Brian Powell for this at the last NI Week and he basically said the idea of wrapping up the C++ STL (which includes maps) had been batted around for a while.

I realized we could just wrap up STL's hash_map ourselves, which we are working on (I doubt I will be able to release it though, sorry). When thinking about a LabVIEW API, I am trying to make it as close to the Queue and Notifier API as possible, since those work pretty well, and LabVIEW users are accustomed to how they work, with respect to named versus unnamed references, and the timeouts, and the release or destroy . Whereas queues are FIFO access to a by-reference data collection, the hash map could be associative (named) access to a by-reference data collection. One feature that I am going to add is that you can request a lock on an item so that it can be modified on a block diagram and reinserted into the map without danger of a race condition. If you want more input, maybe we should start a new thread about the design, but I thought the need has been evident for a while. (given the amount of time and energy which has been put in by various people inside and outside of NI).

Anyway, if you did this in LabVIEW with polymorphic (strictly-typed) functions, it would be way better than what I am going to make. [this is exactly what Jim Kring just wrote. +1]

[Aristos Queue]

QUOTE (jdunham @ Apr 9 2008, 05:05 PM)

Anyway, if you did this in LabVIEW with polymorphic (strictly-typed) functions, it would be way better than what I am going to make. [this is exactly what Jim Kring just wrote. +1]

Oh. That's exactly what is posted to ni.com/labs. It uses the XNode polymorphism to implement the associative array. :-)

[jdunham]

QUOTE (Aristos Queue @ Apr 9 2008, 03:20 PM)

Oh. That's exactly what is posted to ni.com/labs. It uses the XNode polymorphism to implement the associative array. :-)

Yes. Those tools are pretty close. The implementation seems to be by-value, which is not as useful as the queue/notifier by-reference model. Of course one could use a notifier to implement the name lookup and referencing.

The biggest problem with the NI Labs code is that it hasn't been released yet. The NI pre-release license is very specific that they are not to be used in production code or built into any application I might distribute to anyone. The benchmarking and other fiddling around is just about the only thing I can do with them.

There was also some weirdness with cluster element name changes not propagating, but that's not very harmful. That was reported in the discussion forum http://forums.ni.com/ni/board/message?board.id=nilabs&thread.id=5' target="_blank">here.

I don't really care for the oversized icons, but I guess that just makes me a whiner. That could be overlooked if the library were releasable.

Jason

[jdunham]

QUOTE (Aristos Queue @ Apr 9 2008, 11:40 AM)

JD -- would you mind going to ni.com/labs and downloading the XNode Map implementation and adding it to your benchmarks?

The Xnode version is the pink line. I think it's safe to say it needs some performance tuning, though it's not as bad as my original version of the balanced binary tree map. Also, the delete operation would freeze up every few tests, ending up in what seemed to be an infinite loop (didn't have infinite time to verify that).

http://lavag.org/old_files/monthly_04_2008/post-1764-1207818730.png' target="_blank">

[Aristos Queue]

QUOTE (jdunham @ Apr 10 2008, 03:56 AM)

The Xnode version is the pink line.

Thank you for including this one in your test results. I've fielded your posts out to half a dozen NI engineers to evaluate the results and see if there are any obvious slowdowns that can be patched in time for the next release. We'll see what happens.

[Q^Q]

QUOTE (Aristos Queue @ Apr 10 2008, 09:31 PM)

Thank you for including this one in your test results. I've fielded your posts out to half a dozen NI engineers to evaluate the results and see if there are any obvious slowdowns that can be patched in time for the next release. We'll see what happens.

I found there are some obvious slowdowns can be fixed easily in it. I tried to change some of its code yesterday, and the performance improve is huge. The result is it runs faster than all the other approaches.

The original purpose of the LabVIEW Generic Container is just to investigate a way of providing common data structures in LabVIEW. We didn't put much effort on its performance.

Hopefully, we will release a new version of it with better performance in a couple of months.

[jdunham]

QUOTE (Q^Q @ Apr 11 2008, 09:42 AM)

I found there are some obvious slowdowns can be fixed easily in it. I tried to change some of its code yesterday, and the performance improve is huge. The result is it runs faster than all the other approaches.

The original purpose of the LabVIEW Generic Container is just to investigate a way of providing common data structures in LabVIEW. We didn't put much effort on its performance.

Hopefully, we will release a new version of it with better performance in a couple of months.

Well that's great news. I don't know what it would take to get into a real LabVIEW release, but that would be welcome. If the tool can never graduate from NI Labs in to NI LabVIEW (shipping version), it really isn't much help. Did you find/fix the problem where deletes got into an infinite loop?

If you wan't some extra homework, it would be extremely useful to be able to independently lock items read from the map so that a save read-modify-write cycle could be performed on a LabVIEW diagram. This can be done with LabIEW semaphores, but then you are adding an O(n) performance hit to get the semaphore.

Thanks for your efforts Q^Q; it's very encouraging.

[Q^Q]

QUOTE (jdunham @ Apr 12 2008, 01:09 AM)

Well that's great news. I don't know what it would take to get into a real LabVIEW release, but that would be welcome. If the tool can never graduate from NI Labs in to NI LabVIEW (shipping version), it really isn't much help. Did you find/fix the problem where deletes got into an infinite loop?

If you wan't some extra homework, it would be extremely useful to be able to independently lock items read from the map so that a save read-modify-write cycle could be performed on a LabVIEW diagram. This can be done with LabIEW semaphores, but then you are adding an O(n) performance hit to get the semaphore.

Thanks for your efforts Q^Q; it's very encouraging.

I have some urgent job to do in the two weeks. So, I just made a quick test on the XNode Map code. I think I've found the problems in the Map code. It will be fixed once I finish my current work.

The XNode Map, unlike the lvclass one, has to manage the memory of all elements data itself. So, its code is much more complicated. (Could have more bugs.)

NI is investigating the best way of providing common used data structures in LabVIEW. I'm not sure when it will make the final decision. The final app could be the XNode approach or the lvcalss approach, or another approach that includes both advantages of the former two.

Thanks a lot for benchmarking all of them!

[jzoller]

Since I'm very interested in seeing this development continue....

Here's a link-back to Aristos' performance note for the Map.lvclass:

http://forums.lavag.org/LabVOOP-Performanc...ion-t11521.html

Edit: classname was incorrect

[Aristos Queue]

Here's the original attachment:

Map_Class.zip

It was deleted when LAVA got wiped out in early 2009.

[Fab]

Here's the original attachment:

Map_Class.zip

It was deleted when LAVA got wiped out in early 2009.

Aristos,

I know this post is kind of old. So maybe things have changed, do you know if variants are still the best performers for mapping? Also, I couldn't find the XNode implementation @ NI Labs and all the links in this post are pointing to different places, so it is hard to find. Is still there? or has it made it into shipping LabVIEW?

Thanks,

Fab

[Aristos Queue]

Yes, use the Variants.

[Jeannius]

Yes, use the Variants.

I am thinking of creating a small library based on variants that would give the users a simple input/output way of doing maps/hashes/dictionary (depending on which programming language terminology you prefer). Any interest?

[Aristos Queue]

Jeannius:

LabVIEW Containers... already exist:

http://forums.ni.com/t5/LabVIEW/The-LabVIEW-Container/td-p/2838928