For my science fair project, I implemented an optimization to Python's sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and character-width checks, outside of the sort loop and just get them all done in one pass. An optimized comparison function is then selected from a portfolio based on the results of the checks. So, for example, if the checks determine that all the objects are of the same type, the selected comparison function can skip the usually-required "are the object types compatible" check. Etc.
I have to write this up as a paper, and am currently working on a literature review. Are there any papers describing similar techniques in other dynamic languages/generally?
Asked By : René G
Answered By : Derek Elkins
I'm not aware of anything exactly like this, but there are some things that are arguably related.
For specifically sorting this is related to the Schwartzian transform, though with a very different goal. In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the output. This is in contrast to performing that expensive function on each operation. In your case, your "expensive function" would be the type checks and the dynamic dispatches. A bit differently you would be checking a property for the whole list as well and then choosing which comparison operation to use based on that.
In a totally different vein, there's a general technique called polymorphic inline caching (pioneered by the Self team and covered, among many other things, in Craig Chamber's thesis) and more generally adaptive optimization that is used in some virtual machines. Polymorphic inline caching solves the problem that if we do a dynamic dispatch, then we are jumping to some completely unknown code, and thus we can't inline it and optimize it and the current function. The solution is simple: just do an if to test if we are in some specific case, and if so, we can inline that code, else we do the dynamic dispatch. The problem is there is an unbounded, unknown number of possible cases. This isn't a problem, though, for a Just-In-Time (JIT) compiler which can just do this for the cases actually seen at runtime.
This doesn't solve your problem since dynamic dispatch is based on the runtime class of an object, not on some arbitrary predicate like "all the elements of this array have the same type". This is where adaptive optimization comes in and things like tracing JIT compilers. It's quite conceivable that unrolling a loop a few times or inlining a couple levels of recursion can lead to many type checks being eliminated with simple constant propagation style optimizations, and possibly entirely eliminated by more sophisticated optimizations in some cases. Nevertheless, it will often not do the same thing as you are suggesting and would need to see a trace first for each use of the sort function. On the other hand, if it knows all the elements are numbers, say, from earlier code, it can eliminate checking entirely.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/66020
0 comments:
Post a Comment
Let us know your responses and feedback