Fixing stutters in Papers Please on Linux • Hacker News Board

Re: Fixing stutters in Papers Please on Linux

#181

Post by kennylevinsen » Mon, Jan 03, 2022, 8:09 PM UTC

infogulch wrote: post #178

kennylevinsen wrote: post #171

Earlier quoted context omitted.

This argument does not make sense - the kernel already needs to track per-process file descriptors. It just looks for the first hole instead of giving the "next" value. Go's random map iteration does not apply here. Not only is this not an iterable map, the kernel has no problem providing this insertion guarantee so adding additional costly randomization has no benefit and just burns additional cycles. Go would also…

The correct term for this is not "developers ignoring documentation" it's "ossification" or Hyrum's Law: With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody. I guess that we got this "lowest available" rule because that's what the first implementation happened to do (it's the obvious thing to do if yo…

As mentioned elsewhere, the file descriptor table is an array and a bitmask - finding the next fd is a matter of finding the first unset bit, which is extremely efficient. And that's before we ignore that the file descriptor table is read-heavy, not write-heavy.

Should you want to have per-process file descriptor tables, you can do just that: Just create a process without CLONE_FILES. You can still maintain other thread-like behaviors if you want. I doubt you'll ever sit with a profile that shows fd allocation as main culprit however.

> If the spec says iteration order is not guaranteed, but in practice people can rely on it being the same in some specific situation ... This actually happened.

If Hyrum's law held, the API would already be "ossified" at this point.

Instead, the Go developers decided to make a statement: "The language spec rather than implementation is authoritative". They broke this misuse permanently by making the API actively hostile, not by making it "match the spec" as it already did.

While one could interpret the current implementation as "anti-ossification", I interpret the action as anti-Hyrum's Law by choosing to break existing users in the name of the contract.

Re: Fixing stutters in Papers Please on Linux

#182

Post by cryptonector » Mon, Jan 03, 2022, 8:36 PM UTC

loeg wrote: post #81

CyberRabbi wrote: post #77

Earlier quoted context omitted.

> I expect it to be fast unless documented otherwise. Logically you should expect it to block indefinitely unless documented otherwise. The exception would be completing within a time bound, the rule is blocking indefinitely.

> Logically you should expect it to block indefinitely Frankly, that’s completely insane. It should block if and only if there is actual io in flight which could produce a failure return that an application needs. Syscalls should be fast unless there is a very good reason not to be.

u/CyberRabbi is absolutely correct. It's true that for _some_ kinds of devices you could expect fast close(2) IF the device documents that. But as you can see, implementing this can be hard even for devices where you'd think close(2) has to be fast. Even a tmpfs might have trouble making close(2) fast due to concurrency issues.

The correct thing to do when you don't care about the result of close(2) is to call it in a worker thread. Ideally there would be async system calls for everything including closing open resources. Ideally there would be only async system calls except for a "wait for next event on this(these) handle(s)" system call.

Re: Fixing stutters in Papers Please on Linux

#183

Post by Dylan16807 » Mon, Jan 03, 2022, 10:24 PM UTC

CyberRabbi wrote: post #163

Dylan16807 wrote: post #143

Earlier quoted context omitted.

> Linux already operates by this principle. We are examining a situation where best effort was not good enough to hide poor application design. Linux has this principle as a goal, but it's probably not checked often. I would say this code fails the principle, independent of particular application problems.

> I would say this code fails the principle, independent of particular application problems. For every system call you determine satisfies that principle, I could come up with a application level algorithm that is broken because of it. The principle is aspirational, Linux does a best effort as all Unix systems do not because Linux is buggy but because it can never be 100% given the spec. The core issue here was not c…

They're both problems.

This slowness is approaching the point where even checking for joysticks on a dedicated thread would start having delay problems. And spawning a thread per file would be ridiculous and would get even more scorn if it was slow, "why are you spawning so many threads, of course that's not efficient".

Re: Fixing stutters in Papers Please on Linux

#184

Post by CyberRabbi » Mon, Jan 03, 2022, 11:03 PM UTC

Dylan16807 wrote: post #183

CyberRabbi wrote: post #163

Earlier quoted context omitted.

> I would say this code fails the principle, independent of particular application problems. For every system call you determine satisfies that principle, I could come up with a application level algorithm that is broken because of it. The principle is aspirational, Linux does a best effort as all Unix systems do not because Linux is buggy but because it can never be 100% given the spec. The core issue here was not c…

They're both problems. This slowness is approaching the point where even checking for joysticks on a dedicated thread would start having delay problems. And spawning a thread per file would be ridiculous and would get even more scorn if it was slow, "why are you spawning so many threads, of course that's not efficient".

> This slowness is approaching the point where even checking for joysticks on a dedicated thread would start having delay problems.

Poorly designed code will perform poorly. Well designed code won’t have delay problems.

> And spawning a thread per file would be ridiculous and would get even more scorn if it was slow,

Where in this entire thread was it suggested to spawn a thread per file? Threads are able to perform more than a single unit of work.

Re: Fixing stutters in Papers Please on Linux

#185

Post by CyberRabbi » Mon, Jan 03, 2022, 11:23 PM UTC

Dylan16807 wrote: post #153

dagmx wrote: post #152

Earlier quoted context omitted.

The only reason I mentioned that spawning threads/creating an async future is blocking is because you had mentioned that async would generate blocking assembly by my definition. And I agree, it would and therefore the definition is potentially meaningless. But pedantically it is blocking (but the functions called within it aren't to the current thread). In a colloquial every day sense, I'd not be this pedantic. but t…

> And I agree, it would and therefore the definition is potentially meaningless. But pedantically it is blocking (but the functions called within it aren't to the current thread). If I was going for maximally pedantic but still useful definitions, I'd say that a "[non-]blocking syscall" is a different concept from how you'd describe running functions synchronously or asynchronously. And to elaborate, something like:…

> I like the idea of saying a syscall is non-blocking if the spec says it returns instantly.

”instantly” is not a strong enough guarantee to call the syscall non-blocking. The caller needs to know exactly how the callee will perform in terms of run time. Most high level RTOSes spec this as saying the call will take a constant amount of time, allowing you to measure the call once during your testing and using that to estimate future runs.

Words like “fast” “slow” “instantly” are not useful in the domain of building real time systems at all. It’s about specifying a predictable run time.

Without providing any spec on the runtime of a system call, the only robust assumption is to assume it blocks indefinitely. When you assume a run time spec for a call where one is not spec’d (e.g. close()) that will inevitably result in unexpected behavior. Using calls that take unbounded time in a process that has strict time requirements is a recipe for failure. The domain of real-time interactive systems is not the same as the domain of batch processing.

> You ask about getpid() taking a second. I'd say that within the model of "put those RTOS issues aside", that doesn't happen and can't happen. Just like we usually exclude unplugging the computer from our execution model, so too we exclude "linux isn't RTOS" from our execution model. getpid can't get stuck waiting on any resources, and does only trivial computation, so it will return immediately.

This further shows that there is a fundamental misunderstanding in how POSIX systems operate. It’s very possible for getpid() to take longer than one second during normal operation because it’s stuck on a resource and POSIX allows for that on purpose. Every entry into a system call invokes a litany of bookkeeping tasks by the kernel before returning to user space, with the exception of VDSO calls like gettimeofday(). Please see exit_to_user_mode_loop() which gets called before every syscall returns to user space to see all the potentials sources of additional latency a call like getpid() may incur: https://github.com/torvalds/linux/blob/c9e6606c7fe92b50a02ce...

Again this is not by accident, this is on purpose. You’ll find a similar loop in all POSIX kernel system call entry/exit code.

Re: Fixing stutters in Papers Please on Linux

#186

Post by Dylan16807 » Mon, Jan 03, 2022, 11:37 PM UTC

CyberRabbi wrote: post #185

Dylan16807 wrote: post #153

Earlier quoted context omitted.

> And I agree, it would and therefore the definition is potentially meaningless. But pedantically it is blocking (but the functions called within it aren't to the current thread). If I was going for maximally pedantic but still useful definitions, I'd say that a "[non-]blocking syscall" is a different concept from how you'd describe running functions synchronously or asynchronously. And to elaborate, something like:…

> I like the idea of saying a syscall is non-blocking if the spec says it returns instantly. ”instantly” is not a strong enough guarantee to call the syscall non-blocking. The caller needs to know exactly how the callee will perform in terms of run time. Most high level RTOSes spec this as saying the call will take a constant amount of time, allowing you to measure the call once during your testing and using that to…

Pretend I said 10 microseconds everywhere I said instantly, then. Same argument, more or less.

Anything that could make getpid take too long is outside the scope of what linux could guarantee.

But inside that scope, it's still worthwhile to distinguish between "blocking" and "nonblocking with very specific exceptions"

> It’s very possible for getpid() to take longer than one second during normal operation being stuck on a resource

What resource? I did my best to look at the implementation, but the source code is complicated and scattered. I can't really process your link by itself. How often are these things causing delays?

"Being rescheduled" is already part of the model of any process, anyway. If a system call doesn't make it any more likely that my process stops compared to the baseline, then I think "nonblocking" is a reasonable term to want to use.

Re: Fixing stutters in Papers Please on Linux

#187

Post by throwaway81523 » Mon, Jan 03, 2022, 11:51 PM UTC

kennylevinsen wrote: post #168

throwaway81523 wrote: post #166

Earlier quoted context omitted.

You should use io_uring to open and close files asynchronously, instead of open/close.

You would not use io_uring for things like that. Not only will you still use regular file operations on device files for various reasons, should you chose to use io_uring you would want it to run your entire eventloop and all you I/O rather than single operations here and there. Otherwise it just adds complexity with no benefit.

I don't see the big issue. There is no other way in Linux or Posix to open a file asynchronously (not sure about closing). Dan Bernstein complained about that 20 years ago(?) and io_uring finally fixes it. Before that, runtimes with lightweight processes/threads (Erlang, GHC) used a Posix threadpool to open files in the background. That seems just as messy as using io_uring, which at least keeps everything in the same thread.

http://cr.yp.to/unix/asyncdisk.html

Re: Fixing stutters in Papers Please on Linux

#188

Post by Dylan16807 » Mon, Jan 03, 2022, 11:52 PM UTC

CyberRabbi wrote: post #184

Dylan16807 wrote: post #183

Earlier quoted context omitted.

They're both problems. This slowness is approaching the point where even checking for joysticks on a dedicated thread would start having delay problems. And spawning a thread per file would be ridiculous and would get even more scorn if it was slow, "why are you spawning so many threads, of course that's not efficient".

> This slowness is approaching the point where even checking for joysticks on a dedicated thread would start having delay problems. Poorly designed code will perform poorly. Well designed code won’t have delay problems. > And spawning a thread per file would be ridiculous and would get even more scorn if it was slow, Where in this entire thread was it suggested to spawn a thread per file? Threads are able to perform…

> Poorly designed code will perform poorly. Well designed code won’t have delay problems.

If I need to open and close 20 files every few seconds, and they all might have unpredictable latencies, even the best designed code in the world could have delay problems.

> Where in this entire thread was it suggested to spawn a thread per file?

You just implied that checking all the files on a dedicated thread is still 'poorly designed code', didn't you?

So if a dedicated thread for the whole group of files isn't enough, sounds like you need to move to a thread per file. Unless it's wrong to use close() at all, or something? You can only blame the code so much.

Re: Fixing stutters in Papers Please on Linux

#189

Post by CyberRabbi » Mon, Jan 03, 2022, 11:54 PM UTC

Dylan16807 wrote: post #186

CyberRabbi wrote: post #185

Earlier quoted context omitted.

> I like the idea of saying a syscall is non-blocking if the spec says it returns instantly. ”instantly” is not a strong enough guarantee to call the syscall non-blocking. The caller needs to know exactly how the callee will perform in terms of run time. Most high level RTOSes spec this as saying the call will take a constant amount of time, allowing you to measure the call once during your testing and using that to…

Pretend I said 10 microseconds everywhere I said instantly, then. Same argument, more or less. Anything that could make getpid take too long is outside the scope of what linux could guarantee. But inside that scope, it's still worthwhile to distinguish between "blocking" and "nonblocking with very specific exceptions" > It’s very possible for getpid() to take longer than one second during normal operation being stuck…

> What resource? I did my best to look at the implementation, but the source code is complicated and scattered. I can't really process your link by itself. How often are these things causing delays?

A signal may need to be invoked and that could cause paging to disk. The point is that the kernel is allowed to do a non-predictable amount of work on most system calls and therefore you cannot assume getpid() completes in any amount of time. If you’re building a real time interactive system, then this matters. If you’re building a system that’s allowed to be non-responsive (for running batch processes, network servers) then it doesn’t.

Re: Fixing stutters in Papers Please on Linux

#190

Post by Dylan16807 » Tue, Jan 04, 2022, 12:16 AM UTC

CyberRabbi wrote: post #189

Dylan16807 wrote: post #186

Earlier quoted context omitted.

Pretend I said 10 microseconds everywhere I said instantly, then. Same argument, more or less. Anything that could make getpid take too long is outside the scope of what linux could guarantee. But inside that scope, it's still worthwhile to distinguish between "blocking" and "nonblocking with very specific exceptions" > It’s very possible for getpid() to take longer than one second during normal operation being stuck…

> What resource? I did my best to look at the implementation, but the source code is complicated and scattered. I can't really process your link by itself. How often are these things causing delays? A signal may need to be invoked and that could cause paging to disk. The point is that the kernel is allowed to do a non-predictable amount of work on most system calls and therefore you cannot assume getpid() completes i…

People are going to keep using non-realtime systems to run soft realtime UIs.

We can't make them stop, so it's still important to distinguish between "this syscall might hit a signal or an interrupt, just like every single line of code in the program" and "this syscall might hit a signal or an interrupt, but also it might get stuck waiting on a resource in a way that couldn't have otherwise happened".

If you want to suggest different terms from "nonblocking" and "blocking" I'm open to change. But in the absence of better terms, I'm going to keep using those, with an asterisk that says I'm inside linux and literally anything could technically block.