Joachim Breitner

Constructing a list in a monad revisited

Published 2015-10-14 in sections English, Haskell.

Two years ago, I discussed various ways of constructing a list in a Monad (or, more specifically, in IO) in Haskell, and compared their merits in terms of elegance, stack usage, number of traversals of the list and run-time efficiency.

Recently, two blog posts discussed the issue further and proposed new, more daring alternatives. Neil Mitchell breaks through the abstraction provided by IO, duplicates “the world” and traverses the list twice, and obtains a speed-up for long lists.

Twarn van Laarhoven went even further and wrote custom C-- code to destructively update the tail-pointer of the list cell to be able to create the list completely evaluated on the first start. This basically answers my question from two years ago:

I’m still wondering: What would be required from Haskell, GHC or the monads in question to have a fully satisfactory solution here, i.e. one that is as fast as the naive recursion, as stack efficient as the difference list solution, and allocates no thunks, only list cells?

He also has a variant with a slightly nicer interface around “holes”, i.e. explicit objects on the heap that can later be replaced by indirections. Obviously, both approaches are very unsafe.

I took this as an opportunity to redo my benchmark measurements, and include their variants (named escapeIO, hackIO and holeIO). The following table omits the variants with quadratic performance, as I ran it on longer lists now:

Variant 10^0 10^1 10^2 10^3 10^4 10^5 10^6
accumReverse 37ns 153ns 1134ns 12µs 208µs 8540µs 97ms
recursion 29ns 139ns 680ns 6790ns 160µs 6441µs 76ms
replicateM 26ns 126ns 677ns 6785ns 168µs 6314µs 78ms
accumDList 35ns 165ns 995ns 10µs 190µs 9706µs 100ms
streams 27ns 136ns 691ns 6788ns 173µs 5771µs 75ms
unsafeInterleave 60ns 329ns 2804ns 28µs 373µs 5605µs 57ms
listFix 51ns 412ns 4109ns 56µs 2761µs 42ms 445ms
escapeIO 41ns 187ns 1808ns 16µs 234µs 4409µs 45ms
hackIO 30ns 152ns 1199ns 11µs 140µs 3701µs 42ms
holeIO 40ns 222ns 1725ns 17µs 218µs 4446µs 53ms

The following graph shows that around 10000, the naive approaches become much slower and the fancy hacks pay of, with Twarn’s tail-pointer-updating code performing the best:

I would really like to see a package that provides a API like Twarn’s holes, either in this raw unsafe variant (but with the garbage collector related code checked), or with a safe API using type hackery similar to the ST monad that ensures that after “normal” code gets its hands on a term possibly involving holes, the holes may no longer be modified.

I have put the code and results on GitHub.

Comments

Have something to say? You can post a comment by sending an e-Mail to me at <mail@joachim-breitner.de>, and I will include it here.