1. Optimization

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.

new topic     » topic index » view message » categorize

2. Re: Optimization

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

new topic     » goto parent     » topic index » view message » categorize

3. Re: Optimization

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.

new topic     » goto parent     » topic index » view message » categorize

4. Optimization

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

new topic     » goto parent     » topic index » view message » categorize

5. Re: Optimization

>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]

new topic     » goto parent     » topic index » view message » categorize

6. Re: Optimization

>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

new topic     » goto parent     » topic index » view message » categorize

7. Re: Optimization

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]

new topic     » goto parent     » topic index » view message » categorize

8. Re: Optimization

>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

new topic     » goto parent     » topic index » view message » categorize

9. Re: Optimization

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'

new topic     » goto parent     » topic index » view message » categorize

10. Re: Optimization

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

new topic     » goto parent     » topic index » view message » categorize

11. Re: Optimization

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]

new topic     » goto parent     » topic index » view message » categorize

12. Re: Optimization

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'

new topic     » goto parent     » topic index » view message » categorize

Search



Quick Links

User menu

Not signed in.

Misc Menu