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

Concept: codegen ignores parameter passing #16897

Closed
mratsim opened this issue Feb 1, 2021 · 0 comments
Closed

Concept: codegen ignores parameter passing #16897

mratsim opened this issue Feb 1, 2021 · 0 comments

Comments

@mratsim
Copy link
Collaborator

mratsim commented Feb 1, 2021

I tracked down a serious performance bug to how concepts ignore parameter passing rules.
Usually Nim types are automatically passed by reference when they go over 24 bytes which avoids worrying about mutability.
However concepts ignore that and they even ignore the {.byref.} pragma.

This can lead to horrible codegen for large types, for example for Biginteger used in cryptography (mratsim/constantine#146) or serialization libraries which might want to use a concept to serialize any type.

This is the prologue before any function calls to the Fp2 type in my library (think complex of BigInt)
image

Unfortunately I also need Fp4 (complex of complex) and Fp12 (you get the gist) which means I get a significant penalty.
I have been diligently recording all the AAA optimizations that could be done in my problem domain including algebraic, algorithmic and assembly (https://github.com/mratsim/constantine/blob/master/docs/optimizations.md).

I did the most important ones, as shown by very close performance to top (with 10 nanoseconds) for types that don't use concept: https://hackmd.io/@zkteam/eccbench#G1-mixed-additiondoubling
image

However my library drop by 2x on types that use concepts: https://hackmd.io/@zkteam/eccbench#G2-mixed-additiondoubling
image

Test case

type
  Fp[N: static int, T] = object
    big: array[N, T]

type
  QuadraticExt* = concept x
    ## Quadratic Extension concept (like complex)
    type BaseField = auto
    x.c0 is BaseField
    x.c1 is BaseField

{.experimental:"views".}

func prod(r: var QuadraticExt, a, b: lent QuadraticExt) =
  discard

type
  Fp2[N: static int, T] {.byref.}= object
    c0, c1: Fp[N, T]

# This should be passed by reference,
# but concepts do not respect the 24 bytes rule
# or `byref` pragma.
var r, a, b: Fp2[6, uint64]

prod(r, a, b)
/* section: NIM_merge_PROCS */
N_LIB_PRIVATE N_NIMCALL(void, prod__QYARsFOZYzI66SzOlkskoA)(tyObject_Fp2__SVgH9c6gmNsJfyYVtl0YdSQ* r, tyObject_Fp2__SVgH9c6gmNsJfyYVtl0YdSQ a, tyObject_Fp2__SVgH9c6gmNsJfyYVtl0YdSQ b) {
}

Notice how a and b are not pointers

Araq added a commit that referenced this issue Feb 1, 2021
@Araq Araq closed this as completed in 91ace21 Feb 1, 2021
Clyybber added a commit to Clyybber/Nim that referenced this issue Feb 2, 2021
Clyybber added a commit that referenced this issue Feb 2, 2021
narimiran pushed a commit that referenced this issue Feb 4, 2021
(cherry picked from commit 91ace21)
narimiran pushed a commit that referenced this issue Feb 4, 2021
(cherry picked from commit 91ace21)
ardek66 pushed a commit to ardek66/Nim that referenced this issue Mar 26, 2021
ardek66 pushed a commit to ardek66/Nim that referenced this issue Mar 26, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant