Reasonably Logical

Programming language designers and users spend a lot of time talking about casts. The core idea of a cast is to convert between two types - either statically, or dynamically. Reading through a number of sources recently, I’ve been noticing that the term “cast” is massively overloaded. This blog post is an attempt to break down the various uses I’ve seen into their component parts.

Before jumping into the discussion of type casts, conversions, and coercions, let me remind you that every value has at least two types associated with it. The dynamic type is the actual type of the value at execution time. The static type(s) is(are) an approximation of that type available at compile time. Generally, the static type of a value must be accurate, but need not be precise. (i.e. It’s perfect legal and common to refer to a value by a base-type pointer.)

A type conversion is a programmatic way to convert a value from one type to another. Depending on the language involved, this may involving copying the contents, or applying arbitrary user defined conversion logic. The core part though is that the value is changing, not merely the type associated with that value.

A type cast is the replacement of one static type with another without changing the actual value. Generally, the type cast to is assumed to be accurate (if potentially less precise) representation of the actual type of the value. A type cast may be checked or unchecked depending on the semantics of the language. For checked casts, if a type cast fails the program executes defined error behavior such as aborting, or throwing an exception. For unchecked casts, if the type cast fails the program is left in an undefined state and no further guarantees are given.

A type coercion is the forceful reinterpretation of memory as a value of another type. Arguable, such coercions are also unchecked type casts, but the semantics are slightly different. A type coercion relies on the structure of the two types and not on their nominal relationship. To put it another way, a type coercion is expected to violate the type system. Some languages do provide minimal checking for type coercion, but generally, this is a use at your own (extreme) risk feature. If a value is converted to an incompatible type - whatever that might mean - behavior is generally ill-defined.

Each of the above can be either explicit or implicit. Explicit (casts, conversions, coercions) require explicit annotation from the programmer. They do not happen silently, and must appear directly in code. Implicit (casts, conversions, coercions) are inserted by the compiler based on the language semantics. C and C++ implicit numeric conversion are a well known example of the later. As a matter of personal opinion, I think implicit (cast, conversions, coercions) are a horrible mistake in any language design.

To put all of this terminology in the context of a language you may know, let’s consider the “casts” available in C++. C-style casts in C++ are generally type coercions, though they may act like type conversions if a cast operator is available. static_cast is a mixture of type casting and conversion; it will only convert between types which are known statically to be compatible or convertible via a user-defined cast operator. dynamic_cast is a checked type cast. It’s semantics are well defined if the dynamic type of the value doesn’t match the cast. const_cast is a restricted form of type coercion which only applies to type qualifiers (const, volatile). reinterpret_cast is a full power unchecked type coercion.

If you’re interested in type systems, you may find my earlier blog post interesting.

For my programming language theory and design course, I’ve recently been writing up a series of formal proofs in LaTeX for operational and denotational language semantics. (Axiomatic semantics are up next.) I can’t claim to particularly like LaTeX as a tool, but it seems to be significantly better than anything else out there.

I couldn’t find a ready made Latex package, so I figured I’d share my solution. It’s a combination of a few custom macros and a general proof style file.

