1. modified reverse
- Posted by rforno at tutopia.com Aug 05, 2001
- 523 views
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
- Posted by Igor Kachan <kinz at peterlink.ru> Aug 05, 2001
- 495 views
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
- Posted by Igor Kachan <kinz at peterlink.ru> Aug 05, 2001
- 510 views
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
- Posted by Robert Craig <rds at RapidEuphoria.com> Aug 05, 2001
- 491 views
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
- Posted by Derek Parnell <ddparnell at bigpond.com> Aug 05, 2001
- 496 views
> 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
- Posted by Robert Craig <rds at RapidEuphoria.com> Aug 06, 2001
- 505 views
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
- Posted by Igor Kachan <kinz at peterlink.ru> Aug 06, 2001
- 480 views
Ýòî ñîîáùåíèå â ôîðìàòå 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
- 533 views
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
- Posted by Rolf Schroeder <r.schr at T-ONLINE.DE> Aug 07, 2001
- 524 views
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
- Posted by Robert Craig <rds at RapidEuphoria.com> Aug 07, 2001
- 492 views
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
- 500 views
> 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.