David Feuer <david.fe...@gmail.com> writes: > Ah, too bad about reuse. What do you mean about walking over both pointers > and non-pointers? The extra word (for pointers-first layout) or few words > (for bitmapped) will be more than made up for in most cases by not needing > extra heap objects between a node and its children. > Let's consider the case that you want an array of (String, Int#) pairs. Today you have a choice of two representations:
* structure-of-arrays:
type Array = (Array# String, ByteArray#)
where the ByteArray# contains packed `Int#`s.
* array-of-structures:
data Entry = Entry String !Int#
type Array = Array# Entry
In the latter case you indeed incur an extra indirection, but not in the
former. It is true that locality may be in the former (especially
if your entry is a wide product rather than the pair used here) but on
the whole it's often a good choice.
I think you are asking for a very general MixedArray#, which would allow
you to specify dynamically whether each word of the array is a pointer
or not. This seems like a lot of power and may complicate garbage
collection. Apologies if I have misunderstood.
I think you can get most of the power of this idea with a much simpler
idea: rather than allow configuration of each word dynamically, specify
the array as a bunch of packed unboxed tuples. For instance, in Haskell
this might look like:
-- This class would need to be magic since the compiler would need
-- to generate a info table describing the entry layout for each
-- instance.
class HasArrayRep (a :: k)
data PackedArray# (a :: k)
newPackedArray# :: HasArrayRep a
=> Int#
-> State# s -> (# State# s, PackedArray# a)
readPackedArray# :: HasArrayRep a
=> Int -> PackedArray# a ->
-> State# s -> (# State# s, a)
-- ... etc.
Implementation would involve the introduction of a new array closure
type and suitable scavenging logic. Each HasArrayRep instance would emit
an info table; the layout section of this info table would contain a
bitmap (of the same sort used for stack frames) which would describe the
layout of a single array element. To avoid unaligned accesses you would
want to round up the element size to the nearest word size, potentially
incurring some slop (e.g. each element of a `PackedArray# (# Word#,
Word8# #)` would require two words). However, sub-word-size fields could
in principle be packed into a single word (finally allowing us to get
some mileage out of the sub-word-size primitive types we now have).
Perhaps this helps in your use-case?
Cheers,
- Ben
signature.asc
Description: PGP signature
_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
