prawnpdf/prawn — pull request #392 by alexdowad (2012-08-21 20:12:51+00:00)
Title: More performance work

Recently, I've written a number of patches to improve table layout/rendering performance, but I find that PDF rendering performance in my web app is still unacceptably slow in some cases. I've already worked on optimizing layout of *large* tables, and tables which use :inline_format, but I found that there's another thing about the tables in the PDFs I am rendering which makes them slow: in some cases, they are very squeezed horizontally, causing text to be wrapped character by character over a number of lines.

I added a test to the benchmark to simulate this scenario, profiled, and found some more hotspots. These patches improve things... but we're still not totally "there" yet. There are a few places in the wrapping code where Regexp initialization is still a hotspot (previously I submitted a patch to initialize SCAN_PATTERN only once, but there are other Regexps which are being re-initialized for every line of text, which in this case means every character).

Worse than that, I discovered there is some O(n^2) behavior in the wrapping code (when wrapping long strings, without natural breakpoints, in a very narrow space). What happens is:

1. The long string is given to LineWrap as a single "fragment".
2. LineWrap runs a regexp over it to look for breakpoints, and doesn't find any.
3. LineWrap calculates the width of the string, to see if it will fit on one line (it won't).
4. LineWrap starts wrapping character by character, checking the cumulative width of the line at each step.
5. After fitting one or two characters and hitting the end of the line, LineWrap returns to Wrap. Wrap chops the one or two characters which fit off the front of the string, and passes it to LineWrap again (to use as a new line).

Calculating the width of a string takes O(n) time, and if only one character fits on each line, it will be done "n" times. In my profiling results, I see this as a very high number of calls to some low-level methods like Document#font (hundreds of thousands of calls, to render a table with 1300 cells).

Unfortunately, I don't see any easy way to rectify this without redesigning the line wrapping code. I'm not sure what to do right now, but in the meantime, I'm submitting these optimizations, and working on a patch to make all the specs pass under JRuby 1.6. (Right now there is a PNG spec which fails, due to differing behavior of Zlib under MRI and JRuby.)