Mike Gerwitz

Activist for User Freedom

aboutsummaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
authorMike Gerwitz <mike.gerwitz@rtspecialty.com>2019-02-07 15:51:17 -0500
committerMike Gerwitz <mike.gerwitz@rtspecialty.com>2019-02-18 11:56:17 -0500
commitd2ab6e1149276efaff5f841fc4473e45dc0cfeb7 (patch)
tree55263ef7887f52d9e03ec31c4f5f325d5e71aa19 /src
parent09eb442c6387e0d61ede1ee98fbbd96eeedac5c1 (diff)
downloadtame-d2ab6e1149276efaff5f841fc4473e45dc0cfeb7.tar.gz
tame-d2ab6e1149276efaff5f841fc4473e45dc0cfeb7.tar.bz2
tame-d2ab6e1149276efaff5f841fc4473e45dc0cfeb7.zip
resolv-syms: Generate maps for symtable and dependency lists
This is a first step (low-hanging-fruit kinda thing) for improving the performance of symbol resolution, where the compiler has to figure out the dimensions of a symbol by first resolving its dependencies, recursively. This is approximately an O(n³) polynomial-time algorithm _per recursive step_. Yikes. This is traditionally where dynamic programming methods would be used, but that's considerably more difficult in a immutable languages like XSLT, so I'll do my best without. (Saxon does offer some support for mutability, but I'd prefer to avoid it if possible.) This first change improves performance 30--40%. For example, on two large packages we have, build times drop from 55s to 35s and from 1m42s to 1m13s respectively. Good start, but much more to be done! * src/current/include/preproc/package.xsl (preproc:resolv-syms)[lv:package]: Compute maps for preproc:symtable and preproc:sym-deps at each recursive step. Pass along via tunneling. (preproc:resolv-syms)[preproc:sym]: Use them. DEV-4354
Diffstat (limited to 'src')
-rw-r--r--src/current/include/preproc/package.xsl41
1 files changed, 27 insertions, 14 deletions
diff --git a/src/current/include/preproc/package.xsl b/src/current/include/preproc/package.xsl
index 38b0b3b..c36692e 100644
--- a/src/current/include/preproc/package.xsl
+++ b/src/current/include/preproc/package.xsl
@@ -25,6 +25,8 @@
-->
<stylesheet version="1.0"
xmlns="http://www.w3.org/1999/XSL/Transform"
+ xmlns:xs="http://www.w3.org/2001/XMLSchema"
+ xmlns:map="http://www.w3.org/2005/xpath-functions/map"
xmlns:preproc="http://www.lovullo.com/rater/preproc"
xmlns:lv="http://www.lovullo.com/rater"
xmlns:t="http://www.lovullo.com/rater/apply-template"
@@ -565,6 +567,16 @@
<param name="orig-root" as="element()" />
<param name="rpcount" select="0" />
+ <variable name="symtable-map" as="map( xs:string, element( preproc:sym ) )"
+ select="map:merge(
+ for $sym in preproc:symtable/preproc:sym
+ return map{ string( $sym/@name ) : $sym } )" />
+
+ <variable name="symdep-map" as="map( xs:string, element( preproc:sym-dep ) )"
+ select="map:merge(
+ for $sym-dep in preproc:sym-deps/preproc:sym-dep
+ return map{ string( $sym-dep/@name ) : $sym-dep } )" />
+
<!-- arbitrary; intended to prevent infinite recursion -->
<!-- TODO: same method as for templates; ensure changes, but do not create
arbitrary limit -->
@@ -588,6 +600,8 @@
<apply-templates mode="preproc:resolv-syms">
<with-param name="orig-root" select="$orig-root" />
+ <with-param name="symtable-map" select="$symtable-map" tunnel="yes" />
+ <with-param name="symdep-map" select="$symdep-map" tunnel="yes" />
</apply-templates>
</copy>
</variable>
@@ -639,20 +653,25 @@
<template match="preproc:sym[ not( @src ) and @dim='?' ]" mode="preproc:resolv-syms" priority="5">
<param name="orig-root" as="element()" />
+ <param name="symtable-map" as="map(*)" tunnel="yes" />
+ <param name="symdep-map" as="map(*)" tunnel="yes" />
<variable name="name" select="@name" />
<variable name="pkg" as="element( lv:package )"
select="root(.)" />
- <variable name="deps" as="element( preproc:sym-dep )*" select="
- $pkg/preproc:sym-deps/preproc:sym-dep[ @name=$name ]
- " />
+ <variable name="deps" as="element( preproc:sym-dep )?"
+ select="$symdep-map( $name )" />
- <variable name="depsyms-unresolv" as="element( preproc:sym )*" select="
- $pkg/preproc:symtable/preproc:sym[
- @name=$deps/preproc:sym-ref/@name
- ]
- " />
+ <!-- TODO: make this fatal -->
+ <if test="empty( $deps ) and not( @no-deps = 'true' )">
+ <message select="concat( 'internal: failed to located dependencies for `',
+ $name, '''' )" />
+ </if>
+
+ <variable name="depsyms-unresolv" as="element( preproc:sym )*"
+ select="for $ref in $deps/preproc:sym-ref
+ return $symtable-map( $ref/@name )" />
<variable name="depsyms-resolv">
<for-each select="$depsyms-unresolv">
@@ -692,12 +711,6 @@
<when test="
$depsyms/@dim = '?'
">
- <message>
- <text>[preproc] deferring `</text>
- <value-of select="$name" />
- <text>' dimensions with unresolved dependencies</text>
- </message>
-
<!-- schedule repass :x -->
<sequence select="." />
<preproc:repass src="preproc:sym resolv-syms"