#10652: Better cache performance in Array# -------------------------------------+------------------------------------- Reporter: MikeIzbicki | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Revisions: -------------------------------------+------------------------------------- Comment (by rwbarton): One idea I had was to create a new family of array types along with boxed and unboxed arrays, called unpacked arrays. (Note this is the opposite of UnpackingArrays.) The idea is that whenever `T` is a type that can be unpacked with the `{-# UNPACK #-}` pragma, we can form values of type `UnpackedArray# T`. The heap representation of such a value is of the form {{{ UnpackedArray#_info T_con_info n a1 b1 c1 a2 b2 c2 ... an bn cn }}} representing an array containing the values {{{ T_con_info a1 b1 c1 T_con_info a2 b2 c2 ... T_con_info an bn cn }}} (Since `T` can be unpacked, it has just one constructor.) Compared to an `Array#` this costs one extra word `T_con_info`. It might be possible to save this word with a new type of info table layout, then the heap representation of `Array# a` would be identical (modulo info pointer value) to that of `UnpackedArray# (Box a)` where `data Box a = Box a`. The GC can use `T_con_info` to understand the layout of the rest of the heap object, while mutator operations like indexing would use operations from a magically-generated `Unpack` type class. This last part might be tricky. Then `IntArrayTree` could hold an `UnpackedArray# IntArrayTree` to avoid one of the layers of indirection. It won't apply to tibbe's unordered- containers though, since `IntMap` has multiple constructors. (I guess it could be used inside `Collision !Hash !(A.Array (Leaf k v))`, but that's rather pointless.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10652#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler