ChildsplayOSU / bogl

Haskell implementation of the BoGL language
https://bogl.engr.oregonstate.edu
BSD 3-Clause "New" or "Revised" License
7 stars 1 forks source link

Evaluate Apps/Refs from Builtins before Env #160

Closed montymxb closed 3 years ago

montymxb commented 3 years ago

This closes #159. The issue had nothing to do with the while, but it was easiest to observe the problem there due to the speed at which the environment accumulates. The problem was related to attempting to evaluate function application or references by looking them up in the environment instead first. The environment fills with key:value pairs for all references, functions, and local name bindings via parameters and lets. However, the environment is repeatedly filled with duplicates of all of these upon subsequent evaluations (including repeated function definitions). Normally, this leads to no visible effect due to (from what I can tell) haskell's laziness. The relevant bindings are re-declared fairly close to the front of the list, and a lookup returns very quickly without evaluating much of the list.

However, adding any builtin functions or references leads to an incrementally massive slowdown during repeated evaluations. This is due to the lookup on the environment checking the entire environment first before checking the builtins, and this seems to force all related values to evaluated as well. For even basic while loops, this creates an exponential increase in memory usage and computation time due to the full environment size as it runs, and BoGL will freeze, or fail to return a valid response. For example:

-- extremely slow (don't run this on the server please)
bad : Int -> Int
bad(x) = while and(x < 1000, x < 1000) do x+1

and2 : (Bool,Bool) -> Bool
and2(a,b) = if a then if b then True else False else False

-- finishes in a fraction of second via
good : Int -> Int
good(x) = while and2(x < 1000, x < 1000) do x+1

Flipping the order of evaluation around immediately fixed the issue, and since the builtins are finite this should be just fine from here on out. This dramatically improved performance for using any of the builtins, as well as input. This eliminates the latency related to repeated looping inputs for as much as I have tested, a surprisingly dramatic improvement 💯 .

To add briefly, with the patch the bad example runs at the same speed as the good one, there's no noticeable difference.

montymxb commented 3 years ago

I'm going to open up another issue as a kind of open investigation into the environment thing. It appears to be fine for the moment, but it might be worth looking into later on.