<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;"><div id="yiv737508310">kreckel wrote:<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><div class="plainMail"><br>...and second, sharing is currently not pursued aggressively! Rather, it is exploited whenever it is trivial to do so. (The product rule of differentiation is an example where exactly the same terms pop up again and again so exploiting sharing comes at no cost.)<br><br></div></blockquote>I think the benefit would still be large, even if coverage isn't 100%. See below.<br><div class="plainMail"><br></div><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px;"><div class="plainMail"><br>Well, I think that if the size of generated code is so prohibitively large and compiler CSE doesn't help you may be better off writing your own algorithm collecting
similar
terms in an associative array. You could then artificially introduce temporaries, in order to help the compiler. This would boil down to a more aggressive variant of GiNaC's subexpression sharing. What do you think?<br><br></div></blockquote>This is exactly what I have done. As mentioned, I will post that solution here in the next few days. This works well, but is very slow, as it takes something that is sub-linear in the size of the expression tree and makes it O(n^2). <br><br>If GiNaC expression tree nodes had a unique identifier, this approach could achieve sub-linear performance. Specifically, it would be linear in the size of the unique subexpressions, not the size of the actual expression. (If you have a lot of sharing, your expression can be large, but the number of unique expressions can be small.)<br><br>Even if GiNaC doesn't identify every single instance of a shared sub-expression, the benefits could still be
large. In fact, I tried an experiment to test this. I treated ex::gethash() as a unique identifier, even though it isn't. The code I generated was wrong, of course, but it was very fast to generate it, and very fast to compile and execute. Thus, whatever number of unique expressions were not actually identified as such was small enough that this approach would still be quite useful.<br><br>Also, FYI, when using the hash value as a unique identifier, I only got a few collisions out of thousands of sub-expressions. That is, I only found a few expressions with the same hash even though they were different expressions. <br><div class="plainMail"><br>Thanks,<br>Doug<br><br></div></div></td></tr></table><br>