Tweaking a code snippet

The best thing you can do to have very portable and fast code is concentrate on the application code and not the implementation.

Keep the statements short and clear. This not only makes the code easy to maintain but will likely generate the best code from a compiler. When our customers send us benchmark code the easiest code to beat is code written to take advantage of obscure optimizations without regard to the overall effect for the application.

Regards,

-- Walter Banks Byte Craft Limited

Correct. That's why I spent the bulk of my efforts designing the server to be table driven and choosing consistent data types (since a compiler would never have been able to make those sorts of transformations)

But these criteria aren't always mutually compatible. E.g., people make mistakes -- compilers can't compensate for those.

And, changing the writing style to discourage those sorts of typos can make the code more difficult to read. E.g., "x - y" becoming "difference(x, y)", or introducing other assignments ("x = ; y = ") just to minimize the possibility of two instances of an ending up "different".

The easy fix is just to leave everything in the data "type" of the values in question and abstract the "operators" that work on those (e.g., don't use infix notation *anywhere*).

I.e., write the code AS IF you were defining a new data type in C++ and rely on "operator()" throughout. (though, in this case, you can use an "operatorCOMPARE()" that returns the sign of the difference -- ignoring the magnitude).

I'll finish recoding it and see how much that cleans it up...

Thx,

--don

In article , D Yuniskis wrote: }Observe: } x RELOP y ==> (x - y) RELOP 0 } -1 * (x - y) ==> (y - x) }i.e., (paraphrasing): } -1 * [ (x - y) RELOP 0 ] ==> y RELOP x } }(RELOP is ">", "=", etc.)

I'm not too clear what exactly this is saying, but if I understand it correctly, it's not true. uint32_t x = 4, y = 5; a = x > y; // 4 > 5 == 0 b = x - y > 0; // 4 - 5 > 0 == 65535 > 0 == 1 c = -1 * (x - y > 0); // -1 * (4 - 5) == -1 * 65535 == -1

Essentially, the problem is that "x - y" might overflow the representation. For unsigned values, this is well-defined but might not be what you want; signed or floating -point values are even worse.

Also, '==' and '!=' behave differently because they're symmetric: a == b is the same as b == a, while a < b is the same as b > a.

}E.g., } sense * (trial - reference) RELOP 0 }where trial and reference are **expressions** indirectly }driven from the table and sense is trivially related }to a table entry.

How about: (trial RELOP reference) != sense

where sense is 0 or 1.

Alternatively, to help a simple compiler you might have: _Bool b = trial RELOP reference; // or char or bool if (sense) b = !b; // or b ^= sense

If the expression is selected at runtime, you could have a table of functions:

int cmp_gt(TYPE trial, TYPE ref) { return trial > ref; }

int (*cmp_table[])(TYPE trial, TYPE ref) = { cmp_gt, ... };

and call cmp_table[x](trial, ref) for the appropriate x.

If they're selected at compile time, maybe a script which generates the code from your table would be best.

Sorry, you missed my "paraphrasing" comment on that last step.

IGNORING BOUNDARY CONDITIONS (e.g., INT_MIN vs INT_MAX, comparing two floats for equality, etc.), do you agree with the first two "observations"?

4 > 5 ==> (4-5) > 0 4 < 5 ==> (4-5) < 0 4 == 5 ==> (4-5) == 0 4 != 5 ==> (4-5) != 0 4 >= 5 ==> (4-5) >= 0 4 (4-5) (y - x).

I.e., this is grade school "arithmetic"

That would be a buggy implementation on my part, eh? :>

(i.e., not going to happen)

Correct. But, they still follow the rules above. I.e., if RELOP happens to be "==" at some point in the code, then all my "sense" variable did was swap the left and right sides of the operator. So, it deliberately converted "a == b" into "b == a". Note that I am not trying to "complement" the operator but, rather, "reverse it".

So, I want to convert ">=" into "

