Make 'length' fusible - #307

Sounds very awesome! I’m going to make sure I look at this soon , though just in case I miss anything I’ll ask a few other folks to have a look too! (Lots of chaos in nyc etc this week )

Cc @sjakobi @Bodigrim @emilypi

Alright! Stay safe.

I simplified the test: https://gist.github.com/gksato/157a98da55c643f15760720383419b4b

I finally go to review this PR. I digged through code and now I mildly confused. Does original loop stream, clone, length, unsafeCopy still exists? It seems stream was rewritten in meantime to use Bundle.

@gksato did you try to just use stream for length definition?

P.S. this just illustrates how badly we need tests for fusion (#229). So far our answer to question does it fuse is "hopes and prayers" which is clearly not enough

@gksato could you possibly submit a test for this, using inspection-testing?

@Shimuuar Now I get the situation well. Just rewriting back

length = Bundle.length . stream

does work with GHC 8.8.3. However it doesn't work with GHC 8.0.2, the version that was current at the time a811a86 was introduced, since there is, formally, a loop among length, clone, unsafeCopy, stream:

-- | /O(1)/ Yield the length of the vector
length :: Vector v a => v a -> Int
{-# INLINE length #-}
length = Bundle.length . stream

-- | /O(1)/ Convert a vector to a 'Bundle'
stream :: Vector v a => v a -> Bundle v a
{-# INLINE_FUSED stream #-}
stream v = Bundle.fromVector v

{-# RULES
...

"New.unstream/stream [Vector]" forall v.
  New.unstream (stream v) = clone v

...  #-}

-- | Convert a vector to an initialiser which, when run, produces a copy of
-- the vector.
clone :: Vector v a => v a -> New v a
{-# INLINE_FUSED clone #-}
clone v = v `seq` New.create (
  do
    mv <- M.new (length v)
    unsafeCopy mv v
    return mv)

-- | /O(n)/ Copy an immutable vector into a mutable one. The two vectors must
-- have the same length. This is not checked.
unsafeCopy
  :: (PrimMonad m, Vector v a) => Mutable v (PrimState m) a -> v a -> m ()
{-# INLINE unsafeCopy #-}
unsafeCopy dst src = UNSAFE_CHECK(check) "unsafeCopy" "length mismatch"
                                         (M.length dst == length src)
                   $ (dst `seq` src `seq` basicUnsafeCopy dst src)

Since no New.unstream appears at the inline sites of length, this loop is only formal and not actual; I guess that's why reverting a811a86 worked with GHC 8.8.3. However older GHCs seemingly doesn't detect the fact that the loop is not essential.

@Bodigrim I'm skimming through inspection-testing and #229. Wait a moment...

Copy/unsafeCopy/clone require vector to be materialized anyway. So we don't lose anything by switching to basicLength. LGTM

@gksato Could you please add info from #307 (comment) to commit message?

@Bodigrim @lehins what do you think about this PR?

@gksato Could you please add info from #307 (comment) to commit message?

@Shimuuar Oops. I've forgotten to check this PR. Can I reword the commit and force-push? I'll not change the content.

Please do

@Shimuuar I've done it!

Did you look into inspection-testing by chance? Adding even single test would be great contribution since adding more will become relative straightforward.

In fact, I was just puzzled by the tests in #229, because they include test_length and the comment reports that all the tests were successful. I now noticed that test_length was just defined as a test and was not included in the test to be executed.

Here's a small fusion test for this pull request. I picked up @nomeata's work on #229 and modified a bit:

• https://github.com/gksato/vector/tree/fusion-tests
  commit e9e4e8b
  on branch gksato:fusion-tests.
  This is the simple rebase of nomeata:fusion-tests onto the parent of this pull request.
• https://github.com/gksato/vector/tree/fusion-tests-length-failure
  commit 75cf13c
  on branch gksato:fusion-tests-length-failure.
  Added, to gksato:fusion-tests, the test for length. The test fails.
• https://github.com/gksato/vector/tree/fusion-tests-length-success
  commit 4b398ac
  on branch gksato:fusion-tests-length-success.
  This is a merge of gksato:fusion-tests-length-failure and this PR.
  The test passes.

I wasn't really sure it was OK to merge a big mass of tests with this pull request, I left it separate branches. If you know a better-looking way to present these to you, please let me know!

I've merged PR, thanks!

It would be better to submit tests as separate PR. It will probably require several iterations to get into working order and I don't think it makes sense to keep this PR unmerged.

P.S. Didn't look at tests yet