-
Notifications
You must be signed in to change notification settings - Fork 177
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Use a custom array type for SetM? #928
Comments
I think we would want to store the size explicitly too, for bounds checks, since the real size would be >= the requested size. |
GHC stores the size. It needs to, for garbage collection. There's a primop to get it. |
Yes, but consider that we want to store just one bit, but the |
I don't think we need that, do we? We have the |
We could do that at |
Yes. I guess I wasn't thinking clearly. |
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
, andMonad
instances forSetM
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
forSetM
.STUArray
is definedIn our case, that means we're passing around:
Int
for the lower bound.Int
for the upper bound.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
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.The text was updated successfully, but these errors were encountered: