#3755 Bad performance using ** operator with integer operands

obsolete: 8.5a6
closed-fixed
5
2007-09-10
2007-08-03
Emiliano
No

When using integers with ** operand, the speed is considerably slower than if using at least one float argument.

After a few runs, I get consistenly these results:

% time {expr {5.0**2}} 10000
3.6763 microseconds per iteration
% time {expr {5**2.0}} 10000
3.6791 microseconds per iteration
% time {expr {double(5)**2}} 10000
5.4605 microseconds per iteration
% time {expr {5**double(2)}} 10000
5.693 microseconds per iteration
% time {expr {5**2}} 10000
38.9746 microseconds per iteration

just to compare with the other "traditional" ways to obtain 5**2

% time {expr {5*5}} 10000
2.7841 microseconds per iteration
% time {expr {pow(5,2)}} 10000
7.7954 microseconds per iteration

% info patchlevel
8.5a6

Discussion

  • Don Porter

    Don Porter - 2007-08-04
    • labels: 105682 --> 47. Bytecode Compiler
    • assigned_to: msofer --> dgp
     
  • Don Porter

    Don Porter - 2007-08-06
    • priority: 5 --> 3
     
  • Don Porter

    Don Porter - 2007-08-06

    Logged In: YES
    user_id=80530
    Originator: NO

    When at least one of the arguments is double,
    the operation turns into a pow() call at the
    C level, so it's comparable performance to
    [expr {pow(...)}] minus Tcl function call overhead.

    When both are integer, the current implementation
    is an iterative one. It's worth looking for improvements,
    but only to the extent that the current performance
    isn't "fast enough". Patches welcome; otherwise I'll
    get to this when I get to it.

     
  • Don Porter

    Don Porter - 2007-08-06

    Logged In: YES
    user_id=80530
    Originator: NO

    Aha! Spoke too soon.

    Root cause of this one is found at
    line 5240 of Revision 1.309 of
    tclExecute.c:

    /* TODO: Perform those computations that fit in native types */

    Since code to detect and perform those
    computations that fit in native types isn't
    done yet, all non-trivial integer ** operations
    get done as bignums.

    Patch still welcome. Normal priority restored.

     
  • Don Porter

    Don Porter - 2007-08-06
    • priority: 3 --> 5
     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-06

    Logged In: YES
    user_id=99768
    Originator: NO

    The attached patch is working toward a solution.

    Observation #1: Powers of 2 are the same as shifts of 1, and are handled thus.

    Observation #2: For 32-bit integers, a very efficient exponent can be computed by doing special-case straight-line code for raising to powers 3-8, and then using table lookups for higher powers (up to 3**19 and up to 10**10).

    Observation #3: For 64-bit integers, a similar computation can be done with straight-line code for raising to powers 3-16, and then table lookup for higher powers (up to 3**39
    and up to 14**17).

    I haven't tried to implement #3, because I'm none too certain how to initialize
    Tcl_WideInts at compile time with values that don't fit in an int.

    The patch should be commitable as it stands (resulting in performance gains only on 32-bit machines), but obviously #3 is important, too.
    File Added: power.patch

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-06

    Logged In: YES
    user_id=99768
    Originator: NO

    On Win32 (mingw), the patch is observed to fix the performance anomaly:

    % time {expr {5*5}} 100000
    0.63991 microseconds per iteration
    % time {expr {5**2}} 100000
    0.62671 microseconds per iteration
    % time {expr {pow(5,2)}} 100000
    1.68862 microseconds per iteration
    % time {expr {5*5*5*5*5}} 100000
    0.91689 microseconds per iteration
    % time {expr {5**5}} 100000
    0.72139 microseconds per iteration
    % time {expr {pow(5,5)}} 100000
    1.65471 microseconds per iteration

    The performance penalty is still there when quantities overflow from a 32-bit integer; we're still working on that one:

    % time {expr {3**19}} 100000; # this fits in a 32-bit word
    0.61131 microseconds per iteration
    % time {expr {3**20}} 100000; # this doesn't
    5.84269 microseconds per iteration

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-07

    Logged In: YES
    user_id=99768
    Originator: NO

    Updated patch:
    - handles negative exponents correctly (first one had a bug)
    - handles powers up to and including x**16 with 'wide' results
    - does not handle higher powers with 'wide' results.

    File Added: power.patch

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-07

    Logged In: YES
    user_id=99768
    Originator: NO

    One more try - powers of -2 were still not right.
    File Added: power.patch

     
  • Don Porter

    Don Porter - 2007-08-07

    Logged In: YES
    user_id=80530
    Originator: NO

    failing tests mathop-(20.3,25.6,25.13)

     
  • Don Porter

    Don Porter - 2007-08-07
    • assigned_to: dgp --> kennykb
     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-07

    Logged In: YES
    user_id=99768
    Originator: NO

    Updated patch #4 to fix a bug with first powers (I'd misread the earlier code as having a special case to handle them. I was mistaken.)
    File Added: power.patch

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-07

    Logged In: YES
    user_id=99768
    Originator: NO

    Patch #5 - Added a table for the powers (exponent > 16) of small integers that fit in a 64-bit word. This patch should have just about all of the possible optimizations done. It presumes that a Tcl_WideInt is always at least 64 bits; if that is not the case, then we need to figure out a way to test for that and condition out the 64-bit code and tables.

    File Added: power.patch

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-08

    Updated patch - version #6

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-08
    • assigned_to: kennykb --> dgp
     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-08

    Logged In: YES
    user_id=99768
    Originator: NO

    Once more into the breach - version #6 of the patch replaces
    the offending conditional on LLONG_MAX with a test:

    #if LONG_MAX > 0x7fffffff || !defined(TCL_WIDE_INT_IS_LONG)

    which should test true iff the implementation has 64-bit ints.
    dgp: Can I ask for one more review, please?
    File Added: power.patch

     
  • Kevin B KENNY

    Kevin B KENNY - 2007-08-25
    • status: open --> closed-fixed
     
  • Don Porter

    Don Porter - 2007-09-10

    Logged In: YES
    user_id=80530
    Originator: NO

    failing test on Mac OS X 10.3:

    ==== expr-23.52 INST_EXPON: small integer powers with 64-bit results FAILED
    ==== Contents of test case:

    set trouble {test small int powers with 64-bit results}
    for {set exp 2} {$exp <= 16} {incr exp} {
    set base [expr {entier(pow(double(0x7fffffffffffffff),(1.0/$exp)))}]
    set sb 1
    set sbm 1
    for {set i 0} {$i < $exp} {incr i} {
    set sb [expr {$sb * $base}]
    set sbm [expr {$sbm * -$base}]
    }
    set is [expr {$base ** $exp}]
    set ism [expr {-$base ** $exp}]
    if {$sb != $is} {
    append trouble \n $base ** $exp " is " $is " should be " $sb
    }
    if {$sbm != $ism} {
    append trouble \n - $base ** $exp " is " $ism " should be " $sbm
    }
    incr base
    set sb 1
    set sbm 1
    for {set i 0} {$i < $exp} {incr i} {
    set sb [expr {$sb * $base}]
    set sbm [expr {$sbm * -$base}]
    }
    set is [expr {$base ** $exp}]
    set ism [expr {-$base ** $exp}]
    if {$sb != $is} {
    append trouble \n $base ** $exp " is " $is " should be " $sb
    }
    if {$sbm != $ism} {
    append trouble \n - $base ** $exp " is " $ism " should be " $sbm
    }
    }
    set trouble

    ---- Result was:
    test small int powers with 64-bit results
    2097152**3 is -9223372036854775808 should be 9223372036854775808
    512**7 is -9223372036854775808 should be 9223372036854775808
    128**9 is -9223372036854775808 should be 9223372036854775808
    ---- Result should have been (exact matching):
    test small int powers with 64-bit results
    ==== expr-23.52 FAILED

     
  • Don Porter

    Don Porter - 2007-09-10
    • assigned_to: dgp --> kennykb
     

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

JavaScript is required for this form.





No, thanks