From 162be7200332b8e46f1fe611924cdccf3a54f0ba Mon Sep 17 00:00:00 2001 From: Wincent Colaiuta Date: Wed, 13 May 2009 11:04:16 +0200 Subject: [PATCH] Add ary_includes2, ary_includes3 functions A fairly common pattern in the codebase is successively calling the ary_includes function 1, 2 or 3 times. In the worst case scenario this incurs 3 function calls and three array traversals via a for-loop in the function. Add 2 and 3-argument variants of the function so that we can replace these instances with a single function call and a single array traversal. As shown in the benchmarking notes, this bumps the ary_includes function from 4th place in the profile (where it was the "low-hanging fruit") and right off the list. Signed-off-by: Wincent Colaiuta --- benchmarks/NOTES.txt | 33 ++++++++++++++++++++++ ext/ary.c | 23 +++++++++++++++ ext/ary.h | 2 ++ ext/parser.c | 66 +++++++++++++++++++++++--------------------- 4 files changed, 92 insertions(+), 32 deletions(-) diff --git a/benchmarks/NOTES.txt b/benchmarks/NOTES.txt index b78fccb..c6ab30e 100644 --- a/benchmarks/NOTES.txt +++ b/benchmarks/NOTES.txt @@ -78,3 +78,36 @@ improving performance due to removal of inappropriately inlined code: short slab of UTF-8 text 2.310000 0.020000 2.330000 ( 2.352641) longer slab of ASCII text 13.780000 0.100000 13.880000 ( 14.034015) longer slab of UTF-8 text 23.150000 0.130000 23.280000 ( 23.505007) + +1.7 baseline: + + short slab of ASCII text 1.380000 0.010000 1.390000 ( 1.390273) + short slab of UTF-8 text 2.150000 0.010000 2.160000 ( 2.196478) + longer slab of ASCII text 13.210000 0.080000 13.290000 ( 13.547195) + longer slab of UTF-8 text 23.510000 0.170000 23.680000 ( 23.882669) + + 19.9% next_token + 14.9% Wikitext_parser_parse + 9.5% __memcpy + 7.4% ary_includes + 6.9% ary_count + 5.5% str_append + 5.5% ary_push + 4.0% wiki_start_para_if_necessary + +After switching to IN_EITHER_OF and IN_ANY_OF macros: + + short slab of ASCII text 1.330000 0.010000 1.340000 ( 1.353676) + short slab of UTF-8 text 2.120000 0.010000 2.130000 ( 2.158128) + longer slab of ASCII text 12.350000 0.070000 12.420000 ( 12.508288) + longer slab of UTF-8 text 22.810000 0.150000 22.960000 ( 23.160102) + + 21.9% next_token + 13.5% Wikitext_parser_parse + 9.5% __memcpy + 7.1% ary_count + 5.6% str_append + 5.4% ary_push + 4.4% wiki_pop_excess_elements + 4.3% ary_entry + 4.1% wiki_start_para_if_necessary diff --git a/ext/ary.c b/ext/ary.c index 9e88cbc..a9e44ac 100644 --- a/ext/ary.c +++ b/ext/ary.c @@ -75,6 +75,29 @@ int ary_includes(ary_t *ary, int val) return 0; } +int ary_includes2(ary_t *ary, int val1, int val2) +{ + for (int i = 0, max = ary->count; i < max; i++) + { + if (ary->entries[i] == val1 || + ary->entries[i] == val2) + return 1; + } + return 0; +} + +int ary_includes3(ary_t *ary, int val1, int val2, int val3) +{ + for (int i = 0, max = ary->count; i < max; i++) + { + if (ary->entries[i] == val1 || + ary->entries[i] == val2 || + ary->entries[i] == val3) + return 1; + } + return 0; +} + int ary_count(ary_t *ary, int item) { int count = 0; diff --git a/ext/ary.h b/ext/ary.h index 6a5e744..e7010ee 100644 --- a/ext/ary.h +++ b/ext/ary.h @@ -41,6 +41,8 @@ void ary_clear(ary_t *ary); int ary_pop(ary_t *ary); void ary_push(ary_t *ary, int val); int ary_includes(ary_t *ary, int val); +int ary_includes2(ary_t *ary, int val1, int val2); +int ary_includes3(ary_t *ary, int val1, int val2, int val3); // returns a count indicating the number of times the value appears in the collection int ary_count(ary_t *ary, int item); diff --git a/ext/parser.c b/ext/parser.c index 5c8bac7..56a91f8 100644 --- a/ext/parser.c +++ b/ext/parser.c @@ -30,6 +30,8 @@ #include "wikitext_ragel.h" #define IN(type) ary_includes(parser->scope, type) +#define IN_EITHER_OF(type1, type2) ary_includes2(parser->scope, type1, type2) +#define IN_ANY_OF(type1, type2, type3) ary_includes3(parser->scope, type1, type2, type3) // poor man's object orientation in C: // instead of parsing around multiple parameters between functions in the parser @@ -1137,7 +1139,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self) switch (type) { case PRE: - if (IN(NO_WIKI_START) || IN(PRE_START)) + if (IN_EITHER_OF(NO_WIKI_START, PRE_START)) { str_append(parser->output, space, sizeof(space) - 1); break; @@ -1174,7 +1176,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self) break; case PRE_START: - if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START)) + if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START)) { wiki_emit_pending_crlf_if_necessary(parser); str_append(parser->output, escaped_pre_start, sizeof(escaped_pre_start) - 1); @@ -1219,7 +1221,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self) break; case PRE_END: - if (IN(NO_WIKI_START) || IN(PRE)) + if (IN_EITHER_OF(NO_WIKI_START, PRE)) { wiki_emit_pending_crlf_if_necessary(parser); str_append(parser->output, escaped_pre_end, sizeof(escaped_pre_end) - 1); @@ -1239,7 +1241,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self) break; case BLOCKQUOTE: - if (IN(NO_WIKI_START) || IN(PRE_START)) + if (IN_EITHER_OF(NO_WIKI_START, PRE_START)) // no need to check for 
; can never appear inside it
                     str_append(parser->output, escaped_blockquote, TOKEN_LEN(token) + 3); // will either emit ">" or "> "
                 else if (IN(BLOCKQUOTE_START))
@@ -1292,7 +1294,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case BLOCKQUOTE_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_blockquote_start, sizeof(escaped_blockquote_start) - 1);
@@ -1342,7 +1344,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case BLOCKQUOTE_END:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_blockquote_end, sizeof(escaped_blockquote_end) - 1);
@@ -1362,7 +1364,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case NO_WIKI_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_no_wiki_start, sizeof(escaped_no_wiki_start) - 1);
@@ -1389,7 +1391,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case STRONG_EM:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, literal_strong_em, sizeof(literal_strong_em) - 1);
@@ -1455,7 +1457,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case STRONG:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, literal_strong, sizeof(literal_strong) - 1);
@@ -1482,7 +1484,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case STRONG_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_strong_start, sizeof(escaped_strong_start) - 1);
@@ -1490,7 +1492,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 else
                 {
                     output = parser->capture ? parser->capture : parser->output;
-                    if (IN(STRONG_START) || IN(STRONG))
+                    if (IN_EITHER_OF(STRONG_START, STRONG))
                         str_append(output, escaped_strong_start, sizeof(escaped_strong_start) - 1);
                     else
                     {
@@ -1504,7 +1506,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case STRONG_END:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_strong_end, sizeof(escaped_strong_end) - 1);
@@ -1525,7 +1527,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case EM:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, literal_em, sizeof(literal_em) - 1);
@@ -1552,7 +1554,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case EM_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_em_start, sizeof(escaped_em_start) - 1);
@@ -1560,7 +1562,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 else
                 {
                     output = parser->capture ? parser->capture : parser->output;
-                    if (IN(EM_START) || IN(EM))
+                    if (IN_EITHER_OF(EM_START, EM))
                         str_append(output, escaped_em_start, sizeof(escaped_em_start) - 1);
                     else
                     {
@@ -1574,7 +1576,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case EM_END:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_em_end, sizeof(escaped_em_end) - 1);
@@ -1595,7 +1597,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case TT:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, backtick, sizeof(backtick) - 1);
@@ -1622,7 +1624,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case TT_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_tt_start, sizeof(escaped_tt_start) - 1);
@@ -1630,7 +1632,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 else
                 {
                     output = parser->capture ? parser->capture : parser->output;
-                    if (IN(TT_START) || IN(TT))
+                    if (IN_EITHER_OF(TT_START, TT))
                         str_append(output, escaped_tt_start, sizeof(escaped_tt_start) - 1);
                     else
                     {
@@ -1644,7 +1646,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case TT_END:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, escaped_tt_end, sizeof(escaped_tt_end) - 1);
@@ -1666,7 +1668,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
 
             case OL:
             case UL:
-                if (IN(NO_WIKI_START) || IN(PRE_START))
+                if (IN_EITHER_OF(NO_WIKI_START, PRE_START))
                 {
                     // no need to check for PRE; can never appear inside it
                     str_append(parser->output, token->start, TOKEN_LEN(token));
@@ -1800,7 +1802,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
             case H3_START:
             case H2_START:
             case H1_START:
-                if (IN(NO_WIKI_START) || IN(PRE_START))
+                if (IN_EITHER_OF(NO_WIKI_START, PRE_START))
                 {
                     // no need to check for PRE; can never appear inside it
                     str_append(parser->output, token->start, TOKEN_LEN(token));
@@ -1861,7 +1863,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
             case H3_END:
             case H2_END:
             case H1_END:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, token->start, TOKEN_LEN(token));
@@ -1884,7 +1886,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case MAIL:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, token->start, TOKEN_LEN(token));
@@ -1952,7 +1954,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case PATH:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                     str_append(parser->output, token->start, TOKEN_LEN(token));
                 else if (IN(EXT_LINK_START))
                 {
@@ -2017,7 +2019,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
             // everything else will be rejected
             case LINK_START:
                 output = parser->capture ? parser->capture : parser->output;
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(output, link_start, sizeof(link_start) - 1);
@@ -2108,7 +2110,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
 
             case LINK_END:
                 output = parser->capture ? parser->capture : parser->output;
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(output, link_end, sizeof(link_end) - 1);
@@ -2156,7 +2158,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
             //      he was very angery [sic] about the turn of events
             case EXT_LINK_START:
                 output = parser->capture ? parser->capture : parser->output;
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(output, ext_link_start, sizeof(ext_link_start) - 1);
@@ -2191,7 +2193,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
 
             case EXT_LINK_END:
                 output = parser->capture ? parser->capture : parser->output;
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(output, ext_link_end, sizeof(ext_link_end) - 1);
@@ -2229,7 +2231,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
 
             case SPACE:
                 output = parser->capture ? parser->capture : parser->output;
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(output, token->start, TOKEN_LEN(token));
@@ -2312,7 +2314,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 break;
 
             case IMG_START:
-                if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
+                if (IN_ANY_OF(NO_WIKI_START, PRE, PRE_START))
                 {
                     wiki_emit_pending_crlf_if_necessary(parser);
                     str_append(parser->output, token->start, TOKEN_LEN(token));
@@ -2358,7 +2360,7 @@ VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
                 i = parser->pending_crlf;
                 parser->pending_crlf = false;
                 wiki_rollback_failed_link(parser); // if any
-                if (IN(NO_WIKI_START) || IN(PRE_START))
+                if (IN_EITHER_OF(NO_WIKI_START, PRE_START))
                 {
                     ary_clear(parser->line_buffer);
                     str_append_str(parser->output, parser->line_ending);
-- 
2.40.1