# Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance

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?

• 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! – Lee Nov 14 '16 at 4:31
• @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 :) – Elliot Gorokhovsky Nov 14 '16 at 4:44
• "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 – Lee Nov 14 '16 at 5:56
• @LeeGao :) Ya, thanks. I now see that what I'm doing is literally exactly what inline caching is. Good to know! – Elliot Gorokhovsky Nov 14 '16 at 6:08

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.