Proposal: Runtime Performance Improvement Plan

Tested with Daffodil 3.8.0, parsing a ~5 million record file (~640 MiB) using a pre-compiled binary and creating an XML infoset redirected to /dev/null. JVM is given 9GB. JVM memory usage never exceeded 3GB.

Parse times:

• ARINC-choiceDispatch.dfdl.xsd: 230 seconds (3.8 minutes)
• ARINC-speculative.dfdl.xsd: 1025 seconds (17.0 minutes)

The speculative parsing schema is significantly slower, which is not unexpected. The way the speculative schema is written, it first attempts to parse a line as specific record type. If any fields are invalid for that record (e.g. Subsection Code, Application Type), then it backtracks to the beginning of the line and tries the next record type. Worst case this is O(N²) to find the correct record type. And each attempt at a record usually requires parsing multiple fields before before determining it parsed the wrong record type and backtracks. One possible fix for this is to for Daffodil to detect which fields are discriminated on, find a parse those bits, and then exclude branches that are known to fail the discriminator–essentially automating something similar to choice dispatch. The complexity of such an algorithm might not be worth the effort. We may just recommend that speculative parsing only be used as a last resort, and to use choice dispatch where possible.

User reported that choice dispatch variant parsed in 3.5 minutes and the speculative parsing parsed in 15 minutes, which matches the above results. Poor performance is likely not due to different input files, slower CPU, insufficient memory, or some other environmental factor.

Tested with Daffodil 3.8.0, parsing a ~5 million record arinc text file (~617 MB) and a ~5 million record binary file ( ~603 MB) using a pre-compiled binary and creating an XML infoset redirected to /dev/null. JVM is given 9GB. JVM memory usage never exceeded 4GB.

Parse times:

• ARINC-choiceDispatch.dfdl.xsd (text): 222 seconds (3.7 minutes)
• binaryFormat-choiceDispatch.dfdl.xsd (binary): 114 seconds (1.9 minutes)

Tested with Daffodil 3.8.0, parsing a ~5 million record file (~640 MiB) using a pre-compiled binary and creating different infosets redirected to /dev/null. JVM is given 9GB.

With speculative parsing, the overhead of outputting to either XML or EXI seems to be overshadowed by excessive backtracking and I/O operations. But with the more efficient choice dispatch schema, the overhead becomes more more obvious, incurring an additional 30-60% overhead. Improving the speed of our InfoseOutputters could give noticeable gains. Note however, that EXI is a separate library that we do not have the resources to optimize. And the XML InfosetOutputter is fairly simple–finding places to optimize might be difficult.

Modified Daffodil CLI to use a ByteBufferInputSource backed by a MappedByteBuffer for a 640MiB ARINC file with a null infoset outputter. Compared against unmodified Daffodil using a BucketingInputSource. Also compared against reading all bytes into an array and wrapping the array in a ByteBuffer to compare mapped vs non-mapped.

With choiceDispatch, there appears to be about 20% overhead when using the BucketingInputSource. The overhead is less, but still noticeable, with the speculative parsing schema, but that is likely because the excessive backtracking players more of a role than the input source.

It would likely be worth investigating the bucketing algorithm for potential improvements.

See DAFFODIL-2920 and PR #1273 (this has been merged), which reduced overhead compared to ByteBufferInputSource from about 15% to 5%.

Note that a change that was not included was an increase in the default bucket size to something larger than 8k. I tested various default sizes ranging as high as 68MB and did not see a change in performance. This may be worth reinvestigation with different format types and file sizes, but being relatively close in performance to the ByteBufferInputSource, we are likely to only see minimal gains at best.

A large suite of tests was run with this change and compared. There are too many numbers to reasonably include and many schemas are not publicly available, but based on the results we can conclude a few things:

1. This change in the mentioned PR did make a noticeable difference for a large group of files, ranging from just a few percent faster up to 15-25+% faster.
2. In many of the cases where improvements were seen, the gap between bucketing and non-bucketing was less than 5% slower, usually only 1-2%. If performance is critical one should use the non-bucketing algorithm, but if switching to that is cannot be done (e.g. streaming or files larger than 2GB), then in most cases the overhead is fairly minimal.
3. A small number of formats did not see benefits from this change, or did but still experienced slower performance with the bucketing algorithm. Of the publicly available schemas, this includes BMP (no improvement) and NITF (5-10% improvement but still 20% slower). Additional investigations are needed to determine issues specific to these formats.

A small gap of about 5% still remains after optimizing the BucketingInputSource.

See DAFFODIL-2921 and PR #1274, which modifies CLI parse to use a mapped byte buffer wen parsing files <= 2GB.

Tests saw about a 9-10% increase in performance when using the draft decode implementation. Note that ARINC is primarily made up of relatively short strings, so a relatively small increase in performance is not unexpected, since decoder performance improves the most when parsing fairly long strings. That said, 10% is still a noticeable improvement and worth incorporating into Daffodil, especially considering some text formats might have fairly long strings.

Note, later investigations reported in the "Large Number of Infoset Elements" section compare Daffodil 3.8.0 with and without the draft decoder change (labeled "Updated Variant") with non-ARINC data/schema. Although there is some improvement when decoding smaller shorter strings, significant performance increases aren't observed until larger strings (e.g. 10+ characters) are decoded. This may indicate that the majority of overhead is not in decoders and lies elsewhere, but also shows that improvement to decoders can lead to significant performance improvements in specific cases.

The primary barrier to merging the draft is that delimiter scanning only works for fixed width encodings, which means no UTF-8 delimiter scanning. Supporting this with the new decoders likely requires rewriting the delimiter scanning logic to be byte based rather than character based. This is a worthwhile endeavor as it will probably also speed up delimiter scanning, but this is likely not trivial to implement.

• Tuple returned by parseOneInstanceWithMaybePOU
• Lambda allocations in InfosetWalker when calling doOutputter
• Conditionally call captureValueLength (which allocates a ValueLengthState) in various string parsers so that we do not capture if it it isn't actually needed by any expressions

The combination of these changes made virtually no difference in performance (at best 2-5%, and usually with in the margin of error) and made the code much more complex. While these allocations may be important to remove in the future as larger bottle necks are found and fixed, these are within the noise and are not worth the added complexity for now.