[gambit-list] Parameter objects performance Q

Marc Feeley feeley at iro.umontreal.ca
Fri Mar 13 10:22:25 EDT 2020


> On Mar 8, 2020, at 11:22 PM, Adam <adam.mlmb at gmail.com> wrote:
> 
> 3) Faster ways?
> 
>  * Did you have a thought with bringing up fluid/dynamic variables, to make a point along the lines that significant cost reductions to parameter objects may be possible, for a slightly narrower definition of parameter object?
> 
>  * I'd be curious if a "global fixed parameter object" could somehow be made to avoid btree/hashtable lookups. Wildguessing, having a vector allocation or copy at |parameterize| should be fine shouldn't it, and also having the first parameter object load/store operation within a |parameterize| _only_, do some kind of punch-through resolve, should be fine also shouldn't it.
> 
>    Anyhow luckily computers are fast and getting faster, btree/hashtable structures for a couple hundred elements should tend to fit in the L1 cache.
> 
> Looking forward to his benchmarks later.
> 
> 
> Thanks again for taking on the conversation. Was curious about the performance overhead because I find them so useful per the previous teleport hr example.
> 
> Best regards,
> Adam

The implementation of parameter objects has much in common with the implementation of thread local storage.  For the most efficient implementation the compiler would need to know the set of all parameter objects that are used in the whole program.  So if you combine “a fixed set of parameter objects defined by each module/library” and “an intelligent static linker”, then you could implement parameter objects more efficiently with a variety of methods:

1) if the number of parameter objects (P) is small, put their binding in the “dynamic environment” object (which is essentially a vector of P cells) and this vector is functionnaly updated (copied) when you enter a parameterize.

2) otherwise create a K-ary tree containing the P cells at the leaves, which allows to only copy the path leading to the cell of the parameter object to be bound, in time O(K * log_K(P)).

3) if you know that some are more frequently accessed, then give them priority by using an unbalanced tree (similar to a Huffman coding tree).

And I’m sure there are others.  But having a fixed number of parameter objects and static linking is incompatible with all the niceties offered by dynamic languages, for example it precludes the port timeout handling I mentionned previously (where you have to allocate a new parameter object whenever you create a new port).

Marc





More information about the Gambit-list mailing list