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|
|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
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