duktape/doc/property-cache.rst

==============
Property cache
==============

This document describes property caching, a mechanism added in Duktape 2.1.0
to speed up property reads (and maybe writes in the future).

Data structure
==============

The property cache is an array of entries to speed up GETPROP operations.
Each entry contains:

* Object and key reference for original lookup.  The object reference stored
  is for the lookup starting point, which is often different than the object
  actually holding the property (inheritance).

* Property value.

* Generation count to allow quick invalidation.

All key/value references are borrowed.  Only concrete properties (not getters
or virtual property values) can be cached due to the property value not being
reference counted.  In other words, when a property is cached:

* There must be a guarantee that the object, key, and value are reachable by
  some means.

* A GETPROP operation from the same starting point using the same key would
  yield the same value.

The ``duk_heap`` structure holds the property cache which is just an array of
entries of (preferably) 2^N size.  The heap structure also holds the current
generation count which starts from 1; entries with generation count 0 are thus
ignored automatically.

Read handling
=============

* When GETPROP is called, compute a property cache lookup key by combining
  object pointer (for lack of an object hash) with the key string hash.

* Check the entry at the hash index.  If the generation count doesn't match
  current generation count (which is a heap-wide value), the entry must be
  ignored as obsolete.  Otherwise check if the object and the key match, and
  if so, return the cached value.

* If there's a cache miss, proceed with normal property lookup.  There's no
  probing sequence.

* If no property is found, no property cache changes are made.  It would be
  possible to implement negative property caching.

  - Negative property caching would improve e.g. JSON stringify() performance
    because negative .toJSON() lookups could be cached.

* If a property is found, and there are no conditions to prevent caching,
  overwrite the cache entry at prophash: set generation count to current,
  set object and key reference (object reference must be for the lookup
  starting point -- not the final object), and property value.

* There is currently no hash probing/chaining: the existing entry is simply
  overwritten with the hope that collision are relatively rare in practice.

* Conditions preventing caching:

  - Value came from a getter: side effects, value may change per lookup.

  - Value came from a Proxy: side effects, value may change per lookup.

  - Value is virtual and may change per lookup.  Virtual values that won't
    change over time can be read cached however.

  - Array index lookups probably shouldn't be cached because the same index
    is not usually read many times for caching to be useful.  These entries
    would also purge useful entries unnecessarily.

Invalidation
============

Invalidation must be triggered by any operation that might compromise the
cache integrity requirements, i.e.:

* The operation might cause object, key, or value (all borrowed) to become
  unreachable, thus leading to memory unsafe behavior.

* The operation might change the property value if a GETPROP were done.
  For example, looking up a property storage location is by itself not an
  issue, but overwriting the value there is.

The basic challenge with partial invalidation where only actually affected
entries are removed is that: (1) knowing what entries to remove requires
complicated tracking state, and (2) actually scrubbing affected entries
may require multiple lookups if a change in an inherited property affects
multiple lookup cache entries.

The current solution is thus to invalidate the entire cache very cheaply by
using a generation count.  Entries whose generation count don't match current
are entirely ignored, so that simply bumping the current generation count is
enough to invalidate all entries without touching the entries themselves.

Technically, if the generation count wraps, entries should be scrubbed
fully.  This can be achieved by detecting that the generation count became
zero, setting the whole cache to zero, and then bumping the generation count
once more to ignore the zeroed entries.

Operations that require invalidation include:

* PUTPROP

* DELPROP

* defineProperty() and all its variants

* Changes to object internal prototypes: duk_set_prototype(),
  Object.setPrototypeOf(), etc.  Internal direct prototype changes when there's
  any possibility a property access might have happened.

* Any code that looks up an existing property and modifies its storage location
  directly.  Easiest approach, at least initially, is to invalide the cache on
  that storage lookup.

* Any code modifying structures that affect non-array-index virtual properties.
  For example, writing to ``duk_harray.length`` which appears as a virtual
  ``.length`` property.  (Needed if virtual ``.length`` is cached; generally
  virtual properties cannot be cached because heap-allocated borrowed values
  can't be used for dynamic values.)

* Mark-and-sweep might do compaction which affects property storage locations.
  But currently only the value, not its storage location, is cached so that
  compaction by itself is not an issue.

* Mark-and-sweep may finalize objects and then free them however.

* Assuming that the property keys are reachable through the object, there
  should be no chance that the cached key would be freed without the object
  being freed.

* An object may be freed however without any property related operation
  taking place.  There are only a few places where the object is actually
  freed, and those locations can invalidate the property cache.

Future work
===========

* Caching "own property" lookups would speed up some cases where the same
  inheritance path is used by multiple lookups.  Intuitively this would seem
  to be of less practical use.

* Caching property misses would be straightforward; use DUK_TVAL_SET_UNUSED()
  to flag the value as missing.  However, negative caching seems of little
  practical use because most repeated property lookups are for property hits.

* Caching property writes would be possible by caching the storage location
  rather than the value only.  Property attributes can be cached to allow
  writes to be validated.  Alternatively, if only writable properties are
  cached, writability can be assumed if the property is found in the cache.

* Caching array reads/writes would be possible to some extent, but would
  require a slightly different approach to avoid polluting the property
  cache with array indices.  The caching approach could speed up locating
  the ultimate array/array-like object for the index read/write to avoid
  walking through the inheritance chain.  However, subclassed Arrays or
  typed arrays are relatively rare (though Node.js Buffer instances inherit
  from Uint8Array).

* Caching variable reads using the initial property read caching (value only)
  approach doesn't work because every executor register write would need to
  invalidate the read cache.  However, if the cache contained a storage
  reference, variable location caching would be possible and could be applied
  to slow path read/write references.  Inherited properties (scope chain)
  could also be cached, provided that there are no Proxy object bindings.
  Value stack resize and call handling would need to invalidate the variable
  lookup cache because the storage locations might change.

* Hash probing for the cache locations might help some cases where property
  lookup hashes collide.  However, it adds another step to the property
  lookup, and more importantly causes another cache line to be fetched.
  So it may be of relatively little practical value, at least when the
  property cache can just be made larger instead.

* Making ``duk_propcache_entry`` size 2^N would speed up the cache lookup
  and align the lookups better.

* Caching own properties instead of GETPROP/PUTPROP would reduce the benefit
  of caching for inheritance chains, but would make caching simple otherwise.
  For example, a property creation for one object wouldn't invalidate cached
  properties of another because inheritance chains don't matter for caching.