Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Rewrite Int.toFloatString (__tact_float_to_string) in Tact #1781

Open
Tracked by #1761
Gusarich opened this issue Feb 11, 2025 · 4 comments
Open
Tracked by #1761

Rewrite Int.toFloatString (__tact_float_to_string) in Tact #1781

Gusarich opened this issue Feb 11, 2025 · 4 comments
Assignees
@Gusarich
Labels
scope: stdlib The Tact standard library (src/stdlib)

Comments

@Gusarich
Copy link
Member

Similar to #1780

Currently, this function is implemented in FunC, and even worse—it is highly inefficient.

This is what it compiles into:

__tact_float_to_string PROCREF:<{
    DUP
    1 LESSINT
    OVER
    77 GTINT
    OR
    134 THROWIF
    NEWC
    s2 PUSH
    0 LESSINT
    IF:<{
        45 PUSHINT
        SWAP
        8 STU
        s0 s2 XCHG
        NEGATE
        s0 s2 XCHG
    }>
    TRUE
    0 PUSHINT
    NIL
    s0 s4 XCHG
    REPEAT:<{
        s0 s4 XCHG
        10 PUSHINT
        DIVMOD
        DUP
        0 EQINT
        s3 s(-1) PUXC
        AND
        NOT
        IF:<{
            FALSE
            s3 POP
            48 ADDCONST
            s1 s4 XCHG
            TPUSH
            s0 s4 XCHG
            INC
            s0 s4 XCHG
            s0 s3 XCHG
        }>ELSE<{
            DROP
        }>
        s0 s4 XCHG
    }>
    SWAP
    NOT
    IF:<{
        s0 s2 XCHG
        46 PUSHINT
        TPUSH
        s0 s2 XCHG
        INC
    }>
    UNTIL:<{
        s0 s3 XCHG
        10 PUSHINT
        DIVMOD
        48 ADDCONST
        s1 s3 XCHG
        TPUSH
        s0 s3 XCHG
        INC
        s2 PUSH
        0 EQINT
        s3 s4 XCHG
    }>
    s3 POP
    s2 PUSH
    DEC
    s0 s3 XCHG
    REPEAT:<{
        s1 s2 PUSH2
        INDEXVAR
        SWAP
        8 STU
        s0 s2 XCHG
        DEC
        s0 s2 XCHG
    }>
    2 1 BLKDROP2
    ENDC
    CTOS
}>

This implementation is suboptimal and can be significantly improved with manual assembly optimizations.
@Gusarich Gusarich added the scope: stdlib The Tact standard library (src/stdlib) label Feb 11, 2025
@Gusarich Gusarich self-assigned this Feb 11, 2025
@Gusarich Gusarich mentioned this issue Feb 10, 2025
Open
5 tasks
@Gusarich Gusarich changed the title Rewrite toFloatString (__tact_float_to_string) in Tact Rewrite Int.toFloatString (__tact_float_to_string) in Tact Feb 11, 2025
@anton-trunov
Copy link
Member

Wow, let's goooo!

@Gusarich
Copy link
Member Author

Gusarich commented Feb 12, 2025 •
edited
Loading

Current Implementation

Code

Click to open 
DUP
1 LESSINT
OVER
77 GTINT
OR
134 THROWIF
NEWC
s2 PUSH
0 LESSINT
IF:<{
    45 PUSHINT
    SWAP
    8 STU
    s0 s2 XCHG
    NEGATE
    s0 s2 XCHG
}>
TRUE
0 PUSHINT
NIL
s0 s4 XCHG
REPEAT:<{
    s0 s4 XCHG
    10 PUSHINT
    DIVMOD
    DUP
    0 EQINT
    s3 s(-1) PUXC
    AND
    NOT
    IF:<{
        FALSE
        s3 POP
        48 ADDCONST
        s1 s4 XCHG
        TPUSH
        s0 s4 XCHG
        INC
        s0 s4 XCHG
        s0 s3 XCHG
    }>ELSE<{
        DROP
    }>
    s0 s4 XCHG
}>
SWAP
NOT
IF:<{
    s0 s2 XCHG
    46 PUSHINT
    TPUSH
    s0 s2 XCHG
    INC
}>
UNTIL:<{
    s0 s3 XCHG
    10 PUSHINT
    DIVMOD
    48 ADDCONST
    s1 s3 XCHG
    TPUSH
    s0 s3 XCHG
    INC
    s2 PUSH
    0 EQINT
    s3 s4 XCHG
}>
s3 POP
s2 PUSH
DEC
s0 s3 XCHG
REPEAT:<{
    s1 s2 PUSH2
    INDEXVAR
    SWAP
    8 STU
    s0 s2 XCHG
    DEC
    s0 s2 XCHG
}>
2 1 BLKDROP2
ENDC
CTOS

