Improve the complexity of Action exception handling primitives

[pepeiborra]

actionBracket, actionFinally and actionOnException all have an unexpected O(logN) complexity where N is the total number of cleanups registered.

The usual complexity for these primitives is O(1), so it should be documented (or if possible, fixed). Moreover, the cleanup store is global and locked, so these primitives introduce additional lock contention which is also worth documenting.

[ndmitchell]

Is the O(log n) ever visible? Have you managed to measure that as a meaningful slowdown? It's possible to use smarter data structures to avoid that slowdown (an array, that grows, where you delete by swapping the end), but I never thought it might get frequent enough to matter.

[pepeiborra]

Regardless of whether it's visible or not it should be documented since the complexity is different from the assumed one.

Fixing it would be a bonus, but that's not the main issue here

[ndmitchell]

I think this code is O(log N) in the number of simultaneously running calls to actionBracket. I expect in most programs that's tiny, probably not a good idea to do simultaneously, and also not what people would think of as a typical N for this call, which makes me worry that the documentation would do more harm than good. The N is also likely to be bounded by the number of threads (most things don't do recursive actionBracket calls), which again makes it technically O(log N), but less so in a practical sense.

For the lock, we could introduce per-Action Cleanup pools, which would entirely remove the contention. Given the issue in HLS, I'd be keen to understand how much performance used to be lost due to Cleanup, how much performance currently goes into Cleanup, and if Cleanup was an order of magnitude faster, would we do things differently?

[pepeiborra]

It's hard to measure time performance precisely in Haskell, because the precision goes down with the number of SCC, too many and you are no longer measuring the real program, too few and you don't get correct cost attribution. I previously shared this profile but it's hard to say whether the costs attributed to actionBracket are real

[pepeiborra]

Note that in Ghcide we do nest actionBracket in the same thread, as part of the progress reporting loop. We have not changed that in ghcide, but I have limited the nesting depth in private projects where I use ghcide as a library

[pepeiborra]

Why do you think documentation would do harm?

-- | 'actionBracket' has O(logN) time cost in the number of nested actionBracket's

[ndmitchell]

It's the number of simultaneously running actionBrackets across the program, so if you nest deeply somewhere else, that counts too. It also feels that if this matters to you, the solution is to fix actionBracket. But I guess there's no harm in mentioning it.

[ndmitchell]

Documented, and leaving the ticket to improve it (I don't think it would be too hard to make it O(1) with a suitable data structure).