[OPTIMISATION] Improving argument parsing

[denis-migdal]

Current tasklist: #2283 (comment)

See [2275] for other optimizations about function calls.

========================================================

I started working on the optimisation of $B.args0().

I will edit this first message in the future to give a link to a github dedicated to this project + to give a summary of the results and the current progression of the project.

I will use the messages below to discuss about this issue.

Some ideas here.

[denis-migdal]

@PierreQuentel I started to rewrite $B.args0. Currently, it only supports functions call with positional and *t parameters.

Note: We can't give positional and *t arguments on a **args parameter (at least with the implementation of Python I tried).

It seems currently x2 to x5 faster than current implementation.
Tomorrow I will post a github with the code I use to test it.

Do you see any issues with this parser (cf below) ?
Is there something I did not took into account, or do you see a set of parameters that would produce bad results ?

function SimpleParser(fct, args) {

    const result = {};

    const kargs  = args[args.length-2];
    const kwargs = args[args.length-1];

    const args_names    = fct.$infos.arg_names;
    const args_defaults = fct.$infos.__defaults__;
    const default_offset = args_names.length - args_defaults.length;
    const varargs_name  = fct.$infos.vararg;
    const kwargs_name   = fct.$infos.kwarg;

    const max = Math.max( args.length-2, args_names.length );

    // positional parameters...
    let offset = 0;
    for( ; offset < max ; ++offset)
        result[ args_names[offset] ] = args[offset];

    // vararg parameter
    if( varargs_name !== null )
        result[varargs_name] = args.slice( args_names.length, -2 );

    // positionnal only
    if( kargs === null && kwargs === null ) {

        if( default_offset < offset )
            throw new Error('XXX');

        // default parameters
        for(let i = offset - default_offset;
                i < args_defaults.length;
                ++i)
            result[ args_names[offset++] ] = args_defaults[i];

        if( kwargs_name !== null )
            result[kwargs_name] = __BRYTHON__.obj_dict({});

        return result;
    }


    //TODO: named / **args arguments
    //TODO: *arg  / **args parameters

    return result;
}

[denis-migdal]

