Optimize Effect Handling for Tail-resumption with Stack Unwinding

Abstract

Algebraic effect handling is a superior abstraction for non-local control flows, unifying over the existing non-local control flow constructs such as try/catch, destructors, shared state, async/await and generators. To encourage the adoption of effect handlers, improving their performance is essential. Despite having a number of implementations, they lack enough focus on tail resumptive handlers which leaves space for an improvement. We believe that tail resumptive handlers are invoked more frequently and contributes more to the overall performance of programs. The characteristic of them implies the possibility of an implementation with little overhead over function invocation. We propose eff-unwind, an implementation of effect handling as a C++ library which is optimized for tail resumptive handlers at the cost of others. Our implementation uses function calling and returning for tail resuming for improved efficiency while using stack copying and setjmp for general resuming and stack unwinding for yielding. It eliminates the need of recomposing the stack or preserving memory in the lifecycle of a tail resumptive handler at the cost of a less efficient yielding and not-tail resuming. Additionally, our library exposes a functional interface and executes C++ destructors. We evaluate our approach based on a total of 12 cases containing both tail resumptive handlers and others. The result shows performance improvement for tail resuming and slowdown for others. We also discover that multishot handlers presents challenges with C++ destructors.