Re: Array heap objects
Yes, the bitmap structures used to encode the structure of stack frames. These *look* like they might be reusable for mix-and-match arrays in Haskell-land. If so, that could be a pretty cheap new feature. On Wed, Oct 7, 2020 at 1:37 PM Ben Gamari wrote: > > David Feuer writes: > > > It appears that the RTS has more flexibility in its array representations > > than users can access through primops. In particular, there are > > "pointers-first" and "bitmapped" arrays. Are these used for the evaluation > > stack or something? I'd be very interested in getting user access to some > > of this power. > > > I'm a bit unclear on what in particular you are referring to. GHC supports > four types of arrays: > > * ByteArray#: Just a pile of bytes > > * Array#: An array of pointers to lifted things with a card table used >to record which regions of the array are "dirty" (and therefore may >need to be scavenged for young-generation references. > > * ArrayArray#: An array of pointers to Array#s. These also have a card >table. This really should be >generalized and called UnliftedArray#, but oh well. > > * SmallArray#: An array of pointers to lifted things without a card >table. The lack of card table means that the entire array must be >scavenged if any part of it has changed. > > We don't support arrays that mix pointers and non-pointers. > > Perhaps you are thinking of the bitmap structures used to encode the > structure of stack frames? > > Cheers, > > - Ben ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
Re: Array heap objects
David Feuer writes: > It appears that the RTS has more flexibility in its array representations > than users can access through primops. In particular, there are > "pointers-first" and "bitmapped" arrays. Are these used for the evaluation > stack or something? I'd be very interested in getting user access to some > of this power. > I'm a bit unclear on what in particular you are referring to. GHC supports four types of arrays: * ByteArray#: Just a pile of bytes * Array#: An array of pointers to lifted things with a card table used to record which regions of the array are "dirty" (and therefore may need to be scavenged for young-generation references. * ArrayArray#: An array of pointers to Array#s. These also have a card table. This really should be generalized and called UnliftedArray#, but oh well. * SmallArray#: An array of pointers to lifted things without a card table. The lack of card table means that the entire array must be scavenged if any part of it has changed. We don't support arrays that mix pointers and non-pointers. Perhaps you are thinking of the bitmap structures used to encode the structure of stack frames? 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
Array heap objects
It appears that the RTS has more flexibility in its array representations than users can access through primops. In particular, there are "pointers-first" and "bitmapped" arrays. Are these used for the evaluation stack or something? I'd be very interested in getting user access to some of this power. Lots of data structures can be represented efficiently using internal nodes consisting of some (unboxed) structural information, some pointers to other internal nodes, and some (boxed or unboxed) leaves. A hashmap, for example, could have internal nodes laid out something like this (pointers-first would probably work well): bitmap1: which children are inhabited? bitmap2: which children are internal nodes? pointers: pointers to internal nodes and leaf nodes. (If we change some of the traditional arithmetic, we can probably even store keys and values directly in their parent nodes rather than having separate Leaf nodes.) As it is today, we need extra indirections between each array and the next one to accommodate the tagging: node -> array -> node -> array -> ... How feasible would it be to offer things like this? ___ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs
