A test suite for fusion

[nomeata]

The vector library puts in lots of effort to ensure that pipelines of vector functions fuse properly, but this is not really tested. In the similar fusion system in text, I found that not all intended fusion actually happened, and used inspection-testing to comprehensively check for fusion.

I believe the vector library would benefit from this as well. I started working on such a test suite, and want to use this issue to discuss the approach.

[nomeata]

I started some work in a fork, see https://github.com/haskell/vector/compare/master...nomeata:fusion-tests?expand=1 for a comparison. This is what it looks like:

~/build/haskell/vector $ cabal new-run fusion-tests
Resolving dependencies...
Build profile: -w ghc-8.2.2 -O1
In order, the following will be built (use -v for more details):
 - inspection-testing-0.4.1 (lib) (configuration changed)
 - vector-0.12.0.1 (lib) (configuration changed)
 - vector-0.12.0.1 (test:fusion-tests) (configuration changed)
Configuring library for inspection-testing-0.4.1..
Preprocessing library for inspection-testing-0.4.1..
Building library for inspection-testing-0.4.1..
Configuring library for vector-0.12.0.1..
Preprocessing library for vector-0.12.0.1..
Building library for vector-0.12.0.1..
Configuring test suite 'fusion-tests' for vector-0.12.0.1..
Warning: The package has an extraneous version range for a dependency on an
internal library: vector -any && ==0.12.0.1, vector -any && ==0.12.0.1, vector
-any && ==0.12.0.1. This version range includes the current package but isn't
needed as the current package's library will always be used.
Preprocessing test suite 'fusion-tests' for vector-0.12.0.1..
Building test suite 'fusion-tests' for vector-0.12.0.1..
[2 of 2] Compiling Main             ( fusion-test/Main.hs, /home/jojo/build/haskell/vector/dist-newstyle/build/x86_64-linux/ghc-8.2.2/vector-0.12.0.1/t/fusion-tests/build/fusion-tests/fusion-tests-tmp/Main.o )
fusion-test/Main.hs:181:1: test_head passed.
fusion-test/Main.hs:181:1: test_null passed.
fusion-test/Main.hs:181:1: test_bang passed.
fusion-test/Main.hs:181:1: test_safe_bang passed.
fusion-test/Main.hs:181:1: test_head passed.
fusion-test/Main.hs:181:1: test_last passed.
fusion-test/Main.hs:181:1: test_unsafeIndex passed.
fusion-test/Main.hs:181:1: test_unsafeHead passed.
fusion-test/Main.hs:181:1: test_unsafeLast passed.
fusion-test/Main.hs:181:1: test_indexM passed.
fusion-test/Main.hs:181:1: test_headM passed.
fusion-test/Main.hs:181:1: test_lastM passed.
fusion-test/Main.hs:181:1: test_unsafeIndexM passed.
fusion-test/Main.hs:181:1: test_unsafeHeadM passed.
fusion-test/Main.hs:181:1: test_unsafeLastM passed.
fusion-test/Main.hs:181:1: test_slice passed.
fusion-test/Main.hs:181:1: test_init passed.
fusion-test/Main.hs:181:1: test_tail passed.
fusion-test/Main.hs:181:1: test_take passed.
fusion-test/Main.hs:181:1: test_drop passed.
fusion-test/Main.hs:181:1: test_unsafeSlice passed.
fusion-test/Main.hs:181:1: test_unsafeInit passed.
fusion-test/Main.hs:181:1: test_unsafeTail passed.
fusion-test/Main.hs:181:1: test_unsafeTake passed.
fusion-test/Main.hs:181:1: test_singleton passed.
fusion-test/Main.hs:181:1: test_replicate passed.
fusion-test/Main.hs:181:1: test_generate passed.
fusion-test/Main.hs:181:1: test_iterateN passed.
fusion-test/Main.hs:181:1: test_unfoldr passed.
fusion-test/Main.hs:181:1: test_unfoldrN passed.
fusion-test/Main.hs:181:1: test_enumFromN passed.
fusion-test/Main.hs:181:1: test_enumFromStepN passed.
fusion-test/Main.hs:181:1: test_enumFromTo passed.
fusion-test/Main.hs:181:1: test_enumFromThenTo passed.
fusion-test/Main.hs:181:1: test_cons passed.
fusion-test/Main.hs:181:1: test_cons passed.
fusion-test/Main.hs:181:1: test_snoc passed.
fusion-test/Main.hs:181:1: test_append_r passed.
fusion-test/Main.hs:181:1: test_append_l passed.
fusion-test/Main.hs:181:1: test_concat passed.
fusion-test/Main.hs:181:1: test_upd passed.
fusion-test/Main.hs:181:1: test_update_l passed.
fusion-test/Main.hs:181:1: test_update_r passed.
fusion-test/Main.hs:181:1: test_update__1 passed.
fusion-test/Main.hs:181:1: test_update__2 passed.
fusion-test/Main.hs:181:1: test_update__3 passed.
fusion-test/Main.hs:181:1: test_unsafeUpd passed.
fusion-test/Main.hs:181:1: test_unsafeUpdate_l passed.
fusion-test/Main.hs:181:1: test_unsafeUpdate_r passed.
fusion-test/Main.hs:181:1: test_unsafeUpdate__1 passed.
fusion-test/Main.hs:181:1: test_unsafeUpdate__2 passed.
fusion-test/Main.hs:181:1: test_unsafeUpdate__3 passed.
fusion-test/Main.hs:181:1: test_accum passed.
fusion-test/Main.hs:181:1: test_accumulate_l passed.
fusion-test/Main.hs:181:1: test_accumulate_r passed.
fusion-test/Main.hs:181:1: test_accumulate__1 passed.
fusion-test/Main.hs:181:1: test_accumulate__2 passed.
fusion-test/Main.hs:181:1: test_accumulate__3 passed.
fusion-test/Main.hs:181:1: test_unsafeAccum passed.
fusion-test/Main.hs:181:1: test_unsafeAccumulate_l passed.
fusion-test/Main.hs:181:1: test_unsafeAccumulate_r passed.
fusion-test/Main.hs:181:1: test_unsafeAccumulate__1 passed.
fusion-test/Main.hs:181:1: test_unsafeAccumulate__2 passed.
fusion-test/Main.hs:181:1: test_unsafeAccumulate__3 passed.
fusion-test/Main.hs:181:1: test_reverse passed.
fusion-test/Main.hs:181:1: test_backpermute passed.
fusion-test/Main.hs:181:1: test_unsafeBackpermute passed.
fusion-test/Main.hs:181:1: test_indexed passed.
fusion-test/Main.hs:181:1: test_map passed.
fusion-test/Main.hs:181:1: test_imap passed.
fusion-test/Main.hs:181:1: test_concatMap passed.
inspection testing successful
      expected successes: 71
