search

Mikolaj / horde-ad

Higher Order Reverse Derivatives Efficiently - Automatic Differentiation library based on the paper "Provably correct, asymptotically efficient, higher-order reverse-mode automatic differentiation"
BSD 3-Clause "New" or "Revised" License
32 stars 6 forks source link

Unpack r in Delta datatypes via backpack, class or otherwise #23

Open Mikolaj opened 2 years ago

Mikolaj commented 2 years ago

This is low priority, because it's going to be a few (dozen) percent speedup (and a slight space saving and improved storage locality, which may be more important in real world situations). See https://hackage.haskell.org/package/unpacked-containers for a similar endeavour and https://twitter.com/kmett/status/982078739482738688 for a benchmarking anecdote.

I hope this now has a trivial solution and I was just not paying attention. Parameterized datatype not being a zero-cost abstraction is embarrassing. (Of course we could easily avoid the embarrassment by not implementing the datatype field upacking optimization in GHC, which few, if any, programming languages support.)

Mikolaj commented 2 years ago

The fact that DeltaS requires a GADT makes this optimization problematic for the S rank (BTW, it would be interesting to benchmark S rank vs rank 1 and 2). The values contained in DeltaS constructors are polymorphic (vs shape) and so have to be boxed and so can't be unpacked. However, we could instead keep in DeltaS untyped tensors or even the unwrapped monomorphic (once r is fixed) representations of shaped tensors and only retain the shapes in the DeltaS GADT. Whether one can unpack monomorphic values into GADT constructors is to be verified.