Need an efficient method of addings items to a tree control

[Mark Yedinak]

I am working on a test application that will literally have thousands of data files which comprise a test. The user would like to have the ability to select specific files to include in the test. The files will be stored on the hard drive in various folders. Obviously a tree control is the best choice for presenting the data files to the user and allowing them to select or deselect the desired folders/files to include in the test. The problem I am running into is adding the files to the tree control once they select a base path. At least the problem is that the current method is not very efficient. I have disabled front panel updates to help minimize the time however it is still taking considerable time to add all of the files to tree control. I am recursively traversing the directory structure and adding the sub-folders to the tree. The current method I am using is adding the files to the tree individually. This is incredibly slow and for the tree structure that I am working with (472 folders and 11000 files under the base directory) it is taking approximately 110 seconds to fill the tree. This is an unacceptably long time for the user. I do know that multiple items can be added to the tree at one time which significantly improves the performance however the problem with this approach is that I am limited to adding the files at the end of the tree only. As I traverse the directory structure I need to be able to insert the file list under a specific sub-folder name (which translate to a specific parent tag in the tree) and from what I can see I don't have this option. Does anyone have any suggestions on how to achieve a fast method for updating the tree efficiently?

[asco]

you should be able to do what you want with the "add multiple items to end" functionality. you'll just need to maintain the array of items separately from the tree and whenever an update to the tree is necessary you'll first modify the array of items and then delete everything in the tree and reapply the item array. you don't need to know the parent/child tags to use the functionality, you can simply indent the items properly and then use the output from the method to map the tag labview spits back to the original item in the array (see "child two" in screenshot).

also, once you populate the tree and map the tags back to the original item array, you can then do incremental updates to it if you want using the single insertion and deletion methods.

if this works out for you, please reply back to the forum with the stats (number of files, time consumed, amount of memory used, etc.) of the old vs. the improved method.

[jdunham]

This sounds like a relatively hard problem given the minimal tools you have for this in LabVIEW. If it were me, I would leverage the OS file dialog box. Unfortunately that generally lets you browse any folder on the computer. If it's windows, you could map your folder to an unused hard drive letter and then start the filedialog box at the top of that, and then strenuously object if the user picks a file on some other drive.

[mje]

Just curious, have you run any metrics to verify that all that time is indeed spent operating on the tree, and not for example, getting the file/folder listing? If that's the OpenG list VI, I suspect it might be slow...there's a double array search happening in it, and if you're using it recursively...

Trees are indeed slow in LV, but from my experience, your an order of magnitude or two slower than what I'd expect for that many items. I'd be surprised if the tree is the bottleneck given the times you quote and the fact that you're disabling updates.

[jdunham]

What about an interface that doesn't try to populate the entire tree in advance. You could trap the item open event, filter it, fix the tree item which is about to open, and then open it programmatically. Most of the time, your users probably won't ever look at most of the thousands of items in your tree, so there's no real need to stuff them into the tree control.

[JustinThomas]

QUOTE (Mark Yedinak @ Apr 3 2009, 03:33 AM)

I am working on a test application that will literally have thousands of data files which comprise a test.

Dear Mark,

Why do you have to update all the files and folders at the start? How about just adding the top level folders in the beginning and then dynamically populating the sub folders as an when the user selects the particular folder. I think this would be pretty fast with the front panel updates disabled.

Also as MJE suggested I too think the problem would be elsewhere and not with adding tree elements. I think the tree updates are pretty fast with front panel updates disabled. Try finding out time taken for various sections of the code to execute which may give a better idea of the problem.

Regards,

Justin Thomas

[Mark Yedinak]

QUOTE (MJE @ Apr 2 2009, 10:00 PM)

Just curious, have you run any metrics to verify that all that time is indeed spent operating on the tree, and not for example, getting the file/folder listing? If that's the OpenG list VI, I suspect it might be slow...there's a double array search happening in it, and if you're using it recursively...

Trees are indeed slow in LV, but from my experience, your an order of magnitude or two slower than what I'd expect for that many items. I'd be surprised if the tree is the bottleneck given the times you quote and the fact that you're disabling updates.

Yes I have run the profile tool as well as other timings and verified that the bottle neck is in the tree processing. Specifically the Add Item and Check Tag subVis. I have looked at the code for these subVIs and they do very little besides check the tree for the presence of a tag or add a single item. the Add Item was taking an average of 3.2 ms per call and it was getting called over 10000 times. as I said there are lots of files which comprise this test.

I could possibly populate the tree dynamically as particular branches are opened. This could imporve the overall performance. I could also try the array method as well.

Thanks for the suggestions and input. Designing the UI for presenting these tests is certainly challenging. As I mentioned this particular test consists of over 10000 data files. Presenting this to the user and allowing them to select and set of files for a single execution is a nontrivial problem.

[Rolf Kalbermatter]

QUOTE (Mark Yedinak @ Apr 3 2009, 02:43 AM)

Yes I have run the profile tool as well as other timings and verified that the bottle neck is in the tree processing. Specifically the Add Item and Check Tag subVis. I have looked at the code for these subVIs and they do very little besides check the tree for the presence of a tag or add a single item. the Add Item was taking an average of 3.2 ms per call and it was getting called over 10000 times. as I said there are lots of files which comprise this test.

