Map, implemented with classes, for 8.5

[Aristos Queue]

QUOTE(JFM @ Oct 17 2007, 03:38 AM)

I don't know if it is a bug in the "show buffer allocations" algorithm, but I must say it is not always consistent.

I would expect the algorithm to set a dot on all outputs that needs to allocate a buffer, i.e. on all places were the input buffer can not be reused.

In the picture below the dot appears only on the left shift register terminal, eventhough the code resizes the array twice in the loop, but there is no dot to indicate that there is a buffer allocated on the function outputs.

http://lavag.org/old_files/monthly_10_2007/post-5958-1192609210.png' target="_blank">

What AQ is saying, is just what I would expect, i.e. that the dot should appear on the output where the buffer has been allocated, but in the picture above it appears on the shift register instead of the build array output.

My point is that the location of the dots in not always correct (IMO), in respect to what actually causes the buffer allocation, and this makes the "hide the dots" game so difficult (or fun?) sometimes.

/J

The dots appear where a buffer is allocated, not where a buffer is resized. The exact same buffer is used all the way through the VI you've shown here. There isn't any new buffer allocated. The entire loop is done in place, ie, in the same buffer.

[Mellroth]

QUOTE(Aristos Queue @ Oct 18 2007, 09:36 PM)

The dots appear where a buffer is allocated, not where a buffer is resized. The exact same buffer is used all the way through the VI you've shown here. There isn't any new buffer allocated. The entire loop is done in place, ie, in the same buffer.

Maybe it was a bad example, but I tried to give another example of where the buffer allocation tool does not really help in finding the spots that cause buffer allocations.

Without the shift register the dot appears on the build array output, so it is easy to see that the build array is the place to be optimized, but with the shiftregister, the dot appears on the shift register instead.

/J

[Aristos Queue]

QUOTE(JFM @ Oct 19 2007, 08:32 AM)

where the buffer allocation tool does not really help in finding the spots that cause buffer allocations.

The dots never help to find buffer re-allocations, which is what you're talking about here. A re-allocation is where an existing buffer gets larger. The dots help to find places where a new buffer is allocated and from that point forward you now have two buffers instead of one. The dots indicate places where your data actually gets copied and you are now maintaining two copies of the data.

[Aristos Queue]

