Book Review: Write Great Code Volume 1 (part 2 of 4)

+/- 1.F x 2^(Exp)

That's the modern floating point representation (with a few caveats).  It is stored bitwise as SignExpF.  As this representation uses a variable exponent, the point floats to different positions.  By doing so, the computer can store a much greater range of numbers than integer representations, but with a small loss of precision.  In chemistry, I first learned of "significant digits" and floating point limits the user to 5 - 10 significant decimal digits (which requires roughly 15 - 30 binary digits).  For this post and subsequent posts in this series, I'll be writing a combination of what I knew prior to reading, as well as information from the book's text.

There are four official formats for floating point numbers using 16, 32 (a C float), 64 (a C double), and 128 bits respectively.  Primarily, the different representations devote bits to the fraction, which provides increased precision.  Intel also has a 80-bit representation, which has 64 bits for the fraction thereby enabling existing integer arithmetic support when the exponents are the same.  Furthermore, ordering the bits: sign, exponent, fraction also enables integer comparisons between floats.

Given the precision limitations (even with 128-bit floats), there are some gotchas with arithmetic.  First, equality is hard to define.  Equality tests need to respect the level of error present in the floating points.  For example, equality is finding that two numbers are within this error, as follows.

bool Equal(float a, float b)

{

    bool ret = (a == b); // Don't do this

    ret = (abs(a - b) < error);  // Test like this

    return ret;

}

Another gotcha is preserving precision.  With addition and subtraction, the floats need to be converted to have the same exponent, which can result in loss of precision.  Therefore, the text recommends multiplication and division first.  This seems reasonable, and wasn't something I had heard before.

Book Review: Write Great Code Volume 1 (part 1 of 4)

What is great code?  What characteristics would you describe it having?  These questions come to mind as I am reading the first of a four volume series on writing great code.  The first work is subtitled, "Understanding the Machine."  Before I delve into what I've "learned" by reading this volume, what should one hope to gain?  What understanding of modern machines is required for writing code, especially great code?

First, I'd emphasize that great code is more about maintainability and understanding than efficiency.  Correctness over performance.  And therefore, the text is more about how understanding the machine can clean-up the code, simplify any designs, and ensure correctness.

Second, in the context of the previous post, most programs do not need to "understand" the machine.  Most applications will not be constrained by execution time, and therefore the programmer effort should be directed elsewhere.  Yet programmers reach their own insights into the application / computer interaction and modify accordingly, and usually, myself included, these insights are irrelevant for the application.

Third, there are specific aspects of modern computer architecture / machine design that is still worth knowing.  For example, I find that most programmers have limited understanding of branch prediction, cache usage, NUMA hierarchies, and superscalar processors.  (Based on my reading so far, I would also add floating point to this list).

What else should a programmer know?  What should I be looking for while I read this book?

Is vs Ought in Computer Science

In philosophy, we debate what something is versus what it ought to be.  And often the usage is confounded.  In thinking about functional programming, I recalled this debate.

A functional program declares what ought to occur.  The computer has large leeway in how it will successfully execute this program.  In contrast, an imperative program declares what will occur.  The computer has little leeway in executing this program.

In programming imperatively, we can more clearly reason about the specific execution time / space required, as we can know the fullest details about the program.  Each step and instruction is clear, along with the specific allocation points to comprehend the memory usage.  Yet, this model effectively went away over 20 years ago, with superscalar processors and overall program complexity.

A common fallacy that programmers make is to try to reason about the details of execution time.  Questions are pondered like should an increment be "++" or "+= 1"?  Would it make you feel better to know I can construct cases where one executes faster than the other?  Most programmers who want to reason about their program are not sufficiently equipped to do so.

Lest we discard this benefit of imperative programming entirely, there are other decisions that are still within reason.  For example, the specific layout of the data in a structure can have impact on execution time.  And while it is doable by hand, the response I received from other programmers is "can't the compiler do this for me?"

Fine.  Let's only program with what the application ought to be doing.  The compiler / run-time / operating system all serve to take these statements of ought and make them be.  Still someone must reason about the is of programs, unless we have a processor that directly takes the functional statements.

