1. modified reverse
- Posted by rforno at tutopia.com
Aug 05, 2001
Rob:
The following modified reverse routine is simpler and, most of the times,
slightly faster than the standard one. However, I noticed that the
comparison between the two is affected by the type of data (integer or not,
simple or compound sequence), and even it seems that the way of generating
the data (by means of a single sentence or by a loop) affects the resulting
timings. Any explanation for such a behavior?
global function reverse1(sequence s)
integer n
sequence t
n = length(s)
t = repeat(0,n)
for i = 1 to n do
t[n] = s[i]
n -= 1
end for
return t
end function
2. Re: modified reverse
Hi rforno,
> Rob:
> The following modified reverse routine is simpler and, most of the times,
> slightly faster than the standard one. However, I noticed that the
> comparison between the two is affected by the type of data (integer or
not,
> simple or compound sequence), and even it seems that the way of
generating
> the data (by means of a single sentence or by a loop) affects the
resulting
> timings. Any explanation for such a behavior?
>
> global function reverse1(sequence s)
> integer n
> sequence t
> n = length(s)
> t = repeat(0,n)
> for i = 1 to n do
> t[n] = s[i]
> n -= 1
> end for
> return t
> end function
rforno, Rob,
the *very* interesting solution,
but how about the second one,
just inspired by rforno's the first:
sequence S
S={{1},{2},{3},{4},{5},{6},{7},{8},{9}}
global function reverse2(sequence s)
integer n
sequence t
t = s
n = length(s)
for i = 1 to n do
t[n] = s[i]
n -= 1
end for
return t
end function
? reverse2(S) ---- 
Regards,
Igor Kachan
kinz at peterlink.ru
3. Re: modified reverse
Hi rforno again,
Your idea is just excellent,
I think, see new variants below:
>
> Hi rforno,
>
> > Rob:
> > The following modified reverse routine is simpler and, most of the
times,
> > slightly faster than the standard one. However, I noticed that the
> > comparison between the two is affected by the type of data (integer or
> not,
> > simple or compound sequence), and even it seems that the way of
> generating
> > the data (by means of a single sentence or by a loop) affects the
> resulting
> > timings. Any explanation for such a behavior?
> >
> > global function reverse1(sequence s)
> > integer n
> > sequence t
> > n = length(s)
> > t = repeat(0,n)
> > for i = 1 to n do
> > t[n] = s[i]
> > n -= 1
> > end for
> > return t
> > end function
>
> rforno, Rob,
> the *very* interesting solution,
> but how about the second one,
> just inspired by rforno's the first:
>
> sequence S
> S={{1},{2},{3},{4},{5},{6},{7},{8},{9}}
>
> global function reverse2(sequence s)
> integer n
> sequence t
> t = s
> n = length(s)
> for i = 1 to n do
> t[n] = s[i]
> n -= 1
> end for
> return t
> end function
>
> ? reverse2(S) ----
global function reverse3(sequence s, atom n)
sequence t
t = s
for i = 1 to n do
t[n] = s[i]
n -= 1
end for
return t
end function
? reverse3(S, length(S))
sequence t -- this is a single private service sequence
-- for the different functions
-- of the program,
global function reverse4(sequence s, atom n)
t = s
for i = 1 to n do
t[n] = s[i]
n -= 1
end for
return t
end function
? reverse4(S, length(S))
Regards,
Igor Kachan
kinz at peterlink.ru
4. Re: modified reverse
rforno writes:
> The following modified reverse routine is simpler and,
> most of the times, slightly faster than the standard one.
> However, I noticed that the comparison between the two
> is affected by the type of data (integer or not,
> simple or compound sequence), and even it seems that
> the way of generating the data (by means of a single
> sentence or by a loop) affects the resulting
> timings. Any explanation for such a behavior?
>
> global function reverse1(sequence s)
> integer n
> sequence t
> n = length(s)
> t = repeat(0,n)
> for i = 1 to n do
> t[n] = s[i]
> n -= 1
> end for
> return t
> end function
I did a quick test, and your reverse1() above does seem to
be slightly faster than reverse() in misc.e.
This is counter-intuitive since you do n decrements of n
where the standard reverse() only does n/2 increments.
The number of copies, t[n] = s[i], is the same, since the
standard reverse() does two copies per loop but only
half as many loops.
Timings can be unpredictable for a number of reasons.
Euphoria is doing things, especially with storage allocation,
that are not visible in the code. Also the Pentium chips
depend on caching for speed, and it's hard to predict
whether a given algorithm will cache well. It may be faster
(as in this case) to have a short loop that executes
many times, rather than a long loop that executes fewer times.
It makes it easier for the Pentium to keep all the
necessary data and code in its on-chip cache.
I'll try a few more tests and maybe replace the
standard reverse() with yours, or something like it.
Thanks,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
5. Re: modified reverse
> From: Robert Craig <rds at RapidEuphoria.com>
> To: EUforum <EUforum at topica.com>
> Reply-To: EUforum at topica.com
> Organization: Rapid Deployment Software
> Subject: Re: modified reverse
> Date: 6/08/2001 2:21:37 PM
>
>
> rforno writes:
> > The following modified reverse routine is simpler and,
> > most of the times, slightly faster than the standard one.
> > However, I noticed that the comparison between the two
> > is affected by the type of data (integer or not,
> > simple or compound sequence), and even it seems that
> > the way of generating the data (by means of a single
> > sentence or by a loop) affects the resulting
> > timings. Any explanation for such a behavior?
> >
> > global function reverse1(sequence s)
> > integer n
> > sequence t
> > n = length(s)
> > t = repeat(0,n)
> > for i = 1 to n do
> > t[n] = s[i]
> > n -= 1
> > end for
> > return t
> > end function
>
> I did a quick test, and your reverse1() above does seem to
> be slightly faster than reverse() in misc.e.
> This is counter-intuitive since you do n decrements of n
> where the standard reverse() only does n/2 increments.
> The number of copies, t[n] = s[i], is the same, since the
> standard reverse() does two copies per loop but only
> half as many loops.
>
Strange but I found rforno's version slightly slower (96%) than the
standard. One way to get the standard one going slightly faster is to force
an integer conversion of the floor() function. Because the floor() function
is in the for..loop, Euphoria assumes that it is possible to generate a
really big result and does tests for atom-ness and integer overflow on every
comparison of the 'upper' variable. It even does extra work when adding one
to it for the next iteration, just in case it overflows the integer bounds.
This version is ever so slightly faster (3%) ...
global function reverse2(sequence s)
integer lower, n, max
sequence t
n = length(s)
t = repeat(0, n)
lower = 1
-- Force an integer result.
max = floor(n/2)+1
-- Now 'upper' knows that it can safely do integer comparisions
-- because both 'n' and 'max' are integers.
for upper = n to max by -1 do
t[upper] = s[lower]
t[lower] = s[upper]
lower += 1
end for
return t
end function
-----------
cheers,
Derek Parnell
Senior Design Engineer
Global Technology Australasia Ltd
dparnell at glotec.com.au
---------------------
confidential information intended solely for the use of the individual or
entity to whom they are addressed. If you are not the intended recipient of
this message you are hereby notified that any use, dissemination,
distribution or reproduction of this message is prohibited. If you have
received this message in error please notify the sender immediately. Any
views expressed in this message are those of the individual sender and may
not necessarily reflect the views of Global Technology Australasia Limited.
6. Re: modified reverse
Derek Parnell writes:
> Strange but I found rforno's version slightly slower (96%) than the
> standard.
Yes, I searched the mailing list archives, and found a comparison
I did between the current reverse() and a version identical to
rforno's 3 years ago. I was using my old Pentium-150 machine,
and found the current reverse() was faster. That's why I chose it.
Now I have a Pentium II with a different cache size etc.
> One way to get the standard one going slightly faster is to force
> an integer conversion of the floor() function.
> Because the floor() function is in the for..loop, Euphoria assumes
> that it is possible to generate a really big result and does
> tests for atom-ness and integer overflow on every
> comparison of the 'upper' variable. It even does extra
> work when adding one to it for the next iteration,
> just in case it overflows the integer bounds.
Good idea. I'll assign to an integer before the loop.
Note that this helps the translated code quite a bit,
but helps the interpreter very little because the interpreter
decides each time at the start of a for-loop (after
evaluating the expressions) whether
the loop variable can only have integer values or not
during the loop. It then self-modifies some of
the code for the loop. The translator has to decide once
and for all at compile-time when it generates the C code.
If there is any doubt (as in this case), it can't assume integer-only.
The only alternative for the translator would be to
to generate multiple copies of the entire loop and choose
one of them at the start, at run-time.
This would typically be a lot of C code to generate.
(Of course if the translator were *really* smart, it would realize that
floor(x/2)+1 must always be an integer, if x is an integer).
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
7. Re: modified reverse
Ýòî ñîîáùåíèå â ôîðìàòå MIME ñîñòîèò èç íåñêîëüêèõ ÷àñòåé.
------=_NextPart_000_01C11ED1.E027FE00
Robert Craig writes:
> Derek Parnell writes:
> > Strange but I found rforno's version slightly slower (96%) than the
> > standard.
>
> Yes, I searched the mailing list archives, and found a comparison
> I did between the current reverse() and a version identical to
> rforno's 3 years ago. I was using my old Pentium-150 machine,
> and found the current reverse() was faster. That's why I chose it.
> Now I have a Pentium II with a different cache size etc.
I have some results under extremal conditions of swapping on Dos-32
platform.
Timing on the complex sequence with length 80000 was :
reverse () -- 52.9 92.93 -- RDS
reverse1() -- 58.05 31.75 -- rforno
reverse2() -- 124.07 165.49
reverse3() -- 107.93 102.49
reverse4() -- 107.93 180.87
reverse2() -- 53.94 66.19 -- Derec
On Windows in Dos console on the simple sequence with length
194169 without swapping results were :
RDS 2.75 2.80 2.97 2.96 2.75
r1 3.73 4.34 4.07 3.95 5.21
r2 3.73 3.84 3.84 3.79 3.85
r3 4.56 4.56 4.51 4.56 4.62
r4 4.51 4.61 4.5 4.5 4.56
Derec 2.86 2.96 3.02 2.91 3.08
But on plain Dos Derec's function seems the fastest,
not always.
I notice a problem -- with tick_rate(100), swapping
on plain Dos immediately hungs up and swap-file gets
boo-boo, scandisk helps. With tick_rate(300), machine
hungs up. My machine is simplest -- 386
I have attached my test program, try and choose
reverse which you like. Again
Regards,
Igor Kachan
kinz at peterlink.ru
------=_NextPart_000_01C11ED1.E027FE00
Content-Type: application/octet-stream; name="Reverse.ex"
Content-Transfer-Encoding: quoted-printable
Content-Description: Reverse.ex (EX )
Content-Disposition: attachment; filename="Reverse.ex"
--rforno
--Rob:
--The following modified reverse routine is simpler and, most of the =
times,
--slightly faster than the standard one. However, I noticed that the
--comparison between the two is affected by the type of data (integer or =
not,
--simple or compound sequence), and even it seems that the way of =
generating
--the data (by means of a single sentence or by a loop) affects the =
resulting
--timings. Any explanation for such a behavior?
sequence S S=3D{}
sequence R R=3D{}
sequence n n=3D{}
atom T
global function reverse(sequence s)
-- reverse the top-level elements of a sequence.
-- Thanks to Hawke' for helping to make this run faster.
integer lower, n
sequence t
=20
n =3D length(s)
t =3D repeat(0, n)
lower =3D 1
for upper =3D n to floor(n/2)+1 by -1 do
t[upper] =3D s[lower]
t[lower] =3D s[upper]
lower +=3D 1
end for
return t
end function
global function reverse1(sequence s)
integer n
sequence t
n =3D length(s)
t =3D repeat(0,n)
for i =3D 1 to n do
t[n] =3D s[i]
n -=3D 1
end for
return t
end function
global function reverse2(sequence s)
integer n
sequence t
t =3D s
n =3D length(s)
for i =3D 1 to n do
t[n] =3D s[i]
n -=3D 1
end for
return t
end function
global function reverse3(sequence s, integer n)
sequence t
t =3D s
for i =3D 1 to n do
t[n] =3D s[i]
n -=3D 1
end for
return t
end function
global function reverse4(sequence s, integer n)
R =3D s
for i =3D 1 to n do
R[n] =3D s[i]
n -=3D 1
end for
return R
end function
global function reverse5(sequence s)
integer n,m
n =3D length(s)
R =3D s m =3D n
for i =3D 1 to n do
R[m] =3D s[i]
m -=3D 1
end for
return R
end function
global function reverse6(sequence s)
integer lower, n, max
sequence t
=20
n =3D length(s)
t =3D repeat(0, n)
lower =3D 1
-- Force an integer result.
max =3D floor(n/2)+1
=20
-- Now 'upper' knows that it can safely do integer comparisions
-- because both 'n' and 'max' are integers.
for upper =3D n to max by -1 do
t[upper] =3D s[lower]
t[lower] =3D s[upper]
lower +=3D 1
end for
return t
end function
procedure init(integer N)
for i=3D1 to N do
for j=3D1 to rand(50) do
n &=3D rand(100000)
end for
S =3D append(S,n)
S &=3D rand(100000)
n=3D{}
end for
? length(S)
end procedure
procedure test()
T=3Dtime()
R=3Dreverse(S)
puts(1,"rds ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse1(S)
puts(1,"r1 ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse2(S)
puts(1,"r2 ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse3(S, length(S))
puts(1,"r3 ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse4(S, length(S))
puts(1,"r4 ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse5(S)
puts(1,"r5 ")?time()-T
R=3D{}
T=3Dtime()
R=3Dreverse6(S)
puts(1,"r6 ")?time()-T
R=3D{}
end procedure
init(18000)
test()
------=_NextPart_000_01C11ED1.E027FE00--
8. Re: modified reverse
- Posted by rforno at tutopia.com
Aug 07, 2001
Rob, I do not understand. floor(anything) should always be an integer. It
seems that x being an integer does not matter.
----- Original Message -----
From: "Robert Craig" <rds at RapidEuphoria.com>
To: "EUforum" <EUforum at topica.com>
Subject: Re: modified reverse
>
> Derek Parnell writes:
> > Strange but I found rforno's version slightly slower (96%) than the
> > standard.
>
> Yes, I searched the mailing list archives, and found a comparison
> I did between the current reverse() and a version identical to
> rforno's 3 years ago. I was using my old Pentium-150 machine,
> and found the current reverse() was faster. That's why I chose it.
> Now I have a Pentium II with a different cache size etc.
>
> > One way to get the standard one going slightly faster is to force
> > an integer conversion of the floor() function.
> > Because the floor() function is in the for..loop, Euphoria assumes
> > that it is possible to generate a really big result and does
> > tests for atom-ness and integer overflow on every
> > comparison of the 'upper' variable. It even does extra
> > work when adding one to it for the next iteration,
> > just in case it overflows the integer bounds.
>
> Good idea. I'll assign to an integer before the loop.
>
> Note that this helps the translated code quite a bit,
> but helps the interpreter very little because the interpreter
> decides each time at the start of a for-loop (after
> evaluating the expressions) whether
> the loop variable can only have integer values or not
> during the loop. It then self-modifies some of
> the code for the loop. The translator has to decide once
> and for all at compile-time when it generates the C code.
> If there is any doubt (as in this case), it can't assume integer-only.
> The only alternative for the translator would be to
> to generate multiple copies of the entire loop and choose
> one of them at the start, at run-time.
> This would typically be a lot of C code to generate.
>
> (Of course if the translator were *really* smart, it would realize that
> floor(x/2)+1 must always be an integer, if x is an integer).
>
> Regards,
> Rob Craig
> Rapid Deployment Software
> http://www.RapidEuphoria.com
>
>
>
>
>
9. Re: modified reverse
rforno at tutopia.com wrote:
>
> Rob, I do not understand. floor(anything) should always be an integer. It
> seems that x being an integer does not matter.
> ...
Hi,
x could be also a sequence. In that case the return value of floor()
will be a sequence of integers. Only if x is not a sequence, then the
return value of floor is always an integer.
Have a nice day, Rolf
10. Re: modified reverse
rforno writes:
> Rob, I do not understand. floor(anything) should
> always be an integer.
floor(1e12) produces a
"mathematical integer" but does not
produce a 31-bit "Euphoria integer".
> It seems that x being an
> integer does not matter.
In order to generate fast C code,
the Euphoria To C Translator tries to determine
at translation time whether an expression must always
produce a 31-bit "Euphoria integer".
In a for-loop,
for i = start to limit by increment do ...
the translator will output much better C code
if it can "prove" to itself that start, limit, and increment
are always going to be 31-bit integers, whenever
this loop is started. This is easy when
they are all variables that have been declared as
"integer". It gets harder when you have expressions
involving function calls etc. The interpreter will also
speed up very slightly when things are clearly integers.
If x is a 31-bit Euphoria integer then floor(x/2)+1
will always be a Euphoria integer, but the translator
currently won't recognize this pattern. It does recognize
simpler patterns, for instance it assumes that built-in
functions, such as length(), getc(), peek(atom), ... etc.
always return a Euphoria integer.
Note that, in general, x+1 can't even be assumed
to produce a Euphoria integer, but a statement like:
x = x + 1
can be done using an integer calculation because
you have declared the target, x, to be an integer. The translator
assumes that your code contains no type errors or other errors
that the interpreter can catch. It will assume that for-loop
start, limit, and increment values are at least atoms, if not integers.
Regards,
Rob Craig
Rapid Deployment Software
http://www.RapidEuphoria.com
11. Re: modified reverse
- Posted by cklester at yahoo.com
Aug 07, 2001
> simpler patterns, for instance it assumes that built-in
> The translator assumes that your code contains no type
> It will assume that for-loop start, limit, and increment
Come on, Rob!!! You know what assuming does!!! Makes an "assu" out of
"ming," and that's just bad programming practice.
