Warp wrote:
> Daniel Nilsson <pov### [at] daniel-nilssoncom> wrote:
>> The thing to learn from this, and it's my experience from work too, is 
>> that you should write code that is easy to read and maintain rather than 
>> try to be clever with optimizations.
> 
>   IMO this:
> 
>     variable = someLengthyCalculation;
>     useVariable(variable);
>     useVariableForSomethingElse(variable);
> 
> is more readable than:
> 
>     useVariable(someLengthCalculation);
>     useVariableForSomethingElse(someLengthCalculation);
> 
> especially if "someLengtyCalculation" is even a bit complicated. (Basically
> the variable makes it very clear that the two expressions are, in fact, the
> one and same, something which might not be visually obvious if the expression
> is repeated.)
> 
>   As a bonus, you'll make absolutely sure the compiler won't calculate
> it twice. (In some cases it might be that the compiler is forced to
> calculate it twice because it can't know if some called function has
> side-effects.)
> 

Yes, I agree that in this case the code with the variable is the most 
readable. My point is that in general you should not bother with 
optimization. The compiler is most of the time clever enough to figure 
it out. Only try to optimize if profiling shows some inefficiency.

-- 
Daniel Nilsson

Post a reply to this message

Daniel Nilsson <pov### [at] daniel-nilssoncom> wrote:
> > This can be optimized to:
> >     [...]
> > Or maybe this is even a bit faster (and actually a tiny bit more defensively
> > coded):
> >     [...]
>
> No need to optimize the code, that's the job of the compiler. Any modern
> compiler will notice the common subexpressions and optimize them. I just
> did a small test with all three versions above compiled with "gcc -S
> -O2" (gcc 4.1.2 on x86_64 linux). The produced assembly is virtually
> identical for all three cases, the last one actually has the most
> instructions generated (extra moves mostly).

Hm... well, maybe I'm showing my age... I'm actually not too deep into
compiler-based optimizations. It has been a while since I last looked at what
an x86 compiler makes of my C/C++ code.

I'd still consider using the last version though, because I know it cannot run
into number precision issues with the sqrt(). But then agan, I'm not a learned
floating-point expert either, so maybe I'm a bit over-defensive here.

(My job is usually to write robust and easy-to-maintain software (or fix less
robust and more-difficult-to-maintain software), with some hardware jockeys
making sure that the small black boxes it is flashed into provide safe margins
of computing power.)

> Oh, and happy new year!

Same to you, and everyone else around.

Post a reply to this message

andrel <a_l### [at] hotmailcom> wrote:
> sqrt has at worst N/2 iteration, with N the number of significant bits.
> That is a naive implementation. I thought there are even faster
> algorithms. Cheap calculators often have a button for sqrt, implying
> probably that they have a (naive) hardware implementation. I don't know
> if it is available also on more complex processors.

From the "Intel(R) 64 and IA-32 Architectures Software Developer's Manual,
Volume 1: Basic Architecture":

------------------------
8.3.5 Basic Arithmetic Instructions

The following floating-point instructions perform basic arithmetic operations on
floating-point numbers. Where applicable, these instructions match IEEE Standard
754:

FADD/FADDP Add floating point
FIADD Add integer to floating point
FSUB/FSUBP Subtract floating point
FISUB Subtract integer from floating point
FSUBR/FSUBRP Reverse subtract floating point
FISUBR Reverse subtract floating point from integer
FMUL/FMULP Multiply floating point
FIMUL Multiply integer by floating point
FDIV/FDIVP Divide floating point
FIDIV Divide floating point by integer
FDIVR/FDIVRP Reverse divide
FIDIVR Reverse divide integer by floating point
FABS Absolute value
FCHS Change sign
FSQRT Square root                          <--
FPREM Partial remainder
FPREM1 IEEE partial remainder
FRNDINT Round to integral value
FXTRACT Extract exponent and significand

[...]

8.3.7 Trigonometric Instructions

The following instructions perform four common trigonometric functions:

