<div class="gmail_quote">On Mon, May 24, 2010 at 8:25 PM, Gabriel Dos Reis <span dir="ltr"><<a href="mailto:gdr@integrable-solutions.net">gdr@integrable-solutions.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
I'm ignorant of what ECL's collector works. I have so far assumed that<br>
it just reuses the defaul H-W collector; but apparently, that is not the case?</blockquote><div><br></div><div>Well, the Boehm-Weiser garbage collector is a pretty flexible library. It includes a lot of features:</div><div>
* Precise collection</div><div>* Generational garbage collection with write barriers</div><div>* Parallel garbage collection shared among threads</div><div>* Macros for thread-local allocation</div><div>* Macros for inlining allocation without locks</div>
<div>* Facilities to extend the mark phase</div><div>* Finalization</div><div>...</div><div>the list is huge and most of it is not well documented. Making an optimal use requires a man-month of continuous investigation -- but only _after_ all other performance sinks have been eliminated, for we may run the risk of premature optimization choosing the wrong strategy.</div>
<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div class="im">I understand that second point. Even if the client's algorithms are</div>
suboptimal (in terms of theoretical complexity), should we still expect<br>
order of magnitude between runs with ECL and other Lisps on the same<br>
algorithm implementation?</blockquote></div><div><br></div>I am not sure I expressed myself properly. What I meant is that the user code may be making assumptions about the implementation and it strengths leading indeed to significant performance differences.<div>
<br></div><div>The first reason is that you might be exercising functions that are / were also suboptimal in ECL itself. For instance using too much DELETE vs. other loops, or using DELETE-DUPLICATES. In particular those functions were operating on sequences using ELT. That means DELETE and friends could move from O(n) to O(n^2) which for a list with 10 elements is a 10x in time. Indeed the times for runnings the ANSI tests with sequences went from 1 second per file to about 0.09 seconds. Not that it matters much because the whole test suite is dominated by other things, such as the compiler tests, but it gives you an idea of the impact of simple things on the overall performance.</div>
<div><div><br></div><div>Sometimes it is just a simpler things --gentemp I recall, was a huge bottleneck because of using FORMAT-- that make destroy the user's experience and cause the impression that the whole implementation is a disaster. Here I am probably to be blamed because I do not have the time or resources to profile all those bottlenecks, but they are easy to find with time and patience.</div>
<div><br></div><div>The second reason why things can get pretty bad performancewise you have already experienced: the compiler. Here again stupid design choices, such as the algorithms that decide when to unbox or not, or the expectation from user code that type inference is there and works, thus removing all explicit type declarations, or even an improper use of declarations (we had this problem in pprint.lsp, where automatic type checking of arguments was stupidly activated on all functions), may decrease performance by a factor 10 or more just because of introducing boxed values, additional function calls, excesive branching, ...</div>
<div><br></div><div>But again there is no fundamental limitation. The proof is that the sequence functions that I implemented run *faster* in ECL with appropriate type declarations than in other implementations. Have a look at them: *now* they are not fundamentally different from the algorithms that SBCL uses, same asymptotic complexity and all that.</div>
<div><br></div><div>But if you want a short answer to your question</div><div><br></div><blockquote class="gmail_quote" style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex; ">
"should we still expect order of magnitude between runs with ECL and other Lisps on the same algorithm implementation?"</blockquote><div><br></div><div>this is not solved in one day :-)</div><div><div><br></div>
<div>Juanjo </div><div><br>-- <br>Instituto de Física Fundamental, CSIC<br>c/ Serrano, 113b, Madrid 28006 (Spain) <br><a href="http://tream.dreamhosters.com">http://tream.dreamhosters.com</a><br>
</div></div></div>