1. Optimization
- Posted by Jason Gade <jaygade at yahoo.com> Feb 09, 2006
- 430 views
I know I've brought this up before, but I want to ask again. Does Euphoria optimize read-modify-write situation? I know that internally Euphoria passes by reference and only allocates a new sequence if elements are modified. But does the interpreter recognize the following:
sequence foo foo = bar(foo)
Is this optimized as a pattern where foo itself can be modified instead of allocating and returning a new sequence? Recognizing this optimization may be difficult, but I think that it would be very useful. I suppose where the variable are foo[1] or foo[1][2] or whatever would make things even more difficult. Maybe just for top-level references? Of course you could also have:
sequence foo foo = bar(baz, x, y, z, fun(foo), foo[1..a], d, foo, i, j)
Which would be truly horrid, but still... If Euphoria does this automatically it should be in the docs. Unless you'd actually implement a var_id() that is orthogonal with routine_id()... -- "Any programming problem can be solved by adding a level of indirection." --anonymous "Any performance problem can be solved by removing a level of indirection." --M. Haertel j.
2. Re: Optimization
- Posted by Robert Craig <rds at RapidEuphoria.com> Feb 09, 2006
- 418 views
Jason Gade wrote: > I know I've brought this up before, but I want to ask again. > > Does Euphoria optimize read-modify-write situation? > > I know that internally Euphoria passes by reference and only allocates a new > sequence if elements are modified. > > But does the interpreter recognize the following: > }}} <eucode> > sequence foo > foo = bar(foo) > </eucode> {{{ > > Is this optimized as a pattern where foo itself can be modified instead of > allocating > and returning a new sequence? > > Recognizing this optimization may be difficult, but I think that it would be > very useful. I suppose where the variable are foo[1] or foo[1][2] or whatever > would make things even more difficult. Maybe just for top-level references? > > Of course you could also have: > }}} <eucode> > sequence foo > foo = bar(baz, x, y, z, fun(foo), foo[1..a], d, foo, i, j) > </eucode> {{{ > > Which would be truly horrid, but still... > > If Euphoria does this automatically it should be in the docs. I've discussed this before. No, I don't do this optimization, but I have it fairly high on my list to consider. The basic idea is to reduce the reference count on a variable value that you know is not going to be needed again. So in x = sort(x) there would only be one reference count on the value of x that's passed to sort(). That way, there would be no need to copy x inside sort() before modifying it. In general, you could look for situations where a variable is going to be overwritten before it is read again, therefore its value is no longer needed, and the reference count could be decremented early, possibly eliminating a copy. In addition to being a bit tricky, and a bit dangerous, this optimization would leave you with some important variables "undefined" in ex.err and the trace screen, since their values might be temporarily unknown. Also, copying a sequence is a fairly cheap operation compared with any other operation you can think of that's applied to each element. e.g. one copy does not increase the cost of sorting by very much > Unless you'd actually implement a var_id() that is orthogonal with > routine_id()... It's too much like pointers. Regards, Rob Craig Rapid Deployment Software http://www.RapidEuphoria.com
3. Re: Optimization
- Posted by Jason Gade <jaygade at yahoo.com> Feb 09, 2006
- 411 views
Robert Craig wrote: > > Jason Gade wrote: > > Does Euphoria optimize read-modify-write situation? > > }}} <eucode> > > sequence foo > > foo = bar(foo) > > </eucode> {{{ > > I've discussed this before. > No, I don't do this optimization, > but I have it fairly high on my list to consider. Yeah, I know. I think I'm the one that asked before. > The basic idea is to reduce the reference count on > a variable value that you know is not going to be > needed again. So in x = sort(x) there would only > be one reference count on the value of x that's passed to sort(). > That way, there would be no need to copy x inside sort() > before modifying it. In general, you could look for situations > where a variable is going to be overwritten before it is > read again, therefore its value is no longer needed, and the > reference count could be decremented early, possibly eliminating > a copy. > > In addition to being a bit tricky, and a bit dangerous, > this optimization would leave you with some important variables > "undefined" in ex.err and the trace screen, since their > values might be temporarily unknown. Also, copying a sequence > is a fairly cheap operation compared with any other operation > you can think of that's applied to each element. e.g. one copy > does not increase the cost of sorting by very much This is only really of academic interest to me, but bear with me please anyway. I see a lot of other programming languages use modify-by-reference. They take a reference to an existing variable and modify the contents of that variable. Euphoria does a copy-on-write instead. In Euphoria you can get around this by using a global variable. But then each routine needs to know the name of that variable in order to modify it. That makes it difficult to reuse code or to write libraries that want to handle large data objects without incurring a copy. It might be nice there was a way to tell the interpreter that I want to modify *this* variable instead of making a copy of it. Say, like a keyword "static" or something. "static" is the only keyword I could think of, but I don't like that particular word much because of its overuse in C. I know it's a pie-in-the-sky idea, and again it is only of academic interest to me. > > Unless you'd actually implement a var_id() that is orthogonal with > > routine_id()... > > It's too much like pointers. Well, Euphoria already *has* pointers in the form of routine_id(). And the fact that you can roll your own pointers with allocate()/peek()/poke(). In C, I find variable pointers much easier to understand than function pointers, yet Euphoria has function pointers (that are actually easy to understand). But pointers are the 'goto' of data structures, as they say, and they would definitely be abused in Euphoria. As any other construct can be. I still think that, done right, some kind of mechanism could make data encapsulation better. -- "Any programming problem can be solved by adding a level of indirection." --anonymous "Any performance problem can be solved by removing a level of indirection." --M. Haertel j.
4. Optimization
- Posted by Davi Figueiredo <davitf at USA.NET> Sep 26, 1998
- 448 views
Hello all, While doing some simple benchmarks in Euphoria, I came across a very interesting thing. I ran a program like this: -- code begins here procedure proc1() atom foo foo=0 for temp=1 to 15000000 do foo=foo+1 foo=foo+1 foo=foo+1 foo=foo+1 end for ? foo end procedure procedure proc2() atom foo foo=0 for temp=1 to 15000000 do foo=foo+1 foo=foo+1 end for for temp=1 to 15000000 do foo=foo+1 foo=foo+1 end for ? foo end procedure procedure proc3() atom foo foo=0 for temp=1 to 15000000 do foo=foo+1 end for for temp=1 to 15000000 do foo=foo+1 end for for temp=1 to 15000000 do foo=foo+1 end for for temp=1 to 15000000 do foo=foo+1 end for ? foo end procedure atom start -- Time proc1() start=time() proc1() printf(1,"proc1() took %2.2f seconds\n\n",time()-start) -- Time proc2() start=time() proc2() printf(1,"proc2() took %2.2f seconds\n\n",time()-start) -- Time proc3() start=time() proc3() printf(1,"proc3() took %2.2f seconds\n\n",time()-start) -- code ends here The three procedures do basically the same thing, but proc1() has only one for loop, while proc2() has two of them and proc3() has four for loops. So I supposed proc2() would be slower than proc1() and proc3() would be slower than proc2(). However, proc1() took about 6 seconds to run and proc2() took about 7.8 seconds (all right until now), but proc3() took only about 5.3 seconds! The only explanation I could find is that there is some kind of optimization for for loops with a single statement inside. Maybe someone can tell me if it is right or wrong. I just wanted to send this because if I am right some programs may be optimized to become a few milliseconds faster. Regards, Davi T. Figueiredo davitf at usa.net ____________________________________________________________________ Get free e-mail and a permanent address at http://www.amexmail.com/?A=1
5. Re: Optimization
- Posted by Matt Z Nunyabidness <matt1421 at JUNO.COM> Sep 26, 1998
- 420 views
>procedure proc1() > atom foo > foo=0 > > for temp=1 to 15000000 do > foo=foo+1 > foo=foo+1 > foo=foo+1 > foo=foo+1 > end for > > ? foo >end procedure > > >procedure proc2() > atom foo > foo=0 > > for temp=1 to 15000000 do > foo=foo+1 > foo=foo+1 > end for > > for temp=1 to 15000000 do > foo=foo+1 > foo=foo+1 > end for > > ? foo >end procedure > > >procedure proc3() > atom foo > foo=0 > > for temp=1 to 15000000 do > foo=foo+1 > end for > > for temp=1 to 15000000 do > foo=foo+1 > end for > > for temp=1 to 15000000 do > foo=foo+1 > end for > > for temp=1 to 15000000 do > foo=foo+1 > end for > > ? foo > >end procedure >atom start > >-- Time proc1() >start=time() >proc1() >printf(1,"proc1() took %2.2f seconds\n\n",time()-start) > >-- Time proc2() >start=time() >proc2() >printf(1,"proc2() took %2.2f seconds\n\n",time()-start) > >-- Time proc3() >start=time() >proc3() >printf(1,"proc3() took %2.2f seconds\n\n",time()-start) What does foo mean?!?!?!?!?!?!?!?!?! How about foobar and bar and foo.bar too!!! ___________________________________________________________________ You don't need to buy Internet access to use free Internet e-mail. Get completely free e-mail from Juno at http://www.juno.com Or call Juno at (800) 654-JUNO [654-5866]
6. Re: Optimization
- Posted by Davi Figueiredo <davitf at USA.NET> Sep 26, 1998
- 389 views
>What does foo mean?!?!?!?!?!?!?!?!?! How about foobar and bar and foo.bar >too!!! I don't know. I've seen a lot of people on the list using it, so I used it too. I think you use it when you are just giving an example or when you don't have any better name for the variable. Regards, Davi T. Figueiredo davitf at usa.net ____________________________________________________________________ Get free e-mail and a permanent address at http://www.amexmail.com/?A=1
7. Re: Optimization
- Posted by Matt Z Nunyabidness <matt1421 at JUNO.COM> Sep 26, 1998
- 409 views
ok, thx. I wonder who invented 'foo' ------------------------------------- When it comes to programming languages, Euphoria is a cut above - matt1278 at juno.com and matt1421 at juno.com(and soon to be irisnmatt at prodigy.net. Then again, maybe not) Euphoria programmer ___________________________________________________________________ You don't need to buy Internet access to use free Internet e-mail. Get completely free e-mail from Juno at http://www.juno.com Or call Juno at (800) 654-JUNO [654-5866]
8. Re: Optimization
- Posted by Ralf Nieuwenhuijsen <nieuwen at XS4ALL.NL> Sep 26, 1998
- 400 views
- Last edited Sep 27, 1998
>ok, thx. I wonder who invented 'foo' Look at the message archives of this list server, this has been discussed before. I believe it had something to do with the army. But yes, it is used in pseudo code. Ralf
9. Re: Optimization
- Posted by Hawke <mdeland at NWINFO.NET> Sep 26, 1998
- 424 views
Davi Figueiredo wrote: > Hello all, > While doing some simple benchmarks in Euphoria, I came across > a very interesting thing. I ran a program like this: > procedure proc1() > procedure proc2() > procedure proc3() > The three procedures do basically the same thing, but proc1() > has only one for loop, while proc2() has two of them and > proc3() has four for loops. So I supposed proc2() would be > slower than proc1() and proc3() would be slower than proc2(). > However, proc1() took about 6 seconds to run and proc2() took > about 7.8 seconds (all right until now), but proc3() took > only about 5.3 seconds! my results do not match yours, as seen below. i'm not referring to the actual seconds, but the relationship instead... proc1 seems to have won versus proc2 & proc3. i also tested an additional proc4 which is: procedure proc4() atom foo foo=0 for temp=1 to 15000000 do foo=foo+4 end for ? foo end procedure and as you can see from the results below, proc4 beat 1,2,&3 by a very serious margin, with 1 coming in second... 60000000 proc1() took 7.09 seconds 60000000 proc2() took 8.35 seconds 60000000 proc3() took 8.51 seconds 60000000 proc4() took 2.64 seconds > The only explanation I could find is that there is some kind > of optimization for for loops with a single statement inside. what version of EU are you running, and on what machine, and under what conditions? (under a dos box? with other things running? etc) i ran this on a P200mmx, in a dos box that (for all intentent purposes) takes full control of the machine due to the pif settings i have set for command.com, and I had nothing running in my tray that would use clock ticks. i ran the test several times, (as i always do btw) and the answers varied between tests just the barest fraction... like 7.09 versus 7.07 kinda thing.... if we cannot reconcile this, then perhaps we could rerun the tests in *pure* dos with equal copies of euphoria (2.0) *pure* dos=(reboot, f8 @ "starting win95", choose 5, load the fewest drivers possible [himem, sets {like set tmp=c:\tmp stuff}, path, prompt, smartdrv and defnly no mouse, no cdrom, and no soundcard stuff] then run the test several times to make sure that ex.exe and foobar.ex is cached... and if all that *still* doesn't reconcile the win, place, and show rankings of proc1..4() then we can start scratching our heads :) --Hawke'
10. Re: Optimization
- Posted by Davi Figueiredo <davitf at USA.NET> Sep 26, 1998
- 429 views
Hawke wrote: > what version of EU are you running, and on what machine, > and under what conditions? (under a dos box? with other things > running? etc) I ran the benchmark on a Pentium II 233, using Eu 2.0. There were other programs running, but I don't think they have affected the results. I ran the tests about 5 times. > if we cannot reconcile this, then perhaps we could rerun the > tests in *pure* dos with equal copies of euphoria (2.0) After reading your post, I entered safe mode dos prompt (no TSRs or anything) and ran it. Back in Windows, I closed all programs and ran it both with ex.exe and exw.exe . Here are the results (in seconds): DOS Win (ex) Win (exw) proc1 5.41 5.41 5.57 proc2 7.04 7.12 7.25 proc3 4.75 4.78 5.38 proc4 1.58 1.59 1.40 I really don't know what happened then. only if the Pentium II has something the Pentium MMX doesn't... > and if all that *still* doesn't reconcile the win, > place, and show rankings of proc1..4() then we > can start scratching our heads :) I already am... Regards, Davi T. Figueiredo davitf at usa.net ____________________________________________________________________ Get free e-mail and a permanent address at http://www.amexmail.com/?A=1
11. Re: Optimization
- Posted by Matt Z Nunyabidness <matt1421 at JUNO.COM> Sep 26, 1998
- 424 views
- Last edited Sep 27, 1998
uh, mr. hgfhgfhgfhtry4565gtr3wg5(no offense), what's your last name. ------------------------------------- When it comes to programming languages, Euphoria is a cut above - matt1278 at juno.com and matt1421 at juno.com(and soon to be irisnmatt at prodigy.net. Then again, maybe not) Euphoria programmer ___________________________________________________________________ You don't need to buy Internet access to use free Internet e-mail. Get completely free e-mail from Juno at http://www.juno.com Or call Juno at (800) 654-JUNO [654-5866]
12. Re: Optimization
- Posted by Hawke <mdeland at NWINFO.NET> Sep 26, 1998
- 415 views
- Last edited Sep 27, 1998
Davi Figueiredo wrote: > DOS Win (ex) Win (exw) > proc1 5.41 5.41 5.57 > proc2 7.04 7.12 7.25 > proc3 4.75 4.78 5.38 --this has to be P2 > proc4 1.58 1.59 1.40 > I really don't know what happened then. only if the Pentium II > has something the Pentium MMX doesn't... i know the pII has some extra L1 cache, and it has some additional optimizations over Pmmx... it's almost bedtime here and i a wee groggy, but i wanna say that a pII has a prefetching mechanism and all kinda other wierdness that operates upon asm/mach levels... but i jus cannae 'member right now all the kewlness a pII has... most likely, b4 i wake up, someone else who's in the know, and not as groggy (read lazy, as in too lazy to look this up) as tis I, and can give us a better set of pII optimizations that may be taking place here... anyone else who does _not_ have a pII wanna run these tests to see if the come into line with my results? anyone else who _does_ have a pII wanna run them and see if their answers are in line with davi's? tia--nite take care all and care of, indeed. --Hawke'