Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reworked call site, inline cache mechanism. #3638

Merged
merged 1 commit into from Apr 23, 2016
Merged

Reworked call site, inline cache mechanism. #3638

merged 1 commit into from Apr 23, 2016

Conversation

brixen
Copy link
Member

@brixen brixen commented Apr 22, 2016

No description provided.

A CallSite is an abstraction of the point of call & return for another
procedure. An InlineCache is an abstraction of a particular instance of an
executable at a CallSite.

In a 'statically typed' (or early bound) language, the executable at the call
site is known 'statically', via textual analysis of the program text. In a
'dynamically-typed' (or late bound) language, the particular executable is not
known until the program is executed. Consequently, in a late-bound language, a
call site must permit dynamic reconfiguration based on the program's
execution.

This dynamic reconfiguration requires prediction: when this kind of object is
seen, we predict we will see it again. The cost of finding the executable in
the first place can then be reduced by caching the previous result of looking
up the executable. When we see this kind of object, we can retrieve the
executable from the cache at less cost than looking it up.

If our predictions are correct, and the mechanism of creating and retrieving
items from the cache is actually less than searching for the item, we can
execute the program more efficiently. However, predictions can be wrong. If
they are wrong, the cache mechanism can become pure overhead, work done that
produces no value. In this case, the caching mechanism will make the program
*less* efficient rather than more efficient.

The number of cached items is typically limited because as the number grows,
the cost of retrieving items typically grows. Ideally, the first cached item
would always be the desired one. When that is not true, some (hopefully less
costly than lookup) search mechanism is required. Contiguous structures that
permit linear probing and are CPU cache-efficient usually perform very well.
If the number of entries grows, the algorithm needs to change from on O(n)
complexity to something closer to O(1), or the extra work of the caching
mechanism will be a cost increase instead of a cost reduction.

To account for our predictions being wrong, we need to be able to update,
replace, or even discard previous predictions. In same cases, we may need to
disable the caching mechanism completely. This latter case is true when the
types of objects seen at a call site vary widely.

This change also adds some new metrics for understanding how a program is
performing from the perspective of the call sites and inline caches. The next
mechanism to add is diagnostics to see the operation of individual caches
instead of the aggregate values that the metrics provide.

Another improvement that is needed is to cache `#method_missing`,
`#respond_to?` and `#send` call sites.
@brixen brixen merged commit f65a474 into master Apr 23, 2016
@brixen brixen deleted the inline_cache branch April 30, 2016 19:38
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

1 participant