7
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ While this isn't directly related, hopefully it can help point you in potentially useful directions. This is somewhat reminiscent of inline-caching for many JIT/dynamic compilers. The idea is to profile traces that are potentially "hot" into buckets indexed by their properties (e.g. list of ints, list of strings, mixed list, etc). Given these buckets, we then dynamically generate code that are optimized for each property set and cache them accordingly. As a result, the Just-In-Time literature contains quite a few optimizations that more or less fits into your mold. Happy reference-hunting! $\endgroup$ – Lee Nov 14 '16 at 4:31
  • 1
    $\begingroup$ @LeeGao That sounds exactly like what I'm doing, except the "hot" traces are hard-coded, and we don't dynamically generate anything but rather hard-code the optimized traces as well; what's a good survey paper/landmark paper for this technique? I tried googling "JIT buckets" but couldn't find anything :) $\endgroup$ – Elliot Gorokhovsky Nov 14 '16 at 4:44
  • 1
    $\begingroup$ "Inline caching" should give you a few good results. "Bucket" is just a word I use whenever I try to explain it to friends and coworkers. :P $\endgroup$ – Lee Nov 14 '16 at 5:56
  • $\begingroup$ @LeeGao :) Ya, thanks. I now see that what I'm doing is literally exactly what inline caching is. Good to know! $\endgroup$ – Elliot Gorokhovsky Nov 14 '16 at 6:08
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, the polymorphic inline caching is very relevant, because I do have lots of special case compare functions (like for strings, ints, and floats) that are inlined. My code goes through and checks for those special cases, and if it finds one, it replaces the compare function with a special-case one. $\endgroup$ – Elliot Gorokhovsky Nov 14 '16 at 5:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.