tag f340fec7a6a3b21e7d58fea2c98987f9eb7c952d
tagger Mishal Shah <mishal_shah@apple.com> Thu Mar 10 23:38:36 2016 -0800
object fc261045a5c19342a8d8f5a7a0924ab8913bea20

Tag build swift-DEVELOPMENT-SNAPSHOT-2016-02-25-a

commit fc261045a5c19342a8d8f5a7a0924ab8913bea20
author John McCall <rjmccall@apple.com> Thu Feb 25 01:11:28 2016 -0800
committer John McCall <rjmccall@apple.com> Thu Feb 25 01:11:57 2016 -0800
tree f94beb7b7f568393f152bcaa4b456b17347ac26e
parent 4cfccda0d7046d38b52fc6c763619c9e44c64790

Optimize the number of accesses performed on ConcurrentMap
and MetadataCache and fix a re-entrancy bug in metadata
instantiation.

The re-entrancy bug is that we were holding the instantiation
lock of a metadata cache while instantiating metadata.  Doing
so prevents us from creating a different instantiation if
it's needed by the outer instantiation.  This is already
possible, but it's much more likely in a patch I'm working on
to only store the minimal metadata for generic parameters
in generic types.

The same bug could also show up as a deadlock between threads,
so a recursive lock would not be a good fix.  Instead, we add
a condition variable to the metadata cache.  When fetching
metadata, we look for a node in the concurrent map, eagerly
creating an empty one if none currently exists.  If lookup
finds an empty node, we wait on the condition variable for
the node to become populated.  If lookup succeeds in creating
an empty node, we instantiate the metadata, grab the lock,
populate the node, and notify the condition variable.

Safely creating an empty node without any metadata present
requires us to move the key data into the map entry.  That,
plus a few other invariant shifts, makes it sensible to
give the user of ConcurrentMap more control over the
allocation of map nodes and the layout of keys.  That, in
turn, allows us to change the contract so that keys can be
more complex than just a hash code.  Instead of incrementing
hash codes and re-performing the lookup, we just insist
that lookup keys be totally ordered.

For now, I've kept the uniform use of hash codes as a
component of the key for MetadataCaches.  However, hash
codes aren't really profitable for small keys, and we should
probably use direct comparisons instead.

We should also switch the safer metadata caches (i.e. the
ones that don't involve calling an arbitrary instantiation
function, like MetatypeMetadataCache) over to directly use
ConcurrentMap.

LLDB's requirement that we maintain a linked list of metadata
cache instantiations with a known layout means we can't yet
remove the CacheEntry's redundant copy of the generic
arguments.