6 ms·

This is neat. What worries me about this and similar efforts (like https://github.com/takeoutweight/clojure-scheme https://github.com/takeoutweight/clojure-sch

by mullr 13y ago

This is neat. What worries me about this and similar efforts (like https://github.com/takeoutweight/clojure-scheme https://github.com/takeoutweight/clojure-scheme) is that clojure's standard library design assumes that the underlying runtime will be do some kind of polymorphic method inlining. For example: the sequence library is all defined in terms of ISeq, which basically requires a "first" and "rest" to be defined for the data structure in question. These are polymorphic: there are different implementations of these for different data structures (list, vector, map, etc). So a dispatch step is required to choose the right one. In clojure-jvm, this is implemented using a java interface; this means the jvm will inline calls to said methods when they're being used in a tight loop. And if you use the standard library, calls to 'first' and 'rest' are going to be inside nearly all of your inner loops. Compare this to a normal lisp or scheme: 'first' and 'rest' (or 'car' and 'cdr', whatever) are monomorphic. They only work on the linked-list data structure. So compiling these directly down to C functions makes perfect sense and incurs no performance penalty. So in summary: clojure assumes theres a really smart JIT which is helping things along. This means it's not as suitable for alternate compilation targets as you might want it to be. I wonder if there's something clever you could do here. Vtables could be reordered based on expected usage, certainly. Clojure can already do some measure of type inference, so this could be used for AOT inlining when it's available. Even if it's not, perhaps several versions of a call could be speculatively generated based on what the compiler does know already. The normal polymorphic inline caching technique could perhaps be abused to apply here. But it's hard to see how any of this can work in absence of a profile or heavy hinting. (not a compiler writer, just interested in the problem)

pjmlp 13y ago
You can workaround it by making use of PGO (Profile Guided Optimization). This requires you to execute the application with profiling turned on. Then you compile the application a second time with the additional input of the profile results, this way the optimizer gets additional information that helps it to do decisions similar to a JIT. It is all a matter of adding support for this.
nimrody 13y ago
Perhaps you could overcome some of these programs with whole-program-optimization. E.g., the "Stalin" Scheme compiler. It might be interesting to translate Clojure into a subset of Scheme that is widely supported -- and use one of the mature Scheme -> C compilers (Gambit, Chicken, Bigloo) to generate the target executable.
- terhechte 13y ago
  https://github.com/takeoutweight/clojure-scheme https://github.com/takeoutweight/clojure-scheme
vidarh 13y ago
You can do polymorphic method caching/inlining with a hybrid ahead of time / JIT compiler targeting C reasonably easily. The code fragments required for caching at least will be small, and code to generate them at runtime is not a big deal. I'm playing with a Ruby compiler, and Ruby badly needs these type of optimizations to get fast, so I've spent a fair amount of time looking at it. For a fair amount of cases you can do static analysis to get good guesses at likely types, even for cases where you can't be sure. E.g. speculatively even looking near call sites by method name to see if you can guess the type of objects that will get passed in looks to get you a reasonable chance at guessing at the top contenders to let you speculatively generate inlined versions without creating too much junk. But to get the most performance out of this you're likely to need to be prepared to do some very basic JIT.
- mullr 13y ago
  >E.g. speculatively even looking near call sites by method name That is devious and fantastic. > But to get the most performance out of this you're likely to need to be prepared to do some very basic JIT. Yeah. But the attractive targets here are places where you can't have a JIT: embedded systems and iOS.
  - swannodette 13y ago
    re: JIT on iOS I've heard of people compiling their own JavaScriptCore (to use Ejecta), is this still an issue? Embedded systems is another story, I'd be far more concerned about Clojure's assumptions about GC.
    - AntiRush 13y ago
      The JavaScriptCore they are compiling is without the JIT. You still can't have memory pages marked write+execute, which is what you need for a JIT.
  - vidarh 13y ago
    When you spend a few years speculating about what it would take to efficiently compile Ruby as statically as possible (I love Ruby, but I hate moving parts), devious becomes second nature... The idea of speculatively looking at method names comes from testing that to create vtables ahead of time for Ruby classes, to avoid hash tables in the common-case. As it turns out, most method on most Ruby classes are the ones inherited from Object or other standard classes, and the number of classes is usually fairly constrained, so again speculatively looking at method names in the compile-time available source and allocating sparse vtables for the most common names results in relatively little waste. And it reduces typical method lookup to a vtable lookup for common methods, with expensive method dispatch becoming much more rare. There's the tradeoff between theoretical horrible blowup in vtable waste from apps dynamically adding tons of methods and tons of classes, with a unique vtable slot required for each method name across all classes, vs. falling back to doing hash-table lookups all the way up the inheritance chain for "unusual" method names ones you reach certain thresholds for waste. You do incur the cost of propagating vtable changes down the inheritance tree when methods are dynamically redefined in other places than leaves, but it is fairly rare to see apps where this happens at a very high rate, and the number of subclasses usually fairly small, so it is likely to be quite cheap. Doing it that way is something I first saw in a technical report by (now) prof. Michael Franz from '93 or '94 on "Protocol Extension" for Oberon. You can probably also get some decent gains by adding heuristics to give preference to names that appears to be used in loops when picking names for the vtables to reduce the need of any JIT'ing.
saosebastiao 13y ago
Yeah, I wish we could somehow persuade Mike Pall to work some magic here. LuaJIT's general design sounds like the perfect fit for something like this.
lmkg 13y ago
Could the use of Reducers help alleviate this problem? I'm not completely familiar with the internals, but my naive understanding of how they work is that the reducer function would dispatch once on the sequence type, and then iteration stays entirely within that sequence's reducer method.

by mullr 13y ago

pjmlp 13y ago

You can workaround it by making use of PGO (Profile Guided Optimization). This requires you to execute the application with profiling turned on. Then you compile the application a second time with the additional input of the profile results, this way the optimizer gets additional information that helps it to do decisions similar to a JIT. It is all a matter of adding support for this.

nimrody 13y ago

Perhaps you could overcome some of these programs with whole-program-optimization. E.g., the "Stalin" Scheme compiler. It might be interesting to translate Clojure into a subset of Scheme that is widely supported -- and use one of the mature Scheme -> C compilers (Gambit, Chicken, Bigloo) to generate the target executable.

terhechte 13y ago
https://github.com/takeoutweight/clojure-scheme https://github.com/takeoutweight/clojure-scheme

vidarh 13y ago

You can do polymorphic method caching/inlining with a hybrid ahead of time / JIT compiler targeting C reasonably easily. The code fragments required for caching at least will be small, and code to generate them at runtime is not a big deal. I'm playing with a Ruby compiler, and Ruby badly needs these type of optimizations to get fast, so I've spent a fair amount of time looking at it. For a fair amount of cases you can do static analysis to get good guesses at likely types, even for cases where you can't be sure. E.g. speculatively even looking near call sites by method name to see if you can guess the type of objects that will get passed in looks to get you a reasonable chance at guessing at the top contenders to let you speculatively generate inlined versions without creating too much junk. But to get the most performance out of this you're likely to need to be prepared to do some very basic JIT.

mullr 13y ago
>E.g. speculatively even looking near call sites by method name That is devious and fantastic. > But to get the most performance out of this you're likely to need to be prepared to do some very basic JIT. Yeah. But the attractive targets here are places where you can't have a JIT: embedded systems and iOS.
- swannodette 13y ago
  re: JIT on iOS I've heard of people compiling their own JavaScriptCore (to use Ejecta), is this still an issue? Embedded systems is another story, I'd be far more concerned about Clojure's assumptions about GC.
  - AntiRush 13y ago
    The JavaScriptCore they are compiling is without the JIT. You still can't have memory pages marked write+execute, which is what you need for a JIT.
- vidarh 13y ago
  When you spend a few years speculating about what it would take to efficiently compile Ruby as statically as possible (I love Ruby, but I hate moving parts), devious becomes second nature... The idea of speculatively looking at method names comes from testing that to create vtables ahead of time for Ruby classes, to avoid hash tables in the common-case. As it turns out, most method on most Ruby classes are the ones inherited from Object or other standard classes, and the number of classes is usually fairly constrained, so again speculatively looking at method names in the compile-time available source and allocating sparse vtables for the most common names results in relatively little waste. And it reduces typical method lookup to a vtable lookup for common methods, with expensive method dispatch becoming much more rare. There's the tradeoff between theoretical horrible blowup in vtable waste from apps dynamically adding tons of methods and tons of classes, with a unique vtable slot required for each method name across all classes, vs. falling back to doing hash-table lookups all the way up the inheritance chain for "unusual" method names ones you reach certain thresholds for waste. You do incur the cost of propagating vtable changes down the inheritance tree when methods are dynamically redefined in other places than leaves, but it is fairly rare to see apps where this happens at a very high rate, and the number of subclasses usually fairly small, so it is likely to be quite cheap. Doing it that way is something I first saw in a technical report by (now) prof. Michael Franz from '93 or '94 on "Protocol Extension" for Oberon. You can probably also get some decent gains by adding heuristics to give preference to names that appears to be used in loops when picking names for the vtables to reduce the need of any JIT'ing.

saosebastiao 13y ago

Yeah, I wish we could somehow persuade Mike Pall to work some magic here. LuaJIT's general design sounds like the perfect fit for something like this.

lmkg 13y ago

Could the use of Reducers help alleviate this problem? I'm not completely familiar with the internals, but my naive understanding of how they work is that the reducer function would dispatch once on the sequence type, and then iteration stays entirely within that sequence's reducer method.