Tcl Source Code

Attached is a patch for tclCmdIL.c#184 (HEAD) that 
shows a potential speed up for lsort.

My tests show upto 50% speed improvement on large 
lists when using -index, otherwise >20%.

It works by:
1. caching what's to be compared in the sortElement. 
2. using separate sorting functions for 
string/integer/real and command.

So the cost of the solution is a bigger (4 bytes on my 
machine, if you do not cache the double's) SortElement 
to hold the cached value. This potentially means that 
a list previously sortable would not now be since the 
ckalloc might now fail... this is a perfectably good 
reason for rejecting this patch. Anyhow...

Also in the patch is a testcase. Here are my results:

1. lsort test suite:

% source cmdil.test
==== cmdIL-3.4 SortCompare procedure, -index option 
FAILED
==== Contents of test case:

    list [catch {lsort -integer -index 2 "{a b c} 
\\\{"} msg] $msg

---- Result was:
1 {expected integer but got "c"}
---- Result should have been (exact matching):
1 {unmatched open brace in list}
==== cmdIL-3.4 FAILED

cmdil.test:     Total   112     Passed  107     
Skipped 4       Failed  1
Number of tests skipped for each constraint:
        2       hasIsoLocale
        2       memory


... Just one failure where it now finds an error 
earlier than previously!

2. Here's the testcase output:
1       CLEAN: 110331.4  PATCH: 39657.0  => 64 %
2       CLEAN: 131670.2  PATCH: 92018.2  => 30 %
3       CLEAN: 149079.8  PATCH: 73460.8  => 50 %
4       CLEAN: 119905.0  PATCH: 80620.8  => 32 %
5       CLEAN: 93791.4   PATCH: 73729.8  => 21 %
6       CLEAN: 117635.0  PATCH: 100158.2         => 14 
%
7       CLEAN: 114906.2  PATCH: 50793.0  => 55 %
8       CLEAN: 128672.6  PATCH: 83854.8  => 34 %
9       CLEAN: 157616.6  PATCH: 105437.4         => 33 
%
10      CLEAN: 134954.4  PATCH: 78123.2  => 42 %
11      CLEAN: 94857.4   PATCH: 64058.2  => 32 %
12      CLEAN: 123963.4  PATCH: 97011.8  => 21 %
13      CLEAN: 17.454    PATCH: 16.63    => 4 %
14      CLEAN: 5.979     PATCH: 5.482    => 8 %
15      CLEAN: 6.195     PATCH: 5.377    => 13 %
16      CLEAN: 6.273     PATCH: 4.853    => 22 %
17      CLEAN: 6.805     PATCH: 7.494    => -10 %
18      CLEAN: 6.186     PATCH: 5.685    => 8 %
19      CLEAN: 6.85      PATCH: 6.25     => 8 %
20      CLEAN: 1858129   PATCH: 1027576  => 44 %
21      CLEAN: 2134265   PATCH: 2159487  => -1 %
22      CLEAN: 2187077   PATCH: 1533322  => 29 %
23      CLEAN: 741726    PATCH: 735839   => 0 %
24      CLEAN: 5.2992    PATCH: 4.8409   => 8 %
25      CLEAN: 4.6576    PATCH: 4.1616   => 10 %
26      CLEAN: 4.4018    PATCH: 4.4732   => -1 %
27      CLEAN: 5.4154    PATCH: 4.8429   => 10 %
28      CLEAN: 3.119576  PATCH: 3.103229         => 0 %
29      CLEAN: 1646470   PATCH: 1046932  => 36 %
30      CLEAN: 1456428   PATCH: 1000617  => 31 %
31      CLEAN: 4982307   PATCH: 4436950  => 10 %

Logged In: YES 
user_id=79902

closed at submitter request

Logged In: YES 
user_id=1386588

afredd - I'm going to raise a new patch (as a logged in 
user this time!) so that i can attach a new patch. (It 
doesn't appear possible to do so to this one)

Please close this one. Thanks.

Logged In: NO 

Thinking about this patch over the weekend, i've realised 
the extra 'repr' added to SortElement is unnecesary... the 
caching is only useful for the -index case to avoid 
repeated SelectObjFromSublist. I've some other ideas for 
speeding this up, but may not get time this week.

So don't worry about this patch for now. Cheers.

File Added - 156792: tclCmdIL.c-patch