Reasonably Logical

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.

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.

This may seem slightly obvious, but it’s worth saying anyways. If you’re looking at code and you notice something you’d like to change or fix, make a note of it. (If you have time to fix it now, great, but you probably don’t.) You don’t need to be super formal about this - in fact I recommend against it -, but make sure you do record it.

Generally, the problem you’re trying to solve involves the following questions:
(New guy on team): What should I be working on?
(Your boss): What do we need to do before the release?
(You): What can I do to kill time during this meeting?

I’m going to discuss my system below, but please don’t get too caught up in it. While you’re welcome to use it if you’d like, the important part is you find a system which works for you. I’ve known developers with radically different systems that worked for them. Any system or habit which allows you to routinely answer the above without much thought is just fine.

My personal practice is to maintain three lists:
1) Any serious bugs or security problems go into whatever bug tracker the project is using. This is only if I can quickly and easily create specific test cases which illustrate an actual problem. If you don’t have a formal bug tracker, a simple TODO file in the root directory will do. The important part is that a) others might fix them while you’re busy and 2) you remember what they are when its time to do a release.
2) Ugly code goes into its own list. It’s main purpose is to shame me into refactoring when the list gets really long.
3) Unconfirmed bugs go into their own list so I can make sure I make time later to either fix them, or move them into list 1. I often do not take the time to investigate them immediate after noticing them because I’m in midst of something else; breaking my concentration and workflow would be disruptive.

A few example “todo” items:
1) Use of sprintf in C/C++ — First, I take a look to see if this is an obvious bug which needs to get added to list 1. If it’s obviously not a bug or vulnerability, it goes in list 2 for later cleanup. Otherwise, it goes into list 3 and I move on.
2) Function with 10,000 lines of code — Obvious candidate for list 2
3) Undocumented pointer manipulation, const_cast(s), or reinterpret_casts(s) - List 3 if it takes more than a second to understand, otherwise list 2.

To get off list 3, an item must have been analyzed to the point that I’m fairly sure it’s not a real issue or have been moved into a real bug report. I generally try to keep list 3 empty. I might leave something on it for a couple of days, but that’s about it. If assuring myself of it’s innocuousness, I try to document or restructure the code to make the correctness obvious.*

* On first view, this might seem altruistic. After all, I’m out to help the next guy through the code. That’s altruistic right? Well, not really. Most of the time, I’m the poor smuck looking at it next time and it’s been long enough I’ve forgotten my conclusion the first time!

I generally don’t worry about list 2 unless I’m really bored, need a simple project to kill a few minutes during a meeting, or get really annoyed by one of it’s items. As such, it tends to be a pretty dang long list for any project I’ve been working on for more than a few days.

A recent email discussion over on the Clang development mailing list reminded me of a point that I consider rather important, but that seems to be missed in many technical discussions. To put it simply, the design of the patches used to submit a feature to the community do not need to (and usually should not) reflect the design and implementation of the feature itself. Or to put it another way, patch design != change design.

In good software engineering practice, the development of a new feature is a largely incremental process. Whether done on a branch or merely within a local directory, the usual process is to pick a small subset of the feature, implement it, then repeat until done. This has the side effect that unless one is careful, the resulting code can be rather messy: duplicated code, workarounds for previous versions, etc… At this point, any good developer (or at least one with a bit of time before this has to be in) goes back and does a bit of refactoring to clean things up.

A naive developer is tempted to present their patches to the community in the same way. This is wrong. Your coworkers don’t care the order in which you developed this in or how many drafts you had. What they care about is a) having the feature, and b) being able to understand and review the parts as they go in. If anything, the ability to understand your changes and be sure they aren’t going to break anything is actually more important than the feature you’ve implemented.

This may seem odd at first, but take a step back and think about it. You’re contributing to a large project with lots of moving parts. You’re adding one (probably relatively small) feature to a code base that already has hundreds if not thousands of features. If in the process of adding this new feature, something else breaks, do you think your user base is going to be happy? Even the ones clamoring for this new feature?

With this in mind, let’s consider what your goals should be for preparing a patch:
1) it should be small, localized, and obviously correct
2) it should add some bit of logic, structure, or functionality which is obviously useful
3) it should reduce the complexity of the change outstanding so that it has a better chance of meeting the first two goals

I wish I could tell you there was some perfect set of rules for doing this, but there really isn’t. This is where experience comes in. It’s a bit of an art to design “the perfect patch set”. If you’re not sure what you’re doing, talk to your peers. Most communities are more than willing to mentor someone who asks for help.

That concludes the core part of my argument. The rest of this is a collection of side notes that don’t directly relate to the core idea.
1) I’ve been saying “community” above, but the same applies to commercial software development. You should think of “pushing your change to mainline” as “publishing” the change to the community of your fellow developers, testers, and users.
2) From what I’ve observed in the open source world, the majority of patches that sit for long periods without attention don’t follow the guidelines I’ve suggested above. The ones that do tend to get pretty prompt attention. If you’ve ever complained about your patches not getting merged, you might want to think about that for a while.
3) Even if you end up submitting a single massive patch - which you really shouldn’t btw - running through the exercise of mentally splitting up the change into multiple smaller patches can still be useful. If you organize your submit commit around these smaller pieces, someone viewing the patch has a better chance at understanding it.
4) My argument is tangential to the use of centralized vs distributed version control system. While DVCS have major advantages, they actually make this problem worse if anything. By encouraging their users to cherry pick their changes, they encourage users to push back to the community in terms of the commits they themselves made.

As part of getting a new system configured today, I had to remind myself how to get commands such as “ls” or “g++” working on a Windows machine. It had been years since I did this the last time, so it took some research. I’m just making a note of it here, so that next time I know where to look.

Download MinGW and the “basic minsys system” (using their mingw-get installer). Once this runs, you’ll have the mysys command line and can run what you need. Next, you can (but don’t have to) modify your PATH variable to add the paths to the MinGW/bin and MySys/bin directories to the _very end of the string_. (You definitely want these being searched last. Otherwise, windows command scripts may start doing really weird things. There are several commands - find, sort, etc.. - which exist in each toolset.) This allows you to use Linux style command verbs in the command prompt (cmd.exe) on Windows.

To my knowledge, this works on Windows XP, and Windows 7. It probably works elsewhere.

Note: The porting work done in MinGW is pretty good, but not perfect. Don’t expect to be able to compile large open source projects without changes on your Windows box. If you want that, Cygwin is the closest you’ll get. That’s better, but far from perfect. Your best bet is probably a VirtualBox VM.

If you’ve read the news today - particularly the gay news - you may have discovered that Amazon has “chosen” to remove all gay & lesbian items from their best seller lists. Now, usually I’d be the first to complain about something like this, but I’m also a programmer. As such, the possibility that it might actually be a bug as Amazon claims isn’t that hard to believe. Writing a new algorithm - which they’ve clearly done - always brings with it the risk of mistakes and bugs. I’m not saying that that is what has happened, but you know? I’m giving them the benefit of the doubt for now.

Now, if they haven’t fixed the issue in a week or two, that’s when I’m going to get upset.