I have posted a new revision of the Map class, now with tree balancing. I have edited the original post (so that anyone in the future who stumbles on the thread doesn't use the old revision by accident). For convenience, here's a link to the original post so you can download the revised class. As you can read in that post, I didn't implement the tree balancing. Thanks to Jason Dunham who offered up his code for everyone's consumption.

[Norm Kirchner]

QUOTE(Aristos Queue @ Oct 14 2007, 04:44 PM)

If the data type changes from String to LabVIEW Object (as I intend to be able to do in the next version of LV), then Compare Elements will still work just fine -- a class is a scalar as far as any operations on the class are concerned. The fact that there is data bundled together underneath to implement that scalar is hidden away. Note: Do not take this comment as a reason to believe that we'll have class comparison working in the next version of LabVIEW. I may intend this happen, but then, I intended to have classes in 8.0, and we see what happened there...

AQ, What I was asking regarding not the use of just a class, but something more complex, like a cluster. So my comment about needing compare aggregate is still valid.

[jdunham]

QUOTE(Norm Kirchner @ Nov 9 2007, 12:29 PM)

AQ, What I was asking regarding not the use of just a class, but something more complex, like a cluster. So my comment about needing compare aggregate is still valid.

Norm, you are right, but in the current version, CompareKey is a dynamic dispatch VI. If you make a key with a different data type, you have the opportunity to redefine the CompareKey function. Then you can sort your clusters however you like, with the built-in compare aggregates comparison or else with an application-specific comparison. For example, some of the cluster's fields could be ignored when performing the comparison.

[Tomi Maila]

Hi guys! Great job adding balancing algorithm to the tree!

Now that we have a balanced in-place OOP map for objects it's feasible to ask how does this tree perform compared to LabVIEW build-in map namely variant attributes. To my experience variant attributes peform well. They accept any data type and not oly LabVIEW objects. So the question is, if there is actually some real reason to use this LVOOP implementation of map instead of variant attributes. Is this implementation perhaps more memory efficient for LabVIEW objects? Has anybody done any testing?

Tomi

- Is having a headache after 12 hours of XNode development.

[jdunham]

QUOTE(Tomi Maila @ Nov 9 2007, 02:21 PM)

Hi guys! Great job adding balancing algorithm to the tree! Now that we have a balanced in-place OOP map for objects it's feasible to ask how does this tree perform compared to LabVIEW build-in map namely variant attributes. To my experience variant attributes peform well. They accept any data type and not oly LabVIEW objects. So the question is, if there is actually some real reason to use this LVOOP implementation of map instead of variant attributes. Is this implementation perhaps more memory efficient for LabVIEW objects? Has anybody done any testing?

I haven't done any profiling, and I think I exceeded my time budget by a few hundred percent on this topic. It would be very interesting to see some performance results. I would imagine that if you had a complicated data type, then the variant attribute approach might get expensive since the attributes are also stored as variants and so you would be flattening and unflattening the data on every access.

Also, I have to say thanks to you, Tomi, for adding the custom probe to this project. I couldn't have developed or debugged any of my code without it.

Another note (I can't seem to make this a separate message).

During development, I invented some graphical conventions to help me understand the recursion and inheritance, but I started a new thread for discussing them.

Jason

[Aristos Queue]

QUOTE(Tomi Maila @ Nov 9 2007, 04:21 PM)

\ Has anybody done any testing?

Nope. At the end of the day I'm still a C++ programmer, and G is just a hobby. :-)

It was enough for me to prove that LV Classes could solve this use case.

Now, as someone who has actually crawled through the Variant code extensively -- I don't know what happens for small trees, but I'm going to bet that the LVClass solution blows the other away as the number of key-value pairs increases (probably noticable around 2000 pairs). I won't go into why, but that's my bet.

[billings11]

Hey Aristos,

I have been studying this implementation with a lot of interest. I really love what you have been doing working to move labview in the right direction. I started with the non-AVL version just to study what you did. I think I understand how you are doing this, its very cool.

When I saw all of these advanced labview techniques and new structures being used, I couldn't help but wonder if the 8.5 application builder is ready for them. I can see some of these techniques really helping me, but I get nervous about projects building before I go too far with my code. So I tried it with demo.vi in this example and the AB gave me an ambiguous error:

Error 1502 occurred at Invoke Node in AB_Source_VI.lvclass:Close_Reference.vi->AB_Build.lvclass:Copy_Files.vi->AB_Application.lvclass:Copy_Files.vi->AB_Build.lvclass:Build.vi->AB_EXE.lvclass:Build.vi->AB_Build.lvclass:Build_from_Wizard.vi->AB_UI_FRAMEWORK.vi->AB_CreateNewWizard_Invoke_CORE.vi->EBUIP_CreateNewWizard_Invoke.vi->EBUIP_CreateNewWizard_Invoke.vi.ProxyCaller

Possible reason(s):

LabVIEW: Cannot save a bad VI without its block diagram.

On the additional exclusions page or the builder I messed with the settings and figured out that if you have the "Modify project library file after removing unused members" option checked the build generates this error and no executabe gets built. If I uncheck that option the build works fine. (Apart from the annoying namespace conflict warning on every method vi, but I can live with that.) I am a little uncertain what that option even means. So this is buildable, but there is a little trick to making it build. Any ideas what content in this example would be causing this behavior? What is the AB trying to do that is causing the error?

[Aristos Queue]

QUOTE(billings11 @ Feb 4 2008, 04:26 PM)

What is the AB trying to do that is causing the error?

No clue. Someone else tried building this and I thought had done so successfully, but they may have just turned that option off anyway for some reason. I'll try to remember to check into this in the next couple days. Thanks for the post.

[Aristos Queue]

QUOTE(Aristos Queue @ Feb 4 2008, 06:19 PM)

I'll try to remember to check into this in the next couple days.

This has already been reported as CAR 4ELES2FN. The CAR is marked as fixed in the next full release of LabVIEW (not the next bug fix release). The workaround, in the meantime, is, as you discovered, to uncheck that option in the build.

[Tomi Maila]

QUOTE(Aristos Queue @ Feb 5 2008, 07:59 PM)

The CAR is marked as fixed in the next full release of LabVIEW (not the next bug fix release).

Oh, there is a maintenace release coming up? When should we expect this... ?

[Aristos Queue]

QUOTE(Tomi Maila @ Feb 5 2008, 12:11 PM)

Oh, there is a maintenace release coming up? When should we expect this... ?

My advice? Expect nothing. Prepare for anything.

If you want something more helpful, I'm just a developer. :-)

[brian175]

QUOTE(Tomi Maila @ Nov 9 2007, 05:21 PM)

Hi guys! Great job adding balancing algorithm to the tree!

Now that we have a balanced in-place OOP map for objects it's feasible to ask how does this tree perform compared to LabVIEW build-in map namely variant attributes. To my experience variant attributes peform well. They accept any data type and not oly LabVIEW objects. So the question is, if there is actually some real reason to use this LVOOP implementation of map instead of variant attributes. Is this implementation perhaps more memory efficient for LabVIEW objects? Has anybody done any testing?

Tomi

- Is having a headache after 12 hours of XNode development.

QUOTE(Aristos Queue @ Nov 10 2007, 07:59 PM)

Nope. At the end of the day I'm still a C++ programmer, and G is just a hobby. :-)

It was enough for me to prove that

LV

Classes could solve this use case.

Now, as someone who has actually crawled through the Variant code extensively -- I don't know what happens for small trees, but I'm going to bet that the LVClass solution blows the other away as the number of key-value pairs increases (probably noticable around 2000 pairs). I won't go into why, but that's my bet.

How much do you want to bet? I haven't gotten the chance to look at the code or review this lengthy post but here are my testing results and VIs:

LV Class Map: (time in ms)

Number.......Create........Fetch........Delete

100................341............5.............3

1000............49532..........85...........14

2000...........240160........182...........26

LV Variant:

Number.......Create........Fetch........Delete

100.................2.............0...............0

1000..............38.............2...............1

2000..............39.............2...............2

Download File:post-987-1202386557.vi

Download File:post-987-1202386565.vi

Brian

(Is there a way to insert a table into a post? Extra spaces seem to be removed)

[Aristos Queue]

QUOTE(brian175 @ Feb 7 2008, 06:27 AM)

How much do you want to bet? I haven't gotten the chance to look at the code or review this lengthy post but here are my testing results and VIs:

a) I haven't looked at your test code at all yet, but something really smells about the LVVariant speeds because this is something I've benchmarked many times and it has a pretty nasty growth curve*. Staying constant for creation between 1000 and 2000 is pretty close to completely unexpected.

b) Did you use Jason Durham's revised version of the Map that has the AVL balancing code? If not, please see the very first post in this thread which has been edited to have both my original and his modified version. Without the tree balancing, it would be easy to get some pretty nasty times (as I said in my original post).

c) If you are using Durham's version, then there may be one other problem. Do you insert random keys or keys in some already sorted order? The worst case scenario for the tree balancing is going to be inserting already sorted information into the tree -- you'll trigger the tree balancing code A LOT. There's an optimal insert order if your data is already sorted to avoid the tree balancing, which is to start by inserting the middle element of your list, then the middle element of each of the halves, then the middle element of each quarter, etc. ANY map implementation has situations in which its performance seriously degrades, and almost all of them are optimized for random key inserts.

*as of LabVIEW 8.5... I have long hoped that someone would improve the performance of this method, and I heard someone might be working on it for future LV version.

[ragglefrock]

QUOTE(Aristos Queue @ Feb 8 2008, 01:51 PM)

a) I haven't looked at your test code at all yet, but something really smells about the LVVariant speeds because this is something I've benchmarked many times and it has a pretty nasty growth curve*. Staying constant for creation between 1000 and 2000 is pretty close to completely unexpected.

b) Did you use Jason Durham's revised version of the Map that has the AVL balancing code? If not, please see the very first post in this thread which has been edited to have both my original and his modified version. Without the tree balancing, it would be easy to get some pretty nasty times (as I said in my original post).

c) If you are using Durham's version, then there may be one other problem. Do you insert random keys or keys in some already sorted order? The worst case scenario for the tree balancing is going to be inserting already sorted information into the tree -- you'll trigger the tree balancing code A LOT. There's an optimal insert order if your data is already sorted to avoid the tree balancing, which is to start by inserting the middle element of your list, then the middle element of each of the halves, then the middle element of each quarter, etc. ANY map implementation has situations in which its performance seriously degrades, and almost all of them are optimized for random key inserts.

