toARec doesn't inline properly

[Philonous]

At the moment toARec is much slower than just using the Rec constructors, IMO that performance penalty is largely unnecessary.

The way toARec works is this pipeline:

Rec f us 
=go=> [Any] 
=listArray=> Array Int Any
=ARec=> ARec f us

There's two problems with this:

• because go is recursive, it can't be inlined, even though the length of the list is statically known
• The intermediate list isn't eliminated

As an example, I benchmarked this code:

mkToARec :: Int -> ARec ElField Fields
mkToARec i= toARec (Field i :& Field i :& Field i :& Field i :&
                  Field i :& Field i :& Field i :& Field i :&
                  Field i :& Field i :& Field i :& Field i :&
                  Field i :& Field i :& Field i :& Field 99 :&
                  RNil)

Here's the relevant part of the core:
https://gist.github.com/Philonous/135480d9016a9b51568a1495dacdf63f

[Philonous]

Replacing the recursive go function with a class inlines better:

class ToARec (us :: [k]) where
  aRecValues :: Rec f us -> [Any]

instance ToARec '[] where
  aRecValues RNil = []
  {-# INLINE aRecValues #-}

instance ToARec us => ToARec (u ': us) where
  aRecValues (x :& xs) = unsafeCoerce x : aRecValues xs
  {-# INLINE aRecValues #-}

-- | Convert a 'Rec' into an 'ARec' for constant-time field access.
toARecFast
  :: forall f ts.
     (NatToInt (RLength ts), ToARec ts)
  => Rec f ts
  -> ARec f ts
toARecFast rs =
  let n = natToInt @(RLength ts)
  in ARec $! Array.listArray (0, n-1) (aRecValues rs)
{-# INLINE toARecFast #-}

criterion outputs:

benchmarking creating/vinyl record                                                                                     
time                 25.50 ns   (25.47 ns .. 25.56 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 25.80 ns   (25.67 ns .. 25.94 ns)
std dev              491.5 ps   (416.9 ps .. 532.1 ps)
variance introduced by outliers: 27% (moderately inflated)
                                                      
benchmarking creating/toARec      
time                 150.8 ns   (150.7 ns .. 151.0 ns)                                                                 
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 150.8 ns   (150.6 ns .. 151.0 ns)                                                                 
std dev              839.8 ps   (625.0 ps .. 1.188 ns)
                                                      
benchmarking creating/toARecFast  
time                 65.87 ns   (65.69 ns .. 66.08 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)    
mean                 65.89 ns   (65.79 ns .. 66.01 ns)                                                                 
std dev              375.3 ps   (284.6 ps .. 478.0 ps) 

Gist with core: https://gist.github.com/Philonous/44930104228ce08977d8d247773da2da

[Philonous]

I have replaced Array with SmallArray# in ARec, which allows us to avoid using lists as intermediate structures, see here: https://github.com/Philonous/Vinyl/blob/arec-performance/Data/Vinyl/ARec/Internal.hs

This plus the type class trick allows ghc to eliminate all intermediate data structures from toARec, which makes creating ARecs nearly as fast as Recs:

benchmarking creating/vinyl record
time                 25.77 ns   (25.67 ns .. 25.86 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 25.77 ns   (25.70 ns .. 25.83 ns)
std dev              217.3 ps   (175.0 ps .. 264.3 ps)

benchmarking creating/Old style ARec with toARec 
time                 151.5 ns   (151.3 ns .. 151.6 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 151.6 ns   (151.4 ns .. 151.8 ns)
std dev              671.9 ps   (570.2 ps .. 842.0 ps)

benchmarking creating/Old style ARec with toARecFast 
time                 65.74 ns   (65.67 ns .. 65.82 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 65.70 ns   (65.61 ns .. 65.88 ns)
std dev              390.0 ps   (213.9 ps .. 743.6 ps)

benchmarking creating/Old style ARec with arec 
time                 65.93 ns   (65.88 ns .. 65.99 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 65.93 ns   (65.87 ns .. 65.99 ns)
std dev              199.4 ps   (167.9 ps .. 243.0 ps)

benchmarking creating/New style ARec with toARec 
time                 75.25 ns   (75.14 ns .. 75.31 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 74.89 ns   (74.72 ns .. 75.04 ns)
std dev              518.9 ps   (464.3 ps .. 581.4 ps)

benchmarking creating/New style ARec with toARecFast 
time                 27.92 ns   (27.88 ns .. 27.96 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 27.92 ns   (27.88 ns .. 27.98 ns)
std dev              151.4 ps   (115.7 ps .. 202.4 ps)

benchmarking creating/New style ARec with arec 
time                 28.36 ns   (28.35 ns .. 28.38 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 28.38 ns   (28.36 ns .. 28.46 ns)
std dev              150.8 ps   (33.87 ps .. 314.5 ps)

Core: https://gist.github.com/Philonous/071f8fda7dfab057b9bbc35980b71d3a

The downside of this approach is that toArec now needs an additional class constraint which makes its type incompatible with the old version

[Philonous]

I have also implemented an alternative interface to construct ARecs to make them feel more like first class citizens.

Current Array-based version:
https://github.com/Philonous/Vinyl/blob/arec-performance/Data/Vinyl/ARec/Old.hs#L129-L146

SmallArray#-based version:
https://github.com/Philonous/Vinyl/blob/arec-performance/Data/Vinyl/ARec/Internal.hs#L137-L173

Usage example (interface is the same for both versions):
https://github.com/Philonous/Vinyl/blob/arec-performance/benchmarks/Bench/ARec.hs#L16-L21

Their performance is identical to using toARecFast (see #153 (comment)). Indeed, they produce identical core (I was confused at first because GHC detects that and eliminates the duplicate and just calls the other one)

[Philonous]

I'd be happy to cut a PR with the changes, feel free to pick and choose:

• Rewrite ARec to be SmallArray#-based
  • This should also save some bytes per ARec, since we don't need to additional fields in the Array constructor)
  • SmallArray# is more efficient for cases with less than 128 fields, which should be practically always for ARec (see here)
• Change toARec to the class-based solution
• Alternative constructors for ARec, names to be decided

[acowley]

I fully support changes! Is the accessors benchmark sufficient to demonstrate the benefits of ARec? Can you confirm that the performance story there stays the same with these alternatives (i.e. FieldRec access is slower for later fields, but constant for ARec)?

EDIT: My point here is that I'm wary of how many options we're providing (nothing to do with your proposed changes), and I'd like the decision making process to be as simple as possible for users. Ideally we'd verify in a benchmark and say: read-only access with more than N fields is faster with ARec. I think the accessors bench is okay, but I'd welcome something stronger if you have any ideas.

I think you are right that SmallArray fits well here.

It looks sensible to add both toARecFast and the new constructors. Maybe leaving toARec is worth it to provide an option without the needed constraint. How does that sound?

[Philonous]

I'm pretty sure that moving from Array to SmallArray# should - if anything - improve performance throughout, but I haven't checked this yet, so I'll do this next.

My hope was to get ARec to perform as fast or faster than Rec in most common cases, so it could be the default choice unless you have "strange" access patterns like consing on elements a lot (or maybe it would be OK to just replace Rec with ARec + pattern synonyms)

That's why I'm rather vexed about element access being so slow (#150). I'll have to look into how SRec manages to beat Rec while ARec flounders.