Benchmark Summary

  • The minimal gas usage is 1920
  • The average gas usage is 30612
  • Negative numbers consistently consume 129 more gas than their positive counterparts
  • Increasing the order of magnitude adds approximately 237 gas units to the average usage across all digits
  • Increasing the digits adds approximately 436 gas units to the average usage across all orders of magnitude.

Full Benchmark Results:

Click to open 
=== OoM Summary (Aggregated over all digits) ===
  OoM |  Min Gas |  Max Gas |  Avg Gas |    Δ Avg Gas | Avg (Δ Avg Gas) per Digit
-----------------------------------------------------------------
    0 |     1920 |    49968 | 24396.20 |      N/A     |           588.85
    1 |     1920 |    49968 | 25726.05 |      1329.85 |           624.75
    2 |     2320 |    49968 | 25726.52 |         0.47 |           618.95
    3 |     2721 |    49968 | 25738.77 |        12.24 |           613.91
    4 |     3123 |    49968 | 25755.39 |        16.62 |           608.85
    5 |     3983 |    49968 | 25769.35 |        13.96 |           602.74
    6 |     4388 |    49968 | 25804.82 |        35.47 |           596.88
    7 |     4062 |    49968 | 25832.72 |        27.90 |           594.14
    8 |     4741 |    49968 | 25875.98 |        43.26 |           586.43
    9 |     5148 |    49968 | 25905.69 |        29.71 |           582.61
   10 |     5556 |    49968 | 25960.34 |        54.65 |           577.22
   11 |     5965 |    49968 | 26010.55 |        50.22 |           572.09
   12 |     6839 |    49968 | 26079.24 |        68.69 |           565.07
   13 |     6786 |    49968 | 26141.36 |        62.12 |           559.93
   14 |     7810 |    49968 | 26206.04 |        64.68 |           554.71
   15 |     7466 |    49968 | 26283.18 |        77.14 |           548.28
   16 |     8641 |    49968 | 26361.62 |        78.45 |           543.26
   17 |     8440 |    49968 | 26445.03 |        83.41 |           538.58
   18 |     8856 |    49968 | 26536.05 |        91.02 |           533.61
   19 |     9273 |    49968 | 26643.61 |       107.56 |           528.09
   20 |     9691 |    49968 | 26751.21 |       107.59 |           522.87
   21 |    10583 |    49968 | 26851.79 |       100.58 |           516.21
   22 |    10530 |    49968 | 26965.84 |       114.05 |           511.48
   23 |    10951 |    49968 | 27085.24 |       119.40 |           507.06
   24 |    11219 |    49968 | 27225.09 |       139.85 |           500.34
   25 |    11641 |    49968 | 27346.22 |       121.13 |           495.59
   26 |    11909 |    49968 | 27481.05 |       134.83 |           489.47
   27 |    12488 |    49968 | 27632.14 |       151.10 |           482.70
   28 |    13551 |    49968 | 27780.04 |       147.89 |           476.55
   29 |    13498 |    49968 | 27929.18 |       149.15 |           471.75
   30 |    13926 |    49968 | 28084.09 |       154.91 |           468.31
   31 |    14355 |    49968 | 28258.99 |       174.90 |           461.27
   32 |    15269 |    49968 | 28439.14 |       180.15 |           453.89
   33 |    15216 |    49968 | 28616.97 |       177.82 |           449.05
   34 |    15648 |    49968 | 28803.63 |       186.66 |           444.20
   35 |    16081 |    49968 | 28991.74 |       188.11 |           438.48
   36 |    16515 |    49968 | 29197.39 |       205.64 |           432.75
   37 |    16950 |    49968 | 29401.14 |       203.75 |           426.14
   38 |    17386 |    49968 | 29611.81 |       210.68 |           420.38
   39 |    17823 |    49968 | 29832.54 |       220.73 |           415.12
   40 |    18261 |    49968 | 30050.84 |       218.30 |           408.82
   41 |    19193 |    49968 | 30277.38 |       226.54 |           402.66
   42 |    19634 |    49968 | 30518.56 |       241.18 |           396.32
   43 |    20251 |    49968 | 30759.31 |       240.74 |           389.98
   44 |    20344 |    49968 | 31010.02 |       250.72 |           385.17
   45 |    21140 |    49968 | 31263.03 |       253.00 |           378.80
   46 |    20910 |    49968 | 31522.52 |       259.50 |           373.30
   47 |    22033 |    49968 | 31778.37 |       255.84 |           367.05
   48 |    22481 |    49968 | 32060.26 |       281.89 |           360.63
   49 |    22248 |    49968 | 32343.74 |       283.47 |           356.00
   50 |    22696 |    49968 | 32621.69 |       277.95 |           350.22
   51 |    22964 |    49968 | 32923.82 |       302.14 |           344.81
   52 |    23595 |    49968 | 33221.55 |       297.72 |           338.35
   53 |    24551 |    49968 | 33523.94 |       302.39 |           331.48
   54 |    24498 |    49968 | 33828.24 |       304.29 |           325.90
   55 |    24951 |    49968 | 34155.44 |       327.21 |           320.95
   56 |    25405 |    49968 | 34477.07 |       321.62 |           314.44
   57 |    25673 |    49968 | 34805.47 |       328.41 |           307.91
   58 |    26316 |    49968 | 35156.29 |       350.82 |           302.92
   59 |    26773 |    49968 | 35500.46 |       344.16 |           296.37
   60 |    27231 |    49968 | 35853.35 |       352.90 |           290.83
   61 |    28203 |    49968 | 36206.46 |       353.11 |           283.84
   62 |    28150 |    49968 | 36575.94 |       369.48 |           278.07
   63 |    28611 |    49968 | 36959.08 |       383.13 |           273.02
   64 |    29073 |    49968 | 37328.61 |       369.53 |           265.98
   65 |    30053 |    49968 | 37711.49 |       382.88 |           259.45
   66 |    30000 |    49968 | 38105.29 |       393.80 |           253.22
   67 |    30984 |    49968 | 38503.51 |       398.22 |           247.17
   68 |    31437 |    49968 | 38918.61 |       415.10 |           241.01
   69 |    31199 |    49968 | 39326.76 |       408.15 |           234.32
   70 |    31866 |    49968 | 39755.86 |       429.10 |           229.61
   71 |    32335 |    49968 | 40173.42 |       417.56 |           223.85
   72 |    32805 |    49968 | 40611.07 |       437.65 |           217.65
   73 |    33073 |    49968 | 41052.17 |       441.10 |           210.03
   74 |    33544 |    49968 | 41507.15 |       454.98 |           205.20
   75 |    34221 |    49968 | 41957.31 |       450.16 |           197.99
   76 |    35223 |    49968 | 42423.82 |       466.52 |           190.76

