[H-GEN] Which is better?

[Anthony Towns]

On Wed, Apr 28, 2004 at 11:10:48AM +1000, Adrian Sutton wrote:
> >  - Aj's optimisation was not quite as good as Harries, but still
> >    an improvement.  The old C coding tricks still work in java
> >    evidently.  Harry - if you still feel the urge to optimise
> >    your for loops use this.  It doesn't harm readability and is
> >    faster.
> This most definitely does harm readability.  Most programmers will 
> expect that the iteration of an array will occur incrementally, not 
> decrementally.  

Yup. It can also harm performance too -- because most arrays are accessed
from start to finish, people occassionally make optimisations to make
that work faster; eg by loading the next few values after the one you
access into a cache so subsequent accesses are really quick.

Likewise, most algorithms are specified by going forward, not backwards;
trying to convert between the spec and the implementation is a good way
of getting yourself confused and making mistakes.

The only time to start worrying about decrementing arrays is if you
actually care about a single processor cycle per invocation. If you're
programming in Java, you don't care about that -- differences between
JITs, garbage collection, the indirection hit you take going via classes
will all make much higher costs.

The time when it /might/ be relevant is if you're going over a _huge_
array, and doing something very trivial to each element. That mostly means
pretty low-level graphics operations; and even that could be irrelevant
with "recent" innovations like MMX.

> Again, there is You're talking about a speed 
> up of 0.1 of a second even if you consider the measurements above to be 
> valid.

For an empty loop, it's about a 5% improvement. That's the *best case*
improvement, when 100% of your workload is incrementing the loop counter.
If 80% of your workload is in the body of the loop -- say, loading an
array element into a register, operating on it, and writing it back to
memory, ie "a[i] *= 2;" -- then you've got a best case improvement of a
little over a 1% improvement. If you're doing something more complicated
than "a[i] *= 2" in the body, but something no more complicated than
"i == array.length; i++" in the looping condition, you're not even going
to make a 1% improvement by the i-- trick.

> >By the by, I wrote the "dim unoptimised" test in C.  It ran 5,000 times
> >faster than the Java version.  Source code appears at the end.
> This doesn't surprise me at all.  

And do you find the correction that it's not 0.02% of the speed of the
Java version, but actually 130% surprising? (Apparently not)

It doesn't really surprise me either; malloc()'s a pretty expensive
operation in C on Linux, and there's no JIT or similar to make the
expense go away after repeated pointless invocations.

Of course, not being able to predict whether something'll take 0.02%
of the time, or 130% of it, is why you can't optimise based on theory --
you have to profile, and base your optimising on experiment instead.

> Here's what the C code does:
> * Check the RAM is available, if not crash.
> * Mark this section of RAM as in use.
> * Mark this section of RAM as not in use.

One thing it can say is:

	* Find the first bit of RAM in the free list that's big enough for
	  this
	* Remove it from the free list
	* Find the appropriate place in the free list to re-add the RAM
	* Put it in the free list

The two find options can be O(N) depending on how fragmented your process'
free memory list is. They shouldn't be too bad in this example, but can
get pretty bad.

Cheers,
aj

-- 
Anthony Towns <aj at humbug.org.au> <http://azure.humbug.org.au/~aj/>
Don't assume I speak for anyone but myself. GPG signed mail preferred.

Protect Open Source in Australia from over-reaching changes to IP law
http://www.petitiononline.com/auftaip/ & http://www.linux.org.au/fta/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 307 bytes
Desc: Digital signature
URL: <http://lists.humbug.org.au/pipermail/general/attachments/20040428/bf5cb60f/attachment.sig>