[gambit-list] Parameter objects performance Q
feeley at iro.umontreal.ca
Sun Mar 8 11:00:22 EDT 2020
The dynamic environment is implemented as a hybrid structure that combines a dictionary (implemented as a binary tree), with a special case for the frequently accessed parameters (current-input-port, etc), and a cache of the last 3 parameters that were accessed.
So if you access the current input port or one of the last 3 accessed parameters, the time complexity is O(1). Otherwise it is O(log N) where N is the number of bindings in the environment.
I may change the binary tree to a table once the functional API to tables is fully implemented.
So I think the complexity is pretty good, but obviously much slower than an access to a lexical variable. I’ll let you do some benchmarking to determine the hidden constant.
> On Mar 8, 2020, at 10:44 AM, Adam <adam.mlmb at gmail.com> wrote:
> Hi Marc,
> I can't recall if this is somewhere in the mailing list archive from before:
> I recall that you indicated that parameter objects are expensive.
> Would you mind describing/quantifying the average/worst case/best case cost for assigning a value to a parameter object by parameterization (|parameterize|), and for accessing a parameter object (load or store operation by invoking it as a closure)?
> Parameter objects are very practical and have ample use scenarios, both high-level and relatively low-level.
More information about the Gambit-list