| Age | Commit message (Collapse) | Author |
|---|
|
|
|
This removes all allocations from the find_or_insert loop, which
requires us to start the search over after calling the provided create
function.
In exchange that allows us to assume that all concurrent threads insert
will get the same view of the GC state, and so should all be attempting
to clear and reuse a slot containing a garbage object.
|
|
This refactors the concurrent set to examine and reserve a slot via CAS
with the hash, before then doing the same with the key.
This allows us to use an extra bit from the hash as a "continuation bit"
which marks whether we have ever probed past this key while inserting.
When that bit isn't set on deletion we can clear the field instead of
placing a tombstone.
|
|
|
|
Before, the 50% load factor was not working correctly with the new capacity
calculation on resize and too many resizes were seen.
Before this change
------------------
Example:
old_capacity = 32
old_size = 16
deleted_entries = 2 (almost all live)
That means we have:
expected_size = 14
We'll see that 64 > 14 * 4
We'll end up using 32 as the new capacity (same as old) even though that only
leaves us two elements free before we'd have to rebuild again.
Co-authored-by: John Hawthorn <john.hawthorn@shopify.com>
|
|
The atomic load/store operations here should mostly be using
release/acquire semantics. This may lead to better performance than what
we had under the default seq_cst.
On x86 this may make the atomic store of hash faster, as it can avoid
xchg. On ARM the loads may be faster (depending on target CPU for the
compiler).
Reference for comparison of atomic operations
https://godbolt.org/z/6EdaMa5rG
|
|
Previously we just had a comment stating that the code required a
barrier. Turns out it's not too difficult to properly assert that.
Co-authored-by: Luke Gruber <luke.gru@gmail.com>
|
|
When testing we've found that the concurrent_set objects used for
fstrings can grow quite large, and because they reach oldgen quickly end
up not being collected.
This commit is a bit of a hack but aims to improve that by moving the
objects to not be WB_PROTECTED. "Unprotected" objects do not age and
can't become oldgen, so this allows them to be collected in a minor GC.
|
|
When `rb_concurrent_set_foreach_with_replace` deletes entries from a
concurrent set, it should increment the `deleted_entries` field, too.
|
|
Since the hash should never change, we only need to calculate it once.
|
|
If we create a key but don't insert it (due to other Ractor winning the
race), then it would leak memory if we don't free it. This introduces a
new function to free that memory for this case.
|
|
If the object is garbage, then calling cmp on it may crash.
|
|
|
|
|
|
|
|
rb_objspace_garbage_object_p expects only GC managed objects to be passed
in. We should skip the check if curr_key is a special constant.
|
|
Since we resize when `prev_size > set->capacity / 2`, it's possible that
`prev_size == set->capacity / 2`, so we need to change the assertion in
concurrent_set_try_resize_without_locking to be
`new_set->size <= new_set->capacity / 2`.
|
|
We should never modify rb_concurrent_set_funcs during runtime, so we can
make it const.
|
|
There's nothing ractor related in them, and the classic terminology
for these sort of data structures is `concurrent-*`, e.g.
concurrent hash.
|
