Rethink the empty array optimization

[treeowl]

Currently,

createArray 0 _ _ = emptyArray
createArray n x f = runST $ do
  ma <- newArray n x
  f ma
  unsafeFreezeArray ma

This is very straightforward, but it doesn't play particularly well with worker-wrapper. In particular, whenever the array is non-empty, it will allocate both an array and an Array constructor to hold it. Since the empty array is the unusual case, I think we might be better off optimizing the non-empty case more aggressively at its expense:

createArray
  :: Int
  -> a
  -> (forall s. MutableArray s a -> ST s ())
  -> Array a
createArray n x f = Array (createArray# n x f)

createArray#
  :: Int
  -> a
  -> (forall s. MutableArray s a -> ST s ())
  -> Array# a
createArray# 0 _ _ = emptyArray# (# #)
createArray# (I# n) x f = case runRW# $ \s ->
   case newArray# n x s of { (# s', mary# #) ->
   case unST (f (MutableArray mary#)) s' of { (# s'', _ #) ->
   unsafeFreezeArray# mary# s'' }} of (# _, ary# #) -> ary#

unST :: ST s a -> State# s -> (# State# s, a #)
unST (ST f) = f

emptyArray# :: (# #) -> Array# a
emptyArray# _ = case emptyArray of Array ar -> ar
{-# NOINLINE emptyArray# #-}

[cartazio]

Is there a natural benchmark we can use to evaluate these strategies ?

…

On Thu, Mar 22, 2018 at 3:36 AM David Feuer ***@***.***> wrote: Currently, createArray 0 _ _ = emptyArray createArray n x f = runST $ do ma <- newArray n x f ma unsafeFreezeArray ma This is very straightforward, but it doesn't play particularly well with worker-wrapper. In particular, whenever the array is non-empty, it will allocate both an array and an Array constructor to hold it. Since the empty array is the *unusual* case, I think we might be better off optimizing the non-empty case more aggressively at its expense: createArray :: Int -> a -> (forall s. MutableArray s a -> ST s ()) -> Array a createArray n x f = Array (createArray# n x f) createArray# :: Int -> a -> (forall s. MutableArray s a -> ST s ()) -> Array# a createArray# 0 _ _ = emptyArray# (# #) createArray# (I# n) x f = runRW# $ \s -> case newArray# n x s of { (# s', mary# #) -> case unST (f (MutableArray mary#)) s' of { (# s'', _ #) -> case unsafeFreezeArray# mary# s'' of { (# s''', ary# #) -> ary# }}} unST :: ST s a -> State# s -> (# State# s, a #) unST (ST f) = f emptyArray# :: (# #) -> Array# a emptyArray# _ = case emptyArray of Array ar -> ar {-# NOINLINE emptyArray# #-} — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#102>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAAQwho6d1b6UUOxwKrRTakonYKk3vF7ks5tg1SYgaJpZM4S2lKd> .

[treeowl]

@cartazio, I don't really know. Something that creates and uses a slew of small arrays.