The need for speed
Michael
some time ago I wrote a parser to decode a binary file. The binary
file contained a number of records and only some of the fields need to
be extracted and only some fields need to be transformed. The
performance was OK where I could decode a file, do some basic
filtering, do a couple of transformations, and generate an output file
@ 8million records per hour.
The last week I've been looking at ways of improving on this time. My
target is 20 million records per hour for the format that I'm working
with and using my laptop with a Intel Centrino 1.2Mhz with 1GB of RAM.
I'm upto 11.8M with some minor changes to the C++ shared library and
the TCL code - improvement of 47%.
I've taken some rough timings and 17% of time is spend in the C++
part. The other 83% of time is spent in the TCL part. Stopping short
of coding the TCL portion into C/C++ I'm wondering whether there are
any more changes I could make to improve the TCL part.
The variables "mapping" and "settings" are set once at startup from a
configuration file. These I want to keep if possible to allow user to
configure the ouput.
# Open file and create indexes
set recs [ama::init $settings(input,file)]
puts "Records : $recs"
for {set i 0} {$i < $recs} {incr i} {
catch {unset input}
ama::get $i input
#continue
# Do Transformations
if {[doTransformations input derived]} {
continue
}
# Create output record
set record ""
foreach item $settings(output,fields) { << This is where most
time is spent
if {[info exists derived($item)]} {
# Derived value
append record $derived($item)
} elseif {[info exists mapping($item)]} {
if {[info exists input($mapping($item))]} {
# Direct mapping from input
append record $input($mapping($item))
} elseif {[lsearch $settings(input,fields)
$mapping($item)] == -1} {
# mapped value from configuration
append record $mapping($item)
}
}
append record ,
}
set record [string trimright $record ,]
append buffer $record\n
}
# Write buffer to file
Any suggestions welcome.
Michael
miguel
(In no particular order)
(1) Is this within a proc body? If not, make it so! This is likely the
biggest gain.
(2) Move to Tcl8.5: much speedier [info exists] and dicts (see below)
(3) Replace 'settings' with a dict, not a list: [dict exists] is much
faster than lsearch (especially if it is a large list; is it?)
(4) Replace arrays with dicts (stored in scalar local vars )
(5)
if {...} {
...
append record $foo, ;# add the comma here
} elseif {...} {
append record $moo, ;# add the comma here
} else {
append record ,
}
(6) [not measurable, outside the loop. But while we're at it ...]
"catch {unset input}" -> "unset -nocomplain input"
sleb...@gmail.com
Your code don't appear to be inside a proc. Try writing it as a proc:
Donal K. Fellows
> I've taken some rough timings and 17% of time is spend in the C++
> part. The other 83% of time is spent in the TCL part. Stopping short
> of coding the TCL portion into C/C++ I'm wondering whether there are
> any more changes I could make to improve the TCL part.
> Any suggestions welcome.
The first step is to run all that code inside a Tcl procedure. This will
help because it will mean that variable accesses (and the [foreach]
command) will be much more heavily optimized internally. Also note that
your code will gain quite considerably from being built against 8.5, as
the [info exists] command is bytecompiled there. You can also use the
'in' operator for a small boost. In fact, the combination of all these
things would make your inner loop wholly bytecompiled...
Donal.
tom.rmadilo
> for {set i 0} {$i < $recs} {incr i} {
> catch {unset input}
You can also avoid doing [catch {unset input}] if you just set input
the first time, so:
set input ""
for ....
unset input
...
Michael
Thanks (all) for your suggestions. I will for sure try them and see
what performance gain each one gives.
Points 1: Already doing this
proc decodeAma { } {
global settings
global mapping
variable derived
variable input
...
...
set fname ouput
set fd [open $fname w]
if {[info exists buffer]} {
puts $fd $buffer
}
close $fd
ama::end
}
puts [time decodeAma]
Point 2: I'm already doing. I'm using the ActiveState build. Would I
gain anything if I did a compilation myself? This build has threads
enabled but I may use threads later if I can work out how to share
memory between the threads (interpreters) and if I say with TCL.
$ /cygdrive/c/Tcl/bin/tclsh85
set tcl_interactive 1
1
% info tclversion
8.5
% info level
0
% info patchlevel
8.5a7
Point 3: Test files I'm using range from 1M to 10MB with approx 8,000
to 80,000 records.
Items in settings(input,fields) read from configuration file) = 6.
TrunkIdOutgoing.TrunkGroupNumber,DateTimeDuration.Duration,DateTimeDuration.StartTime,
CallingPartyNumber.Digits,CalledPartyNumbers.Digits,ConnectionIdentification
and settings(output,fields) read from configuration file = 49
BSCS_Mapping_Reference,BSCS_stream_description,Served_party_Directory_Number,
Served_party_numbering_plan,Served_party_type_of_number,Other_party_Directory_number,
Other_party_numbering_plan,Other_party_type_of_number,Dialled_digits,
Dialled_digits_numbering_plan,Dialled_digits_type_of_number,Third_party_Directory_Number,
Third_party_numbering_plan,Third_party_type_of_number,Call_completion_indicator,
Call_identification,Call_Classification,Writing_network_indicator,Timestamp_of_the_call_record,
Time_offset_to_UTC_of_the_writing_switch,Service_identification,Action_code,Served_party_Port,
Served_party_Port_numbering_plan,Partial_record_identifier,Original_call_duration,
Unit_of_Measure_Code,Incoming_TRUNK,Outgoing_TRUNK,PRE_RATED_INDICATOR,
PREPAY_IND_INDICATOR,SPONSORED_CALL_INDICATOR,AMOUNT,CURRENCY_USED,
TEST_INDICATOR,DATA_VOLUME,S_P_EQUIPMENT,CAUSE_FOR_FORWARD,USER_NAME,
USER_OWNER,LCP_NAME,LCP_OWNER,PUBLIC_IP_ADDRESS,SF_TERMINATE_CAUSE,SF_PRODUCT_PROFILE_ID,
SERVICE_TYPE_ID,WISPR_LOCATION_ID,WISPR_LOCATION_NAME,WM_TYPE_OF_AUTHENTICATION
Point 4) Replace arrays with dicts (stored in scalar local vars )
I have the C++ code setting a global variable array "input". Should I
replace this with a dict too? If so what is the C prototype for this.
I'm using this to set strings (as suggested by Donal last time)
Tcl_SetVar2Ex(interp, Tcl_GetString(objv[2]),s.c_str(),
Tcl_NewStringObj(s2.c_str(), s2.length()),
TCL_GLOBAL_ONLY);
and this to set up integers
Tcl_SetVar2Ex(interp, Tcl_GetString(objv[2]),s.c_str(),
Tcl_NewIntObj(fm->getI16(roffset + 4)),
TCL_GLOBAL_ONLY)
Where Tcl_GetString(objv[2]) is the variable "input".
(I wonder whether I should just set everything as a string as the
result is appended to a string buffer).
I know I should look this up but my head is spinning as I'm trying to
recode the C++ part so I can eventually split the processing into
multiple threads (OS level) - then move to a 2 core then 4 core CPU
once I squeeze eveything I can out of this CPU.
Point 5) No improvement. Very slight decrease in performance <1%
Point 6) No noticeable improvement.
Now I will try changing the "settings" variable to a dict to see what
difference this makes.
For anyone who's interested I'm building the shared lib (dll) using
mingw environment and g++ compiler. Eventually I've try with Intels
compiler to see how much of a difference this makes plus or minus.
$ g++ -v
Using built-in specs.
Target: mingw32
Configured with: ../gcc-4.2.2/configure --prefix=/mingw --with-local-
prefix=/mingw --build=i686-pc-linux-gnu --host=mingw32 --
target=mingw32 --enable-languages=c,c++,fortran,objc,obj-c++,treelang
--disable-nls --disable-werror --disable-win32-registry --enable-sjlj-
exceptions --enable-threads=win32 --disable-libstdcxx-pch --enable-
fully-dynamic-string --enable-libgomp --with-gmp=/extra/crossgcc/win-
gmp-install --with-mpfr=/extra/crossgcc/win-mpfr-install --with-
libiconv-prefix=/extra/crossgcc/win-iconv-install --with-tune=generic
Thread model: win32
gcc version 4.2.2 (TDM-1)
Michael
Joe English
>
> [...] I'm wondering whether there are
> any more changes I could make to improve the TCL part.
Just looking at the inner loop:
[01] set record ""
[02] foreach item $settings(output,fields) {
[03] if {[info exists derived($item)]} {
[04] # Derived value
[05] append record $derived($item)
[06] } elseif {[info exists mapping($item)]} {
[07] if {[info exists input($mapping($item))]} {
[08] # Direct mapping from input
[09] append record $input($mapping($item))
[10] } elseif {[lsearch $settings(input,fields) $mapping($item)] == -1} {
[11] # mapped value from configuration
[12] append record $mapping($item)
[13] }
[14] }
[15] append record ,
[16] }
[17]
[18] set record [string trimright $record ,]
[19] append buffer $record\n
Lines 6-13, common subexpression elimination: store
"$mapping($item)" in a variable and reference that
instead. This won't be noticeably faster, but may
make what follows easier to read :-)
On line 10, the [lsearch $settings(input,fields) ...] test
takes time proportional to the length of the list.
Consider using an array lookup instead, especially
if the list is long. For example, outside the loop,
initialize:
foreach element $settings(input,fields) {
set configured($element) 1
}
and replace the "if {[lsearch ...] == -1} " test with
"if {![info exists configured(...)]}". This takes
O(1) time instead of O(N).
Each time through the loop, the program _sometimes_
appends a new value to "record", and _always_ appends
a comma; then at the end you do:
[18] set record [string trimright $record ,]
This removes the final "," added after the last value,
along with those added in the latest iterations of
the loop where no value (or an empty value) was appended,
and any trailing commas in the last nonblank value.
It does not, however, remove any ",,..." sequences
in the middle of the record.
I suspect that this is not the precise behavior you want.
Consider using [lappend] in lines 5, 9, and 12 to
build the record as a list instead of using [append]
to build it as a string, and replace this:
[18] set record [string trimright $record ,]
[19] append buffer $record\n
with this:
[19] append buffer [join $record ","] "\n"
(BTW, using [append var $a $b] will typically be faster
than [append var "$a$b"], especially if $a is long, since
it requires fewer copies. This is a good rule of thumb.)
You may need to modify the inner loop to [lappend] an
empty string in the case where the field is unmapped,
depending on what your precise requirements are.
That's all I can spot.
--Joe English
Chun
This gave me around 2% improvement!
>
> On line 10, the [lsearch $settings(input,fields) ...] test
> takes time proportional to the length of the list.
> Consider using an array lookup instead, especially
> if the list is long. For example, outside the loop,
> initialize:
>
> foreach element $settings(input,fields) {
> set configured($element) 1
> }
>
> and replace the "if {[lsearch ...] == -1} " test with
> "if {![info exists configured(...)]}". This takes
> O(1) time instead of O(N).
>
This gave me a 5% decrease in performance :(
I wonder if changing the arrays I have into lists will make a
difference (note to myself to try this) - first I have to try the
dicts.
> Each time through the loop, the program _sometimes_
> appends a new value to "record", and _always_ appends
> a comma; then at the end you do:
>
> [18] set record [string trimright $record ,]
>
> This removes the final "," added after the last value,
> along with those added in the latest iterations of
> the loop where no value (or an empty value) was appended,
> and any trailing commas in the last nonblank value.
> It does not, however, remove any ",,..." sequences
> in the middle of the record.
>
> I suspect that this is not the precise behavior you want.
>
Well spotted would be a bug if the last field wasn't always set.
> Consider using [lappend] in lines 5, 9, and 12 to
> build the record as a list instead of using [append]
> to build it as a string, and replace this:
>
> [18] set record [string trimright $record ,]
> [19] append buffer $record\n
>
> with this:
>
> [19] append buffer [join $record ","] "\n"
>
> (BTW, using [append var $a $b] will typically be faster
> than [append var "$a$b"], especially if $a is long, since
> it requires fewer copies. This is a good rule of thumb.)
>
> You may need to modify the inner loop to [lappend] an
> empty string in the case where the field is unmapped,
> depending on what your precise requirements are.
>
> That's all I can spot.
Thanks for the tips - that's 2% increase, more readable and a bug
fix :)
>
> --Joe English
Chun
Hi,
I changed to mapping to a dict and there was a 4% increase in
performance.
The code block looks like this now.
proc decodeAma { } {
variable settings
variable derived
variable outputFields
variable mappingFields
variable input
# Open file
set recs [ama::init $settings(input,file)]
puts "Records : $recs"
for {set i 0} {$i < $recs} {incr i} {
unset -nocomplain input
ama::get $i input
# Do transformations
if {[doTransformation_Ama input derived]} {
continue
}
# Create output record
set record ""
foreach item $settings(output,fields) {
if {[info exists derived($item)]} {
# Derived value
lappend record $derived($item)
} else {
set a [dict get $mappingFields $item value]
if {[info exists input($a)]} {
# Direct mapping from input
lappend record $input($a)
} elseif {[lsearch $settings(input,fields) $a] == -1} {
# mapped value from configuration
lappend record $a
} else {
lappend record ""
}
}
}
append buffer [join $record ","] "\n"
}
outputFile buffer
ama::end
}
I'm beginning to see that not much more can be done. One interesting
thing was that just by swapping from cygwin (running activstate 8.5a7
c:) to mingw (tclsh 8.5a6 /usr/local/bin) I got a 12% boost - don't
know whether it was the different build version or the environment.
Perhaps I will try with the latest from Activestate to see what
difference that makes.
I'm going to have to do something drastic like trying Lua or Neko. I
know this is off on a tangent but why does Lua benchmark more than 3x
TCL?
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=tcl&lang2=lua
And if this link is to be believed the Neko is faster still
http://nekovm.org/lua#virtual_machine
Michael
Donal K. Fellows
> I'm beginning to see that not much more can be done. One interesting
> thing was that just by swapping from cygwin (running activstate 8.5a7
> c:) to mingw (tclsh 8.5a6 /usr/local/bin) I got a 12% boost - don't
> know whether it was the different build version or the environment.
> Perhaps I will try with the latest from Activestate to see what
> difference that makes.
Do try 8.5.0 as that's had a number of performance improvements that you
*will* benefit from. (We didn't do that much speedup work in the alphas
as chasing a running target gets old fast.)
Donal.
Michael
Thanks Donal!
I downloaded 8.5.0 source from http://tcl.sourceforge.net/ (release
date December 20, 2007).
$ tclsh85
set tcl_interactive 1
1
% info patchlevel
8.5.0
%
Built with -O3. This this gave 76% improvement :) - I even had some
back ground task running so CPU usage was not 100% avaliable.
That means I'm @ > 26.7 million records per hour which is an increase
of 333% from the original 8 million.
Thanks all for your help.
Mission accomplished. On to the dual core processor now.
Michael
Michael
Hi,
was reading other posts and came across Mark Roseman post.
http://www.markroseman.com/tcl/guide85.html
Here instead of lsearch he shows example of the new "in" command. This
gives me a 5% which pushes me just over the 30 million records per
hour mark!
Instead of
} elseif {[lsearch $settings(input,fields) $value] == -1} {
I do:
} elseif {$value in $settings(input,fields)} {
The lastest code is here:
proc decodeAma { } {
variable settings
variable derived
variable outputFields
variable mappingFields
variable input
# Open file
set recs [ama::init $settings(input,file)]
puts "Records : $recs"
for {set i 0} {$i < $recs} {incr i} {
unset -nocomplain input
ama::get $i input
# Do transformations
if {$input(DateTimeDuration.Duration) == 0} {
continue
}
doTransformation_Ama derived
# Create output record
set record ""
foreach item $settings(output,fields) value $mappingFields {
if {[info exists derived($item)]} {
# Derived value
lappend record $derived($item)
} else {
if {[info exists input($value)]} {
# Direct mapping from input
lappend record $input($value)
} elseif {$value in $settings(input,fields)} {
lappend record ""
} else {
# mapped value from configuration
lappend record $value
}
}
}
append buffer [join $record ","] "\n"
}
if {[info exists buffer]} {
outputFile buffer
}
ama::end
}
Michael
Donal K. Fellows
> Here instead of lsearch he shows example of the new "in" command. This
> gives me a 5% which pushes me just over the 30 million records per
> hour mark!
The other thing that you're benefiting from in 8.5.0 is that your calls
to [info exists] are byte-compiled. Previously, they were very slow but
now they're about the same speed as reading a variable (i.e. *very* fast
indeed for local variables). Enjoy!
Donal.
Gerhard Reithofer
> On Dec 25, 7:24 am, Michael <chun....@evolving.com> wrote:
> > On Dec 24, 6:40 pm, "Donal K. Fellows"
> >
> > <donal.k.fell...@manchester.ac.uk> wrote:
> > > Chun wrote:
> > > > I'm beginning to see that not much more can be done. One interesting
> > > > thing was that just by swapping from cygwin (running activstate 8.5a7
> > > > c:) to mingw (tclsh 8.5a6 /usr/local/bin) I got a 12% boost - don't
> > > > know whether it was the different build version or the environment.
> > > > Perhaps I will try with the latest from Activestate to see what
> > > > difference that makes.
> >
> > > Do try 8.5.0 as that's had a number of performance improvements that you
> > > *will* benefit from. (We didn't do that much speedup work in the alphas
> > > as chasing a running target gets old fast.)
...
> Instead of
>
> } elseif {[lsearch $settings(input,fields) $value] == -1} {
>
> I do:
>
> } elseif {$value in $settings(input,fields)} {
You shouldn't forget that searching in sorted lists is much, much
faster. If the list is already fixed at beginning of the loop do a lsort
once.
Example list with 1000000 random entries:
time {lsearch $L $r}
set s [lsort $L]
time {lsearch -sorted $S $r}
610993.4 microseconds per iteration
13.4 microseconds per iteration
--
Gerhard Reithofer
Tech-EDV Support Forum - http://support.tech-edv.co.at
Alexandre Ferrieux
Wow ! That one has been under my radar for I don't know how long...
How long, by the way ? I don't see a trace in the ChangeLog, and
skimming through the SF WebCVS is so excruciatingly slow...
-Alex
Donal K. Fellows
> Wow ! That one has been under my radar for I don't know how long...
> How long, by the way ? I don't see a trace in the ChangeLog, and
> skimming through the SF WebCVS is so excruciatingly slow...
You're best searching the changes file for that. And the entry is from
2000-05-08, which was very very early in the 8.4 cycle.
Donal.
Jeff Hobbs
wrote:
Yes, an old feature addition. It is one that you have to ensure you
pass a sorted list to, as it essentially a hint that a binary search
on the list is acceptable.
Jeff
Fredderic
Gerhard Reithofer <gerhard....@tech-edv.co.at> wrote:
>> Instead of
>> } elseif {[lsearch $settings(input,fields) $value] == -1} {
>> I do:
>> } elseif {$value in $settings(input,fields)} {
> You shouldn't forget that searching in sorted lists is much, much
> faster. If the list is already fixed at beginning of the loop do a
> lsort once.
This is one case where I've often wondered if adding some kind of flags
to TCL's internal structure of a list value would be handy. An
lsorted-default flag would allow "in" and "ni" to automatically employ
binary searching, and could be picked up by [lsearch] also to
automatically assert the -sorted option if it wasn't given. The list
handling functions would clear the flag if anything changes the list
structure (a few bits and pieces may need to be fortified a little
more), and/or re-check the changed portion to make sure it still fits.
Similarly [lsort] (with default sort options) could simply skip sorting
the list if the sorted flag is already set and the sort requested is
the default. This would make it safe to simply throw in an [lsort]
even if it won't normally be needed, just so you can safely do faster
searches.
Perhaps also, instead of just a single-bit flag, use a value indicating
HOW the list was sorted, allowing other sort orderings to be searched
with equal grace (a bitmap of the available sort options should do
the trick, for all but the command sort method where you're just SOL).
Giving [lsort] an option to indicate whether the list is sorted, might
be handy, and be the basis of [lreplace]s code to decide whether or not
to clear the sorted indicator (the internal C function would accept a
start and end position, which would be simply specified as the list
extents by the [lsort] TCL command). It'd also set the flag if
appropriate (relieving the various list manipulation options of
having to do it themselves), and perhaps even take a stab at figuring
out HOW a list is sorted, where appropriate, which might allow it to .
The way I see it, just because a list is sorted using the dictionary
sort, shouldn't make it any less bsearch-able. And this would also fix
that, and make using the -sorted option a whole lot more appealing.
I still think the entire searching and sorting mechanism needs to be
abstracted out, and perhaps made extensible... [lsort] and [lsearch],
(and probably [lindex] and the rest too, to a lesser degree) should both
have exactly the same option set for identifying list structure; they
should both support working with nested lists, grouping fixed numbers of
consecutive items in a list to be manipulated as a virtual sub-list
item, etc. The simplest way would be to construct a sort-options
record, process any options the individual command recognises, and hand
others, along with the sort options record, to the sorting and
searching sub-system. It could then be asked for a suitable sort
function, to which you'd pass the record for anything it needs.
That'd also pave the way for extensibility in sort orders, which as we
all know would be painfully slow to extend from TCL, but quite readily
doable from an extension. And having the various sort options
available from a ::tcl::sorts namespace would be handy for quick
compares along the lines of [string compare] (which itself would come
under ::tcl::sorts::unsorted, or something).
Anyone else think this is a good/bad idea?
Fredderic
Alexandre Ferrieux
>
> This is one case where I've often wondered if adding some kind of flags
> to TCL's internal structure of a list value would be handy. An
> lsorted-default flag would allow "in" and "ni" to automatically employ
> binary searching, and could be picked up by [lsearch] also to
> automatically assert the -sorted option if it wasn't given. The list
> Anyone else think this is a good/bad idea?
Sorry, but I don't like it too much...
Indeed, hiding things is possible when they don't make sense at the
script level (like internal reps and ref counts). On the contrary, the
knowledge that a list is sorted according to a given ordering is an
algorithmic notion, that mightily makes sense to the script
programmer. Moreover, the fact that it is sorted may come from the
outside, not necessarily from a previous [lsort] (e.g by
construction).
Hence, I'm very happy to see this [lsort -sorted] I've been so long to
notice ;-)
I don't see it as "low level", but instead as an algorithmic level
tool for optimizations.
As far as in/ni are concerned, I guess the natural sequel is to add
syntax for passing "options" to them. I have no strong opinion on the
syntax; my $0.02: {$x in -sorted -real $l} etc...
-Alex
Donal K. Fellows
> As far as in/ni are concerned, I guess the natural sequel is to add
> syntax for passing "options" to them. I have no strong opinion on the
> syntax; my $0.02: {$x in -sorted -real $l} etc...
No, that's a syntactic horror. The real answer is to compile [lsearch]
suitably.
Donal.
Donal K. Fellows
> Perhaps also, instead of just a single-bit flag, use a value indicating
> HOW the list was sorted, allowing other sort orderings to be searched
> with equal grace (a bitmap of the available sort options should do
> the trick, for all but the command sort method where you're just SOL).
In theory yes (and FYI we've got flag bits in the list internal
representation already as part of other optimizations) but in practice
I'm really uncertain that the amount of work and complexity is
justified. Some magic is all very well, but QAing this is likely to be
very annoying...
> Anyone else think this is a good/bad idea?
With my Maintainer hat on, I think it's probably a bad idea. Especially
the increase in bloat of the bytecode engine itself. :-\
Donal.
Fredderic
Hmmm..... They're such a neat little thing, it's a shame to have to
ignore in/ni so I can use sorted searches.
From a purely stylistic view, I wouldn't object to seeing in/ni ONLY
work on sorted lists. Though I recognise how much of a nightmare that
would be for unsuspecting noobies. ;)
But I do have to agree, I dread the thought of allowing options to
[expr] operators...! *shivers* Much rather they stay as they are than
go down that road.
Out of perverse curiosity (because I'm a perverse kinda guy), mind if I
ask what those flag-enabled list optimisations you mentioned are?
Fredderic
Gerhard Reithofer
> On Wed, 26 Dec 2007 19:06:20 +0100,
> Gerhard Reithofer <gerhard....@tech-edv.co.at> wrote:
>
> >> Instead of
> >> } elseif {[lsearch $settings(input,fields) $value] == -1} {
> >> I do:
> >> } elseif {$value in $settings(input,fields)} {
> > You shouldn't forget that searching in sorted lists is much, much
> > faster. If the list is already fixed at beginning of the loop do a
> > lsort once.
>
> This is one case where I've often wondered if adding some kind of flags
> to TCL's internal structure of a list value would be handy. An
> lsorted-default flag would allow "in" and "ni" to automatically employ
... removed much wise stuff ;-) ...
> Anyone else think this is a good/bad idea?
This would lead to some sort of different list types.
I also am not very happy to "enrich" TCL objects, as there had be
implemented all introspection methds too to be transparent.
I don't see the reason to focus programming to specific features too
much (like "do only use ni/in...") as this language has a wide range of
specialized functions. My proposal is "just use the right one"!
I like the [string equal ...] construct, but I also use [string compare
...] and eq-operator when when it is the better option.
I'm more suprised why the ni/in operators have been optimized but not
lsearch.
I like TCL because it does not consist ca. 3000 functions (like PHP
does) and this should not be changed without a weighty reason.
Fredderic
Gerhard Reithofer <gerhard....@tech-edv.co.at> wrote:
> On Thu, 27 Dec 2007, Fredderic wrote:
>> On Wed, 26 Dec 2007 19:06:20 +0100,
>> Gerhard Reithofer <gerhard....@tech-edv.co.at> wrote:
>>> You shouldn't forget that searching in sorted lists is much, much
>>> faster. If the list is already fixed at beginning of the loop do a
>>> lsort once.
>> This is one case where I've often wondered if adding some kind of
>> flags to TCL's internal structure of a list value would be handy.
>> An lsorted-default flag would allow "in" and "ni" to automatically
>> employ
> ... removed much wise stuff ;-) ...
>> Anyone else think this is a good/bad idea?
> This would lead to some sort of different list types.
This got me curious.....
I don't see how. I mean, you _could_ have one list type for unsorted
lists, and a second list type that has an extra field for storing the
sort criteria used. But all that would achieve would be to save a
little memory, and probably waste more time than it's worth. The two
types would be functionally identical, and utterly indistinguishable
from a scripting point of view. I'm not talking about transparently
sorting the list, or something freaky like that (although that could be
an entertaining feature - a list that once sorted, stays sorted no
matter what you try to do to it ;) ).
> I also am not very happy to "enrich" TCL objects, as there had be
> implemented all introspection methds too to be transparent.
But, as Donal pointed out in another reply, TCL lists are already
"enriched" by some optimisation flags. All I was proposing, are some
more flags. A little extra checking would be needed anywhere that items
are inserted or replaced (deletions would be fine) to check whether the
list is still sorted, and clear the sort flag when appropriate. (Donal
doesn't like it because it means more work, and I'm much too
chicken-shit to go delving into the innards of the TCL core
myself... ;) )
I'm not sure that it needs any kind of introspection method. If you
want to be able to use fast searching, then make sure you sort the list.
That's an issue for the script author, and I doubt you'd have any kind
of improvement by checking whether the sorted flag is set, and reacting
differently. Especially considering an already sorted list won't
necessarily be marked as sorted. Though it might be handy generally,
if [lsort] had an option to check whether a list is sorted, without
actually sorting it.
> I don't see the reason to focus programming to specific features too
> much (like "do only use ni/in...") as this language has a wide range
> of specialized functions. My proposal is "just use the right one"!
> I like the [string equal ...] construct, but I also use [string
> compare ...] and eq-operator when when it is the better option.
Of course, you choose the right tool for the job, that hasn't
changed any... But in/ni are much more readable than the equivalent
[lsearch] command, so why not use them where possible? It would just be
nice if they automatically did the right thing wherever possible,
especially considering they don't (and should not) have any kind of
options available to them.
> I'm more suprised why the ni/in operators have been optimized but not
> lsearch.
I'd guess they got optimised along with general work on all the [expr]
operators. Just a guess, though.
> I like TCL because it does not consist ca. 3000 functions (like PHP
> does) and this should not be changed without a weighty reason.
*nods* And this proposal wouldn't change that one bit. In fact, it
would remove the possibility for a call for sorted versions of the
in/ni [expr] operators.
Fredderic
Donal K. Fellows
> Out of perverse curiosity (because I'm a perverse kinda guy), mind if I
> ask what those flag-enabled list optimisations you mentioned are?
It used to be the case for a while that there was a notion used in the
Tcl code to enable a faster path through [concat] and [eval], which was
the notion of a "pure list". The idea was that when a list value had no
string representation, it was possible to skip parsing and go straight
to list copying/command dispatch. A nice optimization when doing
function construction, but fragile. I got rid of that by tracking when
the string rep had been built from the list rep, since that was another
case where the overall idea of the optimization was safe, with the side
effect of being much less fragile.
We could do the same for in/ni I suppose, but I worry that it will
involve a lot of maintenance work and introduce subtle bugs too.
Donal.
Jeff Hobbs
I understand Donal's concern, but I would still argue that it would be
valuable to keep a flag bit saying whether the list was sorted (incr
or decr too), as the speed-up potential is quite notable, and lsearch
is a common operation.
Jeff
Jeff Hobbs
The issue is that Tcl still does not have full parse tree
optimization. It is different to ask "does the list contain this
element" (a boolean result) than "what element in the list is this
element" (lsearch result). The first can be better optimized. 'ni'
is the same as:
[lsearch $list $elem] == -1
but again Tcl doesn't check at that level currently. In the same
vein, you mention you use [string compare] still, which is much less
efficient because it returns a lexical comparison, whereas [string
equal] and eq can do a quick first check to see if the objects are
even of the same size. This could be optimized when we see that
[string compare] is compared against a boolean, but it currently isn't
done.
Jeff
Alexandre Ferrieux
>
> I understand Donal's concern, but I would still argue that it would be
> valuable to keep a flag bit saying whether the list was sorted (incr
> or decr too), as the speed-up potential is quite notable, and lsearch
> is a common operation.
Yes, but aren't "common" uses of [lsearch] (without -sorted)
restricted to small lists (where dichotomy is not significantly faster
than linear search) ?
In all other cases, natural selection must have pushed to reorganize
algorithms to use hashtables.
Or maybe do you want to make magically faster those few dinosaurs who
may have survived with O(N) search despite all advice ?
-Alex
Jeff Hobbs
wrote:
I think you overestimate many developer's decisions on using the
"best" algorithm that suits both the problem *and* the language. It
wouldn't be the first case where we magically sped things up for the
advantage of all. With the same philosophy, I wouldn't have bothered
turning regexp calls into much faster string equal/match calls. You
certainly find a lot of code that benefits from that.
Jeff
Alexandre Ferrieux
> On Dec 29, 4:25 am, Alexandre Ferrieux <alexandre.ferri...@gmail.com>
> wrote:
>
> > Or maybe do you want to make magically faster those few dinosaurs who
> > may have survived with O(N) search despite all advice ?
>
> I think you overestimate many developer's decisions on using the
> "best" algorithm that suits both the problem *and* the language.
If you want Tcl to become idiot-proof, why not. My only fear is that
this niche is particularly crowded ;-)
> wouldn't be the first case where we magically sped things up for the
> advantage of all. With the same philosophy, I wouldn't have bothered
> turning regexp calls into much faster string equal/match calls. You
> certainly find a lot of code that benefits from that.
The huge difference is that non-optimized [regexp] equivalent to
[string match] were just a constant factor behind the optimized
versions; this means a weaker selection pressure !
On the other side of the coin, the dinosaurs you are willing to save
are not likely to have their lists sorted anyway: why would they sort
the list if they neither knew about [lsearch -sorted], nor saw any
problem in O(N) search ?
-Alex
Jeff Hobbs
The advantage of lsearch -sorted didn't come around until 8.3 (iirc).
I would argue that it would have been right to first implement the
sorted flag bit check first, then lsearch -sorted as an explicit
indicator.
Jeff
Donal K. Fellows
> The advantage of lsearch -sorted didn't come around until 8.3 (iirc).
Very early 8.4 according to the changes file (committed by Eric Melski).
Donal.
Alexandre Ferrieux
>
>
> > On the other side of the coin, the dinosaurs you are willing to save
> > are not likely to have their lists sorted anyway: why would they sort
> > the list if they neither knew about [lsearch -sorted], nor saw any
> > problem in O(N) search ?
>
> The advantage of lsearch -sorted didn't come around until 8.3 (iirc).
> I would argue that it would have been right to first implement the
> sorted flag bit check first, then lsearch -sorted as an explicit
> indicator.
Sure. But you will never improve those who don't sort the list in the
first place... Unless you want to play dirty, and silently back the
list with a dict after 3 lengthy lsearch'es !
Bottom line: I believe more in spreading good algorithmic practices
than in automagical, behind-the-scenes mechanisms.
-Alex
Jeff Hobbs
wrote:
The real bottom line is that better practices are always best, but I
will have more success knowing that the norm isn't a very high bar and
working to optimize for that. ;)
Jeff
Donald Arseneau
> Hmmm..... They're such a neat little thing, it's a shame to have to
> ignore in/ni so I can use sorted searches.
>
> [expr] operators...! *shivers*
Of course more infix operators could be added to handle the qualified
cases.
I would enjoy a "sin" operation :-)
Donald Arseneau as...@triumf.ca
suchenwi
> Of course more infix operators could be added to handle the qualified
> cases.
>
> I would enjoy a "sin" operation :-)
Infix operators only make sense for exactly two operands. The sine
function takes one..
marc spitzer
only if you lack social skills.
marc
--
ms4...@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org
Donal K. Fellows
> Infix operators only make sense for exactly two operands. The sine
> function takes one..
So the ?: operator doesn't make sense? OK...
(Defining new infix operators is somewhat tricky because you have to
define their precedence and associativity as well, and so need a much
more complex parser...)
Donal.
Donald Arseneau
> (Defining new infix operators is somewhat tricky because you have to
> define their precedence and associativity as well, and so need a much
> more complex parser...)
(You also have to avoid collision with existing function names , viz
sin/sine :-)
D
Donal K. Fellows
That's functions. Defining new functions is easy, since they're all in
the same syntactic class. Defining new operators is much much harder.
(Some languages can do it, e.g. SML.)
Donal.