Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

Exponentially large maps #5

Closed
jonase opened this Issue Jan 9, 2012 · 6 comments

Comments

Projects
None yet
2 participants
Contributor

jonase commented Jan 9, 2012

Having a :children key yields exponentially large maps. They are not strictly necessary since all they essentially do is duplicate information already available in the map. They are, however, very useful for code walking tasks.

One possible solution is to make a children multimethod (dispatching on :op) which would return the same expressions as :children does now.

I have created a branch which implements the above idea, and it seems to work great so far. Would you consider accepting a pull request when I'm confident that it works and when I have converted the examples to use the children function instead of :children?

Currently, the expression,

(binding [*out* (writer "master.out")] 
  (println (analyze-one {:ns {:name 'user} :context :eval} 
           '(let [d (fn [x] (* x x))] 
              (println "2*3 =" (d 3))))))

creates a 27M file. With my (still experimental branch) it's "only" 8K (a ~3500x reduction in size)

Owner

frenchy64 commented Jan 10, 2012

I'd like to know which Expr forms have these large children. Perhaps there's some sort of recursive child.

Contributor

jonase commented Jan 10, 2012

I think it's every Expr that has a :children key. For example

(defmethod Expr->map Compiler$DefExpr
  (let [...
        init (Expr->map (field 'init expr) env)
        meta (when-let [meta (field 'meta expr)]
                   (Expr->map meta env))]
     ...
     :meta meta
     :init init
     :children [meta init]
     ...)

Here, init and meta are duplicated and due to the recursive nature of Expr->map an exponentially large tree is generated.

Another solution would be to define a dynamic var *expand-children* and rewrite the above as

...
:children (when *expand-children* [meta init])
...

So when I want to analyze some expression (and actually read the result) I could do

(binding [*expand-children* false]
  (analyze-one ...))
Owner

frenchy64 commented Jan 10, 2012

I like your children idea, I had a similar idea when writing the initial versions but never implemented it.

If you find any Expr forms in particular that yield massive children, I'd be interested to know. Also "all of them" is an acceptable answer ;)

I'd accept a patch.

Owner

frenchy64 commented Jan 10, 2012

Isn't this a presentation problem? With persistent data structures, we're not duplicating anything in memory.

Why not just dissoc the :children recursively when printing?

Contributor

jonase commented Jan 10, 2012

Yes, it is mainly a presentation problem. It would certainly be possible to create a print-expr function. Maybe that is a good first step.

Still, it feels kind of unnecessay to duplicate information in the expression maps. OTOH, it's also done in the clojurescript compiler so maybe there's some good reason for it that I don't (yet) realize.

Owner

frenchy64 commented Jan 29, 2013

Children nodes can now be toggled.

@frenchy64 frenchy64 closed this Jan 29, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment