This change adds a new type of cache (cache by type descriptor) to the protocol conformance lookup system. This optimization is beneficial for generic types, where the
same conformance can be reused across different instantiations of the generic type.
Key changes:
- Add a `GetOrInsertManyScope` class to `ConcurrentReadableHashMap` for performing
multiple insertions under a single lock
- Add type descriptor-based caching for protocol conformances
- Add environment variables for controlling and debugging the conformance cache
- Add tests to verify the behavior of the conformance cache
- Fix for https://github.com/swiftlang/swift/issues/82889
The implementation is controlled by the `SWIFT_DEBUG_ENABLE_CACHE_PROTOCOL_CONFORMANCES_BY_TYPE_DESCRIPTOR`
environment variable, which is enabled by default.
This reapplies https://github.com/swiftlang/swift/pull/82818 after it's been reverted in https://github.com/swiftlang/swift/pull/83770.
This change adds a new type of cache (cache by type descriptor) to the protocol conformance lookup system. This optimization is beneficial for generic types, where the
same conformance can be reused across different instantiations of the generic type.
Key changes:
- Add a `GetOrInsertManyScope` class to `ConcurrentReadableHashMap` for performing
multiple insertions under a single lock
- Add type descriptor-based caching for protocol conformances
- Add environment variables for controlling and debugging the conformance cache
- Add tests to verify the behavior of the conformance cache
- Fix for https://github.com/swiftlang/swift/issues/82889
The implementation is controlled by the `SWIFT_DEBUG_ENABLE_CACHE_PROTOCOL_CONFORMANCES_BY_TYPE_DESCRIPTOR`
environment variable, which is enabled by default.
This memory is part of the conformance cache concurrent hash map, so
when we clear the conformance cache, record each of the allocated
pointers within the concurrent map's free list. This way, it'll be
freed with the rest of the concurrent map when it's safe to do so.
Moved all the threading code to one place. Added explicit support for
Darwin, Linux, Pthreads, C11 threads and Win32 threads, including new
implementations of Once for Linux, Pthreads, C11 and Win32.
rdar://90776105
Moved all the threading code to one place. Added explicit support for
Darwin, Linux, Pthreads, C11 threads and Win32 threads, including new
implementations of Once for Linux, Pthreads, C11 and Win32.
rdar://90776105
The `ElementStorage` member `Capacity` will be padded up to the next pointer alignment due to the storage of the `ElemTy` by C's struct layout rules. However, this is implicit and not entirely guaranteed. Instead, make the storage a pointer sized value, and then truncate to 32-bits to maintain ABI compatibility. This becomes important as we expand on the runtime metadata handling.
constexpr-if is a C++17 feature. Swift is C++14, so this results in a
lot of warnings. Clang is smart enough that the constant propagation
will elide the unused side of the branch anyway. Since we're doing a
template check on a type, we should always have enough information at
compile to elide. We would need a constexpr/std::enable_if-level
approach if the API's were different to tell clang not to look at one
side of the branch. That's not the case here so we can let the optimizer
do it's thing and let clang look at both sides.
The callbacks made in ImageInspectionMachO.cpp are called in a dangerous context, with the dyld and ObjC runtime locks held. C++ allows programs to overload the global operator new/delete, and there's no guarantee that those overloads behave. Ideally, we'd avoid them entirely, but that's a bigger job. For now, avoid the worst trouble by avoiding STL and new/delete in these callbacks. That use came from ConcurrentReadableArray's free list, so we switch that from a std::vector to a linked list.
rdar://75036800
When reallocating storage, the storing the pointer to the new storage had insufficiently strong ordering. This could cause writers to check the reader count before storing the new storage pointer. If a reader then came in between that load and store, it would end up using the old storage pointer, while the writer could end up freeing it.
Also adjust the Concurrent.cpp tests to test with a variety of reader and writer counts. Counterintuitively, when freeing garbage is gated on there being zero readers, having a single reader will shake out problems that having lots of readers will not. We were testing with lots of readers in order to stress the code as much as possible, but this resulted in it being extremely rare for writers to ever see zero active readers.
rdar://69798617
Mark the relevant snapshot methods as ref-qualified (adding a & after the parameter list) so the compiler will enforce this for us and forbid calling them on temporaries.
rdar://72997638
StableAddressConcurrentReadableHashMap::getOrInsert had a race condition in the first lookup, where the snapshot was destroyed before the pointer was extracted from the returned wrapper. Fix this by creating the snapshot outside the if so that it stays alive.
rdar://problem/71932487
* [Runtime] Switch MetadataCache to ConcurrentReadableHashMap.
Use StableAddressConcurrentReadableHashMap. MetadataCacheEntry's methods for awaiting a particular state assume a stable address, where it will repeatedly examine `this` in a loop while waiting on a condition variable, so we give it a stable address to accommodate that. Some of these caches may be able to tolerate unstable addresses if this code is changed to perform the necessary table lookup each time through the loop instead. Some of them store metadata inline and we assume metadata never moves, so they'll have to stay this way.
* Have StableAddressConcurrentReadableHashMap remember the last found entry and check that before doing a more expensive lookup.
* Make a SmallMutex type that stores the mutex data out of line, and use it to get LockingConcurrentMapStorage to fit into the available space on 32-bit.
rdar://problem/70220660
This gives us faster lookups and a small advantage in memory usage. Most of these maps need stable addresses for their entries, so we add a level of indirection to ConcurrentReadableHashMap for these cases to accommodate that. This costs some extra memory, but it's still a net win.
A new StableAddressConcurrentReadableHashMap type handles this indirection and adds a convenience getOrInsert to take advantage of it.
ConcurrentReadableHashMap is tweaked to avoid any global constructors or destructors when using it as a global variable.
ForeignWitnessTables does not need stable addresses and it now uses ConcurrentReadableHashMap directly.
rdar://problem/70056398
We're using a lot of space on the free lists. Each vector is three words, and we have two of them. Switch to a single linked list. We only need one list, as both kinds of pointers just get free()'d. A linked list optimizes for the common case where the list is empty. This takes us from six words to one.
Also make ReaderCount, ElementCount, and ElementCapacity uint32_ts. The size_ts were unnecessarily large and this saves some space on 64-bit systems.
While we're in there, add 0/NULL initialization to all elements. The current use in the runtime is unaffected (it's statically allocated) but the local variables used in the test were tripping over this.
to use it.
ConcurrentReadableHashMap is lock-free for readers, with writers using a lock to
ensure mutual exclusion amongst each other. The intent is to eventually replace
all uses ConcurrentMap with ConcurrentReadableHashMap.
ConcurrentReadableHashMap provides for relatively quick lookups by using a hash
table. Rearders perform an atomic increment/decrement in order to inform writers
that there are active readers. The design attempts to minimize wasted memory by
storing the actual elements out-of-line, and having the table store indices into
a separate array of elements.
The protocol conformance cache now uses ConcurrentReadableHashMap, which
provides faster lookups and less memory use than the previous ConcurrentMap
implementation. The previous implementation caches
ProtocolConformanceDescriptors and extracts the WitnessTable after the cache
lookup. The new implementation directly caches the WitnessTable, removing an
extra step (potentially a quite slow one) from the fast path.
The previous implementation used a generational scheme to detect when negative
cache entries became obsolete due to new dynamic libraries being loaded, and
update them in place. The new implementation just clears the entire cache when
libraries are loaded, greatly simplifying the code and saving the memory needed
to track the current generation in each negative cache entry. This means we need
to re-cache all requested conformances after loading a dynamic library, but
loading libraries at runtime is rare and slow anyway.
rdar://problem/67268325
This adds a new copy of LLVMSupport into the runtime. This is the final
step before changing the inline namespace for the runtime support. This
will allow us to avoid the ODR violations from the header definitions of
LLVMSupport.
LLVMSupport forked at: 22492eead218ec91d349c8c50439880fbeacf2b7
Changes made to LLVMSupport from that revision:
process.inc forward declares `_beginthreadex` due to compilation issues due to custom flag handling
API changes required that we alter the `Deallocate` routine to account
for the alignment.
This is a temporary state, meant to simplify the process. We do not use
the entire LLVMSupport library and there is no value in keeping the
entire library. Subsequent commits will prune the library to the needs
for the runtime.
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.
