Use a custom array type for SetM?

[treeowl]

I noticed that the marking array we use for DFS doesn't always get unboxed (at least, it didn't in one of my lazy preorder experiments). So I tried making the Functor, Applicative, and Monad instances for SetM explicitly strict in the array. This successfully unboxed it, but unfortunately the effects on performance were somewhat mixed. I suspect the problem may be something like register pressure.

We currently use STUArray s Int Bool for SetM. STUArray is defined

data STUArray s i e = STUArray !i !i !Int (MutableByteArray# s)

In our case, that means we're passing around:

1. A boxed Int for the lower bound.
2. A boxed Int for the upper bound.
3. An unboxed Int# for the array size.

If we use a custom array type, we can remove indirections without so many function arguments. The most extreme version would be

data Markers s = Markers (MutableByteArray# s)

where we store the lower bound in the first word of the byte array and get the array size using getSizeofMutableByteArray#. If I read the GHC heap object layout correctly, this will put the lower bound immediately after the array size, so we'll use at most one cache line for those.

[meooow25]

I think we would want to store the size explicitly too, for bounds checks, since the real size would be >= the requested size.

[treeowl]

GHC stores the size. It needs to, for garbage collection. There's a primop to get it.

[meooow25]

Yes, but consider that we want to store just one bit, but the MutableByteArray# will be the size of a word. We should ideally error on access beyond that one bit.

[treeowl]

I don't think we need that, do we? We have the Graph, which is a Data.Array and therefore has its size stashed. We can do the bounds check against that, no?

[meooow25]

We could do that at dfs yes. If so we might as well not store the lower bound, and check that at the same place. Then we need no checks at all at the MutableByteArray#. Seems a bit extreme though.

[treeowl]

Yes. I guess I wasn't thinking clearly.