lomont.org · Domains · Slashdot Mirror

Re:Surprise? Why? by UnknownSoldier · 2016-07-11 03:09 · Score: 1 · on TIOBE's Language-Popularity Index Sees A New Top 10 Language: Assembly (tiobe.com)

TL:DR; You need to learn HOW to optimize:

@37:30 -- Mike Acton: Code Clinic 2015: How to Write Code the Compiler Can Actually Optimize

- - -

> If you want speed, assembly is the ONLY option.

Total NONSENSE.

A. You keep implying this word optimization -- it doesn't mean what you think it means!

B. There are four lights, er, types of optimizations:

1. Use a lower level language
2. Micro-optimization or Bit-twidling
3. Algorithm
4. Macro or cache-orientated, aka (Data-Orientated Design)

What do these mean?

1. Use a lower level language

With bloated languages and incorrect use of C++, Java, etc., inexperienced programmers naively thing changing to a "lower level" language -- such as C or Assembly -- will help speed up their code. While it is true one has access to more programming paradigms in a low level language, i.e. you can use the carry flag as a return value instead of wasting an entire byte with assembly, this type of optimization only takes you so far before you need to look at alternatives.

2. Micro-optimizations

All good programmers should read (and understand!) these bit twiddling optimizations:

* bit-twiddling hacks
* Hackers Delight

While compilers can generate "good enough code", sometimes hand-optimized instructions can beat the compiler. e.g. Before compilers optimized division with reciprocal multiplication, a common technique for division was to manually change division into reciprocal multiplication. i.e. `/ 3` -> `* 1/3` which means you would see something like this:

int a = 123 / 3;

would be replaced with:

int b = (123 * 65536 / 3) >> 16;

Thankfully most compilers will perform these integer divisions but you can try this out with an online C compiler:

#include <stdio.h> int main() { int a = 123 / 3; int b = (123 * 65536 / 3) >> 16; int c = a == b; printf( "a: %d =%d= b: %d\n", a, c, b ); return 0; }

These types of micro-optimizations are becoming rarer and rarer as compilers (slowly) get better. However Don't assume. VERIFY your assembly output of the compiler.

Floating-point optimizations still show up. The most famous is probably John Carmack's Quake 3 Inverse Square Root

This PDF provides a very good explanation:

* http://www.lomont.org/Math/Pap...

3. Algorithm

The fastest way to optimize (from the programmer's run-time) is to replace a slower algorithm with a faster one.

i.e.

* If the common case for your data is unsorted, then replacing a dog-slow bubble sort with quick-sort will show gains.
* However, if the common caseis that the is 99% mostly sorted, then changing algorithms may not always help.

This is where most people start to optimize. BUT, notice how I said "Common Case". There is a _higher level_ of optimization we can do:

4. Macro or Cache-orientated.

The 0th rule in optimization is:

Know Thy Data

When you optimize you need to optimize for the common case. This means understanding data flow, Memoization, and transforms. You _must_ question ALL assumptions, knowns, and unknowns. What, exactly, are you trying to do? i.e. Printing Primes and Printing

Re:I'm slightly astonished by Anonymous Coward · 2008-12-04 23:27 · Score: 3, Informative · on Players Furious Over Buggy GTA IV PC Release

Assembly will only be used for small, high-cost operations. These pieces are small enough that if they malfunction, it's in a way that will be immediately visible.

Nonsense. Here's one counterexample. There is the assembly routine in Excel 2007 that formats numbers for display; it had a subtle bug with some input values. Bug description from Microsoft, Technical explanation (PDF).

Re:It would be nice to have real information on th by Anonymous Coward · 2007-04-06 14:42 · Score: 0 · on Windows .ANI Problem Surfaced Two Years Ago

I found a detailed description and code at http://www.lomont.org/Software/ANIExploit/ExploitA NI.pdf. Some dude wrote an exploit in two days based on stuff found on the internet and detailed how he did it, including analysis of the flaw. It also has sample HTML that loads a cursor to show how to do it.

Clever trick! by kent.dickey · 2006-12-01 10:58 · Score: 5, Informative · on Origin of Quake3's Fast InvSqrt()

To summarize, the article is about a piece of code to approximate 1/sqrtf(f):

float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x; i = 0x5f3759df - (i>>1); x = *(float*)&i; x = x*(1.5f - xhalf*x*x); return x; }

