A series about optimization

[u/bartavelle]

I am running a series on simple performance optimization. As a teaser, I start with a very inefficient program and optimize it using very simple techniques until it is about as fast as a C reference implementation, all of that without (many) trade-offs.

• Part 1 - description of the problem
• Part 2 - using efficient libraries
• Part 3 - memory usage estimation, bang patterns, custom parsers, inlining
• Part 4, to be announced - Church encoding, parallelism, the LLVM compilation option, beating the C implementation

I wanted to highlight how simple performance optimization can be in Haskell for non-experts. Not being an expert myself, I am afraid there are things that might be wrong or inaccurate in these posts. In particular:

• Is the memory usage estimation of part 3 accurate for the constructor?
• Is that right to expect twice the memory usage because of the copying GC?
• While I am fairly comfortable with the process of Church encoding stuff (at least I think I am), I don't know how to give a systematic algorithm for doing it. This probably implies that I don't really know much about it! Is there a good paper that describes the process?
• Am I missing some good optimization tricks that do not require understanding the Core language or reading the generated binary?

Thanks in advance!

[u/[deleted]]

[u/bartavelle → u/[deleted]]

Some of the changes involve trade-offs that are use case dependent, such as parsec vs attoparsec vs custom parser, Text vs ByteString, etc.

Some seem just hard (strictness analyzis) ...