PR about 3 issues

[BarisAlbayrakIEEE]

Hello @max0x7ba ,

I have three issues about atomic_queue.

Firstly, i could not find in the documentation, but i assume that the queues with atomic::is_always_lock_free (Atomic_Queue and Atomic_QueueB) shall be used with caution such that these queues use a NIL sentinel (T{}). T{} shall not be pushed to these queues as it represents the empty state. I think this should be documented clearly.

The 2nd one is related to replacing the modulo (index % size_) with a bit mask (index & (size_ - 1)) during the index determination which you already mentioned in another issue and already applied to the queues recieving the size parameter. I can apply this modification to the statically sized queues with a PR.

The last one is about the branch prediction annotations missed within the try_ versions of push and pop. i think, the inspections for FULL/EMPTY queue could be annotated UNLIKELY.

If these three points make sense to you, I can prepare a documentation PR for the 1st issue and two PRs for the remaining two.

[max0x7ba]

Hello @max0x7ba ,

I have three issues about atomic_queue.

Firstly, i could not find in the documentation, but i assume that the queues with atomic::is_always_lock_free (Atomic_Queue and Atomic_QueueB) shall be used with caution such that these queues use a NIL sentinel (T{}). T{} shall not be pushed to these queues as it represents the empty state. I think this should be documented clearly.

May I advise reading the laconic documentation in full instead of searching it poorly?

atomic_queue/README.md

Line 134 in 84a2cf0

The queues for atomic elements reserve one value to serve as an empty element marker `NIL`, its default value is `0`. `NIL` value must not be pushed into a queue and there is an [`assert`][13] statement in `push` functions to guard against that in debug mode builds. Pushing `NIL` element into a queue in release mode builds results in undefined behaviour, such as deadlocks and/or lost queue elements.

The 2nd one is related to replacing the modulo (index % size_) with a bit mask (index & (size_ - 1)) during the index determination which you already mentioned in another issue and already applied to the queues recieving the size parameter. I can apply this modification to the statically sized queues with a PR.

You may be pleasantly surprised to learn that compilers do such code transformations for you because size_ is a compile-time constant. It is one of strength reduction transformations, see https://en.wikipedia.org/wiki/Strength_reduction

The documentation mentions that too.

atomic_queue/README.md

Line 158 in 84a2cf0

* The writer and reader indexes get mapped into the ring-buffer array index using remainder binary operator `% SIZE`. Remainder binary operator `%` normally generates a division CPU instruction which isn't cheap, but using a power-of-2 size turns that remainder operator into one cheap binary `and` CPU instruction and that is as fast as it gets.

Have you inspected assembly output and found evidence to the contrary?

The last one is about the branch prediction annotations missed within the try_ versions of push and pop. i think, the inspections for FULL/EMPTY queue could be annotated UNLIKELY.

This hypothesis requires empirical data to confirm or deny: benchmark numbers before and after this change of yours.

There are no branch prediction hints in there because they didn't show any measurable improvements of the benchmarks.

[BarisAlbayrakIEEE]

Thanks alot for returning my poor issue. The NIL sentinel is clearly noted in the documentation and guarded by the assert in the push function. Really, sorry for that one. For the size modulo, i should have known/considered if the compiler optimizes for modulo 2.

I actually studied your code hardly in detail together with the moodycamel concurrent queue, but somehow rushed to contact to you for the above issues. Anyway, thanks for sharing your time to response to my questions although most are already answered in the code or documentation. Now, i am working on the benchmark whether the UNLIKELY annotation makes any difference on the performance of the try functions. I will share my results soon.

thanks and best regards

[max0x7ba]

i should have known/considered if the compiler optimizes for modulo 2.

C++ compilers are optimizing compilers, which means they transform your code.

The only accurate and complete source of information about what actually happens under the hood is the generated machine code.

Anything else is just guessing what a compiler might do, conditional on the language standard, compiler options, architecture, platform ABI, etc..

Diagnosing the generated machine code is the only way to make accurate and useful prescriptions at all times.

---

The compiler generated assembly output is not the full story, though.

The full story is the assembly output along with particular addresses/offsets, padding and instruction bytecodes. Oftentimes, compilers cannot do ideal register allocation or instruction selection/scheduling, which results in longer bytecodes and padding, which results in more L1i cache misses, than otherwise necessary.

