Optimize division-related Integer operations

[kozross]

Describe the feature you'd like

The division-related primops in Plutus are essentially direct copies of their GHC counterparts. While this is a good thing in general, there are some inefficiencies we inherit as a result of this.

The biggest example is that (for positive values at least), quot operations do not reduce to right shifts, even on constant arguments:

     bgroup
        "quotient"
        [ bench "naive with constant" . nf (quot (170141183460469231731687303715 :: Integer)) $ 1073741824,
          bench "shift with constant" . nf (unsafeShiftR (170141183460469231731687303715 :: Integer)) $ 30
        ]
-- Produces the following result
--   quotient
--    naive with constant: OK
--      32.1 ns ± 2.4 ns, 143 B  allocated,   0 B  copied,  33 MB peak memory
--    shift with constant: OK
--      17.3 ns ± 1.5 ns,  86 B  allocated,   0 B  copied,  33 MB peak memory

This is a non-trivial difference in both time and space, and while the numbers appear large, they are not particularly big for Integers. This inefficiency extends to rem operations, which could be implemented with masking.

While this appears to be of minor benefit, we observe that quot n (2 ^ k * d) = quot (quot n (2 ^ k)) d for positive numbers. Furthermore, as per #6390 , we can 'decompose' numbers which have a power of 2 in their prime factorization fairly easily (counting trailing bits), which, combined with the above observation, could give us considerable performance. This also relates to the cases raised in #6390, just in the other direction.

Similar techniques could be applied to div and mod as well (or rather, our definitions of them) to produce improvements.

Describe alternatives you've considered

Currently, these optimizations cannot be obtained. Even using CIP-121, CIP-122 and CIP-123 operations, due to the currently-quadratic cost of CIP-121 conversions, this would drown out any benefits we're likely to see. Even though CIP-121 operations could be linear, this would still be an unavoidable pair of copies, due to pinnedness issues in ghc-bignum.

[effectfully]

This is a non-trivial difference in both time and space

It's very likely a drop in the ocean, because you don't just execute quot at Plutus runtime, you execute this:

monster

