]> git.wincent.com - wikitext.git/commitdiff
Add ary_includes2, ary_includes3 functions
authorWincent Colaiuta <win@wincent.com>
Wed, 13 May 2009 09:04:16 +0000 (11:04 +0200)
committerWincent Colaiuta <win@wincent.com>
Wed, 13 May 2009 09:04:16 +0000 (11:04 +0200)
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 <win@wincent.com>
benchmarks/NOTES.txt
ext/ary.c
ext/ary.h
ext/parser.c

index b78fccbd459b7625ae3ad2e0b57512aa064b46f7..c6ab30e9148d26920bbcdab200f51eb1d1516de1 100644 (file)
@@ -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
index 9e88cbc3badcb245d506a3ea25c78ad7668d31c1..a9e44ac6d4daa2623223c196fd46ecc27e394bb8 100644 (file)
--- 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;
index 6a5e744b233e177fedfed56ff2fb7a940ea90994..e7010ee1037f50c6a14534e3da692bc9455205a3 100644 (file)
--- 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);
index 5c8bac7261a20409f8264d26005c5b6d71e9a281..56a91f87fa5e8b15a15ed6b3aa7f6f8a11323f9b 100644 (file)
@@ -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 <pre>; can never appear inside it
                     str_append(parser->output, escaped_blockquote, TOKEN_LEN(token) + 3); // will either emit "&gt;" or "&gt; "
                 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);