PreviousNextTracker indexSee it online !

(6/22) 2843334 - SideKick: Folding mode performance fix

Operations like "collapse all folds" on large files with a large tree can take a very long time to perform, due to SideKickParsedData.getTreePathForPosition calling the recursive method getNodeAt to map offsets to tree nodes (I got this information from jprofiler). The attached patch builds a TreeMap for mapping offset ranges (IAssets) to tree nodes, then uses this map to efficiently find the tree node of an offset. The patch trades memory for performance.

On a sample xml file, containing ~110,000 lines, "Collapse all folds" in SideKick folding mode takes about 3 minutes without the performance fix (during which, jEdit is frozen), and only 1 second with the performance fix.

Submitted shlomy - 2009-08-24 - 02:03:05z Assigned nobody
Priority 5 Category None
Status Open Group None
Resolution None Visibility No


2009-08-24 - 05:55:28z
Please wait with this. I see there are issues with this patch.
2009-08-24 - 21:04:17z
I've fixed my patch, it should be working fine now.
Please note: For files with large trees, like large xml files, even scrolling down the file can cause jEdit to hang for a while or be very slow, due to the computation of the fold levels for each line visible on screen (during the scrolling). This patch fixes both the scrolling slowness as well as operations like "collapse all folds". Bringing "collapse all folds" down from more than 3 minutes to 1 second I think pretty much justifies it...
2009-08-24 - 21:09:08z
There is one small issue with this patch, which I think is theoretical only: It won't work if the SideKick tree nodes are created lazily by the SideKick parser. I think this is a theoretical issue, as it is very difficult to do "random parsing" of the buffer, which could justify lazy creation. Nevertheless, if there are parsers that use lazy creation, this patch will not work for them and then we can do one of the following;
1. add an API method in SideKickParser or SideKickParsedData to indicate if lazy creation is used.
2. Change the creation of the TreeMap to be lazy as well, by adding listeners to the mutable tree nodes. (not sure to what degree this is possible)
2009-08-24 - 21:14:04z
I'm glad to see version #2 takes advantage of this map for other operations besides fold collapsing, since I was pretty sure that is not the only place in the code where it does that sort of thing. I was going to post as a comment, the question of whether you thought the map could be used anywhere else...

2009-08-24 - 21:29:10z
The performance problems were caused by the basic fold handler method "getFoldLevel". This method is implemented differently in any fold handler. In SideKick, it was implemented by finding the tree node using "getTreePathForPosition", which performed a recursive search on the tree nodes until it found the deepest one that matches the buffer offset. Now, "getTreePathForPosition" no longer finds the node by scanning the tree - it looks the offset up in the map. This method is a central one, it is used both for fold handling, following the caret in the tree, etc.
Where else do you think this map can be used?
2009-09-01 - 18:02:34z
This patch provides a great performance improvement for SideKick folding mode, but causes redundant overhead (both the time it takes to build the map, and memory) when this folding mode is not used.
I don't know what the right way to do this is. Maybe just build the map in a lazy way, adding to it whenever an asset is searched? Then, the lookup should be in the map first, and then recursively in the tree.


2009-08-24 - 21:01:28z

Performance fix for Sidekick folding mode