*as of LabVIEW 8.5... I have long hoped that someone would improve the performance of this method, and I heard someone might be working on it for future LV version.

I ran the tests he had posted with the updated balanced tree and saw times twice as long what he posted. Not sure if that had anything to do with me running it on a Mac (seems like it really shouldn't).

[Tomi Maila]

Actually LabVIEW has two built-in maps: variants and named queues. Named queues could be used as a map by using the name of the queue as a key and what ever you write into the queue as value. So much about the weak link to the discussion on this thread. I was one day comparing the creation time of a named queue with the creation time of a unammed queue whose reference was stored in a variant map. The creation time for both increased exponentially as the number of queues increased. This is expected behaviour for a binary tree implementation. It appeared that named queues scaled up so much poorer than variant maps that I decided to change my application architecture from using named queues to unnamed queues stored in variant maps. I don't know what map algorithm is behind the named queue primitives but it certainly is poorer than the binary tree implementation of variant attributes in LabVIEW 8.5.

[brian175]

QUOTE(Aristos Queue @ Feb 8 2008, 02:51 PM)

a) I haven't looked at your test code at all yet, but something really smells about the LVVariant speeds because this is something I've benchmarked many times and it has a pretty nasty growth curve*. Staying constant for creation between 1000 and 2000 is pretty close to completely unexpected.

b) Did you use Jason Durham's revised version of the Map that has the AVL balancing code? If not, please see the very first post in this thread which has been edited to have both my original and his modified version. Without the tree balancing, it would be easy to get some pretty nasty times (as I said in my original post).

c) If you are using Durham's version, then there may be one other problem. Do you insert random keys or keys in some already sorted order? The worst case scenario for the tree balancing is going to be inserting already sorted information into the tree -- you'll trigger the tree balancing code A LOT. There's an optimal insert order if your data is already sorted to avoid the tree balancing, which is to start by inserting the middle element of your list, then the middle element of each of the halves, then the middle element of each quarter, etc. ANY map implementation has situations in which its performance seriously degrades, and almost all of them are optimized for random key inserts.

*as of LabVIEW 8.5... I have long hoped that someone would improve the performance of this method, and I heard someone might be working on it for future LV version.

a) It seems like the results are the complete opposite of what you expected

b) I did use the revised version

c) The keys were already sorted, but when I create random keys the results are the same

Download File:post-987-1202569102.vi

Download File:post-987-1202569109.vi

[Tomi Maila]

QUOTE(brian175 @ Feb 9 2008, 05:00 PM)

a) It seems like the results are the complete opposite of what you expected

b) I did use the revised version

c) The keys were already sorted, but when I create random keys the results are the same

I can verify Brian's results. However it seems that the balanced version of the OOP map is much slower than AQ's original version. For 1000 elements balanced version is about ten fold slower than the non-balanced version and variant version is about 100 fold faster than the non-balanced version in adding the key-value pairs. For 10000 elements both OOP maps are too slow for me to wait. Clearly they are many folds slower than the variant version.

[Aristos Queue]

QUOTE(brian175 @ Feb 9 2008, 09:00 AM)

a) It seems like the results are the complete opposite of what you expected

Pretty much. And Tomi's timing info about variant attributes vs. named queues also surprises me. The variant code has a single array implementation for the map that makes it reallocate when it runs out of space. That means that when inserting an element, the variant attribs should suffer a major penalty that the others (both named queues and OO maps) don't have to take. On fetch, they should all be just about equivalent -- the algorithms are pretty much equivalent. Definitely worth some exploration.

Other tasks are going to pull my attention away from this topic for a couple months, but I've filed some notes to myself to dig into it when I free up again.

[EDIT] Tomi, I thought of something that could be penalizing the OO versions. The recursion has to allocate a pool of cloned VIs. Try running your 10000 test and then, without stopping the VI, run the 10000 test a second time. See if this improves the speed.

[Tomi Maila]

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

[EDIT] Tomi, I thought of something that could be penalizing the OO versions. The recursion has to allocate a pool of cloned VIs. Try running your 10000 test and then, without stopping the VI, run the 10000 test a second time. See if this improves the speed.

