Description Per Mildner 2015-03-09 09:23:16 EDT

Created attachment 251407 [details]
A naive alternative implementation of ConfigurableLineTracker

org.eclipse.jface.text.ConfigurableLineTracker.nextDelimiterInfo(String, int) uses (linear time in contents length) TextUtilities.indexOf(String[], String, int), which makes ConfigurableLineTracker.set(String text) quadratic in the length of text.

The problem is that TextUtilities.indexOf() always looks through the entire remaining text, which ensures that ConfigurableLineTracker.set(String) looks at the entire text for each line in the text, which makes it quadratic in the length of the text in the worst (and common case) where the number of lines is linear in the length of the text.

Informal measurements shows that ConfigurableLineTracker.set() takes more than a minute for a 10000 line, 200k length char string, making it 2000 times slower than DefaultLineTracker. Making the input ten times larger (in number of lines and text length) makes the slowdown ten times worse.

This makes ConfigurableLineTracker uselessly slow, also for not very large documents.

An informal reimplementation (attacked) that just calls text.startsWith(delim,index) for each valid line delimiter at each text index, shows linear time performance, and a slowdown less than ten compared to DefaultLineTracker. This suggests that some very simple replacement for (or re-implementation of) TextUtilities.indexOf() would suffice. This also suggests that the major problem with TextUtilities.indexOf() is not the ambitious ideas mentionend in bug 96951.