FSIN Sine
FCOS Cosine
FSINCOS Sine and cosine
FPTAN Tangent
FPATAN Arctangent

[...]

8.3.9 Logarithmic, Exponential, and Scale

The following instructions provide two different logarithmic functions, an
exponential function and a scale function:

FYL2X Logarithm
FYL2XP1 Logarithm epsilon
F2XM1 Exponential
FSCALE Scale

[...]

------------------------

Don't expect all these to be "naive hardware implementation" in the same sense
as, say, an integer addition, shift, bit-wise AND/OR/XOR or whatever. Even a
floating-point addition is a non-trivial thing. Rather consider the FPU
(Floating Point Unit) a computer in the computer: You feed some data into it,
give it an instruction what to do with that data, and then basically wait for
the (fast and highly optimized) hard-wired FPU "programlets" to complete. Or do
some other usefull stuff in the meantime.

To my knowledge, a lot of work is saved by using Look-up-tables (like people
used in old times before pocket calculators had a "sin", "log" or "sqrt"
button) to optimize away a few iterations of the algorithms.

BTW, your typical pocket calculator will do just about the same. AFAIK there is
no non-iterative algorithm for computing the square root of an arbitrary
floating point number.

Post a reply to this message

andrel <a_l### [at] hotmailcom> wrote:
> - as you suggest, put it in a regular beta 3.17

(I guess you mean 3.7 ;))

Clearly my favorite as well. The POV team has a copy of my code.

Post a reply to this message

"nemesis" <nam### [at] gmailcom> wrote:
> That message was part of 3.5 as well and perhaps earlier.  An "experimental"
> feature that has been around for, what?, 10 years.  That's even longer than
> Google eternal betas... :))

But it was well deserved - from what I see, it was obviously too crappy in 3.6
to remove that warning :)

Post a reply to this message

Jaime Vives Piqueres posted an interesting radiosity test scene in
p.b.images, where he basically improved the quality of the radiosity
calculations by rendering the same image many times, each time
decrementing the error_bound, and saving/loading the radiosity data
to a file for the next render. The quality of the radiosity lighting
got very significantly improved this way, with a surprisingly moderate
overall render time.

  Given how much this technique improves the quality of the lighting
I think it should be seriously considered to be studied further and
implemented as an internal feature of POV-Ray, so that POV-Ray can be
made to do this automatically, without the need for the save files nor
setting animation rendering manually.

-- 
                                                          - Warp

Post a reply to this message

On 31-Dec-08 4:55, clipka wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>> sqrt has at worst N/2 iteration, with N the number of significant bits.
>> That is a naive implementation. I thought there are even faster
>> algorithms. Cheap calculators often have a button for sqrt, implying
>> probably that they have a (naive) hardware implementation. I don't know
>> if it is available also on more complex processors.
> 
> From the "Intel(R) 64 and IA-32 Architectures Software Developer's Manual,
> Volume 1: Basic Architecture":
> 
> ------------------------
> 8.3.5 Basic Arithmetic Instructions
> 
> The following floating-point instructions perform basic arithmetic operations on
> floating-point numbers. Where applicable, these instructions match IEEE Standard
> 754:
> 
> FADD/FADDP Add floating point
> FIADD Add integer to floating point
> FSUB/FSUBP Subtract floating point
> FISUB Subtract integer from floating point
> FSUBR/FSUBRP Reverse subtract floating point
> FISUBR Reverse subtract floating point from integer
> FMUL/FMULP Multiply floating point
> FIMUL Multiply integer by floating point
> FDIV/FDIVP Divide floating point
> FIDIV Divide floating point by integer
> FDIVR/FDIVRP Reverse divide
> FIDIVR Reverse divide integer by floating point
> FABS Absolute value
> FCHS Change sign
> FSQRT Square root                          <--
> FPREM Partial remainder
> FPREM1 IEEE partial remainder
> FRNDINT Round to integral value
> FXTRACT Extract exponent and significand
> 
> [...]
> 
> 8.3.7 Trigonometric Instructions
> 
> The following instructions perform four common trigonometric functions:
> 
> FSIN Sine
> FCOS Cosine
> FSINCOS Sine and cosine
> FPTAN Tangent
> FPATAN Arctangent
> 
> [...]
> 
> 8.3.9 Logarithmic, Exponential, and Scale
> 
> The following instructions provide two different logarithmic functions, an
> exponential function and a scale function:
> 
> FYL2X Logarithm
> FYL2XP1 Logarithm epsilon
> F2XM1 Exponential
> FSCALE Scale
> 
> [...]
> 
> ------------------------

