Exponentiation primop

[kozross]

Describe the feature you'd like

This is a follow-on from #6335, and relates to prior requests in #4168 and here, as well as #6344 (as it used exponentiation, both modular and not, internally).

Currently, if you want exponentiation, you have to resort to exponentiation by squaring. While for arbitrary semigroups (or monoids, or groups), this is indeed the best we can do, in the specific case of BuiltinInteger (which is ultimately what is interesting to us here), we lose considerably. Thus, we propose that a builtin non-modular exponentiation operation be added, allowing us to provide this functionality efficiently, while also answering some community requests for functionality.

Firstly, even if we just compare a typical exponentiation-by-squaring implementation to Haskell's built-in ^ for Integer, we see we're falling behind, even on small numbers:

      bgroup
        "exp"
        [ bench "naive" . nf (naiveExp 7) $ 1024,
          bench "expBySquaring" . nf (expBySquaring 7) $ 1024
        ]

-- Produces this result:
--     naive:         OK
--      582  ns ±  47 ns, 1.2 KB allocated,   0 B  copied,  33 MB peak memory
--    expBySquaring: OK
--      630  ns ±  50 ns, 1.2 KB allocated,   0 B  copied,  33 MB peak memory

This would only become more of a problem the larger the numbers become.

Secondly, there are notable optimization paths we could take. Firstly, there is the classic case where raising 2 to a positive power is in fact a shift. This is not an optimization GHC seems to perform for Integer at least:

      bgroup
        "power-two"
        [ bench "naive" . nf ((2 :: Integer) ^) $ (10 :: Integer),
          bench "shift" . nf (unsafeShiftL (2 :: Integer)) $ 10
        ]
-- Produces this result
--     naive:         OK
--      73.6 ns ± 6.4 ns, 191 B  allocated,   0 B  copied,  33 MB peak memory
--    shift:         OK
--      27.3 ns ± 2.6 ns, 127 B  allocated,   0 B  copied,  33 MB peak memory

We also noticed that if we know an exponent is an exact power of two, regardless of base, we could beat exponentiation:

{-# INLINE naiveExp #-}
naiveExp :: Integer -> Integer -> Integer
naiveExp = (^)

{-# INLINE kSquare #-}
kSquare :: Integer -> Int -> Integer
kSquare x = go
  where
    go :: Int -> Integer
    go k
      | k == 0 = 1
      | k == 1 = x
      | otherwise = sqrInteger (go (k - 1))

-- Given these benchmarks
b = bgroup
        "exp"
        [ bench "naive" . nf (naiveExp 7) $ 1024,
          bench "k-square" . nf (kSquare 7) $ 10
        ]
-- Produces this result
--     naive:         OK
--      582  ns ±  47 ns, 1.2 KB allocated,   0 B  copied,  33 MB peak memory
--    k-square:      OK
--      172  ns ±  11 ns, 682 B  allocated,   0 B  copied,  33 MB peak memory

We can use both of these facts to gain significant advantage on Integer exponentiation by making further observations:

1. For any even $i$, we can separate it into $2^k \cdot j$, where $j$ is odd, rapidly (effectively by counting trailing zeroes and shifting right)
2. When we have $(2^k \cdot x)^y$, we can break it down into $2^{ky} \cdot x^y$ (making use of shifting and reducing the work in exponentiation)
3. When we have $x^{2^{\ell}y}$, we can break it down into $x^{2^{\ell}} \cdot x^y$ (making use of k-squaring and reducing the work in exponentiation)
4. Observations 2 and 3 combine (with big reductions)

These optimizations require low analysis costs (a trailing zero count effectively), and would work for most inputs (assuming a completely random choice of base or exponent). Further than this, if we were to implement a non-modular exponentiation operation directly, a future move away from GHC 8.10 would permit us to implement this operation mutably (requiring the new ghc-bignum interface), which would significantly improve our performance by requiring only one up-front allocation for the result.

This operation would not only answer these (in some cases long-standing) concerns, but also optimize a useful operation.

Describe alternatives you've considered

The current options consist of either:

• Exponentiation by squaring; or
• Trying a similar strategy to what we described above, using CIP-121, CIP-122 and CIP-123 primitives

The first has the inefficiencies we described, while the second unfortunately is drowned out by the fact that CIP-121 conversions are currently quadratic, and even with ghc-bignum's interface, cannot be made better than linear due to pinning issues. Both of the issues linked above essentially make this point, as in their use cases, these inefficiencies are unacceptable.

[effectfully]

@kwxm I think you were going to respond to this one? I'll triage it afterwards.

[effectfully]

@kwxm a gentle reminder.

[kwxm]

We've considered adding an integer exponentiation in the past but decided against it for a number of reasons.

• We'd have to be very careful with costing: we never want to allow anyone to calculate 100000¹⁰⁰⁰⁰⁰⁰, for example.
• The use cases seemed rather limited: will anonye ever want to caculate 19⁷⁹ or similar things?
• It's qutie easy to implement exponentiaton in languages which compile to Plutus Core, although this may not give optimum performance.

It is plausible that calculating powers of two might be something that people might particularly want to do, but this may be more feasible now that we have the recently-added bytestring builtins, and will become evenmore feasible if we get more efficent integer/bytestring conversions once we've moved on from GHC 8.xx. Also, we're currently adding a modular exponentiation builtin, and careful use of that with a large modulus would be another way to calculate standard integer powers. (Note also that if we ever do want a normal exponentiation function we could perhaps include it in expModInteger using a modulus of zero, which currently causes an error).

Another issue is that it's difficult to take account of special cases in costing: we have to cost the worst case of builtin evaluations, so if some case such as calculating a power of 2 can be implemented particularly efficiently, we'd still have to charge for the non-optimal case: the function might run more quickly in certain cases, but this wouldn't be reflected in the charges paid by the user.

Given these issues we feel that there's probably not a compelling case for adding integer exponentiation at this time. If there's sufficient community demand then we might revisit this in the future.

[effectfully]

I'm not sensing a definite "won't do" here, so I'm going to retriage this as "Low priority" (and "won't do" is better known as closing the issue anyway).

Another issue is that it's difficult to take account of special cases in costing: we have to cost the worst case of builtin evaluations, so if some case such as calculating a power of 2 can be implemented particularly efficiently, we'd still have to charge for the non-optimal case: the function might run more quickly in certain cases, but this wouldn't be reflected in the charges paid by the user.

I think from the implementation point of view this should be fairly straightforward, want me to provide a proof-of-concept? From the spec point of view it's gonna be hard, I'm sure.

[kwxm]

I think from the implementation point of view this should be fairly straightforward, want me to provide a proof-of-concept?

Not really! I think it'd be problematic because we'd have to match up special cases in the costing with special cases in the implementation and keep them synchronised. We already do a certain amount of this kind of thing and it's a bit annoying. You also have to add extra logic to detect the special case before you call the function, which will add extra overhead. In addition we'd need different sets of costing benchmarks for the different special cases, and again these would have to be kept in sync with the implementation.

[effectfully]

OK, yes, that's what I foolishly called "fairly straightforward".

Given some additional feedback elsewhere, it seems like my original assessment of this not being a "won't do" is wrong. I'm closing the issue then, we'll reopen it if ever want to reconsider adding such a builtin.

@kozross thank you for the report and sorry we aren't able to fulfill your request.