[Rd] Package compiler - efficiency problem

[Tomas Kalibera]

Dear Karol,

I don't understand the models behind these function, but I can tell that 
the code generated is very inefficient. The AST interpreter will be very 
inefficient performing each scalar computation with all boxing, 
allocations, function calls. The byte-code compiler removes some of the 
boxing and allocation. While it could certainly compile faster, it will 
always be taking long compiling such functions with so many commands: so 
many expressions to track, so many source references to map, for so 
little computation. The same code could be much more efficient if it 
used vectorized operations and loops. The compiler cannot infer the 
loops and vector operations from the code - it is not that smart and I 
doubt it could easily be for R, but such optimizations could certainly 
be done easily at a higher level, when optimizing computation within the 
model, not within R with all its complicated semantics. I think you 
could hope for ~100x speedups compared to current generated code running 
with R AST interpreter.

So I think it might be worth thinking about writing an interpreter for 
the model (the generator would compute function values on the fly, 
without actually generating code). If that was too slow, it might pay 
off to generate some intermediate representation for the model that 
would be faster to interpret. If that was too hard, then perhaps 
generating the code from the model in a smarter way (use vector 
operations, loops). It is ok to do that opportunistically - only when 
possible. With compilers, this is normal, optimizations often take 
advantage of certain patterns in the code if they are present. If you 
had more specific questions how to optimize the code feel free to ask 
(also offline).

Certainly I don't want the existence of the byte-code compiler to 
require you to switch from R to C/C++, that would be exactly the 
opposite of what the compiler is aiming for. If it turns out you really 
need a way to disable compilation of these generated functions (so they 
run much slower, but you don't have to wait for them to compile), we 
will provide it and using a hack/workaround it is already possible in 
existing versions of R, with all the drawbacks I mentioned previously.

Best
Tomas


On 08/17/2018 12:43 AM, Karol Podemski wrote:
> Dear Thomas,
>
> thank you for prompt response and taking interest in this issue. I 
> really appreciate your compiler project and efficiency gains in usual 
> case. I am aware of limitations of interpreted languages too and 
> because of that even when writing my first mail I had a hunch that it 
> is not that easy to address this problem.  As you mentioned 
> optimisation of compiler for handling non-standard code may be tricky 
> and harmful for usual code. The question is if gEcon is the only 
> package that may face the same issue because of compilation.
>
> The functions generated by gEcon are systems of non-linear equations 
> defining the equilibrium of an economy (see 
> http://gecon.r-forge.r-project.org/files/gEcon-users-guide.pdf if you 
> want to learn a bit how we obtain it). The rows, you suggested to 
> vectorise, are indeed vectorisable because they define equilibrium for 
> similiar markets (e.g. production and sale of beverages and food) but 
> do not have to be vectorisable in general case. So that not to delve 
> into too much details I will stop here in description of how the 
> equations originate. However, I would like to point that similiar 
> large systems of linear equations may arise in other fields ( 
> https://en.wikipedia.org/wiki/Steady_state ) and there may be other 
> packages that generate similar large systems (e.g. network problems 
> like hydraulic networks). In that case, reports such as mine may help 
> you to assess the scale of the problems.
>
> Thank you for suggestions for improvement in our approach, i am going 
> to discuss them with other package developers.
>
> Regards,
> Karol Podemski
>
> pon., 13 sie 2018 o 18:02 Tomas Kalibera <tomas.kalibera using gmail.com 
> <mailto:tomas.kalibera using gmail.com>> napisał(a):
>
>     Dear Karol,
>
>     thank you for the report. I can reproduce that the function from
>     you example takes very long to compile and I can see where most
>     time is spent. The compiler is itself written in R and requires a
>     lot of resources for large functions (foo() has over 16,000 lines
>     of code, nearly 1 million of instructions/operands, 45,000
>     constants). In particular a lot of time is spent in garbage
>     collection and in finding a unique set of constants. Some
>     optimizations of the compiler may be possible, but it is unlikely
>     that functions this large will compile fast any soon. For
>     non-generated code, we now have the byte-compilation on
>     installation by default which at least removes the compile
>     overhead from runtime. Even though the compiler is slow, it is
>     important to keep in mind that in principle, with any compiler
>     there will be functions where compilation would not be improve
>     performance (when the compile time is included or not).
>
>     I think it is not a good idea to generate code for functions like
>     foo() in R (or any interpreted language). You say that R's
>     byte-code compiler produces code that runs 5-10x faster than when
>     the function is interpreted by the AST interpreter (uncompiled),
>     which sounds like a good result, but I believe that avoiding code
>     generation would be much faster than that, apart from drastically
>     reducing code size and therefore compile time. The generator of
>     these functions has much more information than the compiler - it
>     could be turned into an interpreter of these functions and compute
>     their values on the fly.
>
>     A significant source of inefficiency of the generated code are
>     element-wise operations, such as
>
>     r[12] <- -vv[88] + vv[16] * (1 + ppff[1307])
>     ...
>
>     r[139] <- -vv[215] + vv[47] * (1 + ppff[1434])
>
>     (these could be vectorized, which would reduce code size and
>     improve interpretation speed; and make it somewhat readable). Most
>     of the code lines in the generated functions seem to be easily
>     vectorizable.
>
>     Compilers and interpreters necessarily use some heuristics or
>     optimize at some code patterns. Optimizing for generated code may
>     be tricky as it could even harm performance of usual code. And, I
>     would much rather optimize the compiler for the usual code.
>
>     Indeed, a pragmatic solution requiring the least amount of work
>     would be to disable compilation of these generated functions.
>     There is not a documented way to do that and maybe we could add it
>     (and technically it is trivial), but I have been reluctant so far
>     - in some cases, compilation even of these functions may be
>     beneficial - if the speedup is 5-10x and we run very many times.
>     But once the generated code included some pragma preventing
>     compilation, it won't be ever compiled. Also, the trade-offs may
>     change as the compiler evolves, perhaps not in this case, but in
>     other where such pragma may be used.
>
>     Well so the short answer would be that these functions should not
>     be generated in the first place. If it were too much work
>     rewriting, perhaps the generator could just be improved to produce
>     vectorized operations.
>
>     Best
>     Tomas
>
>     On 12.8.2018 21:31, Karol Podemski wrote:
>>       Dear R team,
>>
>>     I am a co-author and maintainer of one of R packages distributed by R-forge
>>     (gEcon). One of gEcon package users found a strange behaviour of package (R
>>     froze for couple of minutes) and reported it to me. I traced the strange
>>     behaviour to compiler package. I attach short demonstration of the problem
>>     to this mail (demonstration makes use of compiler and tictoc packages only).
>>
>>     In short, the compiler package has problems in compiling large functions -
>>     their compilation and execution may take much longer than direct execution
>>     of an uncompiled function. Such functions are generated by gEcon package as
>>     they describe steady state for economy.
>>
>>     I am curious if you are aware of such problems and plan to handle the
>>     efficiency issues. On one of the boards I saw that there were efficiency
>>     issues in rpart package but they have been resolved. Or would you advise to
>>     turn off JIT on package load (package heavily uses such long functions
>>     generated whenever a new model is created)?
>>
>>     Best regards,
>>     Karol Podemski
>>
>>
>>     ______________________________________________
>>     R-devel using r-project.org <mailto:R-devel using r-project.org>  mailing list
>>     https://stat.ethz.ch/mailman/listinfo/r-devel
>


	[[alternative HTML version deleted]]