This PR rewrites from scratch both Knowledge and Primus monads to improve performance and to tame the stack appetites of BAP, in particular it resolves #1267. The performance improvement is quite substantial, ranging from 10% to nearly 50% (i.e., twice as fast) depending on benchmark and compiler options. The use-cases that use Primus Analysis benefit the most (as both monads are used).
The Longer Story
Both monads were using the monad transformer library (Monads) for mixing-in the necessary behaviors. Knowledge was using state and error monad, and Primus was using MultiState, Continuation, Error, and was a transformer itself, so it was mixing an extra monad. The generated code was inefficient as the value was passed through multiple bindings, per each mix in. It was especially annoying since all these features could be implemented with the same structure, which is a function,
that takes two continuations, one for exceptional path, called reject, and another for the normal execution path, called accept. Using this universal structure we can implement a monad of any flavor, for example a pure state monad will be type ('a,'s) state = ('a, unit, 's -> 's) fmonad. The most important takeaway, is not the potential for code reuse (which this PR doesn't realize, as both monads repeat this definition), but that a monadic term could be represented as a single block, no matter how many monads you stack into your transformer. Therefore stacking monads comes for free. An additional important benefit is that we do not need to tag values for exceptional and normal path as we have separate continuations for them. Therefore, we eschew the cost of constructing the result data type. And the continuation monad naturally blends into the structure, as it is already the continuation, so we can easily implement call/cc.
Surprisingly, or maybe not, the resulting code is easier to understand and it opens a few opportunities for specialized implementations. In the future, we might provide fmonad as a universal monad constructor.
This PR rewrites from scratch both Knowledge and Primus monads to improve performance and to tame the stack appetites of BAP, in particular it resolves #1267. The performance improvement is quite substantial, ranging from 10% to nearly 50% (i.e., twice as fast) depending on benchmark and compiler options. The use-cases that use Primus Analysis benefit the most (as both monads are used).
The Longer Story
Both monads were using the monad transformer library (Monads) for mixing-in the necessary behaviors. Knowledge was using state and error monad, and Primus was using MultiState, Continuation, Error, and was a transformer itself, so it was mixing an extra monad. The generated code was inefficient as the value was passed through multiple bindings, per each mix in. It was especially annoying since all these features could be implemented with the same structure, which is a function,
that takes two continuations, one for exceptional path, called
reject, and another for the normal execution path, calledaccept. Using this universal structure we can implement a monad of any flavor, for example a pure state monad will betype ('a,'s) state = ('a, unit, 's -> 's) fmonad. The most important takeaway, is not the potential for code reuse (which this PR doesn't realize, as both monads repeat this definition), but that a monadic term could be represented as a single block, no matter how many monads you stack into your transformer. Therefore stacking monads comes for free. An additional important benefit is that we do not need to tag values for exceptional and normal path as we have separate continuations for them. Therefore, we eschew the cost of constructing theresultdata type. And the continuation monad naturally blends into the structure, as it is already the continuation, so we can easily implementcall/cc.Surprisingly, or maybe not, the resulting code is easier to understand and it opens a few opportunities for specialized implementations. In the future, we might provide
fmonadas a universal monad constructor.