=== Digits Summary (Aggregated over all OoMs) ===
Digit |  Min Gas |  Max Gas |  Avg Gas |      Δ Avg Gas | Avg (Δ Avg Gas) per OoM
----------------------------------------------------------------------
    1 |     1920 |    35431 | 16749.26 |       N/A      |           433.99
    2 |     2188 |    35616 | 17000.58 |         251.32 |           428.61
    3 |     2456 |    35801 | 17242.73 |         242.16 |           423.73
    4 |     2724 |    35986 | 17482.22 |         239.49 |           418.83
    5 |     2992 |    36171 | 17732.00 |         249.78 |           414.44
    6 |     3260 |    36356 | 17985.67 |         253.67 |           409.01
    7 |     3528 |    36541 | 18245.72 |         260.05 |           404.60
    8 |     3796 |    36726 | 18505.06 |         259.34 |           399.14
    9 |     4064 |    36911 | 18764.38 |         259.32 |           393.67
   10 |     4332 |    37096 | 19038.39 |         274.01 |           389.22
   11 |     4600 |    37281 | 19315.42 |         277.03 |           384.76
   12 |     4868 |    37466 | 19597.53 |         282.11 |           378.74
   13 |     5136 |    37651 | 19884.00 |         286.47 |           374.26
   14 |     5404 |    37836 | 20173.10 |         289.10 |           367.18
   15 |     5672 |    38021 | 20469.03 |         295.93 |           364.22
   16 |     5940 |    38206 | 20769.91 |         300.88 |           359.19
   17 |     6208 |    38391 | 21077.26 |         307.35 |           354.14
   18 |     6476 |    38576 | 21394.75 |         317.49 |           349.08
   19 |     6744 |    38761 | 21707.56 |         312.80 |           344.01
   20 |     7012 |    38946 | 22031.66 |         324.10 |           339.44
   21 |     7280 |    39131 | 22356.44 |         324.78 |           334.35
   22 |     7548 |    39316 | 22690.05 |         333.61 |           328.73
   23 |     7816 |    39501 | 23037.83 |         347.78 |           323.09
   24 |     8084 |    39686 | 23378.98 |         341.15 |           317.96
   25 |     8352 |    39871 | 23725.90 |         346.92 |           312.30
   26 |     8620 |    40056 | 24082.01 |         356.11 |           308.70
   27 |     8888 |    40241 | 24439.55 |         357.53 |           301.98
   28 |     9156 |    40426 | 24810.49 |         370.95 |           298.36
   29 |     9424 |    40611 | 25175.30 |         364.81 |           291.61
   30 |     9692 |    40796 | 25548.79 |         373.48 |           286.42
   31 |     9960 |    40981 | 25933.76 |         384.97 |           282.23
   32 |    10228 |    41166 | 26326.51 |         392.75 |           277.53
   33 |    10496 |    41351 | 26717.13 |         390.62 |           271.77
   34 |    10764 |    41536 | 27111.43 |         394.30 |           265.49
   35 |    11032 |    41721 | 27529.25 |         417.82 |           261.78
   36 |    11300 |    41906 | 27931.60 |         402.35 |           255.99
   37 |    11568 |    42091 | 28352.70 |         421.10 |           251.22
   38 |    11836 |    42276 | 28768.11 |         415.42 |           245.93
   39 |    12104 |    42461 | 29195.89 |         427.77 |           240.10
   40 |    12372 |    42646 | 29634.12 |         438.23 |           235.30
   41 |    12640 |    42831 | 30069.04 |         434.92 |           229.45
   42 |    12908 |    43016 | 30521.83 |         452.80 |           224.62
   43 |    13176 |    43201 | 30967.67 |         445.84 |           218.75
   44 |    13444 |    43386 | 31415.61 |         447.94 |           212.87
   45 |    13712 |    43571 | 31886.75 |         471.14 |           207.49
   46 |    13980 |    43756 | 32346.07 |         459.32 |           203.13
   47 |    14248 |    43941 | 32823.12 |         477.04 |           195.15
   48 |    14516 |    44126 | 33295.21 |         472.09 |           190.76
   49 |    14784 |    44311 | 33790.11 |         494.90 |           186.89
   50 |    15052 |    44496 | 34287.29 |         497.18 |           180.42
   51 |    15320 |    44681 | 34780.37 |         493.08 |           175.48
   52 |    15588 |    44866 | 35287.91 |         507.54 |           170.02
   53 |    15856 |    45051 | 35789.63 |         501.72 |           164.55
   54 |    16124 |    45236 | 36304.81 |         515.18 |           159.06
   55 |    16392 |    45421 | 36826.09 |         521.28 |           154.08
   56 |    16660 |    45606 | 37356.52 |         530.43 |           147.54
   57 |    16928 |    45791 | 37887.79 |         531.27 |           142.02
   58 |    17196 |    45976 | 38436.86 |         549.06 |           137.52
   59 |    17464 |    46161 | 38975.54 |         538.68 |           131.46
   60 |    17732 |    46346 | 39528.88 |         553.34 |           125.38
   61 |    18000 |    46531 | 40087.97 |         559.09 |           120.85
   62 |    18268 |    46716 | 40654.28 |         566.31 |           114.24
   63 |    18536 |    46901 | 41227.37 |         573.10 |           109.68
   64 |    18804 |    47086 | 41802.56 |         575.19 |           103.56
   65 |    19072 |    47271 | 42391.31 |         588.75 |            97.42
   66 |    19340 |    47456 | 42971.55 |         580.24 |            92.83
   67 |    19608 |    47641 | 43567.61 |         596.07 |            87.19
   68 |    19876 |    47826 | 44179.11 |         611.49 |            81.02
   69 |    20144 |    48011 | 44790.21 |         611.10 |            74.84
   70 |    20412 |    48196 | 45394.62 |         604.41 |            70.20
   71 |    20680 |    48381 | 46018.15 |         623.53 |            63.48
   72 |    20948 |    48566 | 46646.83 |         628.69 |            58.82
   73 |    21216 |    48751 | 47287.50 |         640.67 |            52.59
   74 |    21484 |    48936 | 47935.18 |         647.68 |            47.38
   75 |    21752 |    49121 | 48580.69 |         645.51 |            41.65
   76 |    22020 |    49306 | 49237.85 |         657.15 |            35.39
   77 |    22288 |    49968 | 49898.36 |         660.52 |            35.90

=== Overall Summary ===
Total tasks processed: 65450
Overall Min Gas: 1920
Overall Max Gas: 49968
Overall Avg Gas: 30612.47
Overall Avg (Δ Avg Gas) per OoM:       237.21
Overall Avg (Avg (Δ Avg Gas) per Digit) per OoM:           416.58
Overall Avg (Δ Avg Gas) per Digit:         436.17
Overall Avg (Avg (Δ Avg Gas) per OoM) per Digit:           237.21

Static Difference (negative - positive) for (x=±12345, digits=5): 129 gas units

@Gusarich
Copy link
Member Author

Gusarich commented Feb 12, 2025 •
edited
Loading

I will proceed with implementing optimized functions and will post benchmark results later.

Here is the full benchmark script code I used (similar to #1780):
https://gist.github.com/Gusarich/f2ea701de160317ed6005733dfb0d507

@anton-trunov
Copy link
Member

awesome, let's go for it!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@Gusarich Gusarich

Labels
scope: stdlib The Tact standard library (src/stdlib)
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@anton-trunov @Gusarich