1. subsequence storage
A thread a while back brought up the problem with sequence expansion: when
a subsequence is appended to beyond the space buffered for it, the entire
sequence and all its branced are relocated. I ran a speed check appending
first to ten sequences, then to ten subsequences and the difference was
startling: what took the first set .74 secs on my computer took the second
set close to ten minutes!
I assume a complex sequence is stored to a single block of memory. Why is
this? I don't pretend to understand the inner workings of interpreters,
but I would think a sequence would be stored as a single strand, with
pointers representing substrings, so that {1,2,{3,4,5},6} would be stored
not as:
1,2,<begin_string>,3,4,5,<end_string>,6
but as:
memblock1: 1,2,<pointer_memblock2>,6
memblock2: 3,4,5
then, if I said
seq[3]=seq[3]&9
then you'd only need to copy memblock2 to memblock3: 3,4,5,9
and change the pointer in memblock1, without recopying the parent sequence
or any of the other subsequences.
How are sequences really stored? The freedom of the sequence structure is
one of my favorite features of euphoria, and I often take advantage of it
with very deep sequences, but now I'm almost afraid to use them. greater
efficiency here is now on the top of my wish list.
In any case, I am curious as to how sequences are handled, but I understand
that Robert might not want to give away all his secrets.
Isaac
-- first number is time for independent sequences
-- second is for subseqences
-- third is ratio
-- currently set at 1000 repetitions; the test mentioned
-- in the message was with 10000
-- with 1000 I got .05 vs. 4.27
include machine.e
sequence q,w,e,r,t,y,u,i,o,p,seq
atom tick,t1,t2
constant reps=1000
tick_rate(100)
q={}
w={}
e={}
r={}
t={}
y={}
u={}
i={}
o={}
p={}
seq=repeat({},10)
tick=time()
for x=1 to reps do
q=q&0
w=w&0
e=e&0
r=r&0
t=t&0
y=y&0
u=u&0
i=i&0
o=o&0
p=p&0
end for
t1=(time()-tick)
?t1
tick=time()
for x=1 to reps do
seq[1]=seq[1]&0
seq[2]=seq[2]&0
seq[3]=seq[3]&0
seq[4]=seq[4]&0
seq[5]=seq[5]&0
seq[6]=seq[6]&0
seq[7]=seq[7]&0
seq[8]=seq[8]&0
seq[9]=seq[9]&0
seq[10]=seq[10]&0
end for
t2=(time()-tick)
?t2
?t2/t1
2. Re: subsequence storage
Isaac writes:
> then, if I said
> seq[3]=seq[3]&9
> then you'd only need to copy memblock2 to memblock3: 3,4,5,9
> and change the pointer in memblock1, without recopying the
> parent sequence or any of the other subsequences.
That's essentially how it's done. But think about your solution.
Your time goes up as N-squared because you are copying
ever-larger sequences.
Euphoria highly optimizes the most common case of
appending to a *simple* variable:
x = append(x, v)
to avoid (most of) the N-squared behavior,
but for cases involving subscripts, Euphoria uses
the slower, N-squared approach as in:
x[i] = append(x[i], v)
You can use x[i] = repeat(0, N) to avoid the
need for appending, or you can use a simple
variable temporarily while you are appending.
This issue has come up several times on this list.
Neither you nor most of the others came across
the problem independently while writing a "real" program.
It has mainly been pointed out by people who
"heard" of the problem and then constructed
an artificial program to demonstrate it. Even
David Cuny, who first reported it, saw it in
a Euphoria program that was *generated* in an artificial
way by his Basic to Euphoria translator. It wasn't in
hand-written Euphoria code.
When you compare an N-squared algorithm
against an order N algorithm, you can always
increase N until the difference in time becomes
huge. You didn't say what your value of N was.
It's on my list of things to better optimize,
but at the moment I'm working on other optimizations.
Regards,
Rob Craig
Rapid Deployment Software
http://members.aol.com/FilesEu/
3. subsequence storage
Isaac wrote:
-- first number is time for independent sequences
-- second is for subsequences
-- third is ratio
-- currently set at 1000 repetitions; the test mentioned
-- in the message was with 10000
-- with 1000 I got .05 vs. 4.27
include machine.e
sequence q, w, e, r, t, y, u, i, o, p, seq
atom tick, t1, t2
constant reps =3D 10000
tick_rate(100)
-- your code commented out
--q=3D{}
--w=3D{}
--e=3D{}
--r=3D{}
--t=3D{}
--y=3D{}
--u=3D{}
--i=3D{}
--o=3D{}
--p=3D{}
--
--seq =3D repeat({}, 10)
--
--tick =3D time()
--for x =3D 1 to reps do
-- q =3D q&0
-- w =3D w&0
-- e =3D e&0
-- r =3D r&0
-- t =3D t&0
-- y =3D y&0
-- u =3D u&0
-- i =3D i&0
-- o =3D o&0
-- p =3D p&0
--end for
--t1 =3D (time()-tick)
--?t1
--
--tick =3D time()
-- for x =3D 1 to reps do
-- seq[1] =3D seq[1]&0
-- seq[2] =3D seq[2]&0
-- seq[3] =3D seq[3]&0
-- seq[4] =3D seq[4]&0
-- seq[5] =3D seq[5]&0
-- seq[6] =3D seq[6]&0
-- seq[7] =3D seq[7]&0
-- seq[8] =3D seq[8]&0
-- seq[9] =3D seq[9]&0
-- seq[10] =3D seq[10]&0
-- end for
--t2 =3D (time()-tick)
--?t2
--?t2/t1
The way you do it is very inefficient. You should first allocate room for=
all sequences and subsequences, and then fill them up. Appending and
concatenating actually has to move and reallocate space, as you rightly
said. But...
-- now try these tests:
tick =3D time()
q =3D repeat({}, reps)
w =3D repeat({}, reps)
e =3D repeat({}, reps)
r =3D repeat({}, reps)
t =3D repeat({}, reps)
y =3D repeat({}, reps)
u =3D repeat({}, reps)
i =3D repeat({}, reps)
o =3D repeat({}, reps)
p =3D repeat({}, reps)
=
for x =3D 1 to reps do
q[reps] =3D 0
w[reps] =3D 0
e[reps] =3D 0
r[reps] =3D 0
t[reps] =3D 0
y[reps] =3D 0
u[reps] =3D 0
i[reps] =3D 0
o[reps] =3D 0
p[reps] =3D 0
end for
=
t1 =3D time() - tick
? t1
=
tick =3D time()
=
seq =3D repeat(repeat({}, reps), 10)
-- this is done very fast, *if* you've got enough memory!
=
for x =3D 1 to 10 do
for z =3D 1 to reps do
seq[x][z] =3D 0
end for
end for
t2 =3D time() - tick
?t2
while get_key() =3D -1 do
end while
Sincerely,
Ad Rienks
writing at 21:42 , =
on Monday 6 July 1998
Using EMail Assist for WinCIM
4. Re: subsequence storage
snipsnipsnipcutcutcutsnipsnip
Ad Rienks wrote:
> The way you do it is very inefficient.
> You should first allocate room for
> all sequences and subsequences, and
> then fill them up. Appending and
> concatenating actually has to move
> and reallocate space, as you rightly
> said. But...
> -- now try these tests:
snipslicecutsnipsnipcutseversnip
I ran the tests Ad gave us to try and on my
machine (Pentium) the subsequence code (part2)
***BEAT***
the sequence code (part1) every time by a
factor of 150% (0.06-part1 vs 0.04-part2)
I found this interesting :)
--Hawke'
5. Re: subsequence storage
Preallocation via repeat is a good solution, thanks.
>It has mainly been pointed out by people who
>"heard" of the problem and then constructed
>an artificial program to demonstrate it.
Actually, I have run across this problem in a "real" program, though I
didn't know it at the time. The program dealt with several little
creatures scurrying around in a virtual environment, 500*500*3 4 byte
spaces stored in memory. Each creature's behavior was controled by a
function into which I fed a sequence repesenting the 101*101*3 area around
it (50 spaces in each direction). Each 4 byte space was translated into
6-8 integers which were appended onto the subseqence representing that
space. I had abandoned the project because it was just too slow, but after
a few changes to the code to avoid appending, it's beginning to look viable.
thanks,
Isaac
6. Re: subsequence storage
Hawke wrote:
>I ran the tests Ad gave us to try and on my
>machine (Pentium) the subsequence code (part2)
> ***BEAT***
>the sequence code (part1) every time by a
>factor of 150% (0.06-part1 vs 0.04-part2)
>I found this interesting :)
>--Hawke'
On my machine (P75, 8Mb) the results were even more interesting: sometime=
s
the first gave 0.11 and the second 0.16-0.17, but another time it was jus=
t
the opposite (0.17 vs 0.11). Only when I set reps to 100.000, the second
test hung my machine under DOS, and gave 'data too big for memory' or
something like that, when run in W95, using D. Cuny's editor. Have to tes=
t
that again after installing 32 extra Mb's.
I've got them here, actually!
Ad
