[GHC] #8923: Add SmallArray# type

[GHC]

#8923: Add SmallArray# type
-------------------------------------+------------------------------------
        Reporter:  tibbe             |            Owner:  tibbe
            Type:  feature request   |           Status:  new
        Priority:  normal            |        Milestone:  7.10.1
       Component:  Compiler          |          Version:  7.9
      Resolution:                    |         Keywords:
Operating System:  Unknown/Multiple  |     Architecture:  Unknown/Multiple
 Type of failure:  None/Unknown      |       Difficulty:  Unknown
       Test Case:                    |       Blocked By:
        Blocking:                    |  Related Tickets:
-------------------------------------+------------------------------------
Changes (by hvr):

 * cc: simonmar (added)
 * milestone:   => 7.10.1


Comment:

 Some older discussion about this topic:

 {{{
 17:41 < JaffaCake> I like the idea of a separate small array type
 17:41 < hvr> JaffaCake: does that single card-table "bit" make sense for
 <128 elements btw?
 17:42 < JaffaCake> no, because we already have a flag for the whole array
 that tells us whether anything was modified
 17:42 < hvr> or rather: having a kind of threshold (say ~16 elements or
 so) below which the card-table is 0-sized
 17:42 < JaffaCake> so it's no use at all
 17:43 < hvr> so we could optimize the <128 element case, by omitting the
 card-table?
 17:43 < hvr> and thus getting a 2+N footprint for <128 elements?
 17:43 < JaffaCake> you'd need a different type though
 17:44 < JaffaCake> otherwise the write barrier would need a conditional on
 the size, which is bad
 17:44 < hvr> and if the 0th card-table bit would be implicit always?
 17:45 < hvr> i.e. derived from the remaining the bits + the whole-array
 flag you mentioned?
 17:45 < JaffaCake> how would you derive it from the remaining bits?
 17:46 < hvr> isn't the "whole array flag" == 'and' over all card-table
 bits?
 17:46 < tibbe> Having it conditional would mean that writes would
 introduce a branch, not good.
 17:47 < hvr> nevermind, that wouldn't allow to deduce it in all cases
 17:47 < JaffaCake> hvr: right :)
 17:48 < JaffaCake> tibbe: yes, we really want to avoid branches in the
 write barrier
 17:48  * hvr needs to read up about write-barriers in that GC-handbook I
 just bought...
 17:48 < JaffaCake> it doesn't have to be a "small array" type as such, you
 could just reintroduce the old card-table-less arrays
 17:49 < JaffaCake> it wouldn't be much code
 17:49 < tibbe> JaffaCake: realistically, how much work would it be to add
 a new closure type for small arrays. I know we have talked about it 10^10
 times but perhaps I'll actually do something about it.
 17:50 < JaffaCake> you could do it in an afternoon, I would think, it's
 mostly mechanical
 17:51 < JaffaCake> start from 0417404f5d1230c9d291ea9f73e2831121c8ec99
 17:51 < JaffaCake> and just add back the old arrays
 17:51 < JaffaCake> with a new primitive type, and primops etc.
 17:52 < JaffaCake> I suggest not actually having a size requirement, you
 can call them small arrays if you want but they would work for all sizes
 17:52  * JaffaCake must disappear
 17:52 < hvr> JaffaCake: so they'd just be a different cost-model for the
 user to choose from...
 17:53 < tibbe> JaffaCake: ok
 17:53 < tibbe> JaffaCake: I guess one size field is required for the GC?
 17:53 < JaffaCake> hvr: precisely
 17:53 < JaffaCake> tibbe: yes
 }}}

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/8923#comment:1>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler