Avoiding combinatorial blowup in emitted C code

[simondlevy]

Here's a little standalone example showing what I mean, along with a makefile that counts the size of the resulting C file in bytes. Look for the XXX in the Haskell code and you'll be able to reproduce the difference quickly. The Haskell code represents the final stage in the flight-control computation I'm running: mixing the throttle, roll, pitch, and yaw demands to get the four motor outputs. If you try to scale the motor values against their max, you get over 10x the output. For this example I simply treat the demands as external variables. In the actual code, the demands are of course computed using the standard open-loop / closed-loop with sensor fusion, which means that the factor-of-ten blowup yields code too big to compile for my microcontroller
codebloat.zip
.

[ivanperez-keera]

Thanks @simondlevy !

[fdedden]

Thank you @simondlevy! That is a rather interesting problem. Copilot currently only supports limited sharing of streams. I am pretty sure that better sharing would help in this case.

@agoodloe @ivanperez-keera: we might want to discuss this issue during our next meeting.

[ivanperez-keera]

The zip file contains a makefile and a Haskell file. I am adding the Haskell code here, which is the most relevant part, so we can discuss it.

{-# LANGUAGE RebindableSyntax #-}

module Main where

import Language.Copilot
import Copilot.Compile.C99
import Prelude hiding((>))

t :: Stream Float
t  = extern "t" Nothing

r :: Stream Float
r  = extern "r" Nothing

p :: Stream Float
p  = extern "p" Nothing

y :: Stream Float
y  = extern "y" Nothing

rescale :: Stream Float -> Stream Float -> Stream Float


-- XXX Un-comment one of these; comment the other
-- rescale mx v = if mx > 1 then v - mx + 1 else v
rescale mx v = v 

spec = do

  let m1 = t - r + p  - y
  let m2 = t - r - p  + y
  let m3 = t + r + p  + y
  let m4 = t + r - p  - y

  let mmax = foldr fmax m1 [m2, m3, m4] where fmax a b = if a > b then a else b

  let m1' = rescale mmax m1
  let m2' = rescale mmax m2
  let m3' = rescale mmax m3
  let m4' = rescale mmax m4

  trigger "run" true [arg m1', arg m2', arg m3', arg m4'] 

-- Compile the spec
main = reify spec >>= compile "copilot"

[simondlevy]

Thanks for looking into this, guys! I'm still eager to see how far I can go with Copilot, and this issue is the only thing holding me back right now. One of my students got me interested in Rust a few weeks ago as a possible alternative, but after reading up on it, I still think that the Copilot approach is far better for my goals and needs (functional purity, syntactic elegance, targetability to both simulation platforms like UnrealEngine and microcontroller platforms like STM32, etc. etc.)

[ivanperez-keera]

I think this is a duplicate of #297. Essentially, if we had the ability to re-use preprocessing functions, we could define rescale mmax as a Copilot function that becomes a C function in the resulting C code, and then re-use it everywhere, which would decrease the amount of code produced.

[ivanperez-keera]

I'm going to close this in favor of #297 for now, and we can re-evaluate once that one is completed to see if there are any other optimization opportunities.