In other words, not always C++ compilers can produce 0-overhead machine code compared to platonically ideal hand-written assembly, and that gets only worse when functions gets inlined. Register allocation and instruction selection/scheduling are hard computer-science problems preventing compilers from generating ideal machine code.

Such issues become apparent and obvious when looking at the machine code. Whereas the compiler assembly output doesn't have this information because it is just another text source code to be fed into a (non-optimizing) assembler.

If you are serious about getting the best possible performance from your C++ code, or just want to have complete and accurate understanding of what some C++ code compiles into, objdump is the right tool for that. That's what «compile to binary» option does for you at https://gcc.godbolt.org/ , which you can and should do on your own in fully automated fashion and 0-friction.

---

Example invocation:

$ cd ~/src/atomic_queue

$ make -j8
...

$ nm -C --defined-only build/release/gcc/benchmarks.o | egrep 'throughput_consumer.+RetryDecorator'
...
0000000000005340 t void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)
...

$ cxx_symbol='void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)'

$ obj=$(realpath build/release/gcc/benchmarks.o)

$ objdump --disassembler-color=on -Mintel -C --disassemble="$cxx_symbol" "$obj" | egrep -v -e '^[[:space:]]*$|^Disassembly of section |^/[^:]+:[[:space:]]+file format'

That function is the benchmark consumer doing try_pop of a power-2-sized AtomicQueue you mention.

Which outputs colourful and most informative:

0000000000005340 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)>:
    5340:	f3 0f 1e fa          	endbr64
    5344:	55                   	push   rbp
    5345:	49 89 d2             	mov    r10,rdx
    5348:	53                   	push   rbx
    5349:	49 89 cb             	mov    r11,rcx
    534c:	89 fb                	mov    ebx,edi
    534e:	f0 41 ff 01          	lock inc DWORD PTR [r9]
    5352:	eb 0e                	jmp    5362 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x22>
    5354:	66 66 2e 0f 1f 84 00 	data16 cs nop WORD PTR [rax+rax*1+0x0]
    535b:	00 00 00 00 
    535f:	90                   	nop
    5360:	f3 90                	pause
    5362:	41 8b 01             	mov    eax,DWORD PTR [r9]
    5365:	85 c0                	test   eax,eax
    5367:	75 f7                	jne    5360 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x20>
    5369:	ff c3                	inc    ebx
    536b:	45 31 c9             	xor    r9d,r9d
    536e:	48 8d 56 40          	lea    rdx,[rsi+0x40]
    5372:	48 8d be 80 00 00 00 	lea    rdi,[rsi+0x80]
    5379:	31 c9                	xor    ecx,ecx
    537b:	0f 1f 44 00 00       	nop    DWORD PTR [rax+rax*1+0x0]
    5380:	8b 02                	mov    eax,DWORD PTR [rdx]
    5382:	8b 2e                	mov    ebp,DWORD PTR [rsi]
    5384:	29 c5                	sub    ebp,eax
    5386:	85 ed                	test   ebp,ebp
    5388:	7e 56                	jle    53e0 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0xa0>
    538a:	8d 68 01             	lea    ebp,[rax+0x1]
    538d:	f0 0f b1 2a          	lock cmpxchg DWORD PTR [rdx],ebp
    5391:	75 ef                	jne    5382 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x42>
    5393:	0f b7 c0             	movzx  eax,ax
    5396:	89 c5                	mov    ebp,eax
    5398:	c1 ed 04             	shr    ebp,0x4
    539b:	31 c5                	xor    ebp,eax
    539d:	83 e5 0f             	and    ebp,0xf
    53a0:	31 e8                	xor    eax,ebp
    53a2:	c1 e5 04             	shl    ebp,0x4
    53a5:	31 e8                	xor    eax,ebp
    53a7:	48 8d 04 87          	lea    rax,[rdi+rax*4]
    53ab:	89 cd                	mov    ebp,ecx
    53ad:	87 28                	xchg   DWORD PTR [rax],ebp
    53af:	85 ed                	test   ebp,ebp
    53b1:	74 0d                	je     53c0 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x80>
    53b3:	39 eb                	cmp    ebx,ebp
    53b5:	74 39                	je     53f0 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0xb0>
    53b7:	89 ed                	mov    ebp,ebp
    53b9:	49 01 e9             	add    r9,rbp
    53bc:	eb c2                	jmp    5380 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x40>
    53be:	66 90                	xchg   ax,ax
    53c0:	f3 90                	pause
    53c2:	8b 28                	mov    ebp,DWORD PTR [rax]
    53c4:	85 ed                	test   ebp,ebp
    53c6:	75 e3                	jne    53ab <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x6b>
    53c8:	f3 90                	pause
    53ca:	8b 28                	mov    ebp,DWORD PTR [rax]
    53cc:	85 ed                	test   ebp,ebp
    53ce:	74 f0                	je     53c0 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x80>
    53d0:	eb d9                	jmp    53ab <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x6b>
    53d2:	66 66 2e 0f 1f 84 00 	data16 cs nop WORD PTR [rax+rax*1+0x0]
    53d9:	00 00 00 00 
    53dd:	0f 1f 00             	nop    DWORD PTR [rax]
    53e0:	f3 90                	pause
    53e2:	eb 9c                	jmp    5380 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0x40>
    53e4:	66 66 2e 0f 1f 84 00 	data16 cs nop WORD PTR [rax+rax*1+0x0]
    53eb:	00 00 00 00 
    53ef:	90                   	nop
    53f0:	0f 31                	rdtsc
    53f2:	48 c1 e2 20          	shl    rdx,0x20
    53f6:	48 09 d0             	or     rax,rdx
    53f9:	f0 41 ff 0b          	lock dec DWORD PTR [r11]
    53fd:	75 03                	jne    5402 <void (anonymous namespace)::throughput_consumer<atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> > >(unsigned int, atomic_queue::RetryDecorator<atomic_queue::AtomicQueue<unsigned int, 65536u, 0u, true, true, false, false> >*, long long*, std::atomic<unsigned int>*, unsigned long long*, atomic_queue::Barrier*)+0xc2>
    53ff:	49 89 00             	mov    QWORD PTR [r8],rax
    5402:	5b                   	pop    rbx
    5403:	4d 89 0a             	mov    QWORD PTR [r10],r9
    5406:	5d                   	pop    rbp
    5407:	c3                   	ret

In the above, index % size_ compiled into:

 5393:	0f b7 c0             	movzx  eax,ax

index % size_ got transformed into index & (size_ - 1). size_ - 1 is 65535, or 0xffff in hex.

What a lucky value of the 2nd argument of and instruction, the optimizing compiler probably thinks to itself, and transforms index & 0xffff further into even cheaper movzx eax, ax.

[max0x7ba]

The last one is about the branch prediction annotations missed within the try_ versions of push and pop. i think, the inspections for FULL/EMPTY queue could be annotated UNLIKELY.

try_push is ideal for when the queue may be full. When that's rather unlikely, push is the best choice.

try_pop is ideal for when the queue may be empty. When that's rather unlikely, pop is the best choice.

In the throughput benchmark, empty queue is unlikely, full queue is likely.

In the latency benchmark, the queue is either empty or has 1 element in it.

The ideal branch prediction hint in try_ versions depends on the particular usage with a particular workload.

This information isn't available inside the scope of try_ function, so that a branch prediction hint in there would have a positive effect on some use cases and negative effect on others.

This information is much more likely to be available at higher-level scopes, and this is where a branch prediction hint can have its maximum strictly-positive impact. In other words, using a branch prediction hint on the return value of try_push or try_pop is the best; whereas placing a wrong prediction hint in these functions prevents/overrides a more informed correct branch prediction hint at a higher level from propagating down into callees and achieving its full positive impact.

Not placing a branch prediction inside try_push or try_pop is avoiding a premature optimization which can have negative impact in 50% of use-cases. No branch prediction in there leaves the door open for branch hint information to propagate from higher levels, and that, in fact, is the best possible optimization at try_push or try_pop level.

That's the logic between the lines in there.

If you think someone took an effort to place specific branch prediction hints everywhere, but somehow overlooked here, think twice -- it may be you overlooking the bigger picture behind the trees. And in 20-40 years that's going to be you telling these same words to younger people, if software engineering is something you love doing, I promise.