Peredvizhnikov Engine: Lock-free game engine written in C++20
github.com
github.com
In a nutshell, non lock free queues are much faster than lock free queues, however you must be prepared to accept the very infrequent longer delay due to a context switch (where the lock is not available to anyone). My benchmarks show that the price is acceptable since so much more performance is available with non lock free queues. 10 million messages per second per work thread can be queued on modern hardware.
Well, except to people who have a hard requirement that there never be this unpredictable, infrequent longer delay you mention.
*: ignoring deliberately esoteric cases, like Doom on a hard real-time system.
(This is not to say the OP has any such issues in its context.)
Depends how high your standards are! One of the things that makes playing old games on the original hardware really satisfying is how consistent they are.
Today, a PC game has to work on a large range of hardware that has come out over the past 5+ years. And there are GPU features that are only available on certain cards, like hardware ray tracing and things like DLSS and FSR for upscaling.
And the game engines are incredibly more complex today to handle modern expectations, with dynamic lighting and shadows, huge maps, etc.
It doesn’t matter what your standards are. Hard realtime just isn’t realistic or even possible any more, except maybe in a game that would be considered truly primitive by today’s standards.
And that was just the sound cards. Writing for different hardware became so much easier when OpenGl and DirectX came into being. Suddenly I just had to write to these APIs.
I think I'm disagreeing with you. Supporting multiple hardware configuration way back when was so much harder than doing it today.
/me shivers at the recollection
We have way better hardware abstractions in the OS today, which I would agree makes modern development easier overall.
Different world. So much easier now.
It depends on whether the game is multi-player and, if so, how it keeps the different players in sync with each other.
Games that rely on deterministic gameplay can desync (two players don't see the same world state) and abort if one player's simulation drops a frame while the other doesn't.
You don't control network latency spikes. Latency tolerance is a hard requirement, or you will have constant problems and likely be unplayable. Or custom networking and hardware stacks, which is deep into esoteric territory.
I don't know how you'd describe a game spontaneously aborting not a "fatal fault". Yes, it's not turning off someone's pacemaker, but within the scope of what a game is able to do, kicking the player back to the matchmaking screen in the middle of a game is about as fatal as it gets.
EDIT: Well, there is one situation where you might get delays like that: if the computer is so woefully inadequate to run the game that it consistently misses frame deadlines by several hundred milliseconds. Of course, in such a situation a different concurrent algorithm wouldn't have solved anything anyway.
Right. This is why lockstep deterministic (LSD) games are bound to the SLOWEST player's machine.
No LSD game in existence crashes the game if one player's machine falls behind. Instead you either pause the simulation for all players until they catch up or you slow down time itself.
Source: shipped RTS games that were lockstep deterministic.
Network latency is a thing and your state management subsystem absolutely has to be fault tolerant.
Deterministic gameplay means after the same x frames with the same external inputs you will end up with the same state y on different hardware. Therefore we only need to make sure the clients stay within a reasonable margin. We can do this by waiting for all players inputs so moving at the slowest speed possible which is the lock-step method. Or we can change our measured frame time so each tick (which still ticks the same amount of sim time) is seen as faster or slower. That way we can track the other frames that other clients have completed from the input they send and slow or speed ourselves up to maintain a decent margin. This is the scheme used in rollback networking as the naïve implementation where this isn’t the case forces all rollbacks onto the faster machine.
So you're not wrong. VR games are much more susceptible to dropped frames causing problems. But it both happens and is hidden remarkably well.
This is usually not serious inflicted and the presentation threads will be higher priority than the simulation in order to minimize visual 'jank'
Lockfree game code ain't fixing jank from the OS.
Latency is like a chain. Every link matters.
A game engine programmer can't do a thing about the OS, but can still keep latency bounded in the code under their control.
There's one significant advantage that a locked vector or deque has over MPSC/MPMC queues: the consumers can dequeue all messages in a single operation by locking the vector, swapping it with an empty vector (typically, that's just 3 words), and locking it again. That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP. Similarly, if the vector is empty, a producer can push any number of messages in a single, constant-time operation.
> That's such a simple operation that it will typically be as fast or even faster than a single pop-one-message operation in an MPSC/MPMP.
Not if the lock is blocked because one of the writers context switched out! The typical case is good, but the worst case is pretty bad.
Under a wait free algorithm, we promise that every individual thread eventually makes progress.
Suppose I have one really dumb thread which just goes to sleep for 10 seconds in a loop, as well as other threads which do some actual work. If we're a lock free algorithm, it is OK if the 10-second-sleep thread is always chosen to make progress, its "progress" consists of sleeping for 10 seconds, too bad, try again next time.
With a wait free algorithm, the threads which actually do useful work will also make at least some progress, eventually despite the 10 second sleeper.
Generally we can't say for sure that we e.g. "reduce impact of contention" only that we definitely make some forward progress, on at least one thread eventually.
Could you tell me if your 10 million figure includes batching or are they a loop that tries to enqueue as many items as possible?
The "Benaphore" was a pretty old idea, but the Futex isn't just "Oh it's a Benaphore but Linux" the essential trick is that you don't actually need a kernel object - your "locking primitive" at all, and that idea is where this goes from "Yeah, everybody knows that" to OK, our OS should add this feature ASAP.
Instead of an OS synchronisation object which is used to handle conflicts, with the futex design the OS carries a list of address -> thread mappings. If a thread T is asleep on a futex at address X, the address X goes in the list pointing to thread T. When the OS is asked to wake the X futex, it walks the list and wakes T.
The give away is the limits. For something like Benaphores you're constrained, these are a costly OS wide resource, I think BeOS only allowed 65536 per machine or something. But a Futex is just memory, so there's no reason to have any limit at all.
I think what you're observing, i.e. that in many cases just use a lock and don't worry about it (or your variation) is true. But there are certain applications/situations where you can do better. Having a consumer pull out everything from the queue with one locking operation and being careful with how you signal the consumer from the producer(s), assuming there's a signal, can also make the queue more efficient/have higher throughput (e.g. you shouldn't signal for every item you put in the queue, only when it becomes non-empty).
The most expensive part of any mutex/futex is not locking, it's waking other threads up when the lock is contended. I'm actually surprised you only get 10 million messages per second, is that for a contended or an uncontended case? I would expect more, but it probably depends on the hardware a lot, these numbers are hard to compare.
My actor framework currently uses a lockfree intrusive mailbox [1]_, which consists of exactly two atomic exchange operations, so pushing a node is probably cheaper than with a mutex. But the nicest part about it is how I found a way to make it "edge triggered". A currently unowned (empty) queue is locked by the first push (almost for free, compared to a classic intrusive mpsc queue [2]_ the second part of push uses an exchange instead of a store), which may start dequeueing nodes or schedule it to an executor. The mailbox will stay locked until it is drained completely, after which it is guaranteed that a concurrent (or some future) push will lock it. This enables very efficient wakeups (or even eliding them completely when performing symmetric transfer between actors).
I actually get ~10 million requests/s in a single-threaded uncontended case (that's at least one allocation per request and two actor context switches: a push into the target mailbox, and a push into the requester mailbox on the way back, plus a couple of steady_clock::now() calls when measuring latency of each request and checking for soft preemption during context switches). Even when heavily contended (thousands of actors call the same actor from multiple threads) I still get ~3 million requests/s. These numbers may vary depending on hardware though, so like I said it's hard to compare.
In conclusion it very much depends on how lockfree queues are actually used, and how they are implemented, they can be faster and more scalable than a mutex (mutex is a lockfree data structure underneath anyway).
I'd agree with you in that mutexes are better when protecting complex logic or data structures however, because using lockfree interactions to make it "scalable" often makes the base performance so low, that you'd maybe need thousands of cores to justify the resulting overhead.
.. [1] https://github.com/snaury/coroactors/blob/a599cc061d754eefea... .. [2] https://www.1024cores.net/home/lock-free-algorithms/queues/i...
The engine also focuses on message passing, but from experience it's very difficult to work with (state machines are hard, especially when working with multiple downstream actors), and at the core actors are more about isolating state without locks than message passing. Swift actors did it right in my opinion, method calls instead of messages are not only easier to reason about, they give additional hints to the runtime when context may switch without involving a scheduler at all (any shared state is slow and inhibits scalability).
I actually wrote a header-only library recently (search for "coroactors" if you're interested) that implements something similar to Swift actors with C++20 coroutines, and I thought ~10 million requests/s (when uncontended) or ~1-3 million/s (when contended and depending on a scheduler) was a way too high of an overhead, especially when compared to normal method calls with shared state protected with mutexes. Coroutines tend to go viral (with more and more functions becoming "async" coroutines), and any non-trivial code base would have a lot of coroutine calls (or messages passed), and that overhead needs to be as low as possible, otherwise you'd spend more time task switching than doing useful work.
Because it is easier for me to think about it is easier for me to see where things will contend the same resource and actually helps me improve potential parallelism. Once you recognize a particular opportunity where SMP can speed things up, you can stray a way from the actor-model a bit and have multiple threads receiving on your message queue, or if that isn't possible, you can just add more actors and split up the data better.
This implementation relies heavily on restartable functions in order to allow another parallel thread to pick up and continue the work of an already in progress but otherwise interrupted actor. See page three of the (excellent) design document: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
Thus while it might not strictly be "more parallel" (same number of actors), it does seem to be able to make better use of more parallelism for completing the same set of work.
Where does it say that? In my understanding actor model means message-passing with asynchronous execution. So quite the contrary, actor model allows N threads executing in parallel given N actors.
It's easy to scatter the computations, but they never go on to explain how to gather them back up.
You're going to render one frame to the screen. Did multiple actors have a write-handle into the frame buffer? What about collisions, does each entity collide with itself, without sharing position information with other actors?
The meat here is scheduler.cpp. It uses std::coroutines.
This is like async/await in other languages. The scheduler has a queue of work(coroutines) and a pool of threads(N>0) to execute those on.
In this case, messages are passed between work that contains the data. No locks are required at the expense of memory footprint.
So the scheduler serializes execution of critical sections?
> In this case, messages are passed between work that contains the data. No locks are required at the expense of memory footprint.
Are messages copied or moved? If moved is there compile time checking for ownership or runtime debugging tools?
https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
export std::mutex iolock{};
export std::mutex errlock{};
SDL_PollEvent
Except for header units, the support is already mostly there.
Can someone please expand on the significance of this achievement to someone used to shooting their foot off in C++ in a predominantly single threaded manner?
https://www.amusingplanet.com/2021/12/belyana-russias-giant-...
There might be some cool data container ideas or primitives. Those could have useful applications. But it isn’t really a “game engine”. Nor does it seem like an interesting way to build one.
Is it a house?
Does a house need a foundation? Yes. Is the foundation the same as the house? No.
They're building a game engine, but it is not an actual engine yet. Just one core component.
If what you were working on--for the entire time you were working on it--was a completely different thing from a house or from a game engine, how could you clame to have built a house or a game engine? Putatively, what you were working on what an entirely different thing from the result.
Regardless of your feelings on the status quo, there is one thing you must do when building a game engine if you want it to succeed: support Windows.
While that works amazingly well, I tend to prefer games with native Linux and SteamOS builds, even though they're rare.
PC is just less than 1/3 of the whole picture
https://www.data.ai/en/insights/mobile-gaming/2022-gaming-sp...
PS5: 1.2m
Switch: 950k
Xbox: 370k
Xbox accounts for just 17% of total console sales in July
Both Switch and PS5 are FreeBSD based
If we count the whole period of the current gen of each vendors, it only accounts for 13%, it's not big
I'd call that a pretty significant piece.
"partially Unix-like via certain components which are based on FreeBSD and Android"
https://en.wikipedia.org/wiki/Nintendo_Switch_system_softwar...
"it is based on a proprietary microkernel"
"....Despite popular misconceptions to the contrary, Horizon (the Switch's OS) is not largely derived from FreeBSD code, nor from Android..."
A Game Engine targets various platforms
A "video-game" is not something exclusive to desktop/laptop windows market
Toy game engines like this are in the majority of cases used on desktop.
(Also, the consoles don't run Linux)
XBOX runs a variant of Windows.
PS3/4/5 OSes have all been based on FreeBSD.
Apparently Nintendo Switch runs a proprietary kernel, which is interesting (https://en.wikipedia.org/wiki/Nintendo_Switch_system_softwar...).
Sure they're both "games" but I don't know that they're competing for the same set of users - either people play one or the other, or the people that do crossover in both markets are probably playing PC/console games at home and mobile games on the bus or train.
I cannot see game developers lining up to even try out this unproven technology when they have no sense of what the eventual fees will be.
The source code of Peredvizhnikov Engine is freely available under the GPLv3 license. However, I may grant permission to use parts or all of the code under a different license on a case-by-case basis. Please inquire by e-mail.
Observation requires good logging, but this isn’t out of line for any complex system. Debugging (as in actual breakpoints in an IDE or post-mortem analysis) can be facilitated with stack tracking (this same problem occurs with async await patterns and is solved in a similar way).
The advantages and disadvantages exist, but I think it’s an extremely effective programming model for many use cases. Formal state-machine programming, that’s the worst model, unless you need it.
Actors are self defeating because they turn everything into a distributed system.
.. because doing lock-free programming is least of problems when creating games.