#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

#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: -------------------------------------+------------------------------------ Comment (by tibbe): simonpj, could you look at the second patch (attachment:0002-Add- SmallArray-type-to-front-end.patch​), which adds the new type to the type system. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8923#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------ Comment (by simonpj): I have not been following the thread, but it seems surprising to add tow new types to `primpops.txt.pp` with no accompanying primpops to manipulate them. But the front-end changes (which amount only to adding stuff to `PrelNames` and `TysPrim`) look ok to me. Simon -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8923#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: -------------------------------------+------------------------------------ Comment (by tibbe): I now got a working implementation. **Both** runtime and allocations are down 8.8% on my unordered-containers insert benchmark, which is already very heavily optimized. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8923#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#8923: Add SmallArray# type -------------------------------------+------------------------------------ Reporter: tibbe | Owner: tibbe Type: feature request | Status: patch 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: -------------------------------------+------------------------------------ Comment (by Johan Tibell ): In [changeset:"90329b6cc183b3cd05956ae6bdeb6ac6951549c2/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="90329b6cc183b3cd05956ae6bdeb6ac6951549c2" Add SmallArray# and SmallMutableArray# types These array types are smaller than Array# and MutableArray# and are faster when the array size is small, as they don't have the overhead of a card table. Having no card table reduces the closure size with 2 words in the typical small array case and leads to less work when updating or GC:ing the array. Reduces both the runtime and memory allocation by 8.8% on my insert benchmark for the HashMap type in the unordered-containers package, which makes use of lots of small arrays. With tuned GC settings (i.e. `+RTS -A6M`) the runtime reduction is 15%. Fixes #8923. }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/8923#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler