Tcl Source Code

Sorry about the repeated submission. (Doesn't seem 
like 'nobody' can upload a second file.)

Here's the percentage speed increase of the current 
patch done on a 8.5a3 on a 100 item list (on one 
particular run):

-ascii => 37 %
-ascii -unique => 36 %
-integer => 48 %
-integer -unique => 44 %
-real => 15 %
-real -unique  => 17 %
-index 1  => 50 %
-index 1 -unique => 48 %
-command compare_cmd => 0 %
-command compare_cmd -unique => 0 %

The saving is better with larger lists. Don't expect 
any saving when using -command, as the called tcl 
command takes the bulk of processing time. See the 
code for why -real and -unique are not quite as quick 
(but still quicker). The "-index $n -integer" is the 
best improver running in less than a third of the 
previous time for lists of more than a 100.

The patch is against the current HEAD (184). (I've not 
tested it - just ported across my 8.5a3 tested version 
into the HEAD copy. fingers crossed)

Logged In: YES 
user_id=1312539
Originator: NO

This Tracker item was closed automatically by the system. It was
previously set to a Pending status, and the original submitter
did not respond within 14 days (the time period specified by
the administrator of this Tracker).

Logged In: YES 
user_id=68433
Originator: NO

Recent [lsort] enhancements (2007-12-21 through 2007-12-26) incorporated (a different implementation of) the most important aspects of this patch (notably, the Schwarzian transform), while preserving the original algorithm.

File Deleted - 199797:

File Added - 226743: tclCmdIL.c#1.114-patch

Logged In: YES 
user_id=1386588
Originator: YES

Patch for 1.114 of tclCmdIL.c (current HEAD).
(NB. test cmdIL-3.4 will fail, but see previous comment)


File Added: tclCmdIL.c#1.114-patch

File Deleted - 171463: 



File Added - 199798: cmdIL.test-patch

File Added - 199797: tclCmdIL.c#1.90-patch

Logged In: YES 
user_id=1386588


Here's an updated patch that runs clean against against the current HEAD version.

Also a patch for cmdIL.test that:
a) splits the one test the patch fails: cmdIL-3.4
 (which is an error test that contains 2 errors,
 and the different implementations pick different ones to return)
 into 2 separate tests
b) some additional lsort tests for:
 * the documented special case of a single element list
   (which was really just documenting the old implementation rather
    than intended functionality)
 * a testcase that calls lsort from another lsort's -command procedure.
c) a test for -nocase using non-ASCII strings. This will fail, but see SW#1236896.

File Deleted - 158409: 



File Added - 171463: tclCmdIL.c#1.86-patch4

Logged In: YES 
user_id=1386588

Found a couple more minor enhancements that shave off
a few cycles here and there. Also cleaned up my code.
Changes:
1. Added SortElementCache struct.
2. Defined SORTELEMENTCACHE_HAS_REAL behaviour.
3. Only SelectObjFromSublist if (sortInfo.indexc != 0)
 ie. save N function calls in common case
4. Store a -comand's objc in sortInfo saves NlogN calls
 to Tcl_ListObjLength.
5. nonUniqueCount ensures final result list is always
 preallocated to the correct length. Although timing does
 not reveal any speed gain either way, it does at least
 ensure a long living result of lsort does not take up
 unused space.

File Added - 162984: perlsort.zip

Logged In: YES 
user_id=1386588

OK as promised :-)
Here's a zip file with a 8.5a3 tclCmdIL.c with Perl's
merge sort in. I've included some timing results
and a test script. NB. the sort is documented as being
stable.

*WARNING* this is not a patch (yeah - i know this probably
isn't the best place for it :-) but might be of interest
to someone.

So is it faster? .... Well, if the list has any
existing order, then yes. For rand()om data using a quick
comparator (ie. not -command!) then no.
It can be massively faster; it is usually not too far off.

Overall. I'm inclined not to go any further with this.
The perl sort uses slightly more memory, and is slower
for [lsort -integer $a_random_list_of_ints].
Not much point swapping the sort alg. if it is slower
in a potentially likely situation.

NB. while i'm here (and apologies for being OT)...
lsort could use a -numeric option
(or -bignum, or ...) that is equivalent to:

proc num_cmp {a b} {
 if {$a > $b} { return 1 }
 if {$a < $b} { return -1 }
 return 0
}
lsort -command num_cmp $num_list

as currently there is no builtin way to sort
either wides or the new big nums if they are
too big. Consider:

set l [list \
 [expr wide(100000000000000002)] \
 [expr wide(100000000000000001)] \
 [expr wide(100000000000000003)] \
]

puts [lsort -real $l] # wrong result
puts [lsort -integer $l] # integer too big

I feel a TIP coming on :-)

Logged In: YES 
user_id=80530


As you're exploring other
algorithms for [lsort],
take note that [lsort]
is documented to provide
a stable sort, and any 
changes need to preserve
that property.

Logged In: YES 
user_id=1386588

dkf> Can I delete the older patch from this ticket?

Sure. Thanks!

#1 Small point... the comment in there about running with 
SORTELEMENT_HAS_OBJPTR==0 on my old 350Mhz laptop should 
say "faster with lists of more than 1000 elements" (the tip 
over seems to be ~700). However, on my quick machine 
SORTELEMENT_HAS_OBJPTR==1 is very definately the better 
option.


#2 btw - i've been comparing the MergeSort alg. against the 
equivalent in Perl and Python. Tcl's does a significant 
number more *comparisons* - especially so for almost sorted 
data (a common case). In fact there's is O(N) for sorted 
data. I'm having a go at hacking Perl's sort alg. into 
tclCmdIL.c to get some benchmark figures. I undertand the 
resultant patch may not be acceptable, but it might be a 
trigger for further work. I'll post more later.
Cheers.

Logged In: YES 
user_id=79902

Can I delete the older patch from this ticket?

File Added - 158409: tclCmdIL.c-patch3

Logged In: YES 
user_id=1386588

Minor update on previous patch.
Main change is to preallocate the result object as a big 
enough list in the case of a non -unique lsort.

Logged In: YES 
user_id=79902

Only the registered submitter (or a tracker tech, i.e. a
maintainer) can manage attachments to a tracker entry.
That's just the way SF works (and I suppose I can see why,
even if it is inconvenient sometimes.)

File Added - 157534: patch2-tclCmdIL.c