Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Peredvizhnikov Engine: Lock-free game engine written in C++20

github.com

Post reply on HN
Print view View original

161–170 of 183 posts

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#161

Post by pramalhe »

schmichael wrote: post #23

Does 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.

Actually, 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

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#162

Post by adwn »

loeg wrote: post #120
foota wrote: post #80

Earlier quoted context omitted.

Aren't lock free data structures more about reducing the impact of contention than throughput under low contention?

Lock free is kind of an overloaded term that can mean a variety of things depending on what the user is thinking. Usually the goal is being able to make forward progress even if one thread is context switched out by the OS scheduler, which might be called wait-free or non-blocking. Using mutexes (unless you can prevent OS scheduling, interrupts, etc) makes this property impossible to achieve. In general, MPSC queues…

> In general, MPSC queues are super fast and there's no real reason to prefer a locked queue.

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.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#163

Post by Voultapher »

As 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.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#164

Post by hoseja »

smallstepforman wrote: post #17

I 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 O…

The problem with vanilla std::deque is that the only acceptable implementation is in clang libc++. On MSVC it's basically an overcomplicated linked list.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#166

Post by friendzis »

munificent wrote: post #67
electroly wrote: post #60

Earlier quoted context omitted.

This is usually called "soft realtime" -- you want it to be fast but it's not wrong if it misses deadlines. It doesn't violate correctness of the system to miss a deadline. In a "hard realtime" system, it is a fatal error if the system misses a deadline because correctness is violated. I presume this difference is what OP is talking about. Games are never hard realtime; missing frame deadlines reduces user experience…

> Games are never hard realtime; missing frame deadlines reduces user experience but it doesn't break the game. 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.

If your program state tracking/management is so tightly coupled to renderer that missing a frame can desync, then you have much bigger architectural problems anyway.

Network latency is a thing and your state management subsystem absolutely has to be fault tolerant.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#167

Post by meheleventyone »

munificent wrote: post #67
electroly wrote: post #60

Earlier quoted context omitted.

This is usually called "soft realtime" -- you want it to be fast but it's not wrong if it misses deadlines. It doesn't violate correctness of the system to miss a deadline. In a "hard realtime" system, it is a fatal error if the system misses a deadline because correctness is violated. I presume this difference is what OP is talking about. Games are never hard realtime; missing frame deadlines reduces user experience…

> Games are never hard realtime; missing frame deadlines reduces user experience but it doesn't break the game. 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.

Since you can’t control latency of individual packets let alone that the hardware timing is identical this isn’t practical as a requirement.

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.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#168

Post by EliRivers »

gamacodre wrote: post #137
EliRivers wrote: post #96

Earlier quoted context omitted.

I am sure I have memories of how hard it was to support a range of hardware when I had to write specifically for each piece. When I had to write separately for a Soundblaster card and an Adlib and a Disney SoundSource and a Roland and a Gravis. 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…

Yeah, and Tandy graphics were different from EGA or VGA, just enough that you needed to write different display code for them. And you had to get the user to tell you which ports/IRQ numbers half of their hardware was configured at. We have way better hardware abstractions in the OS today, which I would agree makes modern development easier overall.

Oh yes, that brings it all back. Having the user tell me the IRQ and also DMAs and... I'm sure there was more. Sometimes the user would end up having to open up the PC and reseat physical jumpers on hardware cards to have the cards use values that were both offered by the software and not clashing with anything else.

Different world. So much easier now.

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#169

Post by rhelz »

squeaky-clean wrote: post #134
rhelz wrote: post #42

Earlier quoted context omitted.

Say you are in the middle of building a house. The foundation has been built and they are framing it up. Is it a house?

No, because otherwise you wouldn't say "the foundation has been built". You'd say the "the house has been built". Does a house need a foundation? Yes. Is the foundation the same as the house? No.

But you do say, “I am building a house.”

Re: Peredvizhnikov Engine: Lock-free game engine written in C++20

#170

Post by rhelz »

xwdv wrote: post #61
rhelz wrote: post #42

Earlier quoted context omitted.

Say you are in the middle of building a house. The foundation has been built and they are framing it up. Is it a house?

No, and if you accept it as a house then this is a recipe for developing a bad habit of leaving a trail of half finished projects in your wake.

Can you point at a house and say “I designed this house?” If the house didn’t have some kind of existence while you were even designing it, how could it be that you designed that, particular house?
Post reply on HN