1. Re: Optimization (was Edom 2.02)
From: Robert Craig
>Statements like:
> x[i] = append(x[i], value)
>and
> x[i] = x[i] & s
>are not optimized.
No kidding... As I found out yesterday. Well, actually as I was bewildered
by yesterday while testing search routines.
-----code excerpt-----
ctime = time()
for count = 1 to numwords do ---75000
wrd = MakeaWord( maxlength )
words[wrd[1]] = append( words[wrd[1]], (wrd + 96) )
end for
printf( 1, "%f seconds", {(time() - ctime)} )
ctime = time()
for count = 1 to searches do ---75000
searchfor = append( searchfor, (MakeaWord( maxlength ) + 96 ) )
end for
printf( 1, "%f seconds", {(time() - ctime)} )
------output-------
Number of words to search through: 75000
Maximum length of a word: 5
Number of searches to perform: 75000
Generating words...105.391619 seconds
Generating list of words to search for...5.860090 seconds
----------------------
Note that both loops ran the same number of times, both used the same
function with the same parameter (5). But look at the difference in time
taken caused only by subscripting with a variable. (Well, and the
assignment of the result to the variable wrd, instead of evaluating it in
the append, but that's negligible...right?)
It left me wondering. I knew it would be less optimal, but had no idea
it would be that much worse. So I did an experiment, with the following
output:
Time for 10 million iterations of an assignment:
expression (all evaluate to 3) time in seconds
------------------------------ ---------------
i = 3 0.730011
i = seq1[3] 1.220019
i = seq1[3][3] 3.750058
i = seq1[3][3][3] 5.520085
i = seq1[seq2[3]] 2.570039
i = seq1[seq2[3][3]] 4.350067
i = seq1[seq2[3][3][3]] 6.140094
i = seq1[seq2[3][3][3]][3][3] 10.990169
i = seq1[seq2[3][3][3]][seq2[3][3][3]][seq2[3][3][3]]
20.720318
i = seq1[seq2[seq2[3][3][3]][seq2[3][3][3]][seq2[3][3]
68.471052
i = seq1[3][3][3][3][3][3][3][3][3][3]
18.370282
And that was with simple variables. So I've taken to using a temp object
for appends and especially for loops and recursion. Instead of:
----
for count = 1 to length( tree[-branchID][CHILDREN][current] ) do
tree[-branchID][CHILDREN][current][count] =
ppend( tree[-branchID][CHILDREN][current][count] , newchild )
end for
----
Use:
----
temp = tree[-branchID][CHILDREN][current]
for count = 1 to length( temp ) do
temp2 = temp[count]
temp2 = append( temp2, newchild )
temp[count] = temp2
end for
tree[-branchID][CHILDREN][current] = temp
----
It may not look pretty, and it takes more code, but it's definitely faster.
Any other optimization tips, anybody?
