Rather than scanning the type descriptor each time we perform a comparison
or hash of a metadata cache entry, do so only once to establish the number
of key parameters and the number of witness tables. Use those values to
more efficiently compare keys.
Metadata uniquing might encounter witness tables that were distinctly
generated but come from identical descriptors. Handle this case in metadata
uniquing be looking into the protocol conformance descriptors themselves.
- `swift_getForeignTypeMetadata` is now a request/response function.
- The initialization function is now a completion function, and the
pointer to it has moved into the type descriptor.
- The cache variable is no longer part of the ABI; it's an
implementation detail of the access function.
- The two points above mean that there is no special header on foreign
type metadata and therefore that they can be marked constant when
there isn't something about them that needs to be initialized.
The only foreign-metadata initialization we actually do right now is
of the superclass field of a foreign class, and since that relationship
is a proper DAG, it's not actually possible to have recursive
initialization problems. But this is the right long-term thing to do,
and it removes one of the last two clients of once-based initialization.
I was going to put this off for awhile, but it turns out that a lot of
my testcases are enums with multi-payload cases, which we currently
compile as tuples, so they were all still hanging until this patch.
I de-templated MetadataState and MetadataRequest because we weren't
relying on the template and because using the template was causing
conversion problems due to the inability to directly template an enum
in C++.
This includes global generic and non-generic global access
functions, protocol associated type access functions,
swift_getGenericMetadata, and generic type completion functions.
The main part of this change is that the functions now need to take
a MetadataRequest and return a MetadataResponse, which is capable
of expressing that the request can fail. The state of the returned
metadata is reported as an second, independent return value; this
allows the caller to easily check the possibility of failure without
having to mask it out from the returned metadata pointer, as well
as allowing it to be easily ignored.
Also, change metadata access functions to use swiftcc to ensure that
this return value is indeed returned in two separate registers.
Also, change protocol associated conformance access functions to use
swiftcc. This isn't really related, but for some reason it snuck in.
Since it's clearly the right thing to do, and since I really didn't
want to retroactively tease that back out from all the rest of the
test changes, I've left it in.
Also, change generic metadata access functions to either pass all
the generic arguments directly or pass them all indirectly. I don't
know how we ended up with the hybrid approach. I needed to change all
the code-generation and calls here anyway in order to pass the request
parameter, and I figured I might as well change the ABI to something
sensible.
I was trying to make the entry-delegation thing do *way* too much.
Just give the entry access to the lock/queue and introduce subclasses
which simplify most of the work.
Also, fix some bad reasoning around the attempts to avoid acquiring
locks in the absence of waiters. It really is always necessary to
acquire the lock when notifying; waiters cannot atomically set the
has-waiters flag and wait, so we have to protect against the
possibility that we notify before they can wait.
Change generic witness table instantiation to use a more lightweight
entry scheme that allocates the witness table as part of the entry.
In contrast, change generic metadata instantiation to use a more
straightforward allocation scheme where the metadata is a totally
independent allocation.
This is preparation for proper cyclic-dependency handling.
This seems to more than fix a performance regression that we
detected on a metadata-allocation microbenchmark.
A few months ago, I improved the metadata cache representation
and changed the metadata allocation scheme to primarily use malloc.
Previously, we'd been using malloc in the concurrent tree data
structure but a per-cache slab allocator for the metadata itself.
At the time, I was concerned about the overhead of per-cache
allocators, since many metadata patterns see only a small number
of instantiations. That's still an important factor, so in the
new scheme we're using a global allocator; but instead of using
malloc for individual allocations, we're using a slab allocator,
which should have better peak, single-thread performance, at the
cost of not easily supporting deallocation. Deallocation is
only used for metadata when there's contention on the cache, and
specifically only when there's contention for the same key, so
leaking a little isn't the worst thing in the world.
The initial slab is a 64K globally-allocated buffer.
Successive slabs are 16K and allocated with malloc.
rdar://28189496
This seems to more than fix a performance regression that we
detected on a metadata-allocation microbenchmark.
A few months ago, I improved the metadata cache representation
and changed the metadata allocation scheme to primarily use malloc.
Previously, we'd been using malloc in the concurrent tree data
structure but a per-cache slab allocator for the metadata itself.
At the time, I was concerned about the overhead of per-cache
allocators, since many metadata patterns see only a small number
of instantiations. That's still an important factor, so in the
new scheme we're using a global allocator; but instead of using
malloc for individual allocations, we're using a slab allocator,
which should have better peak, single-thread performance, at the
cost of not easily supporting deallocation. Deallocation is
only used for metadata when there's contention on the cache, and
specifically only when there's contention for the same key, so
leaking a little isn't the worst thing in the world.
The initial slab is a 64K globally-allocated buffer.
Successive slabs are 16K and allocated with malloc.
rdar://28189496
IIRC we never had any evidence that the performance impact of a
separate allocator here was actually measurable, and it does come
at a significant fragmentation cost because every single cache
allocates at least a page of memory. Sharing that with the system
allocator makes more sense, even if these allocations are typically
permanent.
This also means that standard memory-debugging tools will actually
find problems with out-of-bounds accesses to metadata.
MetadataCache's allocator into it.
The major functional change here is that MetadataCache will now use
the slab allocator for tree nodes, but I also switched the Hashable
conformances cache to use ConcurrentMap directly instead of a
Lazy<ConcurrentMap<>>.
- added read / write lock support
- added non-fatal error support to allow use of mutex in fatal error reporting pathway
- isolated pthread implementation to it own header/cpp file pair
- expanded unit tests to cover new code as well as better test existing mutex
- removed a layer of complexity that added no real value
initialization in-place on demand. Initialize parent metadata
references correctly on struct and enum metadata.
Also includes several minor improvements related to relative
pointers that I was using before deciding to simply switch the
parent reference to an absolute reference to get better access
patterns.
Includes a fix since the earlier commit to make enum metadata
writable if they have an unfilled payload size. This didn't show
up on Darwin because "constant" is currently unenforced there in
global data containing relocations.
This patch requires an associated LLDB change which is being
submitted in parallel.
initialization in-place on demand. Initialize parent metadata
references correctly on struct and enum metadata.
Also includes several minor improvements related to relative
pointers that I was using before deciding to simply switch the
parent reference to an absolute reference to get better access
patterns.
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.
The inputs to the hash function is pointers that have a predictable patten. The
hashes that we were generating and using for the metadata caches were not very
good, and as a result we generated very deep search trees. A small change that
improved the utilization of the 'length' field and another bit-rotate round
improved the quality of the hash function.
I am going to attach to the github commit two pictures. The first picture is the
binary with the old hash. The first tree is very deep and sparse. The second
picture is with the new hash function and the tree is very wide and uniform. I
used the benchmark 'TypeFlood' in debug mode to generate huge amounts of
metadata.
This change cuts the number of mallocs() in the metadata caches in half.
The current metadata cache data structure uses a linked list for each entry in
the tree to handle collissions. This means that we need at least two memory
allocations for each entry, one for the tree node and one for the linked list
node.
This commit changes the map used by the metadata caches from an open hash map
(that embeds a linked list at each entry) into an closed map that uses a
different hash value for each entry. With this change we no longer accept
collissions and it is now the responsibility of the user to prevent collissions.
The new get/trySet API makes this responsibility explicit. The new design also
goes well with the current design where hashing is done externally and the fact
that we don't save the full key, just the hash and the value to save memory.
This change reduces the number of allocated objects per entry in half. Instead
of allocating two 32-byte objects (one for the tree node and one for the linked
list) we just allocate a single entry that contains the hash and the value.
Unfortunately, values that are made of two 64-bit pointers (like protocol
conformance entries) are now too big for the 32-byte tree entry and are rounded
up to 48 bytes. In practice this is not a big deal because malloc has 48-byte pool
entries.
This is the first patch in a series that will allow new protocol
requirements to be added resiliently, with the runtime filling in
default implementations in witness tables.
First, this adds a new flag to the protocol descriptor indicating
that the protocol is resilient. In this case, there are two
additional fields, MinimumWitnessTableSizeInWords and
DefaultWitnessTableSizeInWords, followed by tail-allocated
default witnesses.
The swift_getGenericWitnessTable() entry point now fills in the
default witnesses from the protocol if the given witness table
template is smaller than the expected witness table size.
This also changes the layout of instantiated witness tables to move
the address point to the end of private data. Previously the private
data came after the requirements, but this meant that adding new
requirements would require sliding the private data at runtime and
accessing it indirectly. It is much simpler to access it from
negative offsets instead.
I updated IRGen to emit the new metadata, but currently all protocols
are flagged as not resilient, and default witnesses are not emitted;
this will come in a subsequent patch once some more plumbing is
in place.
To avoid generating GOT entries for references to protocols defined
in the current module, I had to add some hacks to the existing hack
for this. I'll hopefully clean this up in a principled manner later.
We incorrectly tested the uninitialized "next" pointer against MAP_FAILED, instead of the real result of mmap. Fixes rdar://problem/21659505.
Swift SVN r30030
Provide new swift_{alloc,dealloc,project}Box2 entry points that allocate, project, and deallocate typed boxes using runtime-instantiated metadata. Give these a new metadata kind, so that external tools recognize the difference and can interpret the metadata appropriately.
Swift SVN r29714
This has a couple benefits:
- Since metadata allocations are already guarded by a lock, the allocator doesn't require synchronization, and can be much much simpler and a little faster than malloc.
- By bypassing malloc, we also avoid tools like 'heap' prying into our metadata cache and misrepresenting cache entries keyed on classes as live objects, fixing rdar://problem/20562886.
In my unscientific local tests, this appeared to give a small across-the-board improvement to Onone performance in the perf test suite, though not far enough from noise for me to declare that definitively. Fixing the bug is the bigger point here.
Swift SVN r27856
