Data structure run-time in tcl...
Eric Thorne
I'm a long time perl user new to tcl and wrapping my head around non-
perl based hash data structures is proving difficult for me.
For those of you that know perl, imagine this:
if($tile_name =~ /(\S+)_X(\d+)Y(\d+)/) {
my ($type,$x,$y) = ($1,$2,$3);
push @{ $counts{$type}{X}{$y} }, $x; # num of x's for a given y
push @{ $counts{$type}{Y}{$x} }, $y; # num of y's for a given x
}
Now, I have replicated this in tcl, a couple of ways actually, but my
"best" thus far is this:
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
# add_to_counts counts $type X $y $x
# add_to_counts counts $type Y $x $y
if { [dict exists $counts $type X $y] } {
dict with counts $type X {
lappend $y $x
}
} else {
dict set counts $type X $y $x
}
if { [dict exists $counts $type Y $x] } {
dict with counts $type Y {
lappend $x $y
}
} else {
dict set counts $type Y $x $y
}
The commented out "add_counts" is a proc that does the dictionary
construction, same as the code below it, I commented them out and made
the construction explicit to do some time trials.
The problem for me is that for a relatively small data set the entire
perl script runs in about 12 seconds. The tcl script for a loop
wrapped around the above takes 45 seconds for just the dictionary
construction. The regex seems fast enough if I comment out the dict
construction, it really is the dict building that is slow. I'm doing
something horribly inefficient it seems but I'm not sure how to get
myself out of it.
What would be a better way to represent this in something tcl does
more efficiently?
The data being processed is a coordinate system where every coordinate
has a type. Imagine "apple_X0Y0" and "banana_X123Y46", but sometimes
there are holes in the coordinate system, so I need to be able to
count how many "things" are in each row or column, and know exactly
what and where they are (thus the lists).
I'm just surprised by the run time hit of the data structure
construction in tcl.
Thoughts, ideas?
Thanks,
Eric
Aric Bills
Here are three possible approaches, any of which will speed things up
for you:
Method 1: nested dict
proc dictnlappend {dictvar keylist args} {
# from http://wiki.tcl.tk/17686
upvar 1 $dictvar dict
if {[info exists dict] && [dict exists $dict {*}$keylist]} {
set list [dict get $dict {*}$keylist]
}
lappend list {*}$args
dict set dict {*}$keylist $list
}
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
dictnlappend counts [list $type X $y] $x
dictnlappend counts [list $type Y $x] $y
}
Method 2: flat Tcl associative array
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
lappend counts($type,X,$y) $x
lappend counts($type,Y,$x) $y
}
Method 3: SQLite database
package require sqlite3
sqlite3 coordsdb :memory:
coordsdb eval {CREATE TABLE data(type text, x int, y int)}
coordsdb transaction {
# start of your loop goes here...
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
coordsdb eval {INSERT INTO data VALUES($type,$x,$y)}
}
# end of your loop goes here...
}
Pros and cons:
Method 1 gives you a nested dictionary, but of the three methods, it's
the slowest way to put your data into memory. Still a significant
speedup, though.
Method 2 doesn't give you a dict or nested data, but arrays can be
converted to dicts and many of the things you might need nesting for
you can fake or work around. This is the fastest of the three methods
both for data storage and retrieval. If $type, $x, or $y can contain
commas, you'd need to choose a different delimiter.
The advantage of method 3 is richer access to your data; you may or
may not need this. As far as I can tell, data storage with this
method is almost as fast as method 2, and much faster than method 1.
Data retrieval, on the other hand, is relatively slow (you can speed
it up by creating indexes once your data is loaded, but it will still
be slower than pulling data from a dict or an array). If your query
needs are limited to finding the y coordinates of all apples at X=100,
methods 1 and 2 are better for you. If you need to find all the
coordinates for all bananas, all objects of any kind within a given
bounding box, etc., this method is probably worth the trade-offs.
Shaun Deacon
Perhaps someone else will comment on the use and performance of the
'dict' command, but did you try the following in Tcl ?
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
lappend counts($type,X,$y) $x
lappend counts($type,Y,$x) $y
}
IMO this is a closer match to your original Perl code.
Shaun
Aric Bills
> If $type, $x, or $y can contain
> commas, you'd need to choose a different delimiter.
I take that back. It probably doesn't matter whether they contain
commas or not.
Eric Thorne
I've tried method 1 and it was on average about 10 seconds slower then the "dict with" proc that I had. I am using a in-house implementation of tcl (built into another tool) and am talking with the developers about this, whether the slowness is really tcl or our tool.
I haven't tried method 2 as I'm not sure how to iterate over just the tiles. For the dict structure I do this:
dict for {type XY_dict} $counts {
set max_x 0
set max_y 0
dict for {y x_list} [dict get $XY_dict X] {
if { $max_x < [llength $x_list] } {
set max_x [llength $x_list]
}
}
dict for {x y_list} [dict get $XY_dict Y] {
if { $max_y < [llength $y_list] } {
set max_y [llength $y_list]
}
}
if { [ regexp {(green|red)_apple$} $type ] } {
set apple_col [ expr {$apple_col + $max_x} ]
set apple_row $max_y
} elseif { [ regexp {banana} $type ]} {
set banana_col $max_x
} elseif { [ regexp {(blood|navel)_orange} $type ]} {
set orange_col $max_x
}
}
puts "$apple_row,$apple_col,$banana_col,$orange_row"
This seems to be pretty fast compared to the dictionary building, but I didn't immediately see a way to only iterate through part of the associative keys for the array implementation/#2. Since I do iterate through everything to get the list lengths I guess I could build the maximums along the way, but to me that defeats the purpose of the tiered structure (which I like). I guess I could do the maximums when I am building the data structure, but I feel like the structure is there for later flexibility which the associative array doesn't seem to have, or I'm missing something obvious (hopefully the later!).
The usage of the DB is a bit beyond my current skill set but possibly worth investigating. The 12 second data set in perl does scale up to a 1+ hour run so this is why the slowness I'm seeing in tcl is alarming to me.
Thanks again,
Eric
Uwe Klein
> Method 2: flat Tcl associative array
>
> if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
> lappend counts($type,X,$y) $x
> lappend counts($type,Y,$x) $y
> }
>
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
with a banal assignment:
foreach {type x y} [ split $tile {_XY] break
lappend counts($type,X,$y) $x
lappend counts($type,Y,$x) $y
and just ignore potential nonrelevant assignments in the array?
uwe
Aric Bills
> Thanks Aric!
>
> I've tried method 1 and it was on average about 10 seconds slower then the "dict with" proc that I had. I am using a in-house implementation of tcl (built into another tool) and am talking with the developers about this, whether the slowness is really tcl or our tool.
What version of Tcl is integrated into the tool? (One way to find out
is to call [info patchlevel].)
>
> I haven't tried method 2 as I'm not sure how to iterate over just the tiles. For the dict structure I do this:
>
> dict for {type XY_dict} $counts {
> set max_x 0
> set max_y 0
> dict for {y x_list} [dict get $XY_dict X] {
> if { $max_x < [llength $x_list] } {
> set max_x [llength $x_list]
> }
> }
> dict for {x y_list} [dict get $XY_dict Y] {
> if { $max_y < [llength $y_list] } {
> set max_y [llength $y_list]
> }
> }
>
> if { [ regexp {(green|red)_apple$} $type ] } {
> set apple_col [ expr {$apple_col + $max_x} ]
> set apple_row $max_y
> } elseif { [ regexp {banana} $type ]} {
> set banana_col $max_x
> } elseif { [ regexp {(blood|navel)_orange} $type ]} {
> set orange_col $max_x
> }
> }
> puts "$apple_row,$apple_col,$banana_col,$orange_row"
>
> This seems to be pretty fast compared to the dictionary building, but I didn't immediately see a way to only iterate through part of the associative keys for the array implementation/#2. Since I do iterate through everything to get the list lengths I guess I could build the maximums along the way, but to me that defeats the purpose of the tiered structure (which I like). I guess I could do the maximums when I am building the data structure, but I feel like the structure is there for later flexibility which the associative array doesn't seem to have, or I'm missing something obvious (hopefully the later!).
>
> The usage of the DB is a bit beyond my current skill set but possibly worth investigating. The 12 second data set in perl does scale up to a 1+ hour run so this is why the slowness I'm seeing in tcl is alarming to me.
>
> Thanks again,
> Eric
If you went the associative array route and had a list of types, you
might iterate over the data like this:
foreach type $types {
set max_x 0
set max_y 0
foreach key [array names counts -glob $type,X,*] {
if { $max_x < [llength $counts($key)] } {
set max_x [llength $counts($key)]
}
}
foreach key [array names counts -glob $type,Y,*] {
if { $max_y < [llength $counts($key)] } {
set max_y [llength $counts($key)]
}
}
if { [ regexp {(green|red)_apple$} $type ] } {
set apple_col [ expr {$apple_col + $max_x} ]
set apple_row $max_y
} elseif { [ regexp {banana} $type ]} {
set banana_col $max_x
} elseif { [ regexp {(blood|navel)_orange} $type ]} {
set orange_col $max_x
}
}
In the absence of a list of types, and assuming type names cannot
contain commas, you might do something like this:
foreach key [array names counts] {
lassign [split $key ,] type coord value
if {
![info exists max($type,$coord)] ||
$max($type,$coord) < [llength $counts($key)]
} {
set max($type,$coord) [llength $counts($key)]
}
# keep track of types:
set types($type) 1
}
foreach type [array names types] {
if { [ regexp {(green|red)_apple$} $type ] } {
set apple_col [ expr {$apple_col + $max($type,X)} ]
set apple_row $max($type,Y)
} elseif { [ regexp {banana} $type ] } {
set banana_col $max($type,X)
} elseif { [ regexp {(blood|navel)_orange} $type ]} {
set orange_col $max($type,X)
}
}
Hope that helps.
Aric
Cyan
One thing I've noticed is that "dict with" can be _really_ slow (and
have nasty side effects too - all the keys in the dictionary are
created as variables that persist past the scope of the with script,
and overwrite other existing variables of that name)
In my tests I've found:
dict set foo bar baz [concat [dict get $foo bar baz] newthing]
to be faster than:
dict with foo bar {
lappend baz newthing
}
and much safer besides. Of course, if the key you're appending to is
not in a nested dict:
dict lappend foo bar newthing
is much better than both.
Cyan
Donal K. Fellows
> One thing I've noticed is that "dict with" can be _really_ slow (and
> have nasty side effects too - all the keys in the dictionary are
> created as variables that persist past the scope of the with script,
> and overwrite other existing variables of that name)
The side-effects are a consequence of the fact that we simply don't
have nested scopes. (Hmm, they would make a nice thing in 9.0; now
#108 on the wishlist at http://wiki.tcl.tk/883) The speed, not sure
about that.
Donal.
Eric Thorne
The version of tcl we are using is 8.5.6.
From this I've learned that Dictionaries in all their forms/manipulations are seemingly just slow. I ran 4 different implementations of of the dictionary building 5 times and noted the run times (basically the same +/- 1 sec). The "dict with" proc, Aric's nlappend proc, the concat proc suggested by Cyan, and my initial working attempt which was (seemed similar in idea to the concat):
proc add_to_counts_prev { counts_dict type XY xy_val yx_val } {
upvar 1 $counts_dict counts1
if { [dict exists $counts1 $type $XY $xy_val] } {
set prev_xy [dict get $counts1 $type $XY $xy_val]
dict set counts1 $type $XY $xy_val "$prev_xy $yx_val"
} else {
dict set counts1 $type $XY $xy_val $yx_val
}
}
For a data set of 22,733 tiles, on average I found:
Prev: 62 sec
Dict With: 44 sec
nlappend: 56 sec
concat: 57 sec
For as much as dict with is known to be slow, it was still the fastest of what I tried.
I also ran the "dict with" overnight on my largest data set of 425,156 tiles. It took 3 hrs, 54 minutes. The perl script doing the same thing took about 90 seconds.
I implemented Aric's suggest of how to manage the associative arrays. On the small data set it ran in about 20 seconds (original perl script was 12 seconds), and on the large dataset it took 140 seconds. Still not quite as fast as the perl script but at least it is a reasonable enough run time to live with, and much, much faster than the dict.
Thank you all again!
Eric
Donal K. Fellows
> Now, I have replicated this in tcl, a couple of ways actually, but my
> "best" thus far is this:
>
> if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
> # add_to_counts counts $type X $y $x
> # add_to_counts counts $type Y $x $y
> if { [dict exists $counts $type X $y] } {
> dict with counts $type X {
> lappend $y $x
> }
> } else {
> dict set counts $type X $y $x
> }
> if { [dict exists $counts $type Y $x] } {
> dict with counts $type Y {
> lappend $x $y
> }
> } else {
> dict set counts $type Y $x $y
> }
There are potentially two issues here. Firstly, this appears to be
running outside a procedure, which inhibits some optimizations.
Secondly, this is using variable variable names, which is slow. I'd be
interested to see a comparison with:
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile -> type x y] } {
dict with counts $type {
dict lappend X $y $x
dict lappend Y $x $y
}
}
That actually has the potential to not utterly suck. :-) It still
might have problems though, since it is probably going to end up doing
an excessive number of memory copies (because the list append must
necessarily work with a shared dictionary input; the original
reference is in the main 'counts' variable). So I'd try this trickier
version:
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile -> type x y] } {
dict with counts $type {
# Magic hack alert!
dict set counts $type X {}
dict set counts $type Y {}
dict lappend X $y $x
dict lappend Y $x $y
}
}
I still wouldn't be surprised if Perl is faster; the [dict with]
subcommand is not going to be fully compiled (it's quite hard to do in
general). Still, on a real-world dataset I'd hope that managing the
copying (and avoiding making lots of variables) would be a better help
than anything else.
Donal.
Eric Thorne
If you look at my most recent reply to Aric's post I did try the "dict with" and lappend as a procedure and had a dict build time of 44 seconds for my small data set.
Using your "dict with"/"dict lappend" the dict build dropped to 30 seconds and the magic hack dropped it to 21 seconds, which brings it down to the range of associative array implementation. What is the "hack" doing?
I tried the magic hack on the large data set and it is significantly slower the associative array implementation which took about 140 seconds. It's been 7 minutes at this point and I need to head out...
Thanks,
Eric
Christian Gollwitzer
Am 11.07.11 21:17, schrieb Eric Thorne:
> God day tcl-ers...
>
> I'm a long time perl user new to tcl and wrapping my head around non-
> perl based hash data structures is proving difficult for me.
>
> For those of you that know perl, imagine this:
>
> if($tile_name =~ /(\S+)_X(\d+)Y(\d+)/) {
> my ($type,$x,$y) = ($1,$2,$3);
> push @{ $counts{$type}{X}{$y} }, $x; # num of x's for a given y
> push @{ $counts{$type}{Y}{$x} }, $y; # num of y's for a given x
> }
My understanding is that the main problem lies in the change of a deeply
nested dictionary object - there is no built-in dict nlappend, and all
methods discussed here boil down to copying dict elements to temporary
objects and back.
It might be helpful to use "pointers" instead, i.e. store an index in an
index dict and lappend the data to a separate table:
set test "apple_X10Y20 apple_X10Y30 banana_X5Y10"
set counts {}
set index {}
set id 0
foreach tile $test {
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile -> type x y] } {
if {[catch {dict get $index $type X $x} idx]} {
incr id
dict set index $type X $x $id
set idx $id
}
dict lappend counts $idx $y
if {[catch {dict get $index $type Y $y} idy]} {
incr id
dict set index $type Y $y $id
set idy $id
}
dict lappend counts $idy $y
}
}
Accessing the data is then done via
dict get $counts [dict get $index $type X $x]
Christian
Eric Thorne
You do get the dict building speed award, at 16 seconds, an improvement of 4 seconds over the "magic hack". On the large data set this takes 14 minutes to build the data structure compared to the associative array's ~2 minutes and the "magic hack's" 2 hours.
Thanks,
Eric
Donal K. Fellows
> Wow. You win the dict creation contest hands down.
As the author of the [dict] command, I ought to win. I know where the
bodies are buried. :-D
> Using your "dict with"/"dict lappend" the dict build dropped to 30
> seconds and the magic hack dropped it to 21 seconds, which brings
> it down to the range of associative array implementation. What is
> the "hack" doing?
Managing reference counts so that data doesn't need to copied nearly
so much (i.e., so that the dictionaries can be modified in-place while
preserving Tcl's value semantics). Definitely something that requires
high expertise though.
High-level summary: I'm ensuring that the dictionaries in question are
only referred to once at points where I'm doing the update. This makes
a huge difference.
> I tried the magic hack on the large data set and it is significantly
> slower the associative array implementation which took about 140
> seconds. It's been 7 minutes at this point and I need to head out...
That's benefiting from deeper bytecode compilation. To get close to it
with [dict] would require me to tack how to bytecode-compile the [dict
with], which is tricky (or perhaps "messy" is more accurate).
Donal.
Christian Gollwitzer
>
> It might be helpful to use "pointers" instead, i.e. store an index in an
> index dict and lappend the data to a separate table:
Probably this X and Y is always a fixed string, so you can improve on
this further by flattening the level, which decides X vs. Y:
set test "apple_X10Y20 apple_X10Y30 banana_X5Y10"
set counts {}
set indexX {}
set indexY {}
set id 0
foreach tile $test {
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile -> type x y] } {
if {[catch {dict get $index $type X $x} idx]} {
incr id
dict set indexX $type $x $id
set idx $id
}
dict lappend counts $idx $y
if {[catch {dict get $index $type Y $y} idy]} {
incr id
dict set indexY $type $y $id
set idy $id
}
dict lappend counts $idy $y
}
}
I would be curious to know, what exactly does the perl code do? I'm
rather ignorant of perl on this level. Is it the equivalent of:
dict lappend counts [list $type Y $y] $x
But then, how do you iterate over everything with an apple in it in
perl? If its done via filtering the keys, you can achieve the same
effect using dicts, try:
set test "apple_X10Y20 apple_X10Y30 banana_X5Y10"
set counts {}
set id 0
foreach tile $test {
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile -> type x y] } {
dict lappend counts [list $type X $x] $y
dict lappend counts [list $type Y $y] $x
}
}
puts [dict filter $counts key "apple X *"]
puts [dict filter $counts key "banana *"]
Of course, this is sloooow on retrieval, the "dict filter" has to
process the entire list, no benefit from the hash value... However, some
clever combination of the level splitting might do the trick for both
fast construction and fast access. This "trick" depends on the
distribution of your keys, dou you have many different fruits, or only a
small number of fruits, but many different coordinates?
Christian
Eric Thorne
My mental model of the perl code translates (and this is probably a large part of my problem) to roughly to Cyan's idea:
dict set foo bar baz [concat [dict get $foo bar baz] newthing]
Or possibly:
dict lappend counts [dict get $type [dict get X [dict get $y]]] $x
Basically, each key combination represents a different perl hash (or tcl dictionary) that can be worked on independently as a perl hash (or tcl dictionary) and that the total structure contains a perl array (or tcl list).
If I were to iterate over just "apple" items in perl I would:
foreach my $type (sort keys %counts) {
next if ($type !~ /(apple/); # I want both green_apple and red_apple
#Do something with apple
}
I like the idea of the filter command and need to get used to using it.
For this particular data set the number of "fruits" is probably close to a hundred, but can be filtered to less than 10. The coordinate system currently maxes out near 500x650.
The current output of the script is a table, something like:
map_size,apple_row,apple_col,banana_col,orange_col
small_map,120,50,7,6
large_map,470,600,28,24
It is very convenient in perl to just throw everything in a multi-level hash and sort through things if need be later. I think it has lead to me getting very lazy in my programming, pretty much ignoring any other useful structure. Working with tcl is going to be a learning/relearning experience for me.
Thanks,
Eric
Uwe Klein
> It is very convenient in perl to just throw everything in a multi-level hash and sort through
> things if need be later. I think it has lead to me getting very lazy in my programming, pretty
> much ignoring any other useful structure. Working with tcl is going to be a learning/relearning
> experience for me.
>
> Thanks, Eric
My (uncoroborated) feeling is that a single level array with compound keys
creation ( lappend is in_place _and_ "cheap" ):
lappend myMasterArray($type,$x,$y) $val
complemented with
array names myMasterArray <$glob~type,$glob~,$~x glob pattern>
is the more tclish way.
and as I wrote before:
what about replacing the regexp:
if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
with a banal assignment:
foreach {type x y} [ split $tile {_XY] break
lappend counts($type,X,$y) $x
lappend counts($type,Y,$x) $y
and just ignore potential nonrelevant assignments in the array?
The thing to keep in mind is that tcl is not perl ( or python ... )
though the lure of similar paradigm names to help confusion is there, for sure.
uwe
Andreas Kupries
> On Jul 11, 1:17 pm, Eric Thorne <et.newsgro...@gmail.com> wrote:
>> God day tcl-ers...
>>
>> I'm a long time perl user new to tcl and wrapping my head around non-
>> perl based hash data structures is proving difficult for me.
>>
>> For those of you that know perl, imagine this:
>>
>> Thoughts, ideas?
>>
>> Thanks,
>> Eric
>
> Here are three possible approaches, any of which will speed things up
> for you:
> Method 2: flat Tcl associative array
>
> if { [regexp {(\S+)_X(\d+)Y(\d+)} $tile full_match type x y] } {
> lappend counts($type,X,$y) $x
> lappend counts($type,Y,$x) $y
> }
> Method 2 doesn't give you a dict or nested data, but arrays can be
> converted to dicts and many of the things you might need nesting for
> you can fake or work around. This is the fastest of the three methods
> both for data storage and retrieval. If $type, $x, or $y can contain
> commas, you'd need to choose a different delimiter.
Or simply construct the key using [list $type Y $x], etc.
--
So long,
Andreas Kupries <akup...@shaw.ca>
<http://www.purl.org/NET/akupries/>
Developer @ <http://www.activestate.com/>
-------------------------------------------------------------------------------