First, the macros:
\newcommand{\denote}[1]{\text{$[\![ $#1$ ]\!]$}}
\newcommand{\opsem}[3]{\text{$<$#1,#2$>\Downarrow$#3}}

The first one wraps its single argument in the denotation symbols. The second takes three arguments and generates the full ||state expression.

(In case you haven’t noticed, I’m approximating symbols for this post that show up much better in LaTeX!)

For the formal judgments, I used the “bussproofs” package. (\usepackage{bussproofs}) Once you get your head around it’s post-order handling of arguments, it seems to work pretty well. One thing to note is that the error handling recovery for this package is awful. If you have the slightest mistake, it silently omits elements from the proof. Make sure you hand check your results!

Update (Feb 24, 2012): Here’s the macros I created for Hoare triples and axiomatic semantics:
\newcommand{\hoarepred}[1]{\text{ $\{$#1$\}$ }}
\newcommand{\hoarerule}[3]{\text{\hoarepred{#1}#2\hoarepred{#3}}}

If you’re looking for various extra symbols used in formal proofs, you might find this page useful.

One of the lesser documented facts about the OpenCL global memory atomics on AMD platforms, is they force all memory accesses in the entire program onto the complete (i.e, slow) path. Having even a single atomic in your program has this effect.

In our program - which we’re developing for a research project I hope to discuss here by March - , we saw a 50% plus performance gain by removing atomic memory ops. (We were using them to coordinate between workgroups.)

This fact is mentioned in the AMD OpenCL Programming Guide[1], but is not featured prominently. There’s some mention there of being able to mark different memory regions as independent UAVs (which supposedly avoids this), but I haven’t found information on how to do that just yet.

There’s an interesting paper[2] which includes some fairly decent benchmarking of various cases. They also provide a software implementation of atomics for memory bound programs. (Note: Do NOT use this blindly. Read the discussion about when this is a good idea and not.) I found the paper to bit a bit weak overall, but it does provide useful information if you’ve run into this particular problem.

There’s also an OpenCL extension[3] from AMD for coordinating workgroups on a single device which apparently doesn’t have this problem. It can’t be used for coordinating across devices, but within one device, it may solve the problem. There’s a few catches though; the most obvious one is that - according to the documentation - you can’t directly read the counter.

References:

1. AMD. Amd accelerated parallel processing (app) sdk opencl programming
   guide. http://developer.amd.com/sdks/AMDAPPSDK/
   assets/AMD_Accelerated_Parallel_Processing_OpenCL_
   Programming_Guide.pdf
2. Elteir, M.; Heshan Lin; Wu-Chun Feng Performance Characterization and Optimization of Atomic Operations on AMD GPUs, 2011 IEEE International Conference on Cluster Computing (CLUSTER). http://synergy.cs.vt.edu/pubs/papers/elteir-ieeecluster11-atomic-operations.pdf
3. cl_ext_atomic_counters_32. http://www.khronos.org/registry/cl/extensions/ext/cl_ext_atomic_counters_32.txt

When you find a bug, fixing it is not enough. You should take a moment or two to think about how the bug was able to occur. Frequently, a single bug report (particularly in more complex systems) hints at a number of underlying issues.

I generally try to find at least three independent fixes to ensure that a given bug couldn’t occur again. You could think of this as defense in depth or defensive programming, but my original inspiration to apply this came from the 5-whys principle. In my case, I use 3, but the exact number isn’t the important part.

Good questions to reflect on:
1) Was there an earlier point in code where we could have noticed something was going wrong? Can I improve the error reporting anywhere along the call trace?
2) Can I refactor the interface or code to make this class of mistakes less likely? Can I better document what the interface is?
3) Is there another way I could hit this same error case? If so, can I quickly (with low risk) fix that one too?
4) What test could I write which would find this error? (Is it worth the time?)
5) Are there simple code changes which would have made debugging this much faster?

The purpose of a comment in source code is to document why you are doing something or to provide a quick summary of a non-obvious algorithm. It is not to describe what you are doing. Generally, a skilled programmer - i.e. hopefully your peers - can figure out what you’re doing from code just fine. The often confusing part is why. (i.e. “Is this intentional or a bug? If it’s intentional, why is it needed?”.

Good example comments:
“An implementation of merge sort. See http://en.wikipedia.org/wiki/Merge_sort for an overview.”

“There are two obvious implementations here:
a) describe
b) describe
Benchmarking (using the test cases in tests/mybench/*.cxx) shows that using option 1 faster by ~15%. ”

Bad example comments:

“This is broken. (with no explanation or testcase)”
(some complicated bit of code here)

“Sorting an array”
std::sort(vec.begin(), vec.end());

“(none)”
(massive block of hard to read code here)

“(none)”
(edge case or tricky non-obvious behavior)

If you find yourself writing lots of comments (or none), you’re probably “doing it wrong”. Go read up on self-documenting code and start practicing. Remember that self documenting code isn’t writing code without comments; it’s writing code where the comments are executable code themselves.

Please note: Nothing above should be read to discourage the use of function documentation. That’s a separate topic which I may mention later.

I’ve spent the first part of today watching some of the videos from the LLVM Dev Meeting that occurred back in November. (I really wish I’d been able to attend!) The first talk I watched was the Extending Clang talk by Doug Gregor with Apple. If you’re thinking about playing around with Clang, I strongly suggest you watch this video. I’ve spent the last few months hacking on clang for a language extension I’m working on and this was by far the best introduction I’ve seen. I really wish I’d come across this before I spent hours learning it myself.

Other useful links:

• Clang Internals Manual (a great reference for folks looking to extend clang)
• How to add custom attributes (from the above)
• The LLVM Project Blog - which is a good way to track major project starts/
• LLVM Reference Manual - Authoritative documentation on the LLVM language
• Some useful docs on the Link Time Optimization project (LTO)

Over the last few months, I’ve had an opportunity to spend some time playing with OpenCL. In short, we’re trying to use a GPU to accelerate garbage collection for Java. (Once the work is published, I’ll post more here.) We’ve implemented a simple graph traversal algorithm on an AMD chip using OpenCL. This article doesn’t talk about that effort directly, but instead focuses on a few of the lessons we learned the hard way while getting up to speed on OpenCL. (So I remember them for next time!)

This has been a group effort, but the content, opinions, and mistakes herein are all my own.

Stability & Dev Environment

The first and most important lesson we learned was that each developer needs a dedicated test machine which is not their primary development box. This box needs to be local. When debugging OpenCL programs on real hardware, it is shockingly easy to lock up the entire box. On multiple occasions, we had to perform hard power cycles on our test machine to get it into a usable state.

Even when the box didn’t lock up entirely, a crashed program with a OpenCL kernel outstanding has a bad tendency to prevent future kernels from being executed. Supposedly, there should be a time out that will terminate a run away program, but we never saw this happen in practice. Instead, we ended up rebooting the box quite frequently.

In a related vein, we quickly started replacing every while-loop with a for-loop (over a large, but fixed number of iterations). This allows you to (sometimes) recover from what would otherwise have been an infinitely loop without rebooting the box.

Another important note is that the documentation available from Khronos is a best incomplete and in a couple cases potentially wrong. Many of the function descriptions don’t provide relevant details about usage and none of them provide useful examples. (Can can get some of the latter from the AMD and NVIDIA SDKs.) I strongly suggest searching Google for examples before taking the documentation at its word.

OpenCL does not appear to support a mechanism to forceably abort a kernel. Nor does it support an assertion mechanism. Nor does it have any form of debug logging (i.e. printf or the like.) The only way to exit a kernel function is to return from the main kernel function with all threads. Unfortunately, this means that error reporting - even for cases where you can easily tell what happened - is extremely hard. I don’t have a great solution. We ended up writing data into global memory - so the CPU could access it after termination - and then trying to exit cleanly. This worked sometimes, but was error prone to say the least.

I haven’t played with the various debuggers and emulators available, but I suspect that would help greatly in debugging.

Synchronization

OpenCL has different synchronization models for threads within a workgroup vs across workgroups on the same device. As far as I can tell, there is no synchronization available between kernels running on different devices on the same machine. (You can use the CPU to coordinate starting and stopping kernels of course.)

Barriers apply only to threads within a single workgroup. The CLK_LOCAL/GLOBAL_MEM_FENCE parameters enforce memory consistency within a single workgroup, not across workgroups. Note that you can have a barrier - where all threads stop - but not have a consistent view of memory if you don’t pass the appropriate flags.

ALL threads within a workgroup must encounter the same barrier. If even a single thread does not, the program will hang indefinitely. (And require a hard reboot of the machine.) This is unpleasant to debug to say the least.

Atomic operations are the only way to synchronize between workgroups. To avoid memory contention (and thus serialization of requests), you probably want only a single thread per workgroup to execute the atomic operation. Doing this requires an additional synchronization (using a barrier within the workgroup and a temporary local memory value) to get all threads within a workgroup consistent.

Be careful about which versions of the atomic functions you use. OpenCL provides 32 bit vs 64 bit and local vs shared memory versions. The ones we used - which unfortunately are extensions not part of the language, but thankfully seem pretty common - were cl_khr_int64_base_atomics and cl_khr_int64_extended_atomics. I’ve read some reports that the atomic_op functions don’t function the same as the atom_op versions. I can’t find confirmation of this in the documentation, but we used the atom_op versions just in case. Another gotcha is that some cards apparently don’t support the local versions. Check your documentation carefully since by some reports the functions will simply fail silently.

Note that it is unclear whether the atomic operations on global memory are visible by the CPU, different GPUs, or merely different workgroups on the same device. I haven’t spent much time digging through the documentation, but if this matters to you, check! The one thing that is clear from the documentation is that atomic operations executed by different GPUs on a shared address are not guaranteed to be atomic!

Infrastructure

To get good performance - even just to minimize testing time - you should probably be using precompiled files. (Note: These are not binary files and can not be moved between machines. They are purely a caching mechanism.) You’ll need a mechanism - hash, command line parameter, build system, etc.. - to make sure your cached files stay in sync with your source code of course.

Having a separate program which sanity checks your files - i.e. part of your build system - will save you time in the long run. If I get time, I’ll clean the hacky mess I’ve been using and post it here.

Generally, the best way to get data from the CPU to the GPU (at least on our setup) is to use CL_MEM_USE_HOST_PTR. There seems to be a lot of confusion on exactly what this does, the top Google results appear inaccurate, and the documentation isn’t super clear, but some micro benchmarks gave much better results than for either of the other two options. (As always, you can not assume that the CPU and GPU have consistent views of this data or that it’ll be mapped to the same address on both platforms. All synchronization with the GPU kernels has to be explicit.) It’s also unclear to me if OpenCL is required to copy the data back into the host memory after termination or that region can be entirely stale. That wasn’t important for our case, so I never tested it. The documentation is unclear. The best discussion I’ve seen is here, but even that’s somewhat unclear on the finer points.

Depending on what you’re doing, you may find some of the various utility libraries useful - COPRTHR: STDCL, SOCL, or oclUtils from the NIVIDIA SDK. The only one of these I’ve used is the oclUitls files which were moderately useful.

Conclusion

I hope this was useful to you. If you have corrections, or suggestions, please feel free to contact me.

I’d been planning to write a post for a while now on what I consider core principals of programming, but instead I found someone who said most of what I would. Rather than repeat what’s already been said, I’ll just recommend you go read Christopher Diggins list.

http://www.artima.com/weblogs/viewpost.jsp?thread=331531

The one’s I personally rate most important are: Write Code for the Maintainer, and Embrace Change. I see quite a few others on his list as being subitems of the first. For example, KISS, Avoid Premature Optimization, Don’t make me think, Principle of least astonishment, Single Responsibility Principle, and Hide Implementation Details are all about making sure the reader of the code can scan quickly and not get bogged down. This is extremely important if any large code base is going to be maintained over the long haul.

The purpose of this post is to briefly summarize a few important terms that I’ve seen thrown around for type systems and try to clarify what they mean. Usually, I’d go to Wikipedia for such a thing, but the article on type systems is ill organized and hard to understand. I’ve spent the last few weeks reading papers on type systems, and I still don’t understand it!

I’ve chosen to organize this in terms of several orthogonal axises of typing systems. This organization is mostly my own, but I’m freely stealing the best ideas from the papers I’ve read as well.

Typed vs Untyped - Typing is an organization of data which classifies fields or records into distinct groups. These groups can be either predefined or user defined. A language is typed if there exists a feature which helps to express such typing or if such a distinction is implicit in the language specification. Note that a language does not need to check or enforce this semantic organization in any way to be typed.

By this definition, even something like assembly language is typed for some aspects. On most ISAs, there are distinct instructions for operating on floating point numbers and integers. On the other hand, not all ISAs define separate instructions for operating on signed vs unsigned integers. This highlights the important point that a language can be typed with respect to some attribute and not typed with respect to another.

Strong vs Weak - The strength of the typing is essentially just how easy it is to get around. A strongly typed language has a type system which can not be avoided. A weakly typed system is one that is more of a suggestion than an enforced rule. Note that the strength of the typing system says nothing about when the enforcement may happen. (We’ll get to that in a second.)

In practice, every language I know of is somewhere in the middle. A language may be closer to strongly typed or more weakly typed, but it’s a matter of degree. As with typing itself, a language can also be more strongly (or weakly) typed with respect to a particular attribute.

Static vs Dynamic - Expresses when the type is checked. A statically checked language is checked at compile time. A dynamically checked language is checked at execution time. There’s been much debate as to which is preferable over the years, but the basic arguments come down to safety & performance (static) vs ease of use & expressiveness (dynamic).

The term hybrid typing is an acknowledgment that most practical languages are both statically and dynamically typed. While the terminology has only entered the academic literature in the last few years, it’s been around in practice for much longer.

Gradual typing is another recent invention that explicitly merges static and dynamic typing. The basic idea is that a program can be written in a dynamic style and moved to a fully statically checked version incrementally. In terms of real languages, the best example I’ve seen is Cython. Cython focuses on incremental performance, but incremental safety and changeability are also reasons to consider gradually typed systems. Expect a full article on gradual typing in the not too distant future; I’ve been quite engrossed with the idea.

Nominal vs Structural - Another important distinction between typing systems is how they define equivalence. A nominal system defines it by the name of a type. A structural system defines it by the actual interface and field layout of the respective types.

As a side note, the same language may define equivalence differently for varying stages of validation and/or execution. One common optimization performed in nominally typed languages is to combine the implementations of structurally equivalent types during code generation. Some languages also expose this distinction in their syntax.

A duck type system is an odd extension of a structural type system which only considers the structural equivalence at point of use. In particular, two different paths through the same function may have different required interfaces (and thus types.) You could also think of duck typing as a extreme form of dependent typing which includes conditions with runtime values.

A related classification is the rules the system defines for when substituting one type for another is legal. In short, a strictly classic type system allows no substitution, a subtype type system allows substitution along lines of inheritance, and a dependent type system allows substitution if the dependent conditions are met. Given that this is a highly complex topic which I’m not sure I fully understand yet, I plan a future post to discuss this separately. For now, don’t worry to much if this paragraph didn’t make a lot of sense.

I also plan on drilling into type conversion in detail. It has important implications both with regards to practical usability of any type system and their theoretical design.

Update (Feb 28, 2012) - A follow up post on type conversions, casts, and conversions has been posted. It doesn’t address more complicated type systems, but does cover the basics.

This is a topic I’m going to be expanding on in future posts, but for now let’s cover the basics.

Assertions are your single best tool for software reliability. Why? Unlike tests, you can write assertions which check any property of your system as it runs. Tests can only check the results of a given execution.

Assertions serve several purposes:

1. Checking your assumptions - If you write new code that does something you don’t expect, you’ll find out on first execution that violates your assumptions. Ideally, you’ll be running your code in the debugger at the point this happens and can immediate inspect the entire state around the failure.
2. Enforceable documentation of intent and expectations. If you’re working with a team of folks and someone uses a library in a way you didn’t expect, asserts will tell them this immediately. You should still document why your asserts are there mind you.
3. Fault isolation. If you’ve written good assertions, your error statement will be something like “global state does not comply with expectations” right after your update function. This is much easier to debug than noticing a corrupt output thousands of operations later.
4. Preventing corruption. If you’re using an assertion package which calls abort or triggers an exceptions, you don’t need to worry about the line following the assertion running if the assertion has been violated. This simplifies error handling immensely.
5. Performance. Depending on your compiler, it may be able to take advantage of your assertions to optimize the code that follows. If the compiler “knows” - because you told it - that an loop iteration count must be a multiple of four, it can unroll and generate much more efficient code.

The downsides of assertions - as implemented in C with at least - are that they are extra code which executes at runtime. Some of your assertions will be pruned by the compiler, but most will remain. As such, if you add an assertion in the “wrong” spot - for example inside a tight loop - you can slow your program down quite a bit.

Before you panic, remember a few classic quotes about optimization:

• “More computing sins are committed in the name of efficiency (without necessarily achieving it) than for any other single reason — including blind stupidity.” — W.A. Wulf
• “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%. A good programmer will not be lulled into complacency by such reasoning, he will be wise to look carefully at the critical code; but only after that code has been identified“[5] — Donald Knuth
• “Bottlenecks occur in surprising places, so don’t try to second guess and put in a speed hack until you have proven that’s where the bottleneck is.” — Rob Pike

(Credit: Wikipedia, emphasis mine)

You should write your assertions, and only remove (or restructure) those that your profiler tells you are actually at issue. The tiny amount of performance you might gain by omitting them is not worth hours spent debugging or (more importantly) the lower quality software that would result.

As a side note: There’s plenty of ongoing research out there trying to either prove/disprove assertions and/or prune redundant assertions. Expect your compiler to get substantially better over the next few years about giving compiler time errors on assertion violations and pruning unnecessary assertions before runtime.