OpenEuphoria

Re: Well I did it! (variable_id, etc..)

• Posted by Robert Craig <rds at RapidEuphoria.com> Nov 26, 2004
• 632 views

Andy Serpa wrote:
> 
> Greg Haberek wrote:
> > 
> > [sounds like Peter from Family Guy] "Holy friggin crap!!"
> > 
> > That's amazing. Here's a speed update:
> > 
> > sorting 10,000 random objects between 0 and 999
> > 
> > Old stats:
> >     exw: 0.020 seconds
> >     euw: 10.975 seconds (best run, some were 11+)
> > 
> > New stats:
> >     exw: 0.020 seconds
> >     euw: 0.281 seconds
> > 
> > I guess the interpreted interpreter isn't so slow after all!
> > 
> 
> Damn.
> 
> Explanation?  Sounds like a trick I ought to know.  I have often put in such
> "optimizations"
> and taken them back out because it actually made things slower.  And if you
> mess around
> with this much it goes back to being 10x slower.  What's the secret?

There's a very subtle, but in this case major, performance issue here.
I only found it by using profile_time. (It has nothing to do with
2.5. Any version of Euphoria would act the same.)

The new, fast version of the code is below.
I've added some comments with !!!, 
to show how I speeded it up:

procedure opASSIGN_SUBS() -- also ASSIGN_SUBS_CHECK, ASSIGN_SUBS_I
-- LHS single subscript and assignment
    object x, subs

    a = Code[pc+1]  -- the sequence
    b = Code[pc+2]  -- the subscript
    if sequence(val[b]) then
RTFatal("subscript must be an atom\n(assigning to subscript of a
        sequence)")
    end if
    c = Code[pc+3]  -- the RHS value
x = val[a]    -- !!! save val[a] in x, i.e. increments reference count on
    val[a]
    lhs_check_subs(x, val[b])  -- !!! pass x instead of val[a]
    x = val[c]  -- !!! x overwritten, removes a reference count on val[a]
    subs = val[b]
    val[a][subs] = x  -- val[a] now has one reference count, not two
    pc += 4
end procedure

In the original code I was passing val[a] as an argument, i.e.

   lhs_check_subs(val[a], val[b])

What it was actually doing internally is something like:

   temp1 = val[a]
   temp2 = val[b]
   lhs_check_subs(temp1, temp2)

later on when the statement

   val[a][subs] = x

was performed, there were always *two* reference counts
on val[a]. One from val itself, and a dangling reference 
from temp1, since temp1 was still pointing to val[a]. This means
that a full copy of val[a] had to be made in order to
safely change an element of it. i.e. without making a copy, we'd be
disturbing the value of temp1. val[a] is a 10000-element sequence. 
Ouch! 

Euphoria tries to re-use temps as soon as possible, and free their
references, but until a temp is overwritten with a new value, 
any reference count caused by that temp remains. In this case 
temp1 was not used again. Almost any kind of expression would 
have resulted in temp1 being overwritten with a new value, 
with the problematic reference count being removed.

I haven't seen a case as bad as this before, but
I've long considered doing an optimization where temps and vars
whose current value is not going to be used again could be
"erased" immediately, thus dropping the reference count on what they
are pointing to. To avoid problems, I'd set them to NOVALUE (or something), 
but if it was a var, you might sometimes see 
NOVALUE (or something) in ex.err or on the trace screen which 
could be very confusing, since they should really have a value.

Regards,
   Rob Craig
   Rapid Deployment Software
   http://www.RapidEuphoria.com