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.

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

[Code]: The cmp_bytes and cmp_bcs_bytes function could consume much gas when comparing large vector #155

Closed
0xOutOfGas opened this issue Sep 26, 2022 · 1 comment · Fixed by #190
Labels
enhancement New feature or request
Milestone

Comments

@0xOutOfGas
Copy link

Framework version: v11
Description: cmp_bytes and cmp_bcs_bytes calls the cmp_u8 function for each byte, the CALL operation consumes much gas. We did a test, putting the compare codes into cmp_bytes and cmp_bcs_bytes, we got a 20% gas reduction when comparing 100 bytes once.
Code Location: sources/Compare.move, line 38,57

public fun cmp_bcs_bytes(v1: &vector<u8>, v2: &vector<u8>): u8 {
    let i1 = Vector::length(v1);
    let i2 = Vector::length(v2);
    let len_cmp = cmp_u64(i1, i2);

    // BCS uses little endian encoding for all integer types, so we choose to compare from left
    // to right. Going right to left would make the behavior of Compare.cmp diverge from the
    // bytecode operators < and > on integer values (which would be confusing).
    while (i1 > 0 && i2 > 0) {
        i1 = i1 - 1;
        i2 = i2 - 1;
        let elem_cmp = cmp_u8(*Vector::borrow(v1, i1), *Vector::borrow(v2, i2));
        if (elem_cmp != 0) return elem_cmp
        // else, compare next element
    };
    // all compared elements equal; use length comparison to break the tie
    len_cmp
}

public fun cmp_bytes(v1: &vector<u8>, v2: &vector<u8>): u8 {
    let l1 = Vector::length(v1);
    let l2 = Vector::length(v2);
    let len_cmp = cmp_u64(l1, l2);
    let i1 = 0;
    let i2 = 0;
    while (i1 < l1 && i2 < l2) {
        let elem_cmp = cmp_u8(*Vector::borrow(v1, i1), *Vector::borrow(v2, i2));
        if (elem_cmp != 0) {
            return elem_cmp
        };
        // else, compare next element
        i1 = i1 + 1;
        i2 = i2 + 1;
    };
    // all compared elements equal; use length comparison to break the tie
    len_cmp
}

Recommendation: Remove the cmp_u8 call, and write the comparing codes in line.

@0xOutOfGas 0xOutOfGas added the enhancement New feature or request label Sep 26, 2022
@jolestar jolestar added this to the v12 milestone Oct 11, 2022
@jolestar
Copy link
Member

Maybe Move need a #[inline] annotation to function for auto inline when compiling.

@pause125 pause125 mentioned this issue Oct 29, 2022
7 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants