Hi,
I've been playing around with the knuth line breaking code and made a slight refactoring of it. The result is 38% faster for START align, 78% faster for CENTER align and 12% for JUSTIFY align.
Meassured using 'time' command, jdk1.4.2_03, -Xmx200000000 and a rough edition of Sherlock Holmes from the the Gutenberg project:
http://apache.org/~bckfnn/advsh12s.fo http://apache.org/~bckfnn/advsh12c.fo http://apache.org/~bckfnn/advsh12j.fo
(s=start, c=center, j=justify alignment)
The patch is here:
http://issues.apache.org/bugzilla/show_bug.cgi?id=32612
The performance improvement comes from: - Using -INFINITE_RATIO when there is too little shrink in a line for an element to fit. - Reuse the BestRecords instance instead of creating an instance for each line * for each element. - Using ArrayList instead of LinkedList. - Avoiding the indexOf calls on Paragraph. - Use '*' instead of Math.pow() for calculating demerit. - Split activeList into an array indexed by line and nodes within a line linked together.
These improvements could also be applied to the existing code, so I think the more interesting point is the quality of the refactoring job. I guess that I have moved away from a faithful implementation of Knuth's algorithm, but I think the result is more in line with common java code.
Opinions?
regards, finn