I could possibly populate the tree dynamically as particular branches are opened. This could imporve the overall performance. I could also try the array method as well.

Thanks for the suggestions and input. Designing the UI for presenting these tests is certainly challenging. As I mentioned this particular test consists of over 10000 data files. Presenting this to the user and allowing them to select and set of files for a single execution is a nontrivial problem.

Are you sure you have really enabled "Defer Front Panel Updates". 3.2 ms for an Add Item Tree element sounds fairly long although I don't have specific numbers. Or was this 3.2 ms with an already heavily populated tree?

I do think the suggestion to built up an internal data structure first that represents your tree as an array of clusters and after that populate the tree from that is probably not a bad one. It also gives you better performance check abilities to see if the file enumerating or the tree population is really munching up the big part of your processing time.

The other suggestion to only update the tree as it is getting needed (when a folder item is expanded) would be my first approach anyhow. No need to go through a lengthy recursive folder enumeration when the user newer will look at 99% of those items anyhow.

Rolf Kalbermatter

[jdunham]

QUOTE (rolfk @ Apr 2 2009, 11:04 PM)

Are you sure you have really enabled "Defer Front Panel Updates". 3.2 ms for an Add Item Tree element sounds fairly long although I don't have specific numbers. Or was this 3.2 ms with an already heavily populated tree?

I can confirm Mark's observations. I made a very simple LVOOP tree for another purpose and for my testing, I loaded my folder structure into it from my enormous labview project with embedded SVN folders. The tree composed itself in about a second, but to test recursing through the tree and to view the result, I wrote code to put each element into a tree control. That part takes about 5 minutes to run. Defer panel updates didn't help noticeably.

I really think dynamically populating the tree is the way to go; I assume that the most file manager shells do something similar. It would be a good XControl.

[Phillip Brooks]

QUOTE (jdunham @ Apr 3 2009, 11:05 AM)

I really think dynamically populating the tree is the way to go; I assume that the most file manager shells do something similar. It would be a good XControl.

I'll share my XControl. It's rough around the edges, but it started out as throw-away code to help us upgrade from LabVIEW 7.0 and TestStand 3.0. I populate the tree as it is expanded...

There is no 'delete' function, and the folders don't refresh automatically. There are some .NET callbacks that you could register to watch for events from the OS and refresh the tree dynamically.

See the attached ZIP file (LabVIEW 8.6.1)

[Mark Yedinak]

QUOTE (Phillip Brooks @ Apr 3 2009, 10:45 AM)

I'll share my XControl. It's rough around the edges, but it started out as throw-away code to help us upgrade from LabVIEW 7.0 and TestStand 3.0. I populate the tree as it is expanded...

There is no 'delete' function, and the folders don't refresh automatically. There are some .NET callbacks that you could register to watch for events from the OS and refresh the tree dynamically.

See the attached ZIP file (LabVIEW 8.6.1)

Can you please post a version saved for 8.5. We haven't updated yet to 8.6. I would appreciate taking a look at your X-Control.

QUOTE (rolfk @ Apr 3 2009, 02:04 AM)

Are you sure you have really enabled "Defer Front Panel Updates". 3.2 ms for an Add Item Tree element sounds fairly long although I don't have specific numbers. Or was this 3.2 ms with an already heavily populated tree?

I do think the suggestion to built up an internal data structure first that represents your tree as an array of clusters and after that populate the tree from that is probably not a bad one. It also gives you better performance check abilities to see if the file enumerating or the tree population is really munching up the big part of your processing time.

The other suggestion to only update the tree as it is getting needed (when a folder item is expanded) would be my first approach anyhow. No need to go through a lengthy recursive folder enumeration when the user newer will look at 99% of those items anyhow.

Rolf Kalbermatter

Yes, the FP updates are definitely defered and I have confirmed that the delay is isolated to the Add Item and Check Tag subVis. I did see better performance on smaller trees but it seems that once the tree gets fairly large the performance really drops off. I will need to experiment with a few of the suggestions provided here. I would like to see the tree control's performance improved and some additional features added. It would be nice if you could add multiple items to the tree at any location given a parent tag rather than only at the end of the tree.

Thanks again for the suggestions.

[Phillip Brooks]

QUOTE (Mark Yedinak @ Apr 3 2009, 01:12 PM)

Can you please post a version saved for 8.5. We haven't updated yet to 8.6. I would appreciate taking a look at your X-Control.

See attached .ZIP (LV 8.5) Ignore the name; the zip file contains 8.5 files

Download File:post-949-1238779541.zip

This was the callback I was talking about... http://msdn.microsoft.com/en-us/library/sy...temwatcher.aspx

[Mark Yedinak]

QUOTE (Phillip Brooks @ Apr 3 2009, 12:26 PM)

See attached .ZIP (LV 8.5) Ignore the name; the zip file contains 8.5 files

http://lavag.org/old_files/post-949-1238779541.zip'>Download File:post-949-1238779541.zip

Thanks

[Phillip Brooks]

Christina has a timely entry on her blog that should make managing your your tree control appearance a bit easier :thumbup: