How is the performance of https://github.com/crystal-lang/crystal/blob/master/samples/channel_primes.cr affected, replacing 100.times with a bigger number (I think 1000 or 10000 is good for a benchmark)

This is the mean over 5 runs of samples/channel_primes.cr with 10k iterations each:

master: 33.640000   7.760000   41.400000 (  45.352300)
 patch: 35.680000   7.842500   43.522500 (  46.928800)
  diff: +1.06%     +1.01%      +1.05%    (  +1.03%   )

1% doesn't sound too bad considering the example is constantly switching fibers back and forth. In a real-world application it'll barely be noticeable.

The performance loss could probably be avoided with a customized #resume method that gets setup to be scheduled when #cancel is called. But I'd leave such an optimization for later.

With a bit of work an uncatchable exception could be added. But it wouldnt be very useful since ensure blocks can raise, and if they raise that exception can easilly be caught. Accidentally or not.

I don't think this mechanism is robust enough to add.

I'd rather have a different implementation which keeps track of the explicit resources the fiber holds that can deadlock on a seperate stack, and use that to clean up. Is it only mutexes or is there stuff around IO scheduling that can break? If its only mutexes it shouldnt be too hard.

I don't think this is only about avoiding deadlocks with mutexes or anything but to properly clean up a fiber's stack, which means to execute all ensure blocks.

I don't think this mechanism is robust enough to add.

What do you mean with that?

@straight-shoota what do you mean clean up the stack? You can just delete the stack to clean it up. The only issue is you can get deadlocks when you never unlock a mutex or so.

One way to do that is to only execute ensures, but you don't have to go that route.

I mean to unwind the stack and doing all the clean up in the process, such es executing ensure blocks. I mean, if you write an ensure block, you expect that to always execute (unless there is a huge error like segfault).

Cancelling a fiber is not huge error (it's not an error at all) but rather a simple way of canceling a task when it is no longer needed. But in my opinion, it should not just try to do the bare minimum to avoid deadlocks, but properly unwind and do clean up. I guess this is similar to SIGTERM and SIGKILL.

I'd like to have a way to gracefully stop a fiber (likely while it is waiting for IO) which can't be implemented in a nice way in user code. A typical use case for this would be something like the typical algorithm for establishing a TCP connection, which starts multiple connection attempts more or less simultaneously in fibers and as soon as one of them succeeds, the others can be stopped. But they should properly unwind and release their resources (for example sockets).

2 exceptions, 2 stack unwinding (very costly) and an additional check for each and every fiber resume :-/

Isn't killing a thread considered bad practice? I don't see why canceling a fiber would be better.

There are better patterns to stop a fiber with proper cleanup than a hard cancel.

Well, the inner exception is optional. I thought it might be useful to know where a fiber was cancelled, but in practice it's probably not that important.

So it could be only one exception and unwinding. And I don't think there is an alternative to that if you want to execute ensure blocks.

The additional check for each resume adds a minimal overhead. And there should be a way to avoid that if really necessary.

There are better patterns to stop a fiber with proper cleanup than a hard cancel.

First of all, it's not a hard cancel. The fiber can rescue from the exception if necessary.

What would be a better pattern, say for my example use case?

if we do this we should do it with custom codegen so it's actually impossible to rescue. It shouldn't be too hard.

What bugs me is two fold:

1. Stopping a fiber from an outside context (i.e the whole concept of cancel) when I believe there are better patterns;

2. Raising an exception in the fiber context when a similar concept, exit specifically doesn't and uses at_exit callbacks instead for cleanup.

Also, it only cancels the fiber if and when it's resumed by the scheduler. If it never enters the scheduler it will never be cancelled.

Still, cancelling will delayed to later on. Is it really better than to send a message through a channel telling it to stop?

Is it really worth to introduce a "custom codegen"?

Fiber#cancel should generally be followed by Fiber.yield or similar. The fiber to be canceled is enqueued, so it will be executed next. I'm sure this would be fine as a convention. It would also be an option to yield directly from #cancel by default, and provide an argument to not do this (for the purpose described in the OP).

Yes, in some cases it is better to use a channel or a simple loop condition to let the fiber stop itself. The problem is that this doesn't work when the fiber is waiting for an event like IO or a timeout. The only way this can be implemented is to insert a check for a cancel request after each expression that could include a context switch. As this is not practical, this logic should be in Fiber#resume.

I don't think this needs custom codegen. It is fine if a CancelledException can be caught if explicitly asked. It just shouldn't be caught by the default rescue without type restriction. This only requires a minor change in the compiler. And the feature would probably also be fine without it. A blank rescue should be treated with care, anyways. And in stdlib it is mostly used for code for error handling, so not a big deal. But do_something_that_might_raise rescue nil is a common idiom that shouldn't swallow CancelledException.

exit is called maximum once per process. And I would probably even prefer to raise a SystemExitException. Cancelling a fiber however, can be much more common and what happens inside a fiber can't be known by the code that starts and cancels a fiber. And IMHO that's exactly what ensure blocks are made for. To clean up whether the task was successful or not (including being cancelled).

@straight-shoota the problem is that without a larger change to the compiler, an ensure block that raises an exception will raise a standard exception which will be cause by rescue without a restriction. This is an easy bug to create, and a pretty hard bug to catch or test, since ensure throwing is so rare.

Actually the only change needed would be to introduce an intermediate exception and make rescue catch that intermediate exception by default. To catch all exceptions you would rescue from Exception, or Raisable, something like that. Then we could also raise on exit, I think there was an issue about that...

But I don't know about cancelling a fiber. There must be a reason no other language allows such thing.

@asterite I just described the problem with that approach and I think it's the kind of ugly problem that will raise it's head in production and make a mess.

There must be a reason no other language allows such thing.

This proposed behaviour is actually implemented very similar to Python's asyncio.Task.cancel and Trio's cancel.

@RX14 What exactly is the problem with the solution I proposed in the original post? It shouldn't be very difficult to insert a new exception type above Exception and let CancelledException inherit from that. The only change in the compiler would be to recognice the new parent as base exception type but still only catch Exception by default.

It also happens that Ruby has some exceptions that aren't caught by default, and the same is true for a Java (the Error class). In C# there's a ThreadAbortExcrption that can be caught but it's automatically rethrown.

It seems the proposed solution here is similar to other languages, I don't see a problem with that.

Maybe it would be nice if @waj could comment whether gracefully stopping a fiber is something bad.

@straight-shoota I just described how exactly what you describe fails!!! Please read again

Oh, seems like I had overlooked that comment. I'm sorry.

I'm not sure this is really a big issue though. An ensure block should normally not raise. If it raises, it is most likely a severe error that won't allow the continuation of the task anyway. And a blank rescue without restrictions can always be a reason for bugs if it catches something you didn't expect to be thrown. As I already mentioned, it is mostly used for things like do_something_that_might_fail rescue nil if you don't care if there is an result. Maybe in such cases it would be better anyways to only catch specific exceptions. And for this we need a better exception hierarchy.

@straight-shoota yes it usually is a severe error that won't allow continuation of the task. But so are most exceptions, and raising from ensure really isnt that uncommon. io.close can easily raise when it flushes buffered writes, and io.close is a common ensure.

Such a common thing shouldn't abort the whole cancelling of a fiber. That's why it'd need seperate codegen, to automatically silently ignore exceptions in ensure blocks when you were unwinding to close.

And given that complexity, I really don't like the idea of unwinding at all. I'd like to try the simple solution first, which is not to unwind and to identify the few resources which can deadlock and handle them specially.

And not to mention, even having the possibility that a fiber can "fail to cancel" and keep running is confusing for the programmer, invites edge cases by it's very nature, and requires more careful design and more code.

I don't think it is an issue if a cancellation might not work out. It is after all a way to try to gracefully stop a fiber. Concurrency in Crystal is cooperative, so it always depends on how other components behave.

Being able to cancel a fiber gracefully with a chance of not succeeding is an improvement over not being able to cancel at all. It could very well be used in a way that a fiber is given some time to cancel itself and after that, it might just get hard killed (removed from the Scheduler).

Cancellation through an exception is a very simple implementation and IMHO it is sufficient for most use cases, even if it can't guarantee the CancelledException goes all the way to the top of the stack.

@straight-shoota the problem is not that cancel can fail to gracefully stop a fiber, it's that it can actually accidentally resume a fiber instead. That's the whole point of what i'm saying, a cancel which can fail resumed from a "paused" state (not in the scheduler queue) is useless. It's not an improvement on the current situation at all.

I'm not sure why this is a problem. The entire point is to not let a waiting fiber hang around until some timeout kicks in - or even indefinitely. When the fiber is resumed it can deal with the cancellation, even if the specific exception doesn't go through.

If you call #cancel, the fiber should never resume running. It's as simple as that.

I don't understand the problem with ensure and that exception.

@RX14 That's how Pythons cancel implementation works. And I don't think it is wrong:

This arranges for a CancelledError to be thrown into the wrapped coroutine on the next cycle through the event loop. The coroutine then has a chance to clean up or even deny the request using try/except/finally.
This does not guarantee that the task will be cancelled: the exception might be caught and acted upon, delaying cancellation of the task or preventing cancellation completely. The task may also return a value or raise a different exception.

If CancelledException arrives at the fiber's root, it is marked as cancelled. The caller of cancel could check after some grace period if the fiber was successfully cancelled. If not, it can either try again or do something else.

@asterite Fiber#cancel starts raising CancelledException inside the fiber, which then enters an ensure block, containing for example io.close. io.close then raises an exception, probably IO::Error which is inside the standard exception hierarchy. That exception then gets caught by a standard rescue code and the fiber starts executing as normal, an unintended consequence of trying to cancel the fiber.

What's the state of Fiber#join? I haven't noticed one around but you guys are already implementing more advanced features such as Fiber#cancel. I'm new to the language, btw. I just lurking here because a friend pointed me to this discussion.

The initial design looks good. I'll read more carefully later.

@vinipsmaker you might want to take a look at #6468

an additional check for each and every fiber resume :-/

Context switch is where the fat goes anyway. You want to do progress as much as you can before doing a context-switch. Checking on a bool on context-switch seems rather cheap to me. You might enjoy reading this: https://lwn.net/Articles/763056/

Isn't killing a thread considered bad practice? I don't see why canceling a fiber would be better.

Recently I've implemented a fiber.interrupt() for a multi-threaded fiber implementation I use daily at work. I've researched several solutions to stop a thread, including Windows API, POSIX threads, Go approach, discussions on Rust community, Java's list of deprecated thread features and Java's interrupt API, Boost.Fiber, Boost.Thread and maybe a few more that I don't remember right now. It turns out that POSIX-like thread cancellation API is the cleanest solution to interrupt a thread. And the problem is so common that you probably want implement this API rather than pollute user-code with ugly never-ending cascades of handles being passed at every level of abstraction to do yet another ugly select-over-multiple-channels.

I guess the “bad practice” that you mention may refer to APIs that don't match POSIX semantics enough like Windows' and Java's.

In my case, a fiber may not always wake-up on the same thread and there were some kinds of races I had to deal with. My implementation is also more complete with features such as pthread_cancel_state() equivalent. So my case is much more complex.

It would also be an option to yield directly from #cancel by default, and provide an argument to not do this

Don't.

Always do run-to-completion semantics by default. Be safe by default. Dispatch semantics are tricky to the user and may lead to bugs. Also, if Crystal goes multi-thread one day, the whole suggestion doesn't make sense and it shouldn't be even added as an option.

If you call #cancel, the fiber should never resume running. It's as simple as that.

Wrong. If there is clean-up code to be executed, you're already scheduling some task to run (i.e. the #resume).

If CancelledException arrives at the fiber's root, it is marked as cancelled. The caller of cancel could check after some grace period if the fiber was successfully cancelled. If not, it can either try again or do something else.

The “it can either try again or do something else” part worries me. It just complicates design (like Java's state machine on interruption API).

@vinipsmaker

The “it can either try again or do something else” part worries me.

What should happen in this case instead?

Thanks for your great input on this topic, btw!

FWIW I don't love this option, it's a great tool for beginners but can introduce subtle bugs (like exceptions being raised inside finalize handlers so they basically only half cleanup, etc...it's a can of worms, and can cause unexpected behaviors, similar to how Timeout.timeout in ruby feels error prone :|

@rdp A finalizer can only raise if it contains a potential fiber switch. This would most likely be some kind of IO operation which could already raise for a number of other reasons.

The alternative to hard-kill a fiber doesn't even give a chance to run any finalizers.

A finalizer can only raise if it contains a potential fiber switch

I'm not sure what you mean?

Some IO operation, sleep or similar which allows the scheduler to move execution to a different fiber. If the finalizer runs without interruption in the same fiber, it can't raise.
But obviously, finalized are often used to release some resource which likely includes IO operations.

Oh, I think my brain did an incorrect autocorrect. @rdp do you mean object finalizers or ensure blocks? Because the former is already a problem.

What should happen in this case instead?

To proceed with the discussion, we have to establish some goals. What are we trying to achieve and what are the alternatives? A misalignment of expectations will blur the discussion.

Thread cancellation API was designed to avoid stalling threads in IO requests. Threads build a composition of operations and threads run independently of each other. Thread T' does not know the state of thread T''. It's important to keep this point in mind. We do not want to require threads to know about each other state that much as it introduces co-dependence between them (i.e. it would require that both threads are coded with each other's code in mind).

As an example of co-dependence that I faced recently, I had 2 fibers spawned from one parent fiber per client. Each child fiber accessed data on the stack of the parent fiber. And here I'm using C++, so no GC over values of the closures. Parent fiber just had to wait for each child fiber to finish or else they would access invalid memory leading to crash on best scenario. By that time I hadn't finished my join() algorithm yet (nor cancel()), but I had already a fiber_barrier, so that's what I used[1][2]. Create a barrier with count=3 and at the end of each fiber call barrier.wait(). The problem in this scenario is the dependency graph built with this architecture. Each fiber's “independent” code depended on each other. A change in the logic of one fiber would potentially require a change in the code of every other fiber. Complex. Not good. As soon as I implemented the join() algorithm I managed to remove the barrier usage on this piece of code and call fiber{1,2}.join() from parent fiber. Much simpler dependency graph.

The dependency information applies to the design of cancel() as well. A thread is either cancelled or not cancelled (from the point of view of the canceller thread). It's that simple. That's the way POSIX thread cancellation API was designed. That's not how Java's interruption API was designed.

When you cancel a thread, you send an async request to cancel the thread. The Linux's programmer manual does a good job at explaining the the function, so I'll just paste relevant parts here:

The pthread_cancel() function sends a cancellation request
to the thread thread. Whether and when the target thread
reacts to the cancellation request depends on two attributes
that are under the control of that thread: its cancelability
state and type.

A thread's cancelability state, determined by
pthread_setcancelstate(3), can be enabled (the default for
new threads) or disabled. If a thread has disabled
cancellation, then a cancellation request remains queued
until the thread enables cancellation. If a thread has
enabled cancellation, then its cancelability type determines
when cancellation occurs.

A thread's cancellation type, determined by
pthread_setcanceltype(3), may be either asynchronous or
deferred (the default for new threads). Asynchronous
cancelability means that the thread can be canceled at any
time (usually immediately, but the system does not guarantee
this). Deferred cancelability means that cancellation will
be delayed until the thread next calls a function that is a
cancellation point. A list of functions that are or may be
cancellation points is provided in pthreads(7).

— pthread_cancel(3)

If you want to interrupt a thread, it's a fire-and-forget operation. Just send a cancellation request and later join() or detach(). The API doesn't require you to know implementation details of that thread (which would introduce co-dependency between them). As for Java's:

A thread sends an interrupt by invoking interrupt on the Thread object for the thread to be interrupted.

— Thread.interrupt(), https://docs.oracle.com/javase/tutorial/essential/concurrency/interrupt.html

Tests whether the current thread has been interrupted. The interrupted status of the thread is cleared by this method. In other words, if this method were to be called twice in succession, the second call would return false (unless the current thread were interrupted again, after the first call had cleared its interrupted status and before the second call had examined it).

— Thread.interrupted(), https://docs.oracle.com/javase/8/docs/api/java/lang/Thread.html#interrupted--

As for Java, it uses a design where a thread might be interrupted, non-interrupted, and it can go from one state to the other without knowledge of the interrupter thread. The interrupter thread must somehow know implementation details from the other thread (co-dependency again) so it can react to proper ignored cancellation requests and possibly send them again. No sane mind would think this is good design.

Now, going back to POSIX, there is more valuable information on Linux's Programmer's Manual:

Briefly disabling cancelability is useful if a thread
performs some critical action that must not be interrupted
by a cancellation request. Beware of disabling
cancelability for long periods, or around operations that
may block for long periods, since that will render the
thread unresponsive to cancellation requests.

Asynchronous cancelability

Setting the cancelability type to
PTHREAD_CANCEL_ASYNCHRONOUS is rarely useful. Since the
thread could be canceled at any time, it cannot safely
reserve resources (e.g., allocating memory with malloc(3)),
acquire mutexes, semaphores, or locks, and so on. Reserving
resources is unsafe because the application has no way of
knowing what the state of these resources is when the thread
is canceled; that is, did cancellation occur before the
resources were reserved, while they were reserved, or after
they were released? Furthermore, some internal data
structures (e.g., the linked list of free blocks managed by
the malloc(3) family of functions) may be left in an
inconsistent state if cancellation occurs in the middle of
the function call. Consequently, clean-up handlers cease to
be useful.

[...]

One of the few circumstances in which asynchronous
cancelability is useful is for cancellation of a thread that
is in a pure compute-bound loop.

— pthread_setcanceltype(3)

This quote by itself is enough to understand the main problems with cancelability and why PTHREAD_CANCEL_DEFERRED (i.e. deferring the delivery of the cancellation request to a thread only when it reaches a cancellation point) is very useful and desirable. It enters fibers! Fibers are a cooperative API and it already defines suspension points that the programmer relies on. So they're a good fit for cancellation API as we may just define that suspension points are cancellation points.

And we're running out of POSIX here. POSIX also means C here. And C doesn't have exceptions nor RAII. So they had to come up with their own clean-up procedures to act during a thread cancellation. The whole thing is, as my colleague puts, “a manually implemented RAII” (i.e. destructors placed to be called deterministically at the end of each scope).

When you leave the C realm and look at other APIs, this step is usually translated to an exception that is thrown and provokes stack unwinding cleaning any resource. In Java, this exception is InterruptedException[3]. In Boost.Thread, this exception is boost::thread_interrupted[4] (and as an extra note, Boost.Thread follows POSIX model way more closely). And, just like you guys were considering/discussing/planning, Boost.Thread's boost::thread_interrupted class doesn't inherit the standard exception tree to avoid being accidentally caught (and is later caught by a default root handler that does nothing). As for Crystal, I'm hesitant to propose anything because I need to first check its exception model so I can understand what is in play here. And exceptions play a central role in the design of Fiber#cancel.

As for my design of fibers in C++, fiber_interrupted also avoids the standard exception tree and it is okay to catch it anyway if you want (like manually implementing the disable_interruption feature, but with some gotchas).

As for the alternative, the main alternative I see for Crystal is Go's:

• https://www.sohamkamani.com/blog/golang/2018-06-17-golang-using-context-cancellation/
• https://medium.com/@rakyll/context-propagation-over-http-in-go-d4540996e9b0 (this link also discusses the use of Context propagation over several layers of abstraction during the lifetime of a goroutine, but honestly that's something trivial and cleaner to do with fiber local storage — which would also require some standard “key” to be used along-side the chain).

Anyways, what's the most complete documentation circa Crystal's exception model so I can take my time and come back to the discussion later?

[1] https://linux.die.net/man/3/pthread_barrier_init
[2] https://linux.die.net/man/3/pthread_barrier_wait
[3] https://docs.oracle.com/javase/8/docs/api/java/lang/InterruptedException.html
[4] https://www.boost.org/doc/libs/1_68_0/doc/html/thread/thread_management.html#thread.thread_management.this_thread.interruption_point

@vinipsmaker crystal's current exception model is that everything inherits Exception, and you must raise an Exception. The default rescue type is Exception. So there's no way to raise an exception that isn't caught by default. Yet. I think probably the best way to solve this problem is to introduce a new layer to the exception hierarchy, similar to Throwable in Java.

The suggestion to only cancel fibers on suspention points is great!

The suggestion to only cancel fibers on suspention points is great!

That's actually the only feasible way for cancelling fibers. There is no way to preempt a fiber, so it can't be interrupted at any time ("asynchronous" in pthread lingo). The currently scheduling model only allows for "deferred".

Regarding adding an uncatchable exception, erlang has this via the exit function if the reason given is kill then it cannot be caught and cleanup cannot be ran.

Also haskell includes a function throwTo that throws an exception to a green thread (the name ThreadId is misleading)

Just thought i'd mention this, studying other solutions to a problem is the #1 way to get up to speed fast :)

uncatchable exception I presume still runs ensure blocks? In my head it's still just too much of a danger to developers, it opens a can of worms if you let people get by without having graceful stop points, FWIW...

Closing stale PR.
Discussion should be continued in #6468.