If you are trying to find a good way to write this sort of thing that produces optimal code on a range of compilers and targets, then you are out of luck. For smaller processors, code will be smaller and faster if you write "if (condition) ..." and branch on the condition. Multiplying by +1 or -1 will be expensive. For larger processors that have higher costs for branches (especially when mispredicted), so a formulation that can use arithmetic instead of conditionals will be smaller and faster.

/If/ you can be sure that users will use a decent compiler, and enable appropriate optimisations, then you can do as Walter suggested and write clear and simple code, and let the compiler sort it out. My suggestion would be to formulate the code in a "if (condition) ..." style - compilers for smaller targets will handle that well. Good compilers for bigger targets will be able to re-arrange the code (see for example). To give the compiler the best chance, make sure you always give it as much information as you can - for example, keep your variables at the tightest possible scope, declare functions as "static" if possible and use compiler enhancements such as __attribute__((const)) so that the compiler knows what optimisations are valid.

No, not "optimal" but, rather, "non-terrible" (?) -- see above.

If the data type is simple enough (e.g., "int"), the cost of that multiply can still be low.

As I mentioned in another post, I "solved" the problem (actually, "side-stepped" is a better verb! :> ) by keeping all of the "processing" in the chosen data type instead of trying to promote it to something that could handle all types, etc. E.g., do the comparison *as* an operator supported by the "special type".

This lets me keep the invoking code clean and consistent (i.e., no need for anyone to muck with it). And, it also pushes the "work" required for making that implementation choice into the very hands of the developer opting to create that different data type! I.e., presumably, he/she understands the performance issues related to the design of that data type so, now, he/she can further optimize that implementation by dealing with clever ways to "do the comparison", as well.

(and, if the comparison can be suitably trivialized, it can always be inlined!)

Comes a time you have to "shoot the engineer" and see how things fall. On this little issue, I'm gambling that I'm already close enough to a "reasonable" solution...

That's a reasonable aim!

That depends on how the toolchain implements it. Few toolchains, if any, will be able to see that one side is either a 1 or a -1, and optimise accordingly - they will do a normal int * int multiply. If you've got a nice fast processor that does that in a cycle or two, that's fine - if it's an eight bit processor with no hardware multiply, this means a long slow library call.

It's possible to do a few odd tricks when you know that one side of the multiply is -1 or +1 - but I don't think a compiler will see them. For example, you could do something equivalent to this:

int multPMone(int pmone, int x) { pmone >>= 1; // Turns 1 into 0, -1 into -1 int carry = pmone & 0x1; // Either 0 or 1 return (x ^ pmone) + carry; }

For some processors, that's probably the fastest method.

It can be useful to define minimum requirements (such as 16-bit cpu, or hardware multiplier) - it makes it a lot easier to get

:-)

Hi David,

[8>> If you are trying to find a good way to write this sort of thing that

I can't see how it would be possible to find an "optimum" implementation for a wide variety of targets and a loosely constrained "problem". :<

What I strive for is a "reasonably good" implementation that discourages folks from "dicking with it" (otherwise known as REbugging!). E.g., the core code in this section of the algorithm is now *so* heavily documented that the idea of having to "update" the documentation to coincide with any changes a person *might* be tempted to make to the code should be "discouragement enough" -- especially when the code wraps around "stuff" that the developer is *intended* to tweek (i.e., "Change *this* instead of *that*!")

Yes. But, nowadays, even an integer multiply is reasonably commonplace/"cheap". OTOH, forcing everything to be double can eat your lunch in a heartbeat! :<

But, on an 8 bit processor, the developer could have opted to use a different data type -- short int, etc. (as it is now rewritten, the developer could even use a nonlinear encoding driven through yet another table, etc.)

Unfortunately, you can't protect against incompetence. But, if you make the hurdles along the "wrong" path HIGHER than those along the RIGHT path, you can *hope* to coerce folks down that right path! :-/