OSCommerce Product Manager

OSCommerce Product Manager for Windows
Tasklist

FS#111 - Category list is slow to populate...

Attached to Project: OSCommerce Product Manager
Opened by Mario A. Valdez-Ramirez (mvaldez) - Wednesday, 08 September 2004, 01:24 GMT-6
Last edited by Mario A. Valdez-Ramirez (mvaldez) - Monday, 03 April 2006, 00:46 GMT-6
Task Type Bug Report
Category Backend / Core
Status Closed
Assigned To Mario A. Valdez-Ramirez (mvaldez)
Operating System All
Severity Low
Priority Immediate
Reported Version any
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No

Details

Adding more than ~400 nodes to the TTreeView control is very slow. It takes several seconds in our testing workstation.

Pending on evaluate using Virtual TreeView (MPL/LGPL) which people says is pretty fast. However this path may get us far away from the objective of porting the application to Linux (with Kylix).

Maybe using compilation conditionals.
This task depends upon

Closed by  Mario A. Valdez-Ramirez (mvaldez)
Monday, 03 April 2006, 00:46 GMT-6
Reason for closing:  
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 12 September 2004, 01:04 GMT-6

Deferred.
Using Virtual TreeView requires extensive rewriting. (Not that extensive, but too much work).

Closing by now. To be reopened later.
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 02 April 2006, 17:16 GMT-6

This is a copy of content of Bug #320 which really belongs here:


Due to performance issues with the TreeView implementation in Windows, building a tree with thousands of nodes is too slow. We have several alternatives:

a) Replace the TreeView component with a faster one. We have Virtual TreeView (http://www.delphi-gems.com/VirtualTreeview/VT.php) by Mike Lischke. Previously we concluded that using this component w<as not possible due to critical licensing issues. (The problem was that the license was not clear, latter, when it was clear the package was LGPL, it required a non-open source package which we cannot use). Now we know we can use it. (The non-open source package is not really required, it can be disabled). Now we face the problem of the migration to Lazarus, we think VTV does not work in Lazarus. (We can fix it using conditional compilation).

b) Avoid reloading the full category tree. We can add the new nodes to the remote database, and then update locally the category tree, without downloading and rebuilding. However, this goes against the our design goals: to have the most updated information without assuming anything.

c) We can add a quick feeding option, to add categories quickly, plus a recursive category deletion option. It would allow specifying a list of categories to add and then adding them in a batch. The recursive deleting would allows the user to delete the specified category plus all the inner ones.


Pending to evaluate all options.
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 02 April 2006, 17:17 GMT-6


I have reopened this bug, because I am receiving more and more reports of people using huge stores which have big problems with the performance of the category tree.
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 02 April 2006, 17:17 GMT-6

Changing priority and severity.
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 02 April 2006, 17:37 GMT-6


Ok, previous posts were an introduction for the following:

I was blaming the ttreeview performance for this problem, and I was right, it was a problem with ttreeview.

However, it was a single issue that was causing this: AbsoluteIndex (from treenode) is superslow. Very, greatly, super, mega, freakingly SLOW.

If we dismiss the use of AbsoluteIndex (which we called EVERYTIME we added a node to the tree), a 10,000 categories tree loads in seconds. (Otherwise, it takes MINUTES).

In the search for speed improvements, we also modified the PRopm_AddCatTreeNode procedure so that does not cross all categories with themselves while looking for child nodes. This was a O(n) operation, the needed iterations grown exponentially. Now, the procedure do a limited crossing: now it order the catlist by parent_id, do a binary search for the first item with the requested parent_id, then iterates until finishes with the requested parent_id. Now, it is not really a crossing. This reduced the count of iterations from (Cats * Cats) to (Cats * 2) [approx].

So, for example, if the user has 1000 categories, previously the application tested for a match between parent/child nodes 1000000 times before finishing building the tree. One million times. Now, AbsoluteIndex was used only when adding the node, not while testing. So, for 1000 nodes, if AbsoluteIndex took 0.15 seconds (one hundred fifty milliseconds) building the whole tree would take 150 seconds (2.5 minutes); which is unacceptable when adding, deleting or editing categories.

So, the suboptimal implementation of PRopm_AddCatTreeNode along with the use of AbsoluteIndex caused this slowness.

Pending to fix.
Comment by Mario A. Valdez-Ramirez (mvaldez) - Sunday, 02 April 2006, 19:19 GMT-6

Just clear my language:

In the text reading "This was a O(n) operation, the needed iterations grown exponentially" I meant: "This was a O(n2) operation, the needed iterations grown geometrically".

Comment by Mario A. Valdez-Ramirez (mvaldez) - Monday, 03 April 2006, 00:46 GMT-6

This bug has been fixed.

Loading...