1. Object Euphoria optimiztion
I have completed Object Euphoria 1.1 and am currently debugging and updating
the documentation. The code has been aggressively optimized. I will post
it to RDS as soon as possible.
The following benchmarks are for 100000 iterations in a "typical" class
hierarchy:
Object Euphoria 1.0 Object Euphoria 1.1 speed
increase
set_member() 3.79 sec 0.88 sec
76.8%
get_member() 3.79 sec 0.88 sec
76.8%
call_method() 4.12 sec 1.15 sec
72.1%
OE 1.1 is 56K compared to OE 1.0's 46K-- and some of the increase is due to
added features.
Some advice about optimiztions for speed:
1. Minimize type checking--particularly avoid rechecking the same data when
possible.
2. Avoid nested procedure calls--inline simple routine code.
3. Similarly, avoid recursion.
4. It is much faster to search sevaral short sequences than one huge
sequence.
5. Use variables to reduce repetitive subscripting.
--Mike Nelson
2. Re: Object Euphoria optimiztion
Mike Nelson wrote:
> Some advice about optimiztions for speed:
> 1. Minimize type checking--particularly avoid rechecking the same
> data when possible.
> 2. Avoid nested procedure calls--inline simple routine code.
> 3. Similarly, avoid recursion.
> 4. It is much faster to search sevaral short sequences than one
> huge sequence.
> 5. Use variables to reduce repetitive subscripting.
Just a few comments.
I am in complete agreement with you on points 1 and 5. In fact I have
always maintained, rightly or wrongly, type checking is nothing more
than a debugging tool of dubious value.
I think your second point is probably not terribly important. Routine
calls are incredibly cheap in Euphoria, in comparison with just about
any language I know. So unless you are dealing with very short
innermost loops of millions of cycles, it's not worth the trouble
trying to unroll them.
And similarly, your advice against recursion is marginal. Once again,
recursive calls in Euphoria are very efficient, and it's generally
very difficult to find faster alternatives to well designed, tight
recursive routines.
Finally, I have never seen any evidence for your claim under number 4.
I have tested the speed of find() many times, and it seems to be
simply linear with the traversed length. Chopping up sequences just
simply adds to overheads.
jiri
3. Re: Object Euphoria optimiztion
------=_NextPart_000_0032_01BF73DD.DB610B00
charset="Windows-1252"
-----Original Message-----
From: jiri babor <jbabor at PARADISE.NET.NZ>
To: EUPHORIA at LISTSERV.MUOHIO.EDU <EUPHORIA at LISTSERV.MUOHIO.EDU>
Date: Thursday, February 10, 2000 4:03 AM
Subject: Re: Object Euphoria optimiztion
>Mike Nelson wrote:
>
>> Some advice about optimiztions for speed:
>> 1. Minimize type checking--particularly avoid rechecking the same
>> data when possible.
>> 2. Avoid nested procedure calls--inline simple routine code.
>> 3. Similarly, avoid recursion.
>> 4. It is much faster to search sevaral short sequences than one
>> huge sequence.
>> 5. Use variables to reduce repetitive subscripting.
>
>
>Just a few comments.
>
>I am in complete agreement with you on points 1 and 5. In fact I have
>always maintained, rightly or wrongly, type checking is nothing more
>than a debugging tool of dubious value.
>
>I think your second point is probably not terribly important. Routine
>calls are incredibly cheap in Euphoria, in comparison with just about
>any language I know. So unless you are dealing with very short
>innermost loops of millions of cycles, it's not worth the trouble
>trying to unroll them.
>
>And similarly, your advice against recursion is marginal. Once again,
>recursive calls in Euphoria are very efficient, and it's generally
>very difficult to find faster alternatives to well designed, tight
>recursive routines.
>
>Finally, I have never seen any evidence for your claim under number 4.
>I have tested the speed of find() many times, and it seems to be
>simply linear with the traversed length. Chopping up sequences just
>simply adds to overheads.
>
>jiri
>
Jiri,
The file benchmark.ex I am attaching should provide ample proof how much
faster it is to search short sequences--by the way, by "short" I mean small
number of elements. Benchmark.ex searches a 2500-element sequence for a
string then searches a 50-element sequence for the first half of a string
and uses the result as the subscript for a 50-by-50-element sequence and
searches the subsequence for the second half of the string. These are the
results:
100000 searches of 2500 element sequence in 26.96 seconds.
100000 searches of 50 by 50 element sequence
indexed by search of 50 element sequence in 0.61 seconds.
I would say that a 97.7% reduction in execution time is worth a little
complexity. Of all the benchmark tests I ran before starting the OE
optimization, this is the most impressive. Perhaps this clarifies my point
#4.
Points #2 and #3 are marginal but worthwhile if you want to squeeze out the
last drop of performance--calls in Euphoria are very cheap but not free.
-- Mike Nelson
------=_NextPart_000_0032_01BF73DD.DB610B00
name="benchmark.ex"
4. Re: Object Euphoria optimiztion
Mike,
You must be kidding! Only on very rare occasions this sort of thing
can be accomplished in real life without mirrors.
So I have this 2500 element sequence full of random data and I am
looking for the first occurrence of a particular pattern. How on earth
do I construct the index sequence to perform your magic. My data can
be anything, any length. How do I divide it into your neat little
parcels? And why just 50, why not a full 100? The savings will be
even greater!
jiri
5. Re: Object Euphoria optimiztion
-----Original Message-----
From: Jiri Babor <J.Babor at GNS.CRI.NZ>
To: EUPHORIA at LISTSERV.MUOHIO.EDU <EUPHORIA at LISTSERV.MUOHIO.EDU>
Date: Thursday, February 10, 2000 6:39 PM
Subject: Re: Object Euphoria optimiztion
>Mike,
>
>You must be kidding! Only on very rare occasions this sort of thing
>can be accomplished in real life without mirrors.
>
>So I have this 2500 element sequence full of random data and I am
>looking for the first occurrence of a particular pattern. How on earth
>do I construct the index sequence to perform your magic. My data can
>be anything, any length. How do I divide it into your neat little
>parcels? And why just 50, why not a full 100? The savings will be
>even greater!
>
>jiri
Jiri,
My example is admittedly artificial--the real world issue was whether OE
should use a single symbol table for namespaces, classes, members, and
methods rather than the mutiple symbol tables in the current design. My
original thought was that this would run faster because less subscripting
would be required--this and other benchmarks proved this idea to be in
error.
How this works: let's say I'm seaching for the Print method of class
Alpha--the one approach would search for Alpha.Print in a single, very long
symbol table; the other searches for Alpha in the class table, then uses the
result to search the correct subsequence of the method table. The savings
won't be so dramatic in small applications with fewer than 50 classes with
50 methods each--but look at the C++ or Java source code for some real
world programs--my numbers are by no means impossible.
--Mike
6. Re: Object Euphoria optimiztion
Look, Mike, let's not dwell on it. Originally, you gave bad advice, on
that single point, and I tried to be polite about it. You compounded
your mistake by supplying phony evidence. We all make mistakes, that's
nothing tragic, it's the fastest way to learn.
How you solve your search problem is, of course, up to you. But
remnants of my common sense tell me (people in the OO camp are not
terrible well known for it - sorry about the cheap crack ;)) a very
reasonable approach, for small to medium sized sets, would be to keep
the most frequently used elements simply at the beginning of the
sequence. For larger sets, at least some hundreds, possibly thousands
of items, you can choose from any number of hash table schemes, or
simply sort the thing and employ a binary search or whatever, they all
would be just as good, and probably better, than what you are
proposing.
Btw, quite unreasonably, the topic has been abandoned at this end!
jiri
