benchmarks icon indicating copy to clipboard operation
benchmarks copied to clipboard

Improve Haskell brainfuck2 benchmarks

Open tysonzero opened this issue 5 years ago • 0 comments

The existing bf.hs is slow and unidiomatic as it uses an immutable array to represent the tape, which takes O(n) time to update. One of the most idiomatic ways to represent a brainfuck tape immutably in Haskell is with a zipper along an infinite stream, as that gives you O(1) time complexity for all brainfuck operations. So this is what I change bf.hs to use.

If you are willing to use mutability then the optimal way to represent a brainfuck tape is an unboxed mutable vector with an immutable vector to represent the instructions. So I created bf-vector.hs which does this. I didn't delete bf-marray.hs but that would be a pretty reasonable thing to add to this PR, as vectors are generally faster than arrays and the vector instruction representation is also faster.

Performance/memory usage on my machine (3.1 GHz Intel Core i7, macOS 10.13.3, GHC 8.2.2):

Implementation Time, s Memory, MB
old bf.hs 20.90 1.7
bf-marray.hs 7.01 1.7
bf.hs 6.15 1.8
bf-vector.hs 3.97 1.7

These files are still most likely not optimal, as I didn't put much effort into optimizing them besides doing the idiomatic mutable thing and the idiomatic immutable thing plus just a couple more obvious strictness annotations. I would absolutely welcome further attempts to optimize these.

tysonzero avatar Jan 02 '19 01:01 tysonzero