parser: fix quadratic pointer chasing

In the AST, lists (e.g. the list of statements in a file) are kept in
singly-linked lists -- each AST node has a `next` pointer available for
this purpose.

Previously, a node was added to the list by starting from the head,
chasing to the last, and appending. So creating a list of length N would
take ~N^2/2 pointer dereferences.

Now, we always (temporarily) keep the last as well, so appending is O(1)
instead of O(N).

Given a keymap

    xkb_keymap {
    xkb_keycodes {
    minimum = 8;
    minimum = 8;
    minimum = 8;
    minimum = 8;
    minimum = 8;
    [... repeated N times ...]
    };
    xkb_types {};
    xkb_compat {};
    xkb_symbols {};
    };

The compilation times are

N       | Before   | After
--------|----------|-------
10,000  | 0.407s   | 0.006s
20,000  | 1.851s   | 0.015s
30,000  | 5.737s   | 0.021s
40,000  | 12.759s  | 0.023s
50,000  | 21.489s  | 0.035s
60,000  | 40.473s  | 0.041s
70,000  | 53.336s  | 0.039s
80,000  | 72.485s  | 0.044s
90,000  | 94.703s  | 0.048s
100,000 | 118.390s | 0.057s

Another option is to ditch the linked lists and use arrays instead. I
got it to work, but its more involved and allocation heavy so turns out
to be worse without further optimizations.

Signed-off-by: Ran Benita <ran@unusedvar.com>

3 files changed, 73 insertions, 61 deletions

diff --git a/src/xkbcomp/ast-build.c b/src/xkbcomp/ast-build.c
index 64051c7..c2f095d 100644
--- a/src/xkbcomp/ast-build.c
+++ b/src/xkbcomp/ast-build.c
@@ -55,20 +55,6 @@
 #include "ast-build.h"
 #include "include.h"
 
