From b83343fa0dba85dc7e8d357ba7aaeca991315e96 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sun, 18 Feb 2024 21:45:12 -0500 Subject: ioq: Remove some branches from ioq_slot_{push,pop}() --- src/ioq.c | 33 +++++++++++++++++++++------------ 1 file changed, 21 insertions(+), 12 deletions(-) (limited to 'src') diff --git a/src/ioq.c b/src/ioq.c index f23b62f..74e2587 100644 --- a/src/ioq.c +++ b/src/ioq.c @@ -171,8 +171,11 @@ typedef atomic uintptr_t ioq_slot; /** Someone might be waiting on this slot. */ #define IOQ_BLOCKED ((uintptr_t)1) + +/** Bit for IOQ_SKIP. */ +#define IOQ_SKIP_BIT (UINTPTR_WIDTH - 1) /** The next push(es) should skip this slot. */ -#define IOQ_SKIP ((uintptr_t)1 << (UINTPTR_WIDTH - 1)) +#define IOQ_SKIP ((uintptr_t)1 << IOQ_SKIP_BIT) /** Amount to add for an additional skip. */ #define IOQ_SKIP_ONE (~IOQ_BLOCKED) @@ -309,24 +312,30 @@ static void ioq_slot_wake(struct ioqq *ioqq, ioq_slot *slot) { cond_broadcast(&monitor->cond); } +/** Branch-free (slot & IOQ_SKIP) ? ~IOQ_BLOCKED : 0 */ +static uintptr_t ioq_skip_mask(uintptr_t slot) { + return -(slot >> IOQ_SKIP_BIT) << 1; +} + /** Push an entry into a slot. */ static bool ioq_slot_push(struct ioqq *ioqq, ioq_slot *slot, struct ioq_ent *ent) { uintptr_t prev = load(slot, relaxed); + while (true) { - uintptr_t next; - if (prev & IOQ_SKIP) { - // skip(1) → empty - // skip(n) → skip(n - 1) - next = (prev - IOQ_SKIP_ONE) & ~IOQ_BLOCKED; - } else if (prev > IOQ_BLOCKED) { + size_t skip_mask = ioq_skip_mask(prev); + size_t full_mask = ~skip_mask & ~IOQ_BLOCKED; + if (prev & full_mask) { // full(ptr) → wait prev = ioq_slot_wait(ioqq, slot, prev); continue; - } else { - // empty → full(ptr) - next = (uintptr_t)ent >> 1; } + // empty → full(ptr) + uintptr_t next = ((uintptr_t)ent >> 1) & full_mask; + // skip(1) → empty + // skip(n) → skip(n - 1) + next |= (prev - IOQ_SKIP_ONE) & skip_mask; + if (compare_exchange_weak(slot, &prev, next, release, relaxed)) { break; } @@ -349,7 +358,7 @@ static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool bloc uintptr_t next = prev + IOQ_SKIP_ONE; // skip(n) → ~IOQ_BLOCKED // full(ptr) → 0 - next &= (next & IOQ_SKIP) ? ~IOQ_BLOCKED : 0; + next &= ioq_skip_mask(next); if (block && next) { prev = ioq_slot_wait(ioqq, slot, prev); @@ -368,7 +377,7 @@ static struct ioq_ent *ioq_slot_pop(struct ioqq *ioqq, ioq_slot *slot, bool bloc // empty → 0 // skip(n) → 0 // full(ptr) → ptr - prev &= (prev & IOQ_SKIP) ? 0 : ~IOQ_BLOCKED; + prev &= ioq_skip_mask(~prev); return (struct ioq_ent *)(prev << 1); } -- cgit v1.2.3