11 ms·
Peredvizhnikov Engine: Lock-free game engine written in C++20
- gabereiser 3y ago[flagged]
- rychco 3y agoForgive me if it’s common knowledge, but what’s wrong with SDL2 in this case? Broadly speaking, I feel as though there is largely positive sentiment around the SDL project, no?
- gabereiser 3y agoI have nothing against the SDL project. I have everything against the DirectMedia style api of 1997. I get that people are actively developing with it and that roadmap towards 3.0 is getting close but my experience is it’s designed for legacy games, legacy rendering styles, legacy ABI’s. No one is shipping games for Dreamcast or PS2. 2/3rds of the library is dead code when working with Vulkan.
- OnionBlender 3y agoWhat is a better alternative?
- gabereiser 3y agoFor what? Working with Vulkan? Or a windowing library? Personally I use a mix of glfw and native windowing on mobile, which is surprisingly simple for a gfx context window and this gets me to triangle. SDL2 is about the same amount of boilerplate code only in SDL_Thing form. Now, if I was writing a game that needed to be shipped on everything possible and I can’t afford Unity or Unreal, SDL is a viable choice. MonoGame, mine, and others have used it, it’s battle tested. I just can’t look at SDL code anymore and say “this is the cleanest api” for anything outside of C99.
- nickelpro 3y agoAs with most SDL usage, it merely provides a rendering context and an input abstraction. That's almost nothing, its boilerplate you don't want to write. Which particular lib you grab that boilerplate from, SDL, GLFW, fucking GLEW, whatever, it doesn't matter. SDL is a widely accepted library for doing so and it's fine. If you want more complete input handling you'll be using the platform APIs directly.
- gabereiser 3y agoAnd surfaces, and audio… yeah I know. For tinkering and learning, sure. If you’re going to build an engine, pull that boilerplate code within.
- nickelpro 3y agoMany, arguably most, custom game engines never internalize that boilerplate. Most engine codebases are much smaller and more specialized than the AAA players, and gain nothing from splitting their build into platform-specific layers when they could just link SDL.
- rstat1 3y agoTIL Unreal 5 based games were "legacy"
- gabereiser 3y agoThey really only use it for Linux window and audio because there’s so many ways to skin a disto.
- rstat1 3y agoThey definitely use it for more than that, because I'm sure I've seen it ship with Windows games as well. Also there's exactly 2 ways to get a window on Linux, and those 2 ways are common to pretty much every modern distro. Same as audio.
- datameta 3y agoThe painting used is Barge Haulers on the Volga - https://en.m.wikipedia.org/wiki/Barge_Haulers_on_the_Volga https://en.m.wikipedia.org/wiki/Barge_Haulers_on_the_Volga 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?
- mhd 3y agoNever mind that a lot of Volga boats were very single-threaded. https://www.amusingplanet.com/2021/12/belyana-russias-giant-wooden-boats.html https://www.amusingplanet.com/2021/12/belyana-russias-giant-...
- 3seashells 3y agoYou can even see the steam ships that replaced the slave in the background.
- beatcracker 3y agoThey were not the slaves, but unionized workers: https://en.m.wikipedia.org/wiki/Burlak https://en.m.wikipedia.org/wiki/Burlak
- mananaysiempre 3y agoAFAIU an артель artelʼ usually did not engage in collective bargaining as such, so calling it a union is not really accurate; you might compare it to a guild but I think there’s no implicaton of a monopoly on a particular trade either. The most accurate description I can think of is perhaps a cooperative combined with a mutual insurance fund.
- beatcracker 3y agoAgree, I might've stretched It a bit. Your descriptions is more accurate.
- hesdeadjim 3y agoIt’s quite the stretch to call this a game engine, rather than a tech demo for clever locking strategies.
- DennisP 3y agoMaybe it's not done yet.
- forrestthewoods 3y agoThis. There’s no demonstration of any game made with this “game engine”. The benchmarks are some matrix multiplication and unimpressive message passing. 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.
- erwincoumans 3y agoIndeed. The project has no renderer or game physics code it seems? If so, it is too premature to be a game engine.
- rhelz 3y agoSay you are in the middle of building a house. The foundation has been built and they are framing it up. Is it a house?
- mdaniel 3y agoAll those people who complain about project names squatting on existing words have finally been heard :-D
- whynotmaybe 3y ago[flagged]
- deleted 3y ago[deleted]
- tjrgergw 3y ago> Unless the name is explained somewhere, I'm convinced it's complicated on purpose. Tell me you only speak English without telling me you only speak English.
- loeg 3y agoFrom the grammar, I would not assume GP is a native english speaker, much less monolingual.
- bigbillheck 3y agoIt seemed perfectly cromulent to me.
- drt5b7j 3y agoI would love to hear what exactly about the grammar doesn't sound native.
- bee_rider 3y agoThe only thing that seems strange is “such commands as” used to describe a single command. I think a more common way of writing it would be “a command like.” But, I don’t think it is at all definitive, it could just be a native English speaker who went with a slightly odd phrasing.
- hot_gril 3y agoI don't have time to read through the impl, but the readme makes it sound like a classic distributed system between game threads, where patterns like retry-backoff will be common.
- CuriousCosmic 3y agoThe paper goes into more detail without forcing you to go into the impl but it does seem to be a decent bit more advanced than that. https://github.com/eduard-permyakov/peredvizhnikov-engine/blob/master/docs/lockfree.pdf https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
- jeffreygoesto 3y agoLooks BEAMish to me? https://youtu.be/bo5WL5IQAd0?feature=shared https://youtu.be/bo5WL5IQAd0?feature=shared
- xwdv 3y agoAny games built with this
- minitoar 3y agoYes, it’s called C++20 Game Engine Developer.
- smallstepforman 3y agoI have an Actor framework which uses a vanilla std::deque for method pointers, and to add messages to the queue, the locking technique is a Benaphore (the original Futex, which uses an atomic and a locking primitive, with the twist that my locking primitive is a combo of spinlock/mutex based on retry count). Nothing special. Benchmarks show that very rarely does the message push function block, and the chance of an OS context switch is also very low, so even though occasionally we get a locked thread swapping out, it is so infrequent that it doesn't justify the lock-free algorithm cost. 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.
- Y_Y 3y agoWith a post like this, however interesting, you really should link the code. Not only will it prove your claim, but others like me will find the idea intriguing and immediately want to see how it's done.
- smallstepforman 3y agohttps://github.com/smallstepforman/Medo/tree/main/Actor https://github.com/smallstepforman/Medo/tree/main/Actor
- enqk 3y agohow do you deal with msvc's `std::deque`? (or maybe you're not using literal std::dequeue)
- OnionBlender 3y agoWhat is special about msvc's `std::deque`?
- 3y ago
- schmichael 3y agoDoes anyone have experience debugging/profiling highly contended critical sections of STM vs a more traditional mutex implementation? At the end of the day something has to mediate concurrent access to shared memory, there’s no free lunches, and mutexes are so well optimized, profiled, and understood. I’m unclear if the same applies to STM where a transaction may need to be retried an unbounded(?!) number of times.
- gabereiser 3y agoYes. The mediator in this case is the scheduler. The one that actually calls the asynchronous block. Potentially retrying it if it fails. In the OP’s code, there’s atomic blocks, sequential execution of blocks, stateful blocks, etc for ensuring singular access at a time. 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.
- schmichael 3y agoThanks! 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?
- gabereiser 3y agohttps://en.cppreference.com/w/cpp/language/coroutines https://en.cppreference.com/w/cpp/language/coroutines
- pramalhe 3y agoActually, for starvation-free STMs, transactions will retried a _bounded_ number of times. One example is 2PLSF, but there are several others https://zenodo.org/record/7886718 https://zenodo.org/record/7886718
- djmips 3y agoI didn't see mention of how hard it is to debug such an engine.
- edfletcher_t137 3y ago> At the moment, the only supported platform is Linux. 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.
- StevenXC 3y agoI'd love to see the Steam Deck "console" change this status quo.
- NavinF 3y agowin32 is the stable ABI for SteamOS, same as any other Linux distro
- tmccrary55 3y agoMost of the SteamDeck games are just running windows games through photon, wine and other compatibility layers. While that works amazingly well, I tend to prefer games with native Linux and SteamOS builds, even though they're rare.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- WhereIsTheTruth 3y agobullshit, consoles/mobile are bigger markets than PC/Windows PC is just less than 1/3 of the whole picture https://www.data.ai/en/insights/mobile-gaming/2022-gaming-spotlight-report/ https://www.data.ai/en/insights/mobile-gaming/2022-gaming-sp...
- 5e92cb50239222b 3y agoA bit more than that since Xbox runs Windows too.
- throwawayvatnik 3y ago[flagged]
- dang 3y agoBreaking the site guidelines like this will eventually get your main account banned as well, so please don't. HN is no place for nationalistic flamewar, including when there's an actual war going on—in fact, especially not then: "Comments should get more thoughtful and substantive, not less, as a topic gets more divisive." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- devit 3y agoIt says that it's actor-based, and sending messages to an actor is equivalent to running the actor function under a mutex, and thus reduces parallelism (in other words, you have N threads sending messages, but only 1 thread running the actor code, so it's just as serialized as a mutex), so while it may technically be "fully lock-free", using actors means that there is no parallelization improvement.
- deleted 3y ago[deleted]
- onjectic 3y agoYour right that there is no parallelization improvement, but it does not reduce parallelism either, its just a different(imo easier) way to think about concurrency. 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.
- lelandbatey 3y agoNot quite; with mutex based actors an interruption of the actor thread would cause that mutex (and thus that actor code) to remain locked until the original thread resumes. No additional parallelism will allow that actor code to be "restarted" or "resumed" as the mutex owned by the interrupted thread is locked. 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/blob/master/docs/lockfree.pdf 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.
- jstimpfle 3y ago> sending messages to an actor is equivalent to running the actor function under a mutex 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.
- deleted 3y ago[deleted]
- pshirshov 3y agoActors is one of the worst programming models possible. It's hard to observe actor-based systems and debug them. The protocol complexity (and complete protocol informality) usually brings much more trouble than any kind of locking/synchronization.
- deleted 3y ago[deleted]
- lll-o-lll 3y agoI’ve had good success with actor based models. When you say “protocol complexity”, I don’t understand what you mean. 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.
- hot_gril 3y agoFor game dev or in general? I hate using actors for general backend stuff, but for game dev maybe it makes more sense.
- legosexmagic 3y agoActors tend to lead to bloated incomprehensible code. Even when you do want game objects to look like independent message passing actors. Faking it is always easier. Actors are self defeating because they turn everything into a distributed system.
- hot_gril 3y agoThat's what I was thinking. I'm trying not to write Actors off because I'm not an expert on game dev and can imagine the possibility of an unusually large-scaled game. But yeah, if you're writing a typical game, I imagine you're best off doing it the typical way that's been optimized for.
- hankman86 3y agoIt’s licensed under GPL3, where the developer suggests individually negotiating a license for commercial projects. I am not sure this is a good approach given the early stage of this project. Video game development is already commercially and technically risky enough. 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.
- gjvc 3y agoquoting https://github.com/eduard-permyakov/peredvizhnikov-engine https://github.com/eduard-permyakov/peredvizhnikov-engine 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.
- deleted 3y ago[deleted]
- pramalhe 3y ago[dead]
- charcircuit 3y ago>Lock-free export std::mutex iolock{}; export std::mutex errlock{}; SDL_PollEvent Not yet at least.
- malkia 3y agoWhere is the game demo? Also to be considered gaming engine nowadays, you need actual tools, exporters (Maya, 3DSMax, etc.) + who knows what else (collaboration tooling, metrics, alerts)
- adamrezich 3y agoI disagree—"game engine" does not necessarily mean "thing I can replace Unity or Unreal with".
- xwdv 3y agoNot even asking for that much. Any game demo would be appreciated.
- anentropic 3y agoIs there any "game engine" here though currently? Seems like 'just' a lock-free work scheduler
- snaury 3y agoThe lockfree scheduler certainly looks interesting (especially linearizability of event broadcasts), but I was surprised to see benchmark results in the paper with a peak of 43500 messages/s for 12 pairs of actors (and 12 cores?), with a graph showing ~5000 messages/s for a single core, which is surprisingly low for that kind of benchmark. Unfortunately the engine requires linux and more importantly x86 (due to asm intructions) so I wasn't able to replicate them yet, but I would expect at least ~1 million requests/s per a pair of actors (e.g. with Erlang), otherwise the overhead is prohibilitely low. 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.
- Voultapher 3y agoAs cool as lock free sounds, in my opinion any amount of non-trivial atomics usage should be accompanied by a formal, ideally machine checked, proof. Non sequential consistent atomic ordering usage is so difficult to get right. I've repeatedly seen code that gets it wrong, and the bugs that creates are the worst.
- kovacs_x 3y agoI'm 99% sure, the author has never done any completed / published non trivial game... .. because doing lock-free programming is least of problems when creating games.
- pjmlp 3y agoI wonder why it is using clang modules instead of proper C++20 modules. Except for header units, the support is already mostly there.
- erichocean 3y agoWhat formal verification, if any, has been done on this (e.g. with TLA+ or similar)? Lock-free/wait-free designs are notoriously bug prone.