Compilation time go up significantly when nesting multimethods

Description

Code like this takes 140 seconds to compile on my machine. Regular functions don't seem to trigger this behaviour.

Whole project is here https://github.com/maio/slow-cljs-build

Environment

None

Activity

Show:
Mike Fikes
March 4, 2016, 10:32 PM

Hrm. This fix is evidently in the Closure compiler used by 1.7.228: https://github.com/google/closure-compiler/issues/1049

Thomas Heller
March 6, 2016, 12:25 PM

@mfikes the slowdown is not related to the Closure Compiler since it happens when compiling cljs->js not when optimizing.

The reason for the slowdown is due to the arguments of a multimethod call being analyzed twice (or more in case of deep nesting).

See [1] for the problematic code.

multimethods are not fn-var? so the or does not short circuit and (all-values? argexprs) is reached. This forces the argexprs lazy-seq (thereby analyzing the args). Since the args are not all-values? the else-branch of the if is taken, which then later causes the args to be analyzed again. My math is weak but I'm not mistaken this is O(n!), explaining the dramatic slowdown.

Every var that is not fn-var? is affected by this:

One solution would be to fix all-values? that instead of running through analyze it could just check whether all args are fixed literals (ie. not list? but all of number? string? symbol? keyword? etc.).

I'm not really sure why the else-branch in [1] exists at all but I assume it is to work around some JS quirks. I will hold off on writing a patch until I figure out why the extra let introduced in the else-branch is needed.

[1] https://github.com/clojure/clojurescript/blob/f58dcdf4dc37ef52d4eb1e2b7c994282bf6351f5/src/main/clojure/cljs/analyzer.cljc#L2257-L2263

PS: forgot to add that this does not happen with :static-fns false since it also prevents the else from being reached.

Thomas Heller
March 6, 2016, 12:55 PM

The else was introduced in CLJS-855 and is sort of required for invokes without arity information and :static-fns true.

Changing all-values? to just check literals instead of analyzing should be a valid solution.

Thomas Heller
March 14, 2016, 2:31 PM

The patch removes the extra analyze and instead just checks the few cases that can actually be used without assignment first.

This removes the slowdown while keeping all the functionality.

David Nolen
August 10, 2016, 8:32 PM

Assignee

David Nolen

Reporter

import

Labels

Approval

None

Patch

None

Affects versions

Priority

Minor
Configure