SCP-2436: reorder constructors according to frequency #3435
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
|
So it seems it's slightly better in some cases and slightly worse in others? At this point it's hard to provide empirical evidence of what ordering is faster because we don't have a lot of contracts yet. It's definitely worth re-visiting when we have more contracts/know more about the actual use cases. So it's good to put the note in there. |
thealmarty
approved these changes
Jun 25, 2021
|
Yeah, it's unclear that it's noticeable at all, looks like random noise. But I think it's good to have the note there so we think about it in future too. |
bezirg
approved these changes
Jun 26, 2021
kwxm
reviewed
Jun 28, 2021
There was a problem hiding this comment.
This looks entirely harmless. For completeness, here's the number of times the compute step of the CEK machine encounters each constructor during execution of all the benchmark examples. I wanted this data for documentation purposes anyway, so I thought I might as well do it now.
Validation:
Script Total Var LamAbs Apply Force Delay Const Builtin
----------------------------------------------------------------------------------------------
crowdfunding-success-1 22475 28.49% 28.25% 27.79% 9.28% 4.74% 0.79% 0.65%
crowdfunding-success-2 22475 28.49% 28.25% 27.79% 9.28% 4.74% 0.79% 0.65%
crowdfunding-success-3 22475 28.49% 28.25% 27.79% 9.28% 4.74% 0.79% 0.65%
currency-1 21389 28.63% 27.98% 27.53% 9.60% 4.91% 0.75% 0.60%
currency-2 28344 29.76% 26.93% 27.33% 9.83% 5.04% 0.57% 0.55%
escrow-redeem_1-1 31410 29.26% 27.39% 27.57% 9.51% 5.07% 0.61% 0.58%
escrow-redeem_1-2 31410 29.26% 27.39% 27.57% 9.51% 5.07% 0.61% 0.58%
escrow-redeem_2-1 36665 29.42% 27.25% 27.54% 9.56% 5.05% 0.60% 0.58%
escrow-redeem_2-2 36665 29.42% 27.25% 27.54% 9.56% 5.05% 0.60% 0.58%
escrow-redeem_2-3 36665 29.42% 27.25% 27.54% 9.56% 5.05% 0.60% 0.58%
escrow-refund-1 15999 27.75% 28.54% 27.88% 9.16% 5.22% 0.80% 0.66%
future-increase-margin-1 21389 28.63% 27.98% 27.53% 9.60% 4.91% 0.75% 0.60%
future-increase-margin-2 28344 29.76% 26.93% 27.33% 9.83% 5.04% 0.57% 0.55%
future-increase-margin-3 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-increase-margin-4 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-increase-margin-5 41551 29.45% 27.36% 27.58% 9.39% 5.23% 0.49% 0.51%
future-increase-margin-6 63549 30.03% 27.05% 27.47% 9.54% 5.02% 0.41% 0.50%
future-pay-out-1 21389 28.63% 27.98% 27.53% 9.60% 4.91% 0.75% 0.60%
future-pay-out-2 28344 29.76% 26.93% 27.33% 9.83% 5.04% 0.57% 0.55%
future-pay-out-3 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-pay-out-4 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-pay-out-5 59210 30.03% 27.05% 27.47% 9.52% 5.06% 0.38% 0.49%
future-settle-early-1 21389 28.63% 27.98% 27.53% 9.60% 4.91% 0.75% 0.60%
future-settle-early-2 28344 29.76% 26.93% 27.33% 9.83% 5.04% 0.57% 0.55%
future-settle-early-3 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-settle-early-4 47930 29.90% 26.88% 27.40% 9.71% 5.00% 0.56% 0.54%
future-settle-early-5 44385 29.56% 27.34% 27.55% 9.44% 5.13% 0.46% 0.52%
game-sm-success-1 31668 29.30% 27.65% 27.67% 9.37% 4.87% 0.58% 0.58%
game-sm-success-2 22275 29.06% 27.56% 27.42% 9.74% 4.88% 0.75% 0.58%
game-sm-success-3 48817 29.96% 27.00% 27.41% 9.65% 4.99% 0.47% 0.51%
game-sm-success-4 25938 29.18% 27.51% 27.43% 9.73% 4.80% 0.76% 0.59%
game-sm-success_2-1 31668 29.30% 27.65% 27.67% 9.37% 4.87% 0.58% 0.58%
game-sm-success_2-2 22275 29.06% 27.56% 27.42% 9.74% 4.88% 0.75% 0.58%
game-sm-success_2-3 48817 29.96% 27.00% 27.41% 9.65% 4.99% 0.47% 0.51%
game-sm-success_2-4 25938 29.18% 27.51% 27.43% 9.73% 4.80% 0.76% 0.59%
game-sm-success_2-5 49838 30.01% 26.96% 27.40% 9.67% 4.99% 0.46% 0.51%
game-sm-success_2-6 25938 29.18% 27.51% 27.43% 9.73% 4.80% 0.76% 0.59%
multisig-sm-01 32782 29.23% 27.68% 27.73% 9.21% 5.09% 0.52% 0.54%
multisig-sm-02 32811 29.28% 27.72% 27.81% 9.12% 4.99% 0.53% 0.56%
multisig-sm-03 33426 29.32% 27.69% 27.81% 9.12% 4.97% 0.53% 0.56%
multisig-sm-04 34041 29.36% 27.67% 27.82% 9.11% 4.96% 0.52% 0.56%
multisig-sm-05 42402 30.01% 27.05% 27.55% 9.47% 4.94% 0.45% 0.54%
multisig-sm-06 36227 29.34% 27.58% 27.75% 9.23% 5.00% 0.54% 0.57%
multisig-sm-07 32811 29.28% 27.72% 27.81% 9.12% 4.99% 0.53% 0.56%
multisig-sm-08 33426 29.32% 27.69% 27.81% 9.12% 4.97% 0.53% 0.56%
multisig-sm-09 34041 29.36% 27.67% 27.82% 9.11% 4.96% 0.52% 0.56%
multisig-sm-10 42402 30.01% 27.05% 27.55% 9.47% 4.94% 0.45% 0.54%
ping-pong-1 25396 29.11% 27.67% 27.71% 9.32% 5.02% 0.57% 0.59%
ping-pong-2 25396 29.11% 27.67% 27.71% 9.32% 5.02% 0.57% 0.59%
ping-pong_2-1 16887 27.81% 28.56% 27.88% 9.14% 5.27% 0.70% 0.64%
prism-1 18169 28.87% 27.68% 27.38% 9.79% 5.00% 0.71% 0.57%
prism-2 35083 29.32% 27.54% 27.49% 9.56% 4.95% 0.59% 0.54%
prism-3 34673 29.72% 27.02% 27.29% 9.86% 4.99% 0.59% 0.53%
pubkey-1 15576 28.17% 28.28% 27.78% 9.31% 5.03% 0.78% 0.65%
stablecoin_1-1 56718 30.32% 26.02% 28.97% 8.46% 4.03% 0.81% 1.38%
stablecoin_1-2 21847 28.99% 27.53% 27.44% 9.72% 4.95% 0.79% 0.59%
stablecoin_1-3 64244 30.58% 25.58% 29.26% 8.30% 3.85% 0.86% 1.58%
stablecoin_1-4 23609 29.07% 27.50% 27.37% 9.79% 4.93% 0.77% 0.57%
stablecoin_1-5 76654 30.95% 24.72% 29.90% 7.90% 3.52% 1.00% 2.00%
stablecoin_1-6 24885 29.15% 27.50% 27.41% 9.74% 4.85% 0.78% 0.57%
stablecoin_2-1 56718 30.32% 26.02% 28.97% 8.46% 4.03% 0.81% 1.38%
stablecoin_2-2 21847 28.99% 27.53% 27.44% 9.72% 4.95% 0.79% 0.59%
stablecoin_2-3 64244 30.58% 25.58% 29.26% 8.30% 3.85% 0.86% 1.58%
stablecoin_2-4 23609 29.07% 27.50% 27.37% 9.79% 4.93% 0.77% 0.57%
token-account-1 20345 28.55% 28.00% 27.56% 9.57% 4.96% 0.75% 0.61%
token-account-2 23570 29.34% 27.29% 27.39% 9.75% 5.04% 0.63% 0.56%
token-account-3 30057 29.38% 27.23% 27.41% 9.71% 5.13% 0.58% 0.55%
uniswap-1 23477 28.76% 27.94% 27.47% 9.67% 4.83% 0.75% 0.58%
uniswap-2 41111 30.58% 26.23% 27.31% 9.90% 4.95% 0.46% 0.57%
uniswap-3 25761 28.88% 27.88% 27.39% 9.75% 4.80% 0.74% 0.56%
uniswap-4 28986 29.48% 27.32% 27.26% 9.88% 4.89% 0.65% 0.52%
uniswap-5 122404 31.71% 24.53% 29.03% 8.57% 3.90% 0.63% 1.63%
uniswap-6 40111 29.45% 27.29% 27.28% 9.92% 4.70% 0.80% 0.56%
uniswap-7 87114 31.46% 25.20% 28.89% 8.62% 3.70% 0.66% 1.48%
uniswap-8 37729 29.52% 27.23% 27.33% 9.88% 4.65% 0.81% 0.58%
vesting-1 29819 29.50% 27.25% 27.51% 9.56% 5.09% 0.53% 0.56%
marlowe/trustfund-1 66186 28.50% 27.64% 27.59% 9.43% 5.81% 0.49% 0.54%
marlowe/trustfund-2 45251 28.60% 27.20% 27.54% 9.70% 5.85% 0.41% 0.69%
marlowe/zerocoupon-1 70640 28.91% 26.98% 27.40% 9.77% 5.97% 0.40% 0.58%
marlowe/zerocoupon-2 39275 27.89% 27.73% 27.09% 10.05% 6.35% 0.44% 0.46%
There's quite a bit of repetition for scripts that only differ in wallet addresses (and maybe other hashes), but I just left them in.
These confirm the ordering in this PR: it seems pretty clear that Var, LamAbs and Apply are the most important, but the ordering probably doesn't matter a lot apart from that.
Nofib:
Script Total Var LamAbs Apply Force Delay Const Builtin
----------------------------------------------------------------------------------------------
clausify-formula1 2280764 28.27% 32.52% 29.73% 5.56% 3.81% 0.00% 0.11%
clausify-formula2 2807130 28.36% 32.39% 29.72% 5.61% 3.79% 0.00% 0.13%
clausify-formula3 7796706 28.37% 32.36% 29.72% 5.62% 3.79% 0.00% 0.13%
clausify-formula4 10174203 29.73% 30.73% 29.56% 6.18% 3.46% 0.00% 0.35%
clausify-formula5 51115918 28.19% 32.57% 29.73% 5.56% 3.85% 0.00% 0.10%
knights-4x4 4145714 32.84% 24.35% 29.75% 7.79% 2.87% 0.67% 1.74%
knights-6x6 12875754 34.24% 23.84% 29.43% 8.03% 2.75% 0.22% 1.49%
knights-8x8 22038341 34.47% 23.76% 29.31% 8.13% 2.77% 0.14% 1.42%
primetest-05digits 1533903 27.07% 15.48% 35.48% 5.17% 4.55% 4.73% 7.52%
primetest-08digits 2691481 26.62% 14.41% 36.27% 4.70% 4.63% 5.14% 8.22%
primetest-10digits 3689287 26.20% 13.82% 36.65% 4.52% 4.80% 5.40% 8.61%
primetest-20digits 7485593 27.37% 14.27% 36.54% 4.45% 4.04% 5.04% 8.30%
primetest-30digits 10929997 27.64% 14.34% 36.57% 4.39% 3.81% 4.98% 8.26%
primetest-40digits 14666073 27.82% 14.43% 36.52% 4.40% 3.73% 4.91% 8.19%
primetest-50digits 13999383 26.61% 13.55% 36.97% 4.26% 4.40% 5.43% 8.79%
queens4x4-bjbt1 916873 33.63% 23.36% 28.89% 8.30% 4.30% 0.36% 1.17%
queens4x4-bjbt2 984597 33.71% 23.42% 28.91% 8.27% 4.17% 0.34% 1.18%
queens4x4-bm 942203 32.80% 23.65% 28.81% 8.46% 4.38% 0.66% 1.25%
queens4x4-bt 722667 33.78% 23.11% 29.24% 8.04% 4.01% 0.44% 1.38%
queens4x4-fc 2528130 33.41% 24.70% 28.37% 8.53% 3.98% 0.24% 0.77%
queens5x5-bjbt1 11502713 33.88% 23.04% 29.31% 8.00% 3.95% 0.41% 1.42%
queens5x5-bjbt2 12241271 33.91% 23.12% 29.29% 8.00% 3.89% 0.39% 1.39%
queens5x5-bm 10710115 32.73% 23.63% 28.88% 8.42% 4.35% 0.71% 1.29%
queens5x5-bt 9601780 34.07% 22.82% 29.66% 7.73% 3.62% 0.48% 1.61%
queens5x5-fc 32271360 33.47% 24.70% 28.51% 8.39% 3.88% 0.24% 0.82%
The frequencies are a bit more varied for nofib,and sometimes in a different order, but we don't care.
kwxm
reviewed
Jun 28, 2021
| @@ -31,6 +31,22 @@ import PlutusCore.MkPlc | |||
| import qualified PlutusCore.Name as TPLC | |||
| import Universe | |||
|
|
|||
| {- Note [Term constructor ordering and numbers] | |||
| Ordering of constructors has a small but real effect on efficiency. | |||
There was a problem hiding this comment.
If we're doing this for the Term type, I suggest we also do it for StepKind and also CekValue in Cek/Internal.hs, and maybe also Frame (although that looks like a pretty sensible order already). I'm not sure how often the various CekValue types are seen, but we can find out.
There was a problem hiding this comment.
Actually the CekValue types are used in different ways, so it's tricky to tell how important the frequencies are. The only place we dispatch on the full range is in dischargeCekValue, which is irrelevant since it shoud only ever be called once per program. Apart from that VLamAbs and VBuiltin are used in the two cases of forceEvaluate (when you're applying a lambda or a builtin to an argument) and VDelay and VBuiltin are used in forceEvaluate (when you're applying force to something you've just reduced to a value). I think VCon is only ever used is in asConstant when function arguments are passed to the builtin evaluation machinery, and I have no idea if the tag of the constructor matters there. Builtins don't really get called a lot though, so maybe that doesn't matter.
There was a problem hiding this comment.
Based on the figures for the Term type it looks as if a sensible order would be VLamAbs, VDelay, VCon, VBuiltin. Not sure about the order of the last two, if it even matters.
Also, does it matter what order we do matches in, or are they translated to something based on the constructor order?
There was a problem hiding this comment.
Hmm, good idea about CekValue. I'll give that a try, and I agree with your analysis.
I believe the order of matches doesn't matter, it's just the order of the constructors.
koslambrou
pushed a commit
that referenced
this pull request
Jun 29, 2021
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Seems to be noise but I guess it's worth having made an explicit decision 🤷
Pre-submit checklist:
Pre-merge checklist: