Unicode characters in UTF8 and generation performance.

[KonstantinTomashevich]

Hello! I've been using re2c for different simplistic parsers for my pet projects for perhaps 1.5 years already. Great tool and helped me a lot, thanks.

But lately I've decided to build custom C preprocessor and I've decided to try to do it "new way" with proper support of unicode characters in identifiers. So I've used unicode_identifier.re as an example.

However, there is one significant issue: re2c is much slower when using these huge unicode groups. unicode_identifier.re already takes 0.5s on my machine to be generated (re2c version 4.1, arch linux with lts kernel, endeavouros distribution). And adding another rule like " " "123" identifier "something" { return 0; } to the example effectively doubles generation time, making it 1s.

In my case I try to use it like that:

        tokenization_new_line_preprocessor_determine_type:
            /*!re2c
             !use:check_unsupported_in_code;

             whitespace+ { goto tokenization_new_line_preprocessor_determine_type; }

             "if" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_IF); }
             "ifdef" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_IFDEF); }
             "ifndef" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_IFNDEF); }
             "elif" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_ELIF); }
             "elifdef" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_ELIFDEF); }
             "elifndef" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_ELIFNDEF); }
             "else" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_ELSE); }
             "endif" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_ENDIF); }
             "include" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_INCLUDE); }

             "define" whitespace+ @marker_sub_begin identifier @marker_sub_end "("
             {
                 current_token.define_identifier.begin = marker_sub_begin;
                 current_token.define_identifier.end = marker_sub_end;
                 PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_DEFINE_FUNCTION);
             }

             "define" whitespace+ @marker_sub_begin identifier @marker_sub_end
             {
                 current_token.define_identifier.begin = marker_sub_begin;
                 current_token.define_identifier.end = marker_sub_end;
                 PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_DEFINE_OBJECT);
             }

             "undef" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_UNDEF); }
             "pragma" whitespace+ "once" { PREPROCESSOR_TOKEN (TOKEN_TYPE_PREPROCESSOR_PRAGMA_ONCE); }

             // Fallthrough.
             identifier { }
             * { }
             $ { }
             */

In the example above I try to guess what is going on after # on newline and how would I process it. Therefore, having identifier in fallthrough section is important in order to avoid capturing things like ifdef when it really is ifdefohmygod. It is also convenient to use it in matching while deciding which type of define are we dealing with, but I'm not sure if it is a proper way of doing things.

What am I doing wrong in this case? Or is it an expected issue right now?

P.S. It also generates 15k loc, that are difficult to digest for the compiler (Clang, release mode) and take another 1.3s to compile, but that might be my mistake when defining API for re2c, I guess.

P.P.S. When using ASCII identifiers, re2c generates file in 4ms and clang compiles it in 118ms in release mode. Just for comparison.

[skvadrik]

What am I doing wrong in this case? Or is it an expected issue right now?

It's sort of works as expected, meaning that I never tried to optimize Unicode lexers in particular (and I guess it's not easy - Unicode definitions are just huge compared to ASCII). But there might be some obvious things to optimize.

It'm not sure if there's anything to be done immediately. Can you post a complete example? The above lacks some re2c definitions, e.g. block check_unsupported_in_code. Also, it would be good if there was an example that I could compile with clang/gcc after processing it with re2c (but if that's a problem, just any example that compiles with re2c will do).

For code size (just the generated text, not binary) try --case-ranges if you haven't already.

Please post a complete example and I will have a look, this is definitely something I'd like to fix.

[KonstantinTomashevich]

For code size (just the generated text, not binary) try --case-ranges if you haven't already.

Yes, it is with case ranges already, unfortunately.

e.g. block check_unsupported_in_code

Right now it is just empty for unicode, I've added it to print errors on non-ASCII characters outside of comments and string literals when not using unicode identifiers.

It'm not sure if there's anything to be done immediately. Can you post a complete example?

It is just a pile of code in early and unusable stage, as I've just started experimenting several days ago. So, there is not much sense in it. I guess, I will just continue developing and it'll be better to analyze it when it is closer to completion (I can develop with ASCII and just swap it to unicode in the end).

However, as I written in the beginning, this can be sort-of-observed on encoding example. Running re2c unicode_identifier.re -o test.c -8 --case-ranges -I ../../../include/ (from its directory) already takes 0.5s on my side. And if you add another rule with identifier, it might be even worse. For example, with this patch it would already take 2s to generate and would generate almost 12k loc:

diff --git a/examples/c/encodings/unicode_identifier.re b/examples/c/encodings/unicode_identifier.re
index 6a612d68a..dd52c10f3 100644
--- a/examples/c/encodings/unicode_identifier.re
+++ b/examples/c/encodings/unicode_identifier.re
@@ -17,6 +17,9 @@ static int lex(const char *s) {
         identifier  = id_start id_continue*;
 
         identifier { return 0; }
+        "#define " identifier "(" { return 0; }
+        "#define " identifier { return 0; }
+        "#if " identifier { return 0; }
         *          { return 1; }
     */
 }

Also, thanks for the very fast reply, didn't expect it. :)

[skvadrik]

However, as I written in the beginning, this can be sort-of-observed on encoding example.

Good point, thanks. Now I remember that I made myself a TODO to look into it - with so many language backends this one test now is a bottleneck for parallel test run.

[KonstantinTomashevich]

Out of curiosity, I've checked the performance on re2c 3.1, as I still didn't update my main pet project to 4.1. unicode_identifier.re with the patch above takes roughly 1.35s to generate when using 3.1, in comparison with 2s when using re2c 4.1. 1.35s is still not very fast, but I think it might be a good investigation direction nevertheless.

[KonstantinTomashevich]

Other interesting thing about 3.1 vs 4.1 is that perf stat shows significantly more instructions per cycle: ~3.85 in 3.1 vs ~2.54 in 4.1. My guess is that it is somehow connected to memory access, but it is just a guess, I'm not that experienced here. But it seems to correlate with speed difference between 3.1 and 4.1.

[skvadrik]

With perf record / perf report I see that 95% of the time is spent in closure construction (on the encoding example). It's the core determinization algorithm. I'll investigate the difference between 3.1 and 4.1, thanks for the pointer.

[skvadrik]

Commits 3734d5b and 862eee4 add ~1.5x speedup on the example discussed above.

[KonstantinTomashevich]

Thanks you very much for looking into this. I'm kind of stuck in procrastination with my current project, therefore I don't think I'll check this out earlier than next month, so I cannot give any feedback right now. But, anyway, it is greater to hear that you were able to discover and implement these optimizations.