Here is an attached .pdf snippet of programming from the out of print C++ Programmer's Notebook (publisher is PRENTICE HALL) : Using a Linked List Queue.

I am trying to understand the line:

if ( ++count > n/2-1) break;

how it works with regards to n. The variable n is incremented in the first do...while loop. If n is found to be odd then there is truncation.

( Most readable with Adobe Reader or other Adobe software. )

Thank you,

Josheir

That code appears to be formatted for fitting in limited vertical space for printing - that is it's deliberately making the code less readable to make it fit on one page. It's also using three xors to swap two variables, instead of using std::swap(), which is much more readable (and probably faster too).

The line of code in question would be easier to read if it was split up into two or three separate statements:

++count;
int operandCount = (n/2) - 1;
if ( count > operandCount )
  break;

I think the reasoning behind the test is that when there's only binary operators available, there will always be a known ratio of operators to operands, and that is testing for it. It's not a very nice way to detect the end of the expression though.

That is:

- With an input of length 3, you must have one operator and two operands.

- Input of length 4 is invalid.

- Input of length 5 will always have two operators.

- etc.

It's also using three xors to swap two variables, instead of using std::swap(), which is much more readable (and probably faster too).

(for pointers and integer types, the performance of three xors would be the same as std::swap on most processors. the three xors method avoids a temporary and may perform marginally better in some cases)

I am trying to understand the line:

if ( ++count > n/2-1) break;

how it works with regards to n. The variable n is incremented in the first do...while loop. If n is found to be odd then there is truncation.

n is the number of expressions entered.
count is the number of times expressions have been "merged" with parenthesis
since this code only appears to group two expressions and one operator per set of parenthesis, and because at least one expression must be an operator, it can have at most ((n / 2) - 1) groupings.

I must say, this is an awkward piece of code, it assumes all operations are associative, and it took me a minute to just understand what it was supposed to be doing, it took me a few more minutes to understand why it was breaking the loop that way. This was in a textbook??? If I encountered a piece of code as awkwardly written as this in a project I was working on, I would probably leave that project.

It's also using three xors to swap two variables, instead of using std::swap(), which is much more readable (and probably faster too).

(for pointers and integer types, the performance of three xors would be the same as std::swap on most processors. the three xors method avoids a temporary and may perform marginally better in some cases)

True.

At least, true back in the 1980s and earlier.

These days, for the past 25 years or so, it is a very false.

Pipelined CPUs began to make it untrue for desktop computers about 1987 or 1989 or so. A CPU pipeline means that when something is the destination of an operation in progress, new processing needs to stop until the result is assigned and retired back. The pattern "A XOR B, B XOR A, A XOR B" worked fine on non-pipelined processors, but is the direct worst case for adding pipeline bubbles since the second must wait for the first to complete and be retired before it can complete decoding of the second, and the third must also wait for the second to complete and be retired before the third can finish decoding. It is the worst case operation for a pipelined processor.

By the time 1995 and out-of-order processing came around, with a then-astonishingly-huge processing pipeline, the xor-swap was a bad enough problem that Intel had to write code for the Pentium Pro (the flagship at the time) to detect the pattern and rewrite it to use the temporary. When AMD followed suit they also detected it and made it a special case.

If you are lucky enough to be on a "big" processor like an x86, if your compiler doesn't recognize it and fix it for you the x86 chipset will likely detect it and replace it with code that is at most no worse than a swap with a temporary. So yes it performs well on these chips, but it does so because the systems know the stupid pattern destroys performance and fixes it by invisibly using a temporary if one is available.

If you are unlucky and are on a "little" processor, maybe a low-powered arm chip or something embedded, if your compiler doesn't recognize it you've just added the worst case for a pipeline stall.

The XOR Swap took advantage of a shortage of registers that made temporaries expensive, the fact that touching memory (even something residing in the precious few bytes of cache) caused a relatively long stall, and the results were available instantly as there was no instruction pipeline. These days CPU registers are more plentiful, on-die memory and cache hits are as fast as the clock, and pipelines are deep. It is the opposite of what made the XOR Swap fast.


Another of those fun little tidbits was the "Duff's Device", basically using a switch statement as a way to reverse-unroll a loop, letting you jump in to the middle and finish out the job at any point. The jump table of a switch statement generates small and fast code ... up until CPU branch prediction tables were introduced and made sufficiently large. The branch misprediction penalty now typically exceeds the benefit the structure saw from the introduction of a jump table. Now a Duff's Device is an optimizing compiler's nightmare. The pattern still functionally works but it has known-slow performance. Optimizing compilers recognize the pattern, but the difficult choice is to either leave it in and destroy performance with mispredictions, or take out the jump table and thrash the cache with a large number of processing options, more data and instructions. Better compilers evaluate both of the bad options and make an educated guess at which is less bad. Several newer languages expressly forbid the Duff's Device pattern, forcing you to have a break at the end of every case segment.




A problem with many of these little performance tidbits (and there are many) is that the reasoning for them is frequently lost. When the reason behind them vanishes due to hardware evolution, their benefits go away or even become a performance penalty as the XOR swap exemplifies. Even though more than two decades have passed since it was useful, people still call up that outdated 'trick'. Many of the now-wrong gems are slow to die, so please double check that they are still valid, and explain the reasoning for the performance benefits when they are still valid.

Thanks for the amazing trivia, frob. I didn't know that the x86 microcode was so sophisticated. If there's one take-away from this, it should be that programmers are wiser to name such oft-used utilities. It makes for easier mental parsing and future maintenance. I'm pretty sure a SWAP macro would have been possible when that text book was written.

Other examples that I sometimes find unnecessarily complicated :

-"shift left when multiplying by two." if one doesn't trust the compiler to make this one optimization then just write a template mult() or even just mult2() function.

- recursion of incomplete concepts such as factorial. Even mathematicians use "if" and "where"

Well, that helps! It's not a complete working program. The book was published in 2002. I found it informative for the most part. The author's idea was to be succint with code that is explained with arrows and text and also has descripion on the left. I just coudn't understand this one program.

It is an educational text book, the publisher is Pearson Education. It is however out of print.

The program in question wasn't all inclusive so to speak. I do find it interesting too.

Thank you everyone,

Josheir

I actually didn't know that Frob. This is one of the things I was told to do when I first started programming, which based on the timeframe you've given was already at least a decade after it was useful.