I shall continue to be skeptical about programming functionally; however, I advocate further support for stating the "ought" of program statements to aid the verification, etc that is so highly lauded.  Imperative programs need to contain more details about what the program ought to be doing, which can be used in interesting ways beyond mere verification of correct execution.  This direction is part of my research, which I look forward to discussing at HotPar 2011 - "Parallel Pattern Detection for Architectural Improvement".  The specifics of which I'll wait to discuss with the proceedings.

Functional vs Imperative Programming

I was recently provided a link to another "programming" blog.  The blog, Existential Type, is written by a professor from my undergrad institution, Carnegie Mellon.  In it, he appears to be chronicling his efforts of teaching functional programming to freshmen computer science students.  I have been deeply engrossed in reading the posts thus far and they have revived knowledge of past debates in language choice, etc.  You may look forward to several future posts delving deeper into this issue.  But today is Saturday and I have more research to do.

A Rare Error

In the course of my research, I encountered the following error and was unable to find any reference to solutions.  However, this error is likely confined to programmers writing their own types using reflection or perhaps a buggy compiler.

PEVerify - "call to .ctor only allowed to initialize this pointer ..."

This error signifies that a constructor (.ctor) should call the constructor for itself or for the type it is extending; however, it is directly calling a different routine.  The following code is a rough sketch of the error condition.

class baseT  // implicitly derives from Object

{

    baseT() { }

}

class derT : baseT

{

    derT()

    {

        Object();  // calling a different constructor than base class

    }

}

For my work, changing the call from Object() to baseT() fixed the error.

Parallel Programming - First Pass

With my time dominated by preparing to take PhD qualifying exams (i.e., quals), I have been even more slack than usual with regards to preparing regular posts.  Nonetheless, let's talk a little on parallel programming.  In one aspect, the parallel paradigm is the future of computer science, even if I remain highly skeptical about what the specifics of this computing will be.  But just because its usage in general computing may be occluded, the specific usefulness of parallel computing is not in doubt.  This post will serve as an overview of several concepts in parallel programming.

First to distinguish between concurrent and parallel execution.  Concurrent execution has the possibility or potential for executing simultaneously.  Parallel execution is when this potential is realized.  Concurrent execution is possible with a single core; however, parallel execution is not.

Synchronization is the main question when writing concurrent code.  Synchronization introduces a specific ordering to what was otherwise independent execution.  There are two common flavors: exclusion and notification.  Exclusion consists of mutexes, spinlocks, and other constructs that guarantee a single instance of concurrent execution performing a specific set of operations.  With notification, concurrent executions establish information with respect to each other, for example every instance has reached a specific point (e.g., barrier).

An ongoing quest with synchronization research is transactional memory (TM).  TM provides the ability to make a set of memory updates atomicly.  Processors provide the ability to make simple updates atomic (see Compiler Intrinsics), yet a series of updates requires the explicit exclusion guarantee provided by spinlocks, etc.  TM brings the exclusion to the memory address itself, rather than the abstract object protected by the spinlock, and allows an arbitrary set of accesses to be encapsulated in the atomic operation.  However, TM is not presently feasible.

Parallel patterns are formed based on the observation that parallel programs and algorithms can be classified into several distinct groups (i.e., patterns).  An assembly line is a parallel operation and fits the "pipelined" pattern.  By the programmer recognizing the pattern, certain common errors can be avoided.  With the pipeline, the programmer recognizes that the data is to be passed through discreet stages.

Well, that's my prelude to what will likely be many more posts on parallel programming.

VC++ Concurrency Runtime

I was not aware of any particular concurrency support in the VC++ environment, so I was delighted when a friend of mine posted about the VC++ Concurrency Runtime and lambda expressions.  Therefore, while the article was about using lambda expressions, I learned about the concurrency support and especially learning of the parallel pattern library.  Lambda expressions intrigue me, not for actually using them but rather I persist in imagining how cool they are.  I shall save lambdas for another post.