Tracking issue: performance

[nrc]

Nothing much to track yet, and not quite a priority, but we need to do some performance work at some point. Even moderate sized crates take quite some time to format, if we want to be run regularly on large projects, we need to make some improvements and ensure we do not do worse as we get better at formatting.

todo list:

• some kind of benchmarking to make sure we don't regress (need to know time difference for optimised vs debug too)
• profile a long-ish run to see where we're spending our time
• Incremental formatting #385 incremental reformatting
• benchmarking
• profiling

[topecongiro]

0.1.9-nightly () is an order of magnitude slower than the last time I benchmarked (cc #1599).
I have not investigated further since currently the performance is not high priority.
Just leaving it as a comment here since I think it is worth sharing.

[nrc]

Some concrete steps I think would be good to do:

• identify some 'typical' medium to large sized projects and measure the formatting time. Keep track of these large benchmarks
• profile the above to identify where we're spending time
• add some smaller benchmarks to the test suite
• some form of incremental reformatting (based on timestamps or diffs or something like that)
• investigate using a rope or other data structure rather than string concatenation
• investigate more pre-allocation of memory (probably requires the above first)
• look out for any > O(n) behaviour - we've had some nasty blow-ups in the past

[marcusklaas]

I don't know if this is the right place for this, but these are the top 25 function calls I found using callgrind.

--------------------------------------------------------------------------------
         Ir  file:function
--------------------------------------------------------------------------------
103,139,410  ???:<alloc::vec::Vec<T>>::extend_with [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 94,217,847  ???:<rustfmt_nightly::comment::CharClasses<T> as core::iter::iterator::Iterator>::next [/home/marcus/rustfmt/target/release/rustfmt]
 68,762,712  ???:syntax::codemap::CodeMap::lookup_filemap_idx [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 45,885,887  ???:rustfmt_nightly::format_lines [/home/marcus/rustfmt/target/release/rustfmt]
 42,856,475  ???:syntax::parse::lexer::StringReader::bump [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 38,002,028  ???:memcpy@GLIBC_2.2.5 [/usr/lib64/libc-2.25.so]
 33,136,711  /checkout/src/libcore/fmt/mod.rs:core::fmt::write [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]
 30,705,361  ???:<rustfmt_nightly::comment::UngroupedCommentCodeSlices<'a> as core::iter::iterator::Iterator>::next [/home/marcus/rustfmt/target/release/rustfmt]
 28,438,225  ???:syntax::codemap::CodeMap::span_to_snippet [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 24,381,665  ???:_ZN6syntax5parse5lexer12StringReader13advance_token17h3765cf14d7e01289E.llvm.3E1208B2 [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 23,491,170  /checkout/src/liballoc_jemalloc/../jemalloc/src/jemalloc.c:mallocx [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]
 22,470,635  ???:_ZN4core3ptr13drop_in_place17hdbe8add465ba12a0E.llvm.A0C0D04A [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 21,306,647  ???:rustfmt_nightly::comment::combine_strs_with_missing_comments [/home/marcus/rustfmt/target/release/rustfmt]
 21,207,596  ???:alloc::str::<impl str>::contains [/home/marcus/rustfmt/target/release/rustfmt]
 20,497,162  ???:syntax::codemap::CodeMap::bytepos_to_file_charpos [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 20,359,629  /checkout/src/liballoc_jemalloc/../jemalloc/src/jemalloc.c:sdallocx [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]
 19,626,552  ???:syntax::codemap::CodeMap::lookup_byte_offset [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 18,100,492  ???:<strings::string_buffer::Chars<'a> as core::iter::iterator::Iterator>::next [/home/marcus/rustfmt/target/release/rustfmt]
 18,009,897  /checkout/src/liballoc_jemalloc/lib.rs:__rde_alloc [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]
 17,218,912  ???:syntax_pos::span_encoding::Span::data [/home/marcus/rustfmt/target/release/rustfmt]
 17,014,640  ???:syntax_pos::FileMap::lookup_line [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax_pos-a42779b429274f57.so]
 15,312,800  ???:<rustfmt_nightly::file_lines::FileLines as core::clone::Clone>::clone [/home/marcus/rustfmt/target/release/rustfmt]
 15,118,140  /checkout/src/liballoc/vec.rs:<alloc::vec::Vec<T>>::reserve [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]
 14,648,403  ???:_ZN6syntax5parse6parser11TokenCursor4next17h0eae928732eb485aE.llvm.DFCFA51F [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libsyntax-5fbd27a1f9bceeec.so]
 14,597,952  /checkout/src/libcore/fmt/mod.rs:<core::fmt::Write::write_fmt::Adapter<'a, T> as core::fmt::Write>::write_str [/home/marcus/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/libstd-5d73bd20dd205fcf.so]

Some stats are to be expected, such as the many calls to the CodeMap and FileMap functions. The things that stand out to me are the many calls in the comment module, calls related to String (de)allocation and concatenation and format_lines. Note: these are the functions with the most calls, which is not per se the ones where the most time is spent, but they should still give some leads as to where performance could be improved.

[scampi]

In order to properly wrap lines even with unicode chars, it is necessary to use unicode_width::UnicodeWidthStr to compute the length of a line instead of String::len. However, it's computationaly more expensive as noted in #3618 (comment)