-ParseCommon *
-AppendStmt(ParseCommon *to, ParseCommon *append)
-{
-    ParseCommon *iter;
-
-    if (!to)
-        return append;
-
-    for (iter = to; iter->next; iter = iter->next);
-
-    iter->next = append;
-    return to;
-}
-
 static ExprDef *
 ExprCreate(enum expr_op_type op, enum expr_value_type type, size_t size)
 {
@@ -568,7 +554,7 @@ XkbFileFromComponents(struct xkb_context *ctx,
     enum xkb_file_type type;
     IncludeStmt *include = NULL;
     XkbFile *file = NULL;
-    ParseCommon *defs = NULL;
+    ParseCommon *defs = NULL, *defsLast = NULL;
 
     for (type = FIRST_KEYMAP_FILE_TYPE; type <= LAST_KEYMAP_FILE_TYPE; type++) {
         include = IncludeCreate(ctx, components[type], MERGE_DEFAULT);
@@ -581,7 +567,10 @@ XkbFileFromComponents(struct xkb_context *ctx,
             goto err;
         }
 
-        defs = AppendStmt(defs, &file->common);
+        if (!defs)
+            defsLast = defs = &file->common;
+        else
+            defsLast = defsLast->next = &file->common;
     }
 
     file = XkbFileCreate(FILE_TYPE_KEYMAP, NULL, defs, 0);
diff --git a/src/xkbcomp/ast-build.h b/src/xkbcomp/ast-build.h
index 46c7fbb..3afb080 100644
--- a/src/xkbcomp/ast-build.h
+++ b/src/xkbcomp/ast-build.h
@@ -27,9 +27,6 @@
 #ifndef XKBCOMP_AST_BUILD_H
 #define XKBCOMP_AST_BUILD_H
 
-ParseCommon *
-AppendStmt(ParseCommon *to, ParseCommon *append);
-
 ExprDef *
 ExprCreateString(xkb_atom_t str);
 
diff --git a/src/xkbcomp/parser.y b/src/xkbcomp/parser.y
index 5a2f11e..9b16fc7 100644
--- a/src/xkbcomp/parser.y
+++ b/src/xkbcomp/parser.y
@@ -169,9 +169,13 @@ resolve_keysym(const char *name, xkb_keysym_t *sym_rtrn)
         enum xkb_map_flags mapFlags;
         xkb_keysym_t    keysym;
         ParseCommon     *any;
+        struct { ParseCommon *head; ParseCommon *last; } anyList;
         ExprDef         *expr;
+        struct { ExprDef *head; ExprDef *last; } exprList;
         VarDef          *var;
+        struct { VarDef *head; VarDef *last; } varList;
         VModDef         *vmod;
+        struct { VModDef *head; VModDef *last; } vmodList;
         InterpDef       *interp;
         KeyTypeDef      *keyType;
         SymbolsDef      *syms;
@@ -183,6 +187,7 @@ resolve_keysym(const char *name, xkb_keysym_t *sym_rtrn)
         KeyAliasDef     *keyAlias;
         void            *geom;
         XkbFile         *file;
+        struct { XkbFile *head; XkbFile *last; } fileList;
 }
 
 %type <num>     INTEGER FLOAT
@@ -196,11 +201,15 @@ resolve_keysym(const char *name, xkb_keysym_t *sym_rtrn)
 %type <str>     MapName OptMapName
 %type <atom>    FieldSpec Ident Element String
 %type <keysym>  KeySym
-%type <any>     DeclList Decl
-%type <expr>    OptExprList ExprList Expr Term Lhs Terminal ArrayInit KeySyms
-%type <expr>    OptKeySymList KeySymList Action ActionList Coord CoordList
-%type <var>     VarDecl VarDeclList SymbolsBody SymbolsVarDecl
-%type <vmod>    VModDecl VModDefList VModDef
+%type <any>     Decl
+%type <anyList> DeclList
+%type <expr>    Expr Term Lhs Terminal ArrayInit KeySyms
+%type <expr>    OptKeySymList KeySymList Action Coord CoordList
+%type <exprList> OptExprList ExprList ActionList
+%type <var>     VarDecl SymbolsVarDecl
+%type <varList> VarDeclList SymbolsBody
+%type <vmod>    VModDef
+%type <vmodList> VModDefList VModDecl
 %type <interp>  InterpretDecl InterpretMatch
 %type <keyType> KeyTypeDecl
 %type <syms>    SymbolsDecl
@@ -213,15 +222,19 @@ resolve_keysym(const char *name, xkb_keysym_t *sym_rtrn)
 %type <geom>    ShapeDecl SectionDecl SectionBody SectionBodyItem RowBody RowBodyItem
 %type <geom>    Keys Key OverlayDecl OverlayKeyList OverlayKey OutlineList OutlineInList
 %type <geom>    DoodadDecl
-%type <file>    XkbFile XkbMapConfigList XkbMapConfig
+%type <file>    XkbFile XkbMapConfig
+%type <fileList> XkbMapConfigList
 %type <file>    XkbCompositeMap
 
 %destructor { FreeStmt((ParseCommon *) $$); }
     <any> <expr> <var> <vmod> <interp> <keyType> <syms> <modMask> <groupCompat>
     <ledMap> <ledName> <keyCode> <keyAlias>
+%destructor { FreeStmt((ParseCommon *) $$.head); }
+    <anyList> <exprList> <varList> <vmodList>
 /* The destructor also runs on the start symbol when the parser *succeeds*.
  * The `if` here catches this case. */
 %destructor { if (!param->rtrn) FreeXkbFile($$); } <file>
+%destructor { FreeXkbFile($$.head); } <fileList>
 %destructor { free($$); } <str>
 
 %%
@@ -249,7 +262,7 @@ XkbFile         :       XkbCompositeMap
 XkbCompositeMap :       OptFlags XkbCompositeType OptMapName OBRACE
                             XkbMapConfigList
                         CBRACE SEMI
-                        { $$ = XkbFileCreate($2, $3, (ParseCommon *) $5, $1); }
+                        { $$ = XkbFileCreate($2, $3, (ParseCommon *) $5.head, $1); }
                 ;
 
 XkbCompositeType:       XKB_KEYMAP      { $$ = FILE_TYPE_KEYMAP; }
@@ -258,17 +271,16 @@ XkbCompositeType:       XKB_KEYMAP      { $$ = FILE_TYPE_KEYMAP; }
                 ;
 
 XkbMapConfigList :      XkbMapConfigList XkbMapConfig
-                        { $$ = (XkbFile *) AppendStmt((ParseCommon *) $1,
-                                                      (ParseCommon *) $2); }
+                        { $$.head = $1.head; $$.last->common.next = &$2->common; $$.last = $2; }
                 |       XkbMapConfig
-                        { $$ = $1; }
+                        { $$.head = $$.last = $1; }
                 ;
 
 XkbMapConfig    :       OptFlags FileType OptMapName OBRACE
                             DeclList
                         CBRACE SEMI
                         {
-                            $$ = XkbFileCreate($2, $3, $5, $1);
+                            $$ = XkbFileCreate($2, $3, $5.head, $1);
                         }
                 ;
 
@@ -298,8 +310,27 @@ Flag            :       PARTIAL                 { $$ = MAP_IS_PARTIAL; }
                 ;
 
 DeclList        :       DeclList Decl
-                        { $$ = AppendStmt($1, $2); }
-                |       { $$ = NULL; }
+                        {
+                            /*
+                             * TODO: This is needed because of VModDecl, which
+                             * is a list and is "inlined" into the DeclList.
+                             * Should change to avoid the O(N)-append behavior,
+                             * like we do in the other lists.
+                             */
+                            if ($2) {
+                                if (!$1.head)
+                                    $$.head = $2;
+                                else
+                                    $$.head = $1.head;
+                                if (!$1.last)
+                                    $$.last = $2;
+                                else
+                                    $$.last = $1.last->next = $2;
+                                while ($$.last->next)
+                                    $$.last = $$.last->next;
+                            }
+                        }
+                |       { $$.head = $$.last = NULL; }
                 ;
 
 Decl            :       OptMergeMode VarDecl
@@ -309,9 +340,9 @@ Decl            :       OptMergeMode VarDecl
                         }
                 |       OptMergeMode VModDecl
                         {
-                            for (VModDef *vmod = $2; vmod; vmod = (VModDef *) vmod->common.next)
+                            for (VModDef *vmod = $2.head; vmod; vmod = (VModDef *) vmod->common.next)
                                 vmod->merge = $1;
-                            $$ = (ParseCommon *) $2;
+                            $$ = (ParseCommon *) $2.head;
                         }
                 |       OptMergeMode InterpretDecl
                         {
@@ -389,10 +420,9 @@ VModDecl        :       VIRTUAL_MODS VModDefList SEMI
                 ;
 
 VModDefList     :       VModDefList COMMA VModDef
-                        { $$ = (VModDef *) AppendStmt((ParseCommon *) $1,
-                                                      (ParseCommon *) $3); }
+                        { $$.head = $1.head; $$.last->common.next = &$3->common; $$.last = $3; }
                 |       VModDef
-                        { $$ = $1; }
+                        { $$.head = $$.last = $1; }
                 ;
 
 VModDef         :       Ident
@@ -404,7 +434,7 @@ VModDef         :       Ident
 InterpretDecl   :       INTERPRET InterpretMatch OBRACE
                             VarDeclList
                         CBRACE SEMI
-                        { $2->def = $4; $$ = $2; }
+                        { $2->def = $4.head; $$ = $2; }
                 ;
 
 InterpretMatch  :       KeySym PLUS Expr
@@ -414,30 +444,28 @@ InterpretMatch  :       KeySym PLUS Expr
                 ;
 
 VarDeclList     :       VarDeclList VarDecl
-                        { $$ = (VarDef *) AppendStmt((ParseCommon *) $1,
-                                                     (ParseCommon *) $2); }
+                        { $$.head = $1.head; $$.last->common.next = &$2->common; $$.last = $2; }
                 |       VarDecl
-                        { $$ = $1; }
+                        { $$.head = $$.last = $1; }
                 ;
 
 KeyTypeDecl     :       TYPE String OBRACE
                             VarDeclList
                         CBRACE SEMI
-                        { $$ = KeyTypeCreate($2, $4); }
+                        { $$ = KeyTypeCreate($2, $4.head); }
                 ;
 
 SymbolsDecl     :       KEY KEYNAME OBRACE
                             SymbolsBody
                         CBRACE SEMI
-                        { $$ = SymbolsCreate($2, $4); }
+                        { $$ = SymbolsCreate($2, $4.head); }
                 ;
 
 SymbolsBody     :       SymbolsBody COMMA SymbolsVarDecl
-                        { $$ = (VarDef *) AppendStmt((ParseCommon *) $1,
-                                                     (ParseCommon *) $3); }
+                        { $$.head = $1.head; $$.last->common.next = &$3->common; $$.last = $3; }
                 |       SymbolsVarDecl
-                        { $$ = $1; }
-                |       { $$ = NULL; }
+                        { $$.head = $$.last = $1; }
+                |       { $$.head = $$.last = NULL; }
                 ;
 
 SymbolsVarDecl  :       Lhs EQUALS Expr         { $$ = VarCreate($1, $3); }
@@ -450,7 +478,7 @@ SymbolsVarDecl  :       Lhs EQUALS Expr         { $$ = VarCreate($1, $3); }
 ArrayInit       :       OBRACKET OptKeySymList CBRACKET
                         { $$ = $2; }
                 |       OBRACKET ActionList CBRACKET
-                        { $$ = ExprCreateActionList($2); }
+                        { $$ = ExprCreateActionList($2.head); }
                 ;
 
 GroupCompatDecl :       GROUP Integer EQUALS Expr SEMI
@@ -458,11 +486,11 @@ GroupCompatDecl :       GROUP Integer EQUALS Expr SEMI
                 ;
 
 ModMapDecl      :       MODIFIER_MAP Ident OBRACE ExprList CBRACE SEMI
-                        { $$ = ModMapCreate($2, $4); }
+                        { $$ = ModMapCreate($2, $4.head); }
                 ;
 
 LedMapDecl:             INDICATOR String OBRACE VarDeclList CBRACE SEMI
-                        { $$ = LedMapCreate($2, $4); }
+                        { $$ = LedMapCreate($2, $4.head); }
                 ;
 
 LedNameDecl:            INDICATOR Integer EQUALS Expr SEMI
@@ -513,7 +541,7 @@ Keys            :       Keys COMMA Key          { $$ = NULL; }
 Key             :       KEYNAME
                         { $$ = NULL; }
                 |       OBRACE ExprList CBRACE
-                        { FreeStmt((ParseCommon *) $2); $$ = NULL; }
+                        { FreeStmt((ParseCommon *) $2.head); $$ = NULL; }
                 ;
 
 OverlayDecl     :       OVERLAY String OBRACE OverlayKeyList CBRACE SEMI
@@ -552,7 +580,7 @@ Coord           :       OBRACKET SignedNumber COMMA SignedNumber CBRACKET
                 ;
 
 DoodadDecl      :       DoodadType String OBRACE VarDeclList CBRACE SEMI
-                        { FreeStmt((ParseCommon *) $4); $$ = NULL; }
+                        { FreeStmt((ParseCommon *) $4.head); $$ = NULL; }
                 ;
 
 DoodadType      :       TEXT    { $$ = 0; }
@@ -608,14 +636,13 @@ MergeMode       :       INCLUDE         { $$ = MERGE_DEFAULT; }
                 ;
 
 OptExprList     :       ExprList        { $$ = $1; }
-                |                       { $$ = NULL; }
+                |                       { $$.head = $$.last = NULL; }
                 ;
 
 ExprList        :       ExprList COMMA Expr
-                        { $$ = (ExprDef *) AppendStmt((ParseCommon *) $1,
-                                                      (ParseCommon *) $3); }
+                        { $$.head = $1.head; $$.last->common.next = &$3->common; $$.last = $3; }
                 |       Expr
-                        { $$ = $1; }
+                        { $$.head = $$.last = $1; }
                 ;
 
 Expr            :       Expr DIVIDE Expr
@@ -643,7 +670,7 @@ Term            :       MINUS Term
                 |       Lhs
                         { $$ = $1;  }
                 |       FieldSpec OPAREN OptExprList CPAREN %prec OPAREN
-                        { $$ = ExprCreateAction($1, $3); }
+                        { $$ = ExprCreateAction($1, $3.head); }
                 |       Terminal
                         { $$ = $1;  }
                 |       OPAREN Expr CPAREN
@@ -651,14 +678,13 @@ Term            :       MINUS Term
                 ;
 
 ActionList      :       ActionList COMMA Action
-                        { $$ = (ExprDef *) AppendStmt((ParseCommon *) $1,
-                                                      (ParseCommon *) $3); }
+                        { $$.head = $1.head; $$.last->common.next = &$3->common; $$.last = $3; }
                 |       Action
-                        { $$ = $1; }
+                        { $$.head = $$.last = $1; }
                 ;
 
 Action          :       FieldSpec OPAREN OptExprList CPAREN
-                        { $$ = ExprCreateAction($1, $3); }
+                        { $$ = ExprCreateAction($1, $3.head); }
                 ;
 
 Lhs             :       FieldSpec