That didn't have a huge affect. However I noticed that there were a few VIs in the Map class that were consuming most of the time when adding elements to the map, namely Branch Node.lvclass:Insert on Right.vi and Branch Node.lvclass:Insert on Left.vi. Using inplace element structure in these two VIs significantly improved the performance of map element additions. However the performance is still much weaker than in the variant map. Now for 1000, 10 000 and 100 000 elements the addition times for OOP map are 157, 1562 and 17933 ms. So we get nearly linear scaling which is good. However the respective numbers for variant map are 16, 295 and 8509 ms which is still significantly faster but non-linear. I guess for 1 000 000 elements the OOP map would now take the lead.

The element removal is now the bottleneck for OOP maps after the change. The removal times of 1000, 10 000 and 100 000 elements are 1 210, 28 917 and 409 072 respectively. The scaling is not linear. The removal times of 1000, 10 000 and 100 000 elements for variant map are 18, 199 and 5108 respectively. Significantly faster than OOP map but again a little stronger non-linearity than with OOP version.

Second run suggested by AQ affected the perfomance a little. The addition times of 1000, 10 000 and 100 000 elements are 118, 1555 and 18 508. The removal times of 1000, 10 000 and 100 000 elements are 2035, 55 318 and 641 088 respectively. So the addition times gain a small improvement but the removal times actually perform worse which is totally unexpected.

[jdunham]

Ok, I have also been curious about some of the issues raised by Tomi, so I added some more map types and improved the benchmark tester with some dynamic dispatching wrappers.

I fixed some of the problems with the AVL-rebalanced binary tree, but it still is not as fast as the unbalanced tree. I tried to play a game of hide-the-dots to get rid of unnecessary buffer allocations (usually data copies) but with only limited success. It's possible that it could be fixed, because a lot of time is spent rebalancing the tree. There might be tweaks to make it rebalance fewer times, or to eliminate some of the memory copies made during rebalancing. Overall it seems like a lost cause. Sorry, AQ, but I think some problems were just not meant to be solved with by-value objects

Variant Attributes still have the best performance. I know that in older LV versions they were terrible, so kudos to NI.

The graph on the left shows the best performers, and the graph on the right is the same data, zoomed differently so the worst performers can be compared

(Right graph's X axis shows smaller data sets and its Y axis shows times a couple orders of magnitude slower)

I made another map consisting of a hash table of queues, which is a reasonable pure-G implementation. The hash lookup returns an unnamed queue containing the stored value, so the hash map only stores the queues and their keys, rather than the actual data. Each hash bucket contains an array of queues, so if there is a hash collision (two items hash to the same bin) then the map has to do a search for all the items in the bucket.

Since queue references are pretty fast, this method gives the variant attributes a run for their money. The insert and delete times were not as great as the fetch times, but for my application that's perfectly acceptable. Since it uses singleton queues, there is also a locking feature, so you can safely modify an item and replace it in the map while other threads can either preview the data or wait their turn for a locked copy.

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 would be extremely useful to have a fast and polymorphic set of built-in functions, and the strong typing of the queues and notifiers would be a big improvement over using variant attributes, not to mention that variant attributes can't do locking and seem like a crazy hack anyway.

Here are the VIs so that you can play along at home...

Download File:post-1764-1207693477.zip

[Norm Kirchner]

Before AQ whips up his reply I wanted to interject a question on the note of variant attributes.

If the data stored is of any reasonable size, is there any expectation of in-placeness when extracting, modifying and placing back the attribute?

Thanks

[Aristos Queue]

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

QUOTE (Norm Kirchner @ Apr 8 2008, 10:39 PM)

Before AQ whips up his reply I wanted to interject a question on the note of variant attributes.

If the data stored is of any reasonable size, is there any expectation of in-placeness when extracting, modifying and placing back the attribute?

Reading or writing an existing attribute always results in a copy. I'm not sure about adding a new attribute or deleting an attribute -- depending upon how it was implemented, if you delete an attribute, the "deleted attribute" output may be set without a copy (aka using the same top swap trick I've described elsewhere used by queues and notifiers). You could then modify the attribute and then put it back in. I don't know the implementation details.

QUOTE

Sorry, AQ, but I think some problems were just not meant to be solved with by-value objects

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.

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?