Menu
▾
▴
[Tcl-bugs] [ tcl-Patches-1366484 ] patch: speed up lsort (follow on to 1360413)
|
From: SourceForge.net <no...@so...> - 2005-12-10 16:30:22
|
Patches item #1366484, was opened at 2005-11-25 13:12 Message generated for change (Comment added) made by dgp You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=310894&aid=1366484&group_id=10894 Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: 17. Commands I-L Group: None Status: Open Resolution: None Priority: 5 Submitted By: afredd (afredd) Assigned to: Donal K. Fellows (dkf) Summary: patch: speed up lsort (follow on to 1360413) Initial Comment: 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) ---------------------------------------------------------------------- >Comment By: Don Porter (dgp) Date: 2005-12-10 11:30 Message: 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. ---------------------------------------------------------------------- Comment By: afredd (afredd) Date: 2005-12-09 12:32 Message: 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. ---------------------------------------------------------------------- Comment By: Donal K. Fellows (dkf) Date: 2005-12-09 11:34 Message: Logged In: YES user_id=79902 Can I delete the older patch from this ticket? ---------------------------------------------------------------------- Comment By: afredd (afredd) Date: 2005-12-02 12:27 Message: 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. ---------------------------------------------------------------------- Comment By: Donal K. Fellows (dkf) Date: 2005-11-28 04:12 Message: 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.) ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=310894&aid=1366484&group_id=10894 |