The trick is the "i = 0x5f3759df" line. It's certainly a magic number.

The algorithm is simple Newton-Raphson -- make a good initial guess, then iterate making the guess better. I think Newton-Raphson on 1/sqrt picks up 5-6 bits each try in the line "x = x*(1.5f - xhalf*x*x)". It can be repeated to get a more accurate result each time it's repeated.

The problem with Newton-Raphson is making a good first guess--otherwise, you need an extra iteration or two. And that's what the magic number is doing, making a good first guess.

So let's work out what a good first guess would look like for 1/sqrt(f), to see where this code came from.

Floating Point numbers are stored with a mantissa and an exponent: f = mantissa * (2 ^ exponent), where exponent is 8-bits wide and the mantissa is 23-bits wide.

Let's take an example: 1/sqrt(16) would have f = 1.0 * (2 ^ 4). We want the result 0.25 which is f = 1.0 * ( 2 ^ -2).

So our first guess should take our exponent, negate it, and cut it in half. (Try more examples to see that this works--it's basically the definition of 1/sqrt(f)). We'll ignore the mantissa--if we can just get within a factor of 2 of the answer in one step, we're doing pretty well.

Unfortunately, the exponent is stored in FP numbers in an offset format. In memory,

exp_field = (actual_exp + 127) << 23

The mantissa is in the low 23 bits, and the most-significant bit is the sign (which will be 0 if we're taking roots). For now, let's just assume we have our exponents as 8-bit values, to work out what we need to do with the +127 offset.

We want new_actual_exp = -(actual_exp)/2. But in memory, exp = (actual_exp + 127). Or, actual_exp = exp - 127.

Substituting gives (new_exp - 127) = -(exp - 127)/2. Simplify this to: new_exp = 127 - (exp - 127)/2 => new_exp = 3*127/2 - (exp / 2).

Now the exponent is shifted 23 places in memory, so let's write out our code (and ignore the mantissa completely for now...):

i = ((3*127)/2) << 23) - (i >> 1);

rewriting as hex:

i = 0x5f400000 - (i >> 1);

Well, first, it's arguable whether it should be 0x5f000000 or 0x5f400000 (The "4" is actually in the mantissa). I'm guessing resolving that dilemma led to the original author discovering that choosing a particular pattern of bits in the mantissa can help make the initial guess even more accurate, leading to the 0x5f3759df constant.

I haven't worked it out, but Chris Lomont http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf shows this first guess is accurate to about 4-5 bits of significance for all floating point values. That's a good result, considering that mucking with the exponents was just hoping to get us within 1-2 bits of significance.

Re:What's with use of Pointers? by dsci · 2006-12-01 09:36 · Score: 2, Informative · on Origin of Quake3's Fast InvSqrt()

How on earth does subtracting the result from a magic value then give you the inverse square root?

Subtracting the right shifted value from the magic value does NOT give the 'inverse square root.' This line of code only gives the initial guess for the Newton-Raphson algorithm.

While the initial guess is a huge part of the real beauty of the algorithm (ie, why it can converge to a sufficiently accurate value after ONLY ONE ITERATION), the 'real work' is done in the

x = x*( 1.5f - xhalf*x*x )

line. That's that application of one iteration of Newton-Raphson (rewritten a bit from what I and others posted earlier, but for this problem algebraically the same). To get more accuracy in the calculation, apply this line repeatedly.

The explanation of the why the magic value - (right shifted int represenation of the float) is a good initial guess is given in the Paper by Chris Lomont linked to in article. Specifically, look on Section 4 beginning on Page 3 of Lomont's article; that's where the fun starts.

In a nutshell, from Lomont, the initial guess is computed "by multiplying the exponent by -1/2, and then picking bits to minimize error." I have not worked through all the details on why this is a good initial guess, but will reemphasize that getting a good result from Newton-Raphson DEPENDS on the initial guess. So, it is not surprising that someone hunted for a general algorithm to find a good initial guess.

Another nice tagger (Especially a good viewer!) by Anonymous Coward · 2006-01-24 03:31 · Score: 0 · on An Accurate ID3 Tag Database?

When editing my tags with some popular taggers, I noticed they did not view tags the same, and a few were inserting incorrect tags. Viewing what one editor inserted appeared differently on another. I found someone's free tagger at http://www.lomont.org/Software/Utilities/TEdit/ind ex.php which has some really nice viewing features, and I have used it for editing a lot of tags without problem.