Programmers,
What is/are your definition(s) of “programming trick”?
Thanks!
Anything I don’t know or haven’t seen before.
Why is this in GQ?
From my own experience, a trick is typically just a method of achieving a certain specific, usually small goal in a better or more efficient manner than is commonly employed.
It can also be used to refer to a method to achieve a certain specific goal that is itself obscure, complicated, or in some cases a bit counter-intuitive, that is difficult to suss out on one’s own.
I think a programming trick is a way of achieving a result using a method that might not be most people’s first choice. For example: say I need to calculate the sin of x many times. The straightforward way would be to call sin(x). But, I might resize that my inputs were all bounded, and fell in a small enough range to create a lookup table and then just do something like sinx = sign_lookup. This would entail a small amount of work at the beginning, but would save an immense amount of time during program execution. I often program 8-bit devices in assembly language, so these tricks are more important than they would be on a big machine.
>Why is this in GQ?
Where else would it be?
It seems like classic IMHO material as it looks like a poll. BTW, please use the standard quoting facility or otherwise indicate who you are replying to.
Mindfield gave a good definition.
I recently ran into a bit of code that eliminated a conditional jump by doing a “bitwise and” with the 2’s complement of the value of bit mask operation. The bit mask operation produces a value of 0 or 1. The two’s complement operator converts that to all bits clear or all bits set. That value can then be used as a mask in an expression.
Here’s an example:
acc = (acc >> 1) ^ (-(acc & 1) & POLY);
Instead of:
if (acc & 1)
acc = (acc >> 1) ^ POLY;
else
acc >>= 1;
The code implements a linear feedback shift register (LFSR), commonly used to generate random numbers. Getting rid of a conditional branch may seem like a trivial improvement, but it can make a big difference in the performance of the code on modern processors.
See HAKMEM for lots of examples of programming tricks.
Since this probably won’t stay here long, I’ll give it a IMHO answer.
I think a programming trick is really just a subjective idea. I’ll give an example of a “trick” that I learned as a beginner.
Doing a for loop in c++, for example, you are supposed to initialize a variable to be used as a counter. But I didn’t know I could initialize the variable in the parenthesis itself.
for (int i = 0; i < 100; i++)
So for me, that was a “trick.” And as I learn more, the “tricks” I learn are really just more in-depth ways to use the language. You can be competent in a language without knowing every minute detail. When you understand the subtleties of the language (and compiler) and know more how it operates, you will deviate from the standard protocol when it provides a benefit of some kind or another. This can usually appear unorthodox, but if you know what you’re doing there’s a method to the madness.
One of my favorite tricks in high-level languages is the use of dispatch tables to avoid gigantic conditional structures.
Ugly way:
if ( $action eq 'foo' ) {
foo();
} elsif ( $action eq 'bar' ) {
bar();
} elsif ( $action eq 'baz' ) {
baz();
} # .... etc
Prettier way:
my %dispatch = ( foo => \&foo, bar => \&bar, baz => \&baz );
$dispatch{$action}->();
Though I’ve never used it, my favorite trick in C is Duff’s Device.
To me a programing trick is using a command or set of instructions to achieve a goal that it wasn’t intended for.
As an analogy, let’s say you invented asprin specifically to cure a headache. BUT THEN you found it also cure’s blood clots. To me that would be a trick.
So if you had a command to count and it also could be used to do something else that would be a programming trick.
A hack on the other hand is a command used to get around a limitation. For instance, in IE6 the borders on a CSS box are measured differently than in Firefox. So you have to use a hack or set of instructions to get the CSS box to look the same in both browsers. A hack is additional commands to achieve one goal. A trick is using ONE thing to achieve two goals
What’s a “trick” for one programmer can be standard fare for another, depending on the cleverness of the programmer. So the answer to what’s a trick will just be one’s opinion vs. fact. I consider a piece of code as a trick if it’s a way of achieving an end result in an elegant way. I guess I can say the same thing about a mathematical proof. Now don’t ask me what I mean by “elegant”. I know it when I see it.
Duff’s device is what comes to mind. Also John Carmack’s sqrt function implementation and stuff like type-level programming in Haskell, C++, etc. where people solve Rubik’s cubes entirely at compile time.
My favorite is to find the higher or lower of two unknown values without resorting to any IF statement.
max (x,y) = ( x + y + abs(x-y) ) / 2
min (x,y) = ( x + y - abs(x-y) ) / 2
(Here’s how it works: First find the average of the two numbers. Then find the absolute value of their difference. If you want the bigger one, take the average and add half of the difference. If you want the smaller, take the average and subtract half of the difference. It works even if one or the other (or both) is negative.)
I thought of another fun trick. Here is how to swap two variables without using a temporary variable in the middle (for languages that don’t allow parallel assignment.)
int x = 42;
int y = 99;
x ^= y;
y = x ^ y;
x ^= y;
The XOR-swap trick can also be used to implement a bidirectional linked list with only one pointer per node (containing the XORed values of the next and previous addresses; you have to know the address of where you’re coming from to get the next one.)
Both of these tricks are ways to save memory at the expense of clarity and easy debuggability. It’s pretty hard to justify using them these days.
>To me a programing trick is using a command or set of instructions to achieve a goal that it wasn’t intended for.
Markxxx, this definition of a trick is very intriguing. I am interested in particular in situations where a goal is met with less code or time or resources, which is good, but by doing something others may have trouble understanding, which is bad - and most particularly in those situations where as you say a thing is used for other than its intended purpose. There is a compromise here, and I wondered if usage of the phrase “programming trick” would include just such compromise situations as these. I think your post is evidence it would.
friedo, your post describes the trick I find most inspiring. Whether its utility outweighs its traceability is debatable as you point out. But, it’s still an excellent trick, especially because it relies on something deeply important inside the operations, and isn’t just a play on linguistics.
You may also be interested in Superoptimization, which is an automated way of finding code sequences that accomplish a specified task at minimum cost. The results are often surprising.
To my mind, a programming trick is any way of getting something done that’s very language-specific. Abusing C++ templates to do calculations or optimizations at compile time qualifies, because translating your code into straight C is going to be difficult.
Missed the edit window: when you’re thinking about translations, you need to consider similar languages. Translating between C and Prolog is always difficult, but that doesn’t make either language’s hello world a trick.
Could you direct me to an example solution? I am interested in how this would work.
A good example fitting this description is the inverse square root function of 32-bit floats that’s used in Quake III. See also this analysis of the function by one Chris Lomont. (Warning: 2nd document is PDF.)