Linking /home/jojo/build/haskell/vector/dist-newstyle/build/x86_64-linux/ghc-8.2.2/vector-0.12.0.1/t/fusion-tests/build/fusion-tests/fusion-tests ...

It is a relatively tedious process, including having to copy all fusion-related rules, so before I continue I'd like some discussion if this is wanted.

Some findings so far:

• Monadic functions are not good producers.
• construct and constructN do not fuse.
• Bulk updates and accumulators are good consumers (in all arguments), but not good producers.
• reverse is a good producer, but not a good consumer
• backpermute is only a good consumer in the second argument, but not the first and not a good producer
• concatMap is a good consumer and producer, but a good producer in the argument does not fuse away.

Any surprises so far?

[nomeata]

@dcoutts This is what we briefly talked about this morning.

[nomeata]

Currently, this tests fusion only against fromList and toList, two “known good consumers/producers”. It might be more interesting to create random expressions and pipelines.

I could imagine a list with entries like

[ ('map, O ~> V ~> F ~> V)
, ('reverse,  V ~> F)
, ('backpermute, V ~> F ~> V)
]

that specify the fusion-behavior of the function’s arguments and return type (F = fusing vector, V = non-fusing vector, O = other type), and then lego-like putting these pieces together to create big pipelines (or even trees – some functions can fuse with multiple arguments) to create more interesting test cases.

And maybe we can put these annotations somehow into the haddocks of the function, to publicly document the fusion behaviour.

[cartazio]

Ok, this is very cool! I’m in the middle of holidays and fam stuff but I’m doing some prelim stuff to vector. This is a great little bunch. I’ll carve some time soon to work through what you’ve put down.

…

On Sat, Nov 17, 2018 at 9:58 AM Joachim Breitner ***@***.***> wrote: Currently, this tests fusion only against fromList and toList, two “known good consumers/producers”. It might be more interesting to create random expressions and pipelines. I could imagine a list with entries like [ ('map, O ~> V ~> F ~> V) , ('reverse, V ~> F) , ('backpermute, V ~> F ~> V) ] that specify the fusion-behavior of the function’s arguments and return type (F = fusing vector, V = non-fusing vector, O = other type), and then lego-like putting these pieces together to create big pipelines (or even trees – some functions can fuse with multiple arguments) to create more interesting test cases. And maybe we can put these annotations somehow into the haddocks of the function, to publicly document the fusion behaviour. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#229 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAAQwh_jZAKAyHUiiugjW2mzgHX22oxiks5uwCQegaJpZM4YncTD> .

[cartazio]

i'll pull this back onto my todo list in the next month or so,

[cartazio]

this should be done after this current release this winter

[Shimuuar]

I'm copying @Bodigrim's comment #389 (comment)

Fusion tests in text were generated using my fork of inspection-testing: https://github.com/Bodigrim/inspection-testing/tree/6b99b613b30fc2216f391db08b857a54352e4f48/examples/text-api
It should be possible to adapt the generator to vector.