Abstract List (TIP-636) Performance

Difference between version 2 and 3 - Previous - Next
**AbstractList Performance**

The promise of the AbstractList TIP-636 is improved Tcl performance, by reducing shimmering in common "list" operations, especially when custom ObjTypes are actively used in a script. Custom ObjTypes typically originating from 3rd party extensions or embedded applications. The work presented here is an attempt to measure the impact of an AbstractList implentation to see if and how well the promise is kept.

The AbstractList approach redirects common List operations with custom functions to do the work specific to the custom Type. For example, when `\[llength $x]` is called, if the type of $x provides a "length" function, the List code will use that function in place of the internal code to obtain the list length value.

**Approach**
The test scenario uses a modified VecTCL implementation with a simple demo testcase to measure the implact of each AbstractList function. Not all functions are implemented since not all possible commands are used by the demo testcase.

***Demo Testcase***

In the demo script, an initial compound list of 1000 3-dimensional points is defined, where each pair of points represents a line segment.  The 3-D set of lines is then transformed into a projection onto a 2-D surface, i.e., 2-D point pairs used to draw lines on a Tk Canvas.  The VecTCL implementation has an optimized ObjType to represent the list of points used to perform the transformation.  The result is a custom value as well. The results list is decomposed via `foreach` loops to extract each pair of points, which are passed to the canvas widget. It, in turn, will convert the numeric values to "pixel" values, yet another custom ObjType.


======    
    # Compute transform
    set width [winfo width $canvas]
    set height [winfo height $canvas]
    # '3dx' value is of type NumArray
    set 3dx [do3DTransform $data $width $height]

    # Clear canvas
    $canvas delete all

    # draw line segments
    # foreach will shimmer '3dx' to a list by default
    foreach {x y} $3dx {
        # Here, foreach will shimmer 'x' and 'y' to a list by default
        foreach {x1 x2} $x {y1 y2} $y {
            # canvas will shimmer the x and y double values to 'pixel' values.
            $canvas create line [list $x1 $y1 $x2 $y2]
        }
    }
======


**VecTCL**

The VecTCL extension has been updated for compatibility with Tcl 9.0. This work is available on github at bgriffinfortytwo/VecTcl9. There is also an abstractlist branch implementing most of the AbstratList functions. Only the reverse and replace operations have not been implemented at this point.

With help from auriocus, 2 other tweaks to the code were identified. 

   1. When custom indexing is in play, the individual scalar values are also NumArray types, just as the rest of the list value.  When the canvas needs the value, it must be converted to `double` first; another shimmer.  Modifying the index function to return `double` values for 1-D slices, i.e. scalar values, will avoid the need for the canvas code to trigger a shimmer of the value.
   2. This issue can be generalized, or abstracted as well.  The `Tcl_GetDoubleFromObj()` function was modified to look for a `getdouble` function in the ObjType and use that to obtain the `double` value without having to shimmer the type of the `Tcl_Obj`. 
   
**Performance Results**

To measure the performance, the script above was run using `timerate` in a loop with a delay on each iteration. (Note: timerate itself iterates the script)  The delay allows for screen updates in order to see and confirm correct behavior of the testcase.  It should be noted that timerate values varied approximately up to 10% each outer iteration.  I assume these variations where due to effects of Tk screen upates, and other MacOS activity, including things like mouse movements. 

In the table below the functions in place for each test are listed, along with the timerate results.  The table is sorted in decreasing iteration runtime.  The "baseline" number is without AbstractList.

***Table 1***

%|Abstract Functions|µs/#|#|#/sec|net-ms|improvement|%
&|+length +index|7543.53|133|132.56|1003.290|-53.3%|&
&|+length +index +slice|7543.40|133|132.57|1003.272|-53.3%|&
&|+length | 5273.54|190|189.63|1001.972|-7.2%|&
&|+length +getelements|4950.87|202|201.98|1000.075|-0.6%|&
&|+length +getelements +scalarastclobj|4927.41|203|202.95|1000.265|-0.1%|&
&|'''baseline'''|4920.65|204|203.23|1003.812|0.0%|&
&|+length +index +slice +getelements +getdouble|4811.38|208|207.84|1000.766|2.2%|&
&|+length +index +slice +getdouble|4740.58|211|210.94|1000.262|3.7%|&
&|+length +index +slice +getelements +scalarastclobj|2429.98|412|411.53|1001.151|50.6%|&
&|+length +index +getelements +scalarastclobj|2410.06|415|414.93|1000.175|51.0%|&
&|+length +index +slice +getelements +getdouble +scalarastclobj|2334.63|429|428.33|1001.555|52.6%|&
&|+length +index +slice +getelements +scalarastclobj|2327.93|430|429.57|1001.012|52.7%|&
&|+length +index +slice +scalarastclobj|2319.83|432|431.07|1002.166|52.9%|&
&|+length +index +scalarastclobj|2298.89|435|434.99|1000.019|53.3%|&

# ****Code References****
This test was run using https://core.tcl-lang.org/tcl/timeline?r=tip-636-tcl9-644%|%Tcl branch tip-636-tcl9-644%|%, Tk branch main, https://github.com/bgriffinfortytwo/VecTcl9/tree/abstractlist%|%VecTcl9 abstractlist branch%|% on github.

-Brian