[flang-dev] FW: Performance of std::remove_if in F18 file I/O

Fri Apr 3 07:57:01 PDT 2020

Hi all,

I've got some results for Windows on an Intel Core i5-9600K<https://www.amazon.co.uk/gp/product/B07HHLX1R8/ref=ppx_yo_dt_b_search_asin_title?ie=UTF8&psc=1>; although only with the program Richard attached, not with Steve's modified version: https://gist.github.com/DavidTruby/aa885134abcab6746ddef962fd90bfc0

The result show that on Windows with msvc std::remove_if is significantly faster in this case (where there are carriage returns). This matches my expectations given how much emphasis Microsoft put on C++ features over C features in their compiler and runtime. When using clang on Windows, all 3 implementations are indistinguishable in performance.
Therefore if we're likely to want to optimise for the slow case for Windows since this case is more common there, the remove_if implementation would be a better choice. I don't have any data about what happens if there's no carraige returns on Windows though, if Steve could share his modified benchmark then I'd be happy to get those results too.

Another thing to consider: In a previous email about this topic (http://lists.llvm.org/pipermail/flang-dev/2020-February/000236.html) Steve mentioned that we may need to extend this to normalising other types of line end characters in future. I believe the std::remove_if implementation is trivial to extend to that, whereas it seems the RemoveCarriageReturns implementation relies on the fact that you're only looking for one character to normalise? Please correct me if I'm wrong here.

Thanks
David Truby

________________________________
From: flang-dev <flang-dev-bounces at lists.llvm.org> on behalf of Steve Scalpone via flang-dev <flang-dev at lists.llvm.org>
Sent: 03 April 2020 01:19
To: Richard Barton <Richard.Barton at arm.com>; flang-dev at lists.llvm.org <flang-dev at lists.llvm.org>
Subject: Re: [flang-dev] FW: Performance of std::remove_if in F18 file I/O

Hi Rich,

Most systems, including UNIX derivatives, use a single linefeed character (^J, ASCII LF = 0x0a) as an end-of-line marker in source files.  Others (DOS, Windows) use a carriage return / linefeed sequence (0x0d 0x0a).  The f18 compiler normalizes source files by removing all of their carriage return characters.

I have extended the benchmark to add another path that runs over source code containing no original carriage return characters.  We expect this use case to be the most common outside Windows environments.

I posted the test results.  Each set has four runs, each comprising the combination of remove_if and RemoveCarriageReturns with linefeeds and carriage returns.

In summary, RemoveCarriageReturns is faster when there actually are no carriage returns to remove.  For cases with carriage returns, RemoveCarriageReturns is faster on x86 Linux, about the same on macOS, and slower on aarch64.

Linux x86-64
https://gist.github.com/sscalpone/11f58f248cc2a984be80a6b0867836ae

macOS
https://gist.github.com/sscalpone/79434dcdfd8e5d8b568a485329562063

aarch64
https://gist.github.com/sscalpone/8aaec89cadb27c7ee580c6f460c955f4

 - Steve

On 4/2/20, 12:11 PM, "flang-dev on behalf of Richard Barton via flang-dev" <flang-dev-bounces at lists.llvm.org on behalf of flang-dev at lists.llvm.org> wrote:

    Hi flang-dev

    During the code review on the patch to switch F18's file handling code from using C library to C++ library routines [1] we hit upon a case that seemed to show the C++ std::remove_if routine was much slower than the C routine on some platforms. The routine in question is RemoveCarriageReturns in lib/Parser/source.cpp [2] and existing findings are at [3][4][5]. We are seeing quite different performance numbers across different platforms.

    Peter Klausler made a little performance harness around the two proposed implementations  and a third naïve implementation that we would expect to be the slowest (for reference rather than proposed for use in F18). I have attached this harness, with a few NFC modifications to this email.

    Is anyone able to give this a run on their system and report their results? Please enable optimisation whilst compiling as this will match the F18 configuration we most care about. Please include the compiler and C & C++ standard library versions used as well as the architecture and platform. We've not tried this at all on Windows, so we'd be interested if anyone can provide that info.

    The implementation using std::remove_if is preferred on LLVM-like style grounds so we would like to make this change. However, we don't want to significantly regress the performance of F18 file reading while we do that. We'd like to make the change but only if the new code is in the same performance ballpark as the existing code.

    Thanks
    Rich

    [1] https://github.com/flang-compiler/f18/pull/1032
    [2] https://github.com/flang-compiler/f18/blob/96c6be633ff65ec6d84c18e0d14393137d8097dd/lib/Parser/source.cpp#L73
    [3] https://github.com/flang-compiler/f18/pull/1032#discussion_r391846621
    [4] https://github.com/flang-compiler/f18/pull/1032#discussion_r392125932
    [5] https://github.com/flang-compiler/f18/pull/1032#discussion_r392311031
    -----------------------------------------------------------------------------------
    This email message is for the sole use of the intended recipient(s) and may contain
    confidential information.  Any unauthorized review, use, disclosure or distribution
    is prohibited.  If you are not the intended recipient, please contact the sender by
    reply email and destroy all copies of the original message.
    -----------------------------------------------------------------------------------
    _______________________________________________
    flang-dev mailing list
    flang-dev at lists.llvm.org
    https://lists.llvm.org/cgi-bin/mailman/listinfo/flang-dev

_______________________________________________
flang-dev mailing list
flang-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/flang-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/flang-dev/attachments/20200403/2c04215b/attachment-0001.html>