search

erikd / vector-algorithms

Other
23 stars 15 forks source link

Excessive and insufficient inlining #31

Open sgraf812 opened 3 years ago

sgraf812 commented 3 years ago

While going through https://gitlab.haskell.org/ghc/ghc/-/issues/19283, @bgamari noticed that many call sites in statistics fail to inline vector-algorithm functions, probably because some of them are recursive or just too huge to inline.

I haven't looked at the Core, but the use of Comparison and delegation of sort to sortBy suggests that the comparator won't properly specialise in some cases, namely when the function binding the Comparison isn't inlined.

I think it might be better to mark them INLINABLE and have clients SPECIALISE if needed. Although the Comparison matter might need special handling, by re-introducing it as a type class. This way, call sites pay for specialisation if they want.

That might also substantitally speed up compilation of tests/properties/Tests.hs, which took 20s on my machine, about as long as it took to compile the whole package.

erikd commented 3 years ago

What do you suggest? Should I just change all INLINE pragmas to INLINABLE or something more nuanced?

sgraf812 commented 3 years ago

Yes: INLINABLE, then have a look at the Core in the testsuite to see whether the call sites specialise appropriately. Maybe SPECIALISE key functions to the different vector implementations, although that always has rather huge compile-time overhead. Better do it at call sites, although that requires users to be aware... You can add SPECIALISE pragmas in the testsuite to see when specialisation is impossible because of a missing unfolding. But no way to be sure without looking at Core, I think.

We might see that Comparison doesn't specialise properly, so we might have to get a little creative.

bgamari commented 3 years ago

Ideally code like vector-algorithms would have inspection-testing tests in its testsuite to ensure that the algorithms can be adequately specialised. This would take much of the guess-work out of determining which pragmas are necessary where.

erikd commented 3 years ago

@bgamari Pointers to examples or documentation for inspection-testing ?

arybczak commented 3 years ago

@erikd You can have a look at the testsuite of optics, it uses inspection-testing extensively.

Boarders commented 3 years ago

I'm interested to maybe try tackling this issue if someone can give me some rough guidance on what I am aiming for.