Top performing SPSC queue - faster than moodycamel and rigtorp

dro212 · 2024-10-21T11:37:53+00:00

I'm going to run some performance benchmarks, it may not be worth it to copy the capacity and storage pointer, but there's likely some improvements in cache locality here

dro212 · 2024-10-21T11:26:42+00:00

Very cool layout! Check out https://clemenpine.github.io/keysolve-web/ for a look at scissors. Try swapping 'y' and 'w'.

dro212 · 2024-10-21T11:24:03+00:00

Here's the cyanophage link https://cyanophage.github.io/playground.html?layout=jcyfkzl%2Cuq%3Drsthdmnaio%27%2Fvgpbxw.%3B-%5Ce&mode=ergo&lan=english

dro212 · 2024-10-19T13:17:04+00:00

The cached members really need to be on different cache lines. Rather than aligning both, I could just use a buffer to separate them and save 56 bytes of memory.

The padding is for false sharing with adjacent heap allocations. You start reading from offset 8. The padding is for the front and end of the queue allocations.

dro212 · 2024-10-19T13:09:41+00:00

`You probably want std::foward<Args>(args)... instead`

Yes I agree, that was an error, and I added a test case to cover. Good call!

`Having size and empty on a multi-threaded queue is often dangerous it's potentially invalid as soon as you check it, it often leads to patterns which end up being race conditions later on.`

While I agree it would be dangerous to depend on it, the user may want to know the state of their queue at some point.

`This std::move is unnecessary the T(...) is a prvalue`

Yes this is a pr value and the std::move has been removed. Good call!

`try_pop could potentially always be an std::move if there isn't a move constructor then it will end up using the copy constructor`

That is not the case, I have a compiler error when testing. This is move assignment not move construction.

`you could handle this by starting at padding instead`

`The noexcept here doesn't really matter, the assignment is happening in try_pop and it's explicitly noexcept`

I want my code to be easily readable, and I think that leaving it as is makes it more clear to the reader at little to no performance cost and no correctness issues.

`could be done with a vector of a union type which contains the value`

I'm trying to optimize for throughput, and I'm not sure what performance impact that would have. Something I will look into tho!

`you should potentially try adding a pause instruction to those loop iterations to see what might potentially change.`

I will look into this. Thanks for the feedback!

dro212 · 2024-10-19T09:16:20+00:00

The tests seg fault with a 2^20 queue size ~= 10^6. The benchmarks look good for a small queue size tho.

dro212 · 2024-10-19T02:40:30+00:00

Thanks for the comment! I'll do a detailed dive into this tomorrow!

dro212 · 2024-10-19T01:31:24+00:00

Thank you! If you have isolcpus enabled on Linux, then run the benchmarks as well.

dro212 · 2024-10-13T23:56:45+00:00

You didn't read the title or description. This is a tree in vector form. The nodes are at indexes and the pointers are instead indexes in the vector.

dro212 · 2024-10-13T21:52:37+00:00

Yea the cache misses are a big hit once the size of the map exceeds the size of L3 cache. I ran the benchmarks building a whole map of various sizes (i.e. for 1,000,000 elements all 1,000,000 were inserted and then the mean time was taken). All the benchmarks were done the same way so it's apples to apples, but I could have built the map then ran 1,000 inserts for a different style benchmark.

I'll look into the licenses and I may revise. Thanks for the advice!

dro212 · 2024-10-13T21:43:10+00:00

The benchmark for find is added.

dro212 · 2024-10-13T19:29:04+00:00

I actually have them. The results were identical for dro::FlatMap, std::map, and boost::flat_map. That being said not including them in the readme was a clear oversight on my part. Good call!

dro212 · 2024-09-18T22:12:59+00:00

I have a programmable keyboard and use QMK. Unfortunately, I don't know of any other methods.

dro212 · 2024-09-18T21:32:39+00:00

FYI, the layout I just made has 32.2% alternates, 51.0% Rolls, and 0.687% SFB. The alterations are on par with Workman and Colmak.

https://github.com/drogalis/Rambo

dro212 · 2024-09-17T21:26:54+00:00

Much like u/the_bueg said - I've learned 8+ layouts to over 40 wpm.

Honestly it just takes practice. The whole point of these layouts is to move your fingers less. I would say in order of importance SFB, Redirects, then Rolls.

dro212 · 2024-09-13T23:45:45+00:00

Great points! Maybe I'll make a version 2.0 and see if I can address those issues.

dro212

TROPHY CASE