3 Replies Last post: Feb 22, 2013 9:15 PM by Ivan Dubrov  
Ivan Dubrov Newbie 3 posts since
Nov 15, 2012
Currently Being Moderated

Feb 22, 2013 3:23 AM

com.intellij.util.diff.DiffTree (inconsistent?) behavior

Hi,

 

I am trying to improve performance of the standard properties editor to handle huge properties files (tens of thousands lines) which we have. The problem is that if you start editing such a big properties file, you get eventual lock ups (up to 20-30 seconds). After spending some time debugging/profiling, I tracked the issue to the Psi trees diffing algorithm. It looks like the problem is that when you add property at the end, the algorithm ends up generating too many diff's.

 

Looking at the DiffTree#compareLevel I noticed one subtle fact in the implementation. First it tries to go backwards (from the end to the beginning of the tree). Therefore, when it compares two PropertiesElementTypes#PROPERTIES_LIST's, it gets at the position where I added a new property. Starting from that, it enters some sort of "one off" state thinking that all properties before an added one are changed. For example, given the file:

 

test.properties

A =

B =

C =

D =

 

if I add property after property C:

 

A =

B =

C =

newProp

D =

 

the algorithm compares C to newProp, then B to C, then A to B, etc, up to the beginning of the file. Given the huge size of the properties file, it ends up with about ~20k of changes causing a major slowdown.

 

If I make this algorithm to leave first loop (one, that goes backwards) after encountering added property (by providing my own comparator that returns ThreeState.NO if property name does not match), it goes into the second loop (one that goes from the beginning to the end). Now the key part is that the second loop is actually smart enough to detect this "one off" difference between old Psi tree and new Psi tree and generates reasonably small amount of differences.

 

So, the question is, shouldn't the first loop try to match nodes using the same way as the second one?

 

P.S. With my custom comparator put into PsiBuilderImpl, the properties editor becomes responsive again -- no lockups. I also converted parser to use LighterASTNode, but given that I wasn't able to find any documentation telling the difference between ASTNodes and LighterASTNodes, I don't know if that makes difference, too.

Alexey Kudravtsev JetBrains 2,957 posts since
May 29, 2002
Currently Being Moderated
Feb 22, 2013 3:06 PM in response to: Ivan Dubrov
Re: com.intellij.util.diff.DiffTree (inconsistent?) behavior

Sounds good. Could you please create a request in the http://youtrack.jetbrains.com/issue/ ?

Alexey Kudravtsev
Intellij IDEA  developer
JetBrains, Inc
http://www.jetbrains.com
"Develop with  pleasure!"

More Like This

  • Retrieving data ...