BuiltinExpectArgument
  (\ (v_i3DiB :: CekValue DefaultUni DefaultFun ()) ->
     case v_i3DiB of {
       __DEFAULT -> lvl136_r3JLL;
       VCon val_i3GRr ->
         let! { ValueOf uniAct_s3J31 x7_s3J32 ~
         <- val_i3GRr `cast` <Co:9> :: ... } in
         case uniAct_s3J31 `cast` <Co:9> :: ...
         of wild5_i3DiQ {
           __DEFAULT -> <failure>
           DefaultUniInteger co6_i3DiR ->
             BuiltinExpectArgument
               (\ (v1_i3Dj3
                     :: CekValue
                          DefaultUni DefaultFun ()) ->
                  case v1_i3Dj3 of {
                    __DEFAULT -> <failure>;
                    VCon val1_X3 ->
                      let! { ValueOf uniAct1_s3J3a
                                     x11_s3J3b ~
                      <- val1_X3 `cast` <Co:9> :: ... } in
                      case uniAct1_s3J3a
                           `cast` <Co:9> :: ...
                      of wild8_i3Dji {
                        __DEFAULT -> <failure>
                        DefaultUniInteger co9_i3Djj ->
                          let {
                            eta17_i3DiX :: CostStream
                            eta17_i3DiX
                              = let! { __DEFAULT ~ ww_i1jEI
                                <- $wmemoryUsageInteger
                                     (x7_s3J32
                                      `cast` <Co:3> :: ...) } in
                                CostLast ww_i1jEI } in
                          let {
                            mem5_i3Djo :: CostStream
                            mem5_i3Djo
                              = let! { __DEFAULT ~ ww_i1jEI
                                <- $wmemoryUsageInteger
                                     (x11_s3J3b
                                      `cast` <Co:3> :: ...) } in
                                CostLast ww_i1jEI } in
                          join {
                            $j4_i3Dju
                              :: ExBudgetStream
                                 -> BuiltinRuntime
                                      (CekValue
                                         DefaultUni
                                         DefaultFun
                                         ())
                            $j4_i3Dju (nt_i3Djv
                                         :: ExBudgetStream)
                              = let! { __DEFAULT ~ nt1_i3Djw
                                <- nt_i3Djv } in
                                BuiltinCostedResult
                                  nt1_i3Djw
                                  (join {
                                     $j5_i3DjF
                                       :: BuiltinResult
                                            (CekValue
                                               DefaultUni
                                               DefaultFun
                                               ())
                                     $j5_i3DjF
                                       = case x11_s3J3b
                                              `cast` <Co:3> :: ...
                                         of wild9_i3DjP {
                                           IS x12_i3DjQ ->
                                             case x12_i3DjQ
                                             of {
                                               __DEFAULT ->
                                                 let! { __DEFAULT ~ conrep180_i3DjH
                                                 <- integerQuot
                                                      (x7_s3J32
                                                       `cast` <Co:3> :: ...)
                                                      wild9_i3DjP } in
                                                 let! { UnsafeRefl co12_i3DjN ~
                                                 <- unsafeEqualityProof } in
                                                 BuiltinSuccess
                                                   (VCon
                                                      ((ValueOf
                                                          ($WDefaultUniInteger
                                                           `cast` <Co:50> :: ...)
                                                          conrep180_i3DjH)
                                                       `cast` <Co:14> :: ...));
                                               0# ->
                                                 case divZeroError
                                                 of wild11_00 {
                                                 }
                                             };
                                           IP x12_i3DjT ->
                                             let! { __DEFAULT ~ conrep180_i3DjH
                                             <- integerQuot
                                                  (x7_s3J32
                                                   `cast` <Co:3> :: ...)
                                                  wild9_i3DjP } in
                                             let! { UnsafeRefl co12_i3DjN ~
                                             <- unsafeEqualityProof } in
                                             BuiltinSuccess
                                               (VCon
                                                  ((ValueOf
                                                      ($WDefaultUniInteger
                                                       `cast` <Co:50> :: ...)
                                                      conrep180_i3DjH)
                                                   `cast` <Co:14> :: ...));
                                           IN x12_i3DjV ->
                                             let! { __DEFAULT ~ conrep180_i3DjH
                                             <- integerQuot
                                                  (x7_s3J32
                                                   `cast` <Co:3> :: ...)
                                                  wild9_i3DjP } in
                                             let! { UnsafeRefl co12_i3DjN ~
                                             <- unsafeEqualityProof } in
                                             BuiltinSuccess
                                               (VCon
                                                  ((ValueOf
                                                      ($WDefaultUniInteger
                                                       `cast` <Co:50> :: ...)
                                                      conrep180_i3DjH)
                                                   `cast` <Co:14> :: ...))
                                         } } in
                                   case x11_s3J3b
                                        `cast` <Co:3> :: ...
                                   of {
                                     IS x12_i3DjY ->
                                       case x12_i3DjY of {
                                         __DEFAULT ->
                                           jump $j5_i3DjF;
                                         0# -> lvl92_r3JIJ
                                       };
                                     IP x12_i3Dk4 ->
                                       jump $j5_i3DjF;
                                     IN x12_i3Dk6 ->
                                       jump $j5_i3DjF
                                   }) } in
                          case runCpu_i3Diz
                                 eta17_i3DiX mem5_i3Djo
                          of wild9_i3Dk8 {
                            CostLast bx_i3Dk9 ->
                              case runMem_i3DiA
                                     eta17_i3DiX mem5_i3Djo
                              of wild10_i3Dkb {
                                CostLast bx1_i3Dkc ->
                                  jump $j4_i3Dju
                                    (ExBudgetLast
                                       (ExBudget
                                          bx_i3Dk9
                                          bx1_i3Dkc));
                                CostCons ipv_i3Dke
                                         ipv1_i3Dkf ->
                                  jump $j4_i3Dju
                                    (zipCostStreamGo
                                       wild9_i3Dk8
                                       wild10_i3Dkb)
                              };
                            CostCons ipv_i3Dki
                                     ipv1_i3Dkj ->
                              jump $j4_i3Dju
                                (zipCostStreamGo
                                   wild9_i3Dk8
                                   (runMem_i3DiA
                                      eta17_i3DiX
                                      mem5_i3Djo))
                          }
                      }
                  })
         }
     })) } in

Most of that is pretty cheap, but is still overhead and I really doubt that 15 extra nanoseconds gonna make a difference.

I think this is very low-priority, so I'm going to triage it as such.