I didn't know even sin and cos are now hardware supported, interesting. 
That will enable you to pinpoint the last time I did some assembler 
programming to within two years. Another source gives the 8087 as the 
first one to implement FSQRT and the 80387 as the first one for the FSIN 
etc. That makes sense.
If we could now also find the average timing of these instructions, we 
might even be able to answer Warp's question on how much faster SQRT is 
compared to e.g. sin.

> 
> Don't expect all these to be "naive hardware implementation" in the same sense
> as, say, an integer addition, shift, bit-wise AND/OR/XOR or whatever. Even a
> floating-point addition is a non-trivial thing. Rather consider the FPU
> (Floating Point Unit) a computer in the computer: You feed some data into it,
> give it an instruction what to do with that data, and then basically wait for
> the (fast and highly optimized) hard-wired FPU "programlets" to complete. Or do
> some other usefull stuff in the meantime.

Microcode may be the word you are looking for.

> To my knowledge, a lot of work is saved by using Look-up-tables (like people
> used in old times before pocket calculators had a "sin", "log" or "sqrt"
> button) to optimize away a few iterations of the algorithms.
> 
> BTW, your typical pocket calculator will do just about the same. AFAIK there is
> no non-iterative algorithm for computing the square root of an arbitrary
> floating point number.

It is an iterative procedure but you need the same hardware as for a 
divide. So when you build something that can do division in hardware 
with some shift registers and a comparator, there is bound to be some 
space in the chip left to add the few gates to do a SQRT also.
You can do a SQRT and a division in pure hardware without microcode.
I wouldn't be surprised if current FPUs do use some clever tricks in 
microcode to speed up the SQRT by using a more sophisticated algorithm. 
But, as I said, I am doing not much programming close to the machine 
anymore these days.
Hmm, I have not even read Dr Dobbs for a few years. Been thinking of 
renewing my subscription for almost as long, never came round to it. 
Let's spend some cash before the year ends.

Post a reply to this message

andrel <a_l### [at] hotmailcom> wrote:
> I didn't know even sin and cos are now hardware supported, interesting.

  "Now"? In which cave are you living?-)

  When was the 80387 introduced? According to wikipedia, 1987. That's like
21 years ago...

-- 
                                                          - Warp

Post a reply to this message

On 31-Dec-08 11:50, Warp wrote:
> andrel <a_l### [at] hotmailcom> wrote:
>> I didn't know even sin and cos are now hardware supported, interesting.
> 
>   "Now"? In which cave are you living?-)
> 
>   When was the 80387 introduced? According to wikipedia, 1987. That's like
> 21 years ago...
> 
I invited you to do the math ;) That 1987 was more or less the last time 
I wrote some machine code and that was not for a 386/7 system. As far as 
I am concerned the hardware and software developers for the PC 
compatibles did not really invite programming close to the hardware.

Post a reply to this message

clipka wrote:
> Don't expect all these to be "naive hardware implementation" in the same sense
> as, say, an integer addition, shift, bit-wise AND/OR/XOR or whatever.

Exactly that is why you ought to be looking at the SSE2/3 floating-point 
registers and associated hardware support. The x87 FPU is only there for 
legacy support and rather inefficient.

 > Even a floating-point addition is a non-trivial thing.

Actually, it is not more complex than integer addition and multiplication.

	Thorsten

Post a reply to this message