. This is part of my as yet unreleased 3D showcase at: http://qs.co.nz/Tcl/3D/INITIAL CONVERSIONIn looking at the code we can see some undesirable constructs. These are addressed outside the main optimisation effort as they are just wrong.- return [list ....]
- select ... case x : do x()
- expr { ... [expr ...]}
- for vs foreach
set x [expr {[lindex $M 1 2] * 45}]
set y [expr {[lindex $M 1 2] * 63}]Could become: set p [lindex $M 1 2]
set x [expr {$p * 45}]
set y [expr {$p * 63}]My preference: set x [expr {[set p [lindex $M 1 2]] * 45}]
set y [expr {$p * 63}]While lindex may not be much of an overhead, one only has to change the above to use [averyslowproc ...] and the benefit becomes self-evident.The latter example is the way specialisation would occur without affecting the execution of the code.Memoizing is such a simple technique that any proc that is in fact functional that may be called numerous times during the life of an application should be memoized by default.We have seen that we can auto memoize a proc by including the command 'MEMOIZE as the first line of a proc. We could also simply add the line:memoize MyProcat the end of the source file.Colour lookup cacheWhile the natural string-based approach to colour generation is to use "#$r$g$b" there is no need to do this every frame when the colours are a fixed selection. We precompute the colors and then select the appropriate one from a list. This also allows Tk to convert the object into a colour type for faster processing.It would be nice if Tcl would support a numeric specification for colours such as a three number list, so that we don't have to resort to string concatination all the time.Flatten lists.While the new syntax of Tcl allows for accessing nested lists from lindex like we can access arrays in C, this is not quick when we must perform multiple lindex commands to access data.While the notation of a list of lists models the way we view the data such as vertex arrays, we find that we are repeatedly converting the sublist back into its separate components (e.g., x y z) to process the data. This means constructs like:
foreach v $lvtx {
foreach {x y z} $v {break}
...With a flattened list we can use one foreach with: foreach {x y z} $flat_lvtx {
...Foreach extensionNow the lists are flattened we can place the list scanning into one foreach statement.Most Tcl programmers are familiar with scanning a single value with foreach, but the command is much more flexible than that.A standard loop may look something like: foreach v $vertex_list {
foreach {x y z} $v {break}
foreach f $face {
...We can now merge all the above into one giant loop: foreach {x y z} $::flat_lnv kv $::flat_lvtx p $lpoly
...We still need to process each vertex with a separate loop with: foreach {x y z} $kv {
...This is because we have a variable length of vertices and a fixed length for normals and faces.SpecialisationIn only 50 lines of raw code we specialise three produres each frame. For objects with a small number of faces this reduces the performance due to the time taken to byte code the new procs.Note that in this demonstration we create a new proc from the existing one. This is solely for the purpose of being able to run with the optimisations turned on or off for comparison. This has meant some minor changes to some procs to select the appropriate proc to call. There is nothing in this technique that would stop the changes from being applied to the original procs. This is the desired goal so that we do not need to adopt special coding conventions to allow specialisation to be effective.I have also inserted special comment markers in the code to make it trivial for the specialisation procs to locate the correct code fragment to extract. Again this not necesarry for this technique per se, and we could have appled analysis to the code to make the necessary changes needed for specialisation.In this application we specialise the Projection and VectorMatrix code. As a next level we specialise the Rendering code to inline the vertex projection code as well as take out the Shading code when rendering as wire frame.Cull then transfrom verticesSince we are going to cull the back facing polygons, there is not much point in transforming the vertices for these polygons. We compute the face normal z component and remove the poly by moving to a place off screen. For visible faces we then continue with the x and y projection.Since vertices are shared amoung faces we now need to know which ones we have transformed so that we don't do it twice.For this we use an associative array to provide memoisation of the vertex transformation. We could also have used a list but the multiple lindex commands would be slower than the single foreach.Advantageous ChangesSome code was changed to make the rendering faster that does less work than the previous version. This makes a somewhat unfair comparison of end result but the code dropped does not make a huge difference to the overall time.The changes are:- Culled faces are removed.
- Light vector.
- Transform BarryCenter3D for culling
- For all but the simplest of polyhedra, the specialising of the matrix transformation provides large performance gains.
- At up to 100 faces, the specalising of the Main display proc takes as long to byte code as is saved by inlining the projection code.
- Over 100 faces there is no contest as the specialised code gains increase with an increasing number of polygons.
- At over 2000 polygons the time taken to display the polygons in the Tk canvas starts to dominate the loop time and the apparant frame rate does not increase.
ie if num faces > $breakpoint Specialise else do not.While compiled languages make the decision to optimise at compile time and must have decision logic in the processing loop to select different code paths, in Tcl we have the opportunity to make the decision at run time.Because of the code as data model of Tcl we can analyse the data given at this instant in time and then rewrite our processing routines to best match the given data.With the ability to introspect our environment we can apply heuristics to the running application and dynamicaly change the processing and evaluate performance of those changes.The technique of specialisation can be applied to existing code, thus allowing the programmer to write code using a structured approach without having to think in terms of how to make it efficient.The days of writing programs to process data are over. As programmers we need to focus more on writing programs that create programs that process data.
GS (050827) - Wow! Very, very impressive. Thanks for this wonderful and instructive contribution.RS 2005-08-28 - Another argument for using set res instead of return $res: the latter, while being easier readable for people not so acquainted with Tcl, is in fact two commands - $res being basically equivalent to [set res]. But this is a (sometimes) hotly debated matter of taste.RHS 22Sept2005 - Just to add an opposing argument, the use of [return $x] is considered better style by some, since it gives a clear indication that the code is returning the value on purpose, rather than just because it happens to be the last command to run in the proc. I'll note that I prefer [return $x] myself, but rely on my automated tests to tell me what behaviour is intended, and what is an accidental effect of how I wrote the code.
