We have done things right, now it’s time to do things faster. We would keep Donald Knuth‘s warning in mind, “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”.
According to Jonathan Hedley, he uses YourKit Java Profiler to measure memory usage and find the performance hot point. Using statistic result of such kind of tools is crucial for the success of optimizations, it will prevent you spend time just wondering and making useless tunings, which doesn’t improve performance but also make your code unnecessarily complex and hard to maintain. Jonathan also talked about this in the “Colophon”.
We will list some tips and tricks used in Jsoup, they are randomly ordered currently, would be re-organized in the future.
1. Padding for Indent
1 | // memoised padding up to 21, from "", " ", " " to " " |
Pretty smart, right? It maintains a cache of different lengths of paddings which would cover 80% of the cases - which I assume would be based on the author’s experience and statistic.
2. Has Class Or Not?
Element#hasClass was marked as performance sensitive, for example, we want to check whether <div class="logged-in env-production intent-mouse"> has class production, split class by whitespace to an array then loop and search would work, but in a deep traverse this would be in-efficiency. Jsoup introduces Early Exit here first, by compare length with target class name to avoid unnecessary scan and search, which will also be beneficial. Then it uses a pointer detecting whitespace and performs regionMatches - honestly speaking this is the first time I got to know method String#regionMatches🙈😅
1 | public boolean hasClass(String className) { |
3. Tag Name In or Not?
As we analyzed in previous articles, HtmlTreeBuilderState will validate nest correctness by checking whether tag name in a certain collection or not. We can compare the implementation before and after 1.7.3 to have a check.
1 | // 1.7.2 |
According to the comment written by the author, “A little harder to read here, but causes less GC than dynamic varargs. Was contributing around 10% of parse GC load. Must make sure these are sorted, as used in findSorted”. Simply using static final constant array, also make them sorted so that binary search will also improve from O(n) to O(log(n)), the cost–performance ratio is pretty good here.
However, “MUST update HtmlTreebuilderStateTest if more arrays added” is not a good way to synchronize IMHO, rather than Copy & Paste I would use reflection to retrieve those constants. You may find my proposal in Pull Request #1157: “Simplify state sorting status unit test - avoid duplicated code in HtmlTreeBuilderStateTest.java”.
4. Flyweight Pattern
Do you know the trick of Integer.valueOf(i)? It maintains a IntegerCache cache from -128 to 127 or higher if configured(java.lang.Integer.IntegerCache.high), as a result, == and equals result will be different when the value is located in a different range(a classic Java interview question?). This is an example of Flyweight Pattern actually. As for Jsoup, applying this pattern will also reduce object created times and gain benefit to performance.
1 | /** |
There is also another scenario to minimize new StringBuilder GCs using the same idea.
1 | private static final Stack<StringBuilder> builders = new Stack<>(); |
Actually, CharacterReader and StringUtil are worthy to digest more and more as there are many useful tips and tricks that will inspire you.
5. Other Improvement Methods
- Use RandomAccessFile to read files that improved file read time by 2x. Check #248 for more details
- Node hierarchy refactoring. Check #911 for more details
- “Improvements largely from re-ordering the HtmlTreeBuilder methods based on analysis of various websites” - I list this one here because it’s very practical. Deeper understanding and observation of how the code will run will also give you some insights
- Call
list.toArray(0)rather thanlist.toArray(list.size())- this has been used in certain open source projects such as h2database, so I also proposed this in another Pull Request #1158
6. The Unknowns
Optimization never ends. There are still many tips and tricks I didn’t discover at this time. I would appreciate if you can share them to me if you find more inspiring ideas in Jsoup. You may find my contact information in the left sidebar of this website or simply email to ny83427 at gmail.com.
-To Be Continued-
