Tcl Source Code

The attached patch against 8.5.1 is a cleanup of the [lrange] implementation, including:

 - use of T_LOL to stick to the style of other list ops, instead of a complex and unique anti-shimmering share-intrep mechanism dedicated to a rare and already fast case [lrange $x $x $x].

 - flattening of if-return's to stick to the style of other list ops, improving readability.

 - detection of unshared case to operate in-place, by calling twice Tcl_ListObjReplace (in correct order).

The first two points are just a matter of style, but allow for the third, which is a pretty significant optimization. Measurements on a 100-million list [lrepeat 100000000 1]:

 [lrange ... 1 end] in-place gives a 3x speedup
 [lrange ... 0 end-1] in-place gives a 24000x speedup

-Alex


% set l [lrepeat 100000000 1];llength $l
100000000
% time {set l [lrange $l 1 end];llength $l}
814663 microseconds per iteration
% proc K { x y } {set x}
% time {set l [lrange [K $l [unset l]] 1 end];llength $l}
272517 microseconds per iteration

% set l [lrepeat 100000000 1];llength $l
100000000
% time {set l [lrange $l 0 end-1];llength $l}
815985 microseconds per iteration
% set l [lrepeat 100000000 1];llength $l
100000000
% time {set l [lrange [K $l [unset l]] 0 end-1];llength $l}
34 microseconds per iteration

Logged In: YES 
user_id=496139
Originator: YES

Test suite updated with a relative speed test.

Logged In: YES 
user_id=496139
Originator: YES

Committed to HEAD.
Will be preparing test and tclbench cases from now on.
Leaving this open as a reminder.

Logged In: YES 
user_id=148712
Originator: NO

This looks OK for commit to HEAD; Alex, please do. 

It would be nice to insure that the testsuite covers any possible gotcha (although I cannot thing of any right now). 

It'd be also nice to check if tclbench will expose the improvement, and to write a small bench to include there if not.

Logged In: YES 
user_id=496139
Originator: YES

Miguel, again throwing this one to you in the hope of reducing the pressure on Donal's shoulders...
Tell me if you prefer otherwise.

Logged In: YES 
user_id=80530
Originator: NO


dkf can make the call whether he wants
any changes before committing.

Logged In: YES 
user_id=496139
Originator: YES

About the needed refactoring to avoid (List *), please notice that I stole it from Tcl_LreverseObjCmd, right in the same file, and that half a dozen other places in tclCmdIL.c directly reach into Lists. So, I suggest either to leave it that way, or to clean everything up at the same time (slight preference for the former). Your choice ?

Also, thanks for the K-free K trick. I was really amazed to see $l"" not shimmer to pure-string; has this optimization of concat existed for long ?

Logged In: YES 
user_id=80530
Originator: NO


The patch intrudes a bit into the
internal rep of the "list" Tcl_ObjType
with the cast to (List *).  I'd like a
slight refactoring better where that
code got moved into tclListObj.c as
some internal routine called by
Tcl_LrangeObjCmd().  Just a preference
to put as much of the code needing to know
about "list" intReps over in tclListObj.c
as we can.  Not a requirement, but something
nice to do.

I know we're not "pure" by that measure
currently.  It's about preference and
direction.

Might be interesting to try the K-free K
as well:

lrange $l[unset l] 0 end-1

File Added - 265796: lrange_cleanup.patch