Anything much faster than this needs vector operations in the interpreter so the “get to the OP function” overhead is once per time series rather than once per element in the series.
From: <golang-nuts@googlegroups.com> on behalf of Egon <egonel...@gmail.com> Date: Monday, July 18, 2016 at 1:32 AM To: golang-nuts <golang-nuts@googlegroups.com> Cc: <ondrej.ko...@gmail.com> Subject: [go-nuts] Re: An efficient runtime expression evaluation On Monday, 18 July 2016 11:13:08 UTC+3, Egon wrote: On Monday, 18 July 2016 10:30:14 UTC+3, Egon wrote: On Monday, 18 July 2016 03:11:29 UTC+3, ondrej...@gmail.com wrote: Cheers, I tried replicating my endeavours (https://play.golang.org/p/Qxoo2ASac6), sorry if it's still too verbose. It's essentially rewriting the inbuilt ast.Node into a simpler nested struct and then walking it. In testing the performance, I started adding algebraic expressions, which make my walking more expensive, but don't change the 'native' expression evaluation (I guess due to constant folding). As to your suggestion three - I do the variable lookup in the parsing stage, but I still need to retain the pointer, not the value itself, because I'm accessing an element of that given variable (time series), and this element (time period) changes at runtime. https://play.golang.org/p/dd4hTpMKrp Of course you can additionally add constant folding and similar... Additionally instead of working on a single float at a time, make each variable an array of 8 floats, that are computed in parallel. Just realized that it's trivial to write basic constant folding: https://play.golang.org/p/iqWX5_Mweb Although it probably will be easier to maintain and extend as a separate pass: https://play.golang.org/p/xcz5mXoaOG This brings the result to: interpreter: 17.001ms native: 7.0004ms Which is approximately the best I would expect from an interpreter without JIT (and not computing multiple time-points at a time). + Egon One performance gain I can think of is to implement some pruning through the abovementioned constant folding and other optimisations, but I'd rather leave that as the last resort. Another thing that comes to mind is that I could return nested closures in some way - meaning that '1+3*x' would be, in go-like pseudocode, add(func() { return one }, func mul(func() { return three}, func() {return model[x]} )), where the one/tree are values passed to the closure when parsing the equation; but that's just now off the top of my head. I attached a pprof result in the header. Thanks again. On Friday, 8 July 2016 15:46:32 UTC+1, Egon wrote: On Friday, 8 July 2016 16:25:40 UTC+3, Ondrej wrote: Hi all, I have a model with variables, let's call them a, b, c, ..., z. These are numerical values (time series loaded from a database) and I let the user specify their relationships in a JSON, say 'z = 12; x = a + 2/3 + 3*c; y = log(12*f) + exp(g)' etc. The syntax is trivial - it's basically just algebraic relationships + a few functions (log, log2, log10, exp, trigonometrics, ...; all 1:1 mappings to their math package equivalents). Tip: include a working piece of code that you want to make faster, it makes it easier for people to see the problems and common issues. Now, I get these relationships in a JSON and I parse them using go/parser. Then I walk the tree once and process it a bit - replacing keywords by pointers to my variable stores, replacing all the log/exp/sin with function pointers, leaving literals be literals etc. Each node is then a struct with a type and the actual contents (sadly a generic interface, because the value can be almost anything). The prep stage is now over. When actually running the model, I loop through years and within each year I solve each variable - I walk the tree and evaluate it where needed. The only non-trivial action is when I get to a model variable, I need to do a bit of lookup (it's a time series, so I need to look up the correct time period and other bits). Otherwise it's just literals, operators and function calls, all of which is fairly straightforward. This is all well and good. One of the issues is that it's rather slow. I thought it would be the recursive nature (and interface assertions), but converting all this into a shunting yard system didn't improve the performance dramatically. I've profiled the thing and removed a few hotspots, my question is not about profiling. I'm after a bit more general advice on how to handle these runtime evaluations and if there are better ways of doing so. Essentially some sort of a JIT (but Go does not have runtime assembly, right?), or maybe convert each expression into a closure or maybe a whole different algorithm or...? Reduce the amount of code and indirection that you need to do, few basic ideas: 1. implement a VM https://play.golang.org/p/dlmZ2lGPY7 2. operate on vectors of variables instead of single values https://play.golang.org/p/25MIjIXs0D 3. try to do the lookup of all necessary variables before starting to compute with them; if possible Obviously pprof is your friend. (https://blog.golang.org/profiling-go-programs) + Egon -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
