Mike Gerwitz

Activist for User Freedom

diff options
authorMike Gerwitz <mike.gerwitz@rtspecialty.com>2019-02-07 11:12:27 -0500
committerMike Gerwitz <mike.gerwitz@rtspecialty.com>2019-02-07 11:39:50 -0500
commitb6cfdb422165d6b2725a5c720f7e488b81237c01 (patch)
treee9207fe4e8fdac2dbf89e8e8e0031a7834e3e03c /HACKING
parent8e7a9461279fd90f901480bbff33eb1c1ac0be4a (diff)
depgen: Quadratic=>linear-time algorithm
This is a significant performance improvement for dependency generation (which is responsible for building the dependency graph for a package). The previous algorithm ran in O(n²) time: it would iterate over the given symbol table, and for _each_ symbol, do a linear scan of the entire document to search for the corresponding source block. This resulted in explosive depgen time for larger packages. This makes the algorithm run in O(n) by: - Using an XSLT 3 map for the symbol table for O(1) lookups; and - Iterating over the _document_ a single time rather than the symbol table, referencing the symbol table as needed (in O(1) time). There are other parts of the system that can benefit from these same improvements. This is important, since we need to be able to handle many thousands of symbols efficiently. * src/current/compiler/linker.xsl (l:depgen-sym): Recognize smybol `no-deps' property, permitting missing dependencies. This allows us to avoid creating nonsense nodes just to satisfy the linker, while still allowing the linker to perform essential checks to defend against compiler bugs. * src/current/compiler/map.xsl (lvmc:stub-symtable): Set @no-deps on `___head' and `___tail' symbols. (lvmc:mapsym): Set `no-deps' as appropriate on map symbols. (preproc:depgen)[lvm:map[@from]]: Generate `preproc:sym-dep' node, which is now expected by the depgen process. (preproc:depgen)[lvm:map[*]]: Likewise. (preproc:depgen)[*[@lvmc:type='retmap']//lvmm:map[@from]]: Remove unnecessary template. (preproc:symtable)[lvm:map[@value]]: Pass `no-deps' to `lvmc:mapsym'. * src/current/include/depgen.xsl (preproc:depgen)[preproc:symtable]: Create and use XSLT 3 map in place of `preproc:symtable' tree. This allows for constant-time lookups. Provide to templates via tunnelling. Use it in place of exiting tree references. Process source tree rather than iterating over symbol table. (preproc:depgen)[lv:rate, c:sum[@generates], c:product[@generates], lv:classify, lv:function/lv:param, lv:function, lv:typedef]: Produce `preproc:sym-dep' nodes (which was previously done while iterating over the symbol table). (preproc:depgen)[preproc:sym]: Remove all such processing, since we no longer iterate over the symbol table. (preproc:depgen)[c:value-of]: Use symtable map. (preproc:depgen-match): Likewise. (preproc:depgen)[lv:union]: Modify to handle changes to lv:typedef template. (preproc:depgen)[text()]: Remove and replace with `node()'. * src/current/include/preproc/package.xsl (preproc:resolv-syms): Remove logging of symbol resolution. This has a slight performace impact since there is a lot of output. * src/current/include/preproc/symtable.xsl (lv:function/lv:param, c:let/c:Values/c:value): Set `no-deps'. * src/symtable/symbols.xsl: Add documentation of `no-deps'. (preproc:symtable)[lv:meta]: Set `no-deps'.
Diffstat (limited to 'HACKING')
0 files changed, 0 insertions, 0 deletions