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.
