Abstract List (TIP-636) Performance

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

Observations

• The most important column here is µs/# and functions list. The # and net-ms columns are the raw data used to compute µs/#.
• It appears that "slice" and "getelements" play little to no role in this script, and Length alone contributes no benefit.
• With length and index alone, the type is forced to stay as a NumArray, causing more work for the Canvas end to obtain the numeric value.
• But, adding "scalarastclobj" provides for the biggest boost. Here, lindex dives through NumArray data directly, without needing to shimmer the whole value, but when reaching the end scalar value, it returns the value in native Tcl form, i.e, a Tcl Double.
• It is surprising (to me) that the "getdouble" abstraction does not have the same impact as "scalarastclobj".

Code References

This test was run using Tcl branch tip-636-tcl9-644 , Tk branch main, VecTcl9 abstractlist branch on github.

-Brian