@PierreQuentel Normally I should have a complete version now (?). I didn't fully tested it.
I do not show the proper error messages (but that won't affect performances).

Do you see an issue with this implementation ?

On the very limited test I made, I am generally x1.7 faster than current implementation. In fact it is even faster as my measures include the time taken by the loop (so in fact I am normally ~x1.85 faster).
Note: It only shows when testing >10000000 arguments parsing, else results are too unstables. Indeed, for small durations, browsers time measurement aren't very precise.

Some variables can still be precomputed to speed things up, and maybe some little tweaks could increase performances a little more :

• fct.$infos => const $infos = fct.$infos
• $infos.karg_names doesn't seems to exists (some parameters can't accept positionnal arguments, and therefore shouldn't be in $infos.arg_names e.g. in def foo(a,*t, b):, b can't be positionnal.
• I use an array for const keys, maybe there are structs that'd perform better. Potentially preallocated.
  • Map() with values set to true at first when not yet set, then set to false once set (but initialization may be quite costly).
  • {} with values set to true at first when not yet set, then set to false once set (but initialization may be quite costly).
  • {} of already defined values and a {} of values not defined yet (idem can be costly).
  • idem with 2 Set().
• For functions having **kargs parameter, we can optimize things (we don't need keys as an array).

There are some changes for function calls. The last arguments is always named arguments, therefore we don't need the strange {$kw:[]} structure, only an array or null if no named parameters. This could give us a very small speed increase too.

Here the web page I used to test it : test.html.zip
This is quite dirty but it does the trick.

And here my argument parser :

function SimpleParser(fct, args) {

    const result = {};

    //TODO: rename :
    // - args   = when calling   the function.
    // - params = when declaring the function.

    const args_names    = fct.$infos.arg_names;
    const nb_pos_params = args_names.length;
    const varargs_name  = fct.$infos.vararg;
    const kwargs_name   = fct.$infos.kwarg;
    const nb_pos_args   = args.length-1;

    const min = Math.min( nb_pos_args, nb_pos_params );

    const kargss  = args[nb_pos_args];

    // positional parameters...
    let offset = 0;
    for( ; offset < min ; ++offset)
        result[ args_names[offset] ] = args[offset];

    // vararg parameter
    //TODO: NOT SURE FOR kargss !!!!
    if( varargs_name !== null )
        result[varargs_name] = args.slice( nb_pos_params, -1 );
    else if( nb_pos_args > nb_pos_params ) {
        throw new Error('Too much pos parameters');
    }

    // positionnal only
    if( kargss === null ) {

        const args_defaults = fct.$infos.__defaults__;
        const nb_defaults   = args_defaults.length;
        const default_offset= nb_pos_params - nb_defaults;

        if( default_offset < offset )
            throw new Error('Not enough pos parameters');

        // default parameters
        for(let i = offset - default_offset;
                i < nb_defaults;
                ++i)
            result[ args_names[offset++] ] = args_defaults[i];

        if( kwargs_name !== null )
            result[kwargs_name] = __BRYTHON__.obj_dict({});

        return result;
    }

    const kargs_names   = fct.$infos.karg_names ?? args_names.slice(); // TODO: missing !!!

    const keys  = kargs_names.slice(offset);
    // other structs possibles ???

    const extra = {};

    for(let id = 0; id < kargss.length; ++id ) {

        const
[test.html.zip](https://github.com/brython-dev/brython/files/13060472/test.html.zip)
 kargs = kargss[id];
        for(let argname in kargs) {

            let i = keys.indexOf(argname);

            if( i === -1) {
                if( kwargs_name === null )
                    throw new Error('Unfound named parameters or duplicate');

                // not quite optimized for *kwargs parameters...
                // no need for keys indexOf if *kwargs parameters.
                if(argname in result || argname in extra)
                    throw new Error('Defined many times !');

                extra[argname] = kargs[argname];
                continue;
            }

            result[ argname ] = kargs[argname];
            //delete keys[i];
            keys[i] = null;
        }
    }

    if( kwargs_name !== null )
        result[kwargs_name] = __BRYTHON__.obj_dict(extra);

    const kargs_defaults= fct.$infos.__kwdefaults__;

    // checks default values...
    for(let ioffset = 0; ioffset < keys.length; ++ioffset) {

        const key = keys[ioffset];
        if( key !== null ) {
            if( ! (key in kargs_defaults ))
                throw new Error('missing values !!');

            result[key] = kargs_defaults[key];
        }

    }

    return result;
}

[denis-migdal]

Hmmm... it seems I can be even faster for named argument processing :

• if there is a **args parameter : we don't need keys anyways, do an optimized parsing. (?).
• if there is no **args parameter : I don't really need keys, just to count the number of assignation I'd made. Then count the number of unfound parameters when searching for their default value (likely to add a little cost). Then I compare the 2 numbers to determine if an argument was duplicate or an inexistant argument was given.

This could be tested. But I think, first, we should determine whether the proposed implementation is correct.

[denis-migdal]

Still doing some tests (but I'll try to stop now xD).

• New version (cf below) seems more optimized when having named arguments (didn't optimized it for **kwargs parameter though).
• Testing is hard. Not enough tests = unstable results. Too much tests = strange memory issues it seems (started to manifest when I put the functions into different files).
• Tests might be slightly skewed against my new parsing methods as I test them firsts (putting it in seconds seems to speed them up a little ???).

Sources: parse_args.zip

See also : https://jfmengels.net/optimizing-javascript-is-hard/

[PierreQuentel]

Denis, I'm sorry but I need a Pull Request with a complete replacement for argument parsing, that is, a new version of the functions in py_utils.js that passes all the tests in the built-in test suite (/tests/index.html).

Otherwise it's impossible to know if your version correctly covers all the cases, and comparing its speed to that of the current implementation won't be useful.

[denis-migdal]

Denis, I'm sorry but I need a Pull Request with a complete replacement for argument parsing, that is, a new version of the functions in py_utils.js that passes all the tests in the built-in test suite (/tests/index.html).

Something isn't right.

I downloaded the zip from github, remplaced $B.arg0 in py_utils.js, called python make_dist.py, tested /test/index.html ... and I passed all test the first time... This isn't normal.

Are the tests relying more on $B.parse_args ?
Do you have tests for all possible combination of parameters and arguments ?
Is there another script I have to call to build the Brython files ?

EDIT: I throw an exception in my new function and still pass all the tests.
It seems clear that my function isn't called.
EDIT: did the same in parse_args.

[denis-migdal]

Also :

$ python3.12 make_release.py 
/tmp/brython-master/scripts/make_release.py:54: SyntaxWarning: invalid escape sequence '\d'
  content = re.sub("npm/brython@\d\.\d+\.\d+", "npm/brython@" + vname,
/tmp/brython-master/scripts/make_release.py:56: SyntaxWarning: invalid escape sequence '\d'
  content = re.sub("npm/brython@\d\.\d+\s", "npm/brython@" + vname2,
/tmp/brython-master/scripts/make_release.py:58: SyntaxWarning: invalid escape sequence '\d'
  content = re.sub("npm/brython@\d\.\d+\.x", "npm/brython@" + vname2 + '.x',
/tmp/brython-master/scripts/make_release.py:60: SyntaxWarning: invalid escape sequence '\d'
  content = re.sub("npm/brython@\d\s", "npm/brython@" + vname1,
/tmp/brython-master/scripts/make_release.py:62: SyntaxWarning: invalid escape sequence '\d'
  content = re.sub("npm/brython@\d\.x\.y", "npm/brython@" + vname1 + '.x.y',
/tmp/brython-master/scripts/make_release.py:64: SyntaxWarning: invalid escape sequence '\.'
  content = re.sub("3\.\d+\.x", f'3.{version.version[1]}.x', content)
Brython [3, 12]
CPython (3, 12)
Traceback (most recent call last):
  File "/tmp/brython-master/scripts/make_release.py", line 17, in <module>
    import make_ast_classes       # generates /src/py_ast_classes.js
    ^^^^^^^^^^^^^^^^^^^^^^^
  File "/tmp/brython-master/scripts/make_ast_classes.py", line 12, in <module>
    f = open('Python.asdl', encoding='utf-8')
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
FileNotFoundError: [Errno 2] No such file or directory: 'Python.asdl'

[PierreQuentel]

I downloaded the zip from github, remplaced $B.arg0 in py_utils.js, called python make_dist.py, tested /test/index.html ... and I passed all test the first time... This isn't normal.

I don't know what is wrong here.

You don't have to run make_dist.py, tests/index.html uses the individual Brython scripts (brython_builtins.js, py_utils.js, etc...).

Can you call /src/py_utils.js in the address bar to see if it is the version you have modified ?

The error message in make_release.py does not surprise me. It is not a script meant to be used by Brython users, only the release manager :-). It uses files downloaded from various places by the script scripts/downloads.py.

[denis-migdal]

It seems the files are cached. I have to go to src/py_utils.js, then refresh the page, in order to update it after modifying it.

Now I get some errors :)
Gonna see if I can fix them quick ;).

[denis-migdal]

It seems to work quite well (for now I got an error at line 529 of the basic test suite).

Got few small errors to fix :

• some stuff linked to the input/precomputed data.
• transforming the *args into a tupple.
• I confused < and > in one condition (my bad xD).

My code may be a little slower as I don't have access to some pre-computed data in the format I'd need, so I have to compute them when parsing arguments.

For now, I also use the original $B.args0() to build the excepted exception.

So we'll have to discuss a little once I'd pass all tests ;).

I also have one question :

• What are the differences between $defaults and $infos.__kwdefaults__ ?

[denis-migdal]

Another question (sorry I am not quite used to Python) :

• in def format(self, /, **kwargs):, what is / ?

[denis-migdal]

Yeah I'm stuck at 1043 of the basic test suite because of this /.
I don't understand this behavior :

>>> class X:
...     def foo(self, **args):
...             print(args)
... 
>>> x = X()
>>> x.foo(self=x)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: X.foo() got multiple values for argument 'self'
>>> class X:
...     def foo(self, /, **args):
...             print(args)
... 
>>> x = X()
>>> x.foo(self=x)
{'self': <__main__.X object at 0x7feb070463e0>} 

EDIT: I think I understand it now.
I found no Python documentation on it. But it seems everything in the left-side of "/" can only be set using position argument, and it won't raise an error when using a key in a **args with the same name as a parameter name in the left-side of "/".

[PierreQuentel]

Your guess is correct. The reference here is the Language Reference, specifically the section about function definition.

[denis-migdal]

Thanks.

I'm struggling to fix little details like this xD.
Passed the first test suite though ^^.

[denis-migdal]

completed all tests in 44.59 s.
failed : []

^^

Normal time with the current implementation : ~45 s.

However, comparison isn't fair :

• I need to clean my code a little.
• When I detect an error, I call the original args0() function to build the expected error message.
• I do not always use or have the pre-computed data I'd need. So this adds a little cost.