Torvalds' Folly

Read this message on the subject of C++ as a programming language from Linus Torvalds.
To give you a little context, this is the git mailing list (or rather, newsgroup) which is the revision control system they chose after all the controversy around BitKeeper (which was proprietary and not at all suitable for the Linux kernel.)
Torvalds and others are developing git from ground up and they have opted to use C as opposed to C++. This message here is Torvalds going medieval on some guy because he suggested that they could start using C++ features to make their software better.
He even mentions STL and Boost as samples of bad C++! This is not the first time I've seen him act like this (not the opinion, but the behavior) which might be expected from someone who has zero time for newbies, but the opinion. Man, is he wrong! He just doesn't understand that a language is just as good as the programmer. He seems not to realize the "zero-overhead" rule of the C++ language: that no feature of the language has any runtime overhead when not used.
Anyway, I knew Torvalds was a bad leader (because of his attitude towards free software (as opposed to merely open-source software)) but I still counted him as a brilliant programmer and engineer. I guess we cannot rule out the "engineer" part, because of the evidence in the form of the kernel, but the "programmer" part has become under a dark cloud in my mind.

C++: Fun With Comments

There's much fun to be had with C++ comments, and a lot of seriously usable tricks there as well. Of course, most of programmers already know all I could tell about the subject, but nonetheless, I think I'll take a shot at bringing all the techniques I think might be useful together, and I might be able to use a few possible tricks that a possible visitor would possibly leave on this post!
The first thing any programmer has to realize about comments is that (as their name suggests)

Comments are not the code that the compiler doesn't see, but the sentences that a human would read.

Write comments (and code in general) for another human (or you yourself) to read. This generally means you should generally avoid too clever constructs that have no other advantage. I say it again: Write code for other humans to read, not the compiler to compile.
You can use special comments and tools like doxygen to generate useful, beautiful, always-up-to-date and comprehensive documentation of your source codes automatically, with little extra work (e.g. with putting a line with three slashes ("///") at the beginning and describing the purpose of a function before its prototype.) These kinds of tools make you appreciate the value of comments!
My first advice is never use "//" or "/*" to comment out a piece of code. Those characters are reserved for "comments", i.e for writing descriptions of your code! Always put another character (or sequence of characters) after them, and use different characters to distinguish the different situations in which you've commented out the code. For example, use "//0" and "/*0" for code that you suspect is incorrect, use "//1" and "/*1" for test code, and so on and so forth. Keep in mind that these are only suggestions. Any system you opt to use, must be documented somewhere. Write 10 lines to describe the meaning and connotation of the 10 different types of comments you use. Don't take this lightly! As time goes by and you write more code, you'll accumulate these rules and split or merge them, but your commenting rules become more comprehensive, more concise and more useful.
Anyway, suppose you want to comment a multi-line piece of code. Always put the comment openning and closing on a line by themselves. No code on those lines! Also, use "//*/" for the closing marker (instead of just "*/".) This way, you can uncomment and recomment that part with only a single character; a '/' that you add to or remove from the beginning of the openning marker. Look at snippets 1 and 2.
There are times that you want to switch between commenting two parts of a single line. In these situations, you can put "/**" before the first part, put "/*/" between the two parts and "/**/" after the second part. Like snippets 3 and 4, you can then switch between the first part being commented out and the second one by adding a single '/' after the comment before the first part. (Also note the parsing/formatting bug of jEdit on line 18!)
You can also do it in the slightly prettier way that snippets 5 and 6 demonstrate (I really think so!) but only if you want to switch between two multi-line segments of code.
Commenting large blocks with "/*" and "*/" has a major problem. The commented blocks don't nest. For this reason, I suggest the cleaner method of using "#if 0", "#else" and "#endif" blocks (snippets 7 and 8, but they lack the coloring.) This way, not only you can nest commented out blocks inside of each other and enable/disable them individually just changing the '0' to '1' (provided the outer blocks are not disabled) but also you can comment the commented-outness(!) of these peices, and you can use preprocessor macros instead of just '0' to be able to switch these segments on and off from elsewhere. The only problem is that many editors and IDEs don't process preprocessor directives and they won't colorify the disabled parts as inactive.
In your "comment" comments, you can use well-recognized keywords like "NOTE", "WARNING", "TODO" and "FIXME" to make their meanings more apparent and to searching for them easier. Just remember to use them neatly and consistently.
If you have more ideas for using comments, I'd be happy to hear about them and to include them here. By the way, anybody has a clean and pretty way of switching (commenting/uncommenting) among three or more segments of code?

   1://{Snippet 1}
   2:/*0
   3:    for (unsigned i = 0; i < v.size(); ++i)
   4:        swap (v[i], v[v.size() - 1 - i]);
   5://*/
   6:
   7://{Snippet 2}
   8://*0
   9:    for (unsigned i = 0; i < v.size(); ++i)
  10:        swap (v[i], v[v.size() - 1 - i]);
  11://*/
  12:
  13://{Snippet 3}
  14:    for (unsigned i = 0; i < /**/ v.size() /*/ v.size() / 2 /**/; ++i)
  15:        swap (v[i], v[v.size() - 1 - i]);
  16:        
  17://{Snippet 4}
  18:    for (unsigned i = 0; i < /** v.size() /*/ v.size() / 2 /**/; ++i)
  19:        swap (v[i], v[v.size() - 1 - i]);
  20:        
  21://{Snippet 5}
  22:/*0
  23:    for (unsigned i = 0; i < v.size(); ++i)
  24:        swap (v[i], v[v.size() - 1 - i]);
  25:/*/
  26:    for (unsigned i = 0; i < v.size() / 2; ++i)
  27:        swap (v[i], v[v.size() - 1 - i]);
  28://*/
  29:        
  30://{Snippet 6}
  31://*0
  32:    for (unsigned i = 0; i < v.size(); ++i)
  33:        swap (v[i], v[v.size() - 1 - i]);
  34:/*/
  35:    for (unsigned i = 0; i < v.size() / 2; ++i)
  36:        swap (v[i], v[v.size() - 1 - i]);
  37://*/
  38:        
  39://{Snippet 7}
  40:#if 0
  41:    for (unsigned i = 0; i < v.size(); ++i)
  42:        swap (v[i], v[v.size() - 1 - i]);
  43:#else
  44:    for (unsigned i = 0; i < v.size() / 2; ++i)
  45:        swap (v[i], v[v.size() - 1 - i]);
  46:#endif
  47:        
  48://{Snippet 8}
  49:#if 1
  50:    for (unsigned i = 0; i < v.size(); ++i)
  51:        swap (v[i], v[v.size() - 1 - i]);
  52:#else
  53:    for (unsigned i = 0; i < v.size() / 2; ++i)
  54:        swap (v[i], v[v.size() - 1 - i]);
  55:#endif

UPDATE:I was wrong about the parsing/formatting bug in jEdit I mentioned above. That's a Doxygen comment and jEdit handles it correctly. Oops!

Precompiled Boost 1.34 for MSVC 8.0

I've compiled Boost for Microsoft Visual C++ 2005 (MSVC 8.0 32bit) and have put the package here: http://yaserzt.com/files/. Several notes:

• In the same directory, you'll find Boost 1.33.1 packages for VC 7.1 and 8.0 as well. These were not built by me, and I'm merely providing them as a single package for convenience.
• The packages are 7z files. I suggest you get 7-Zip if you don't have it already, although other programs (like WinRar) can extract 7z too.
• The ".ymeta" files are part of an experiment of mine. Don't take them seriously. They merely provide unuseful information about their respective files.
• The Boost 1.34 package will be around 1 GiB (that's 1024 MiB) when unpacked!
• All the header files and library files and DLL files are in the package. There's no documentation though.
• All buildable Boost libraries are built. The regex library may not have Unicode support (ICU is really hard to compile on VC 2005) and the Iostreams library may have been built without compression support. The reason that I say "may" is because the bjam command line syntax and switches have changed since the last version and the documentation is sparse.
• Many Boost libraries are "header-only". They use template wizardry to accomplish tasks and won't need link/run time addition of files.
• Enjoy, spread the word, and let me know of any errors.

Boost 1.34 is Near

If you program in C++, and you've been doing so for more than a year, and you do not know about or use the Boost libraries, you're missing the point of C++. Go get it. Please do so! It's not just that boost libraries are very useful as tools, but also the fact that even reading the prefaces to the documentation gives you insight into software design in general and C++ programming in particular. Delving into the source is an eye-opener for any C++ programmer who thinks he/she knows the language.
The parts are so useful that I've been using them (or wishing to be able to use them) in all my projects in the past year. And it's expanding by the week. Also, many of the libraries that are currently part of Boost, have been accepted into the standard library of the next version of C++ language, what people call C++0x (because it will hopefully come out before 2010, but we don't know when.)
From the traffic on the boost developers' mailing list (which is very high volume and highly technical, certainly higher than my level,) it seems that the 1.34 version is near (the current version is 1.33.1) which will contain many new parts, most notably asio. Of course, you can get all the bleeding edge stuff mostly from their respective homes, and definitely from the boost CVS repository (which I do,) but keeping your compiled versions up-to-date where a full rebuild takes 20 minutes on my system, in addition to the chance of slight incompatibilities is a bit more than I'm prepared to take on my plate.
Anyway, go and check it out if you're not already familiar with it. See the amazing stuff these people are doing. Maybe I'll try to write about some of the boost libraries that I'm more familiar with. Maybe!

Must We Multi-thread? (Part 3)

Up to this point, we've talked about how processor clock speeds are not advancing as fast as they used to, we may have yet to hit the physical limits of the current generation of chip-making technology but we're not far from it. Dual-core CPUs are quite the norm now, and quad-core is becoming popular. I'm guessing we're going to see 16 or more threads in an end-user-level system in less than 2 years. That means we have to write concurrent software to be able to exploit this fact, or you'll be swept away by the people who do write scalable programs. On the other hand, the data we need to operate on gets larger by the minute and memory access rates are becoming more and more the bottleneck. This emphasizes the role of cache hierarchies. But as the number of threads goes up, so does the rate of cache misses. This is but one of the problems we face in multi-threading our code.
Also, writing a concurrent program is hard. It's certainly harder that the serial version (most of the time,) both because we are used to (or trained to be used to) thinking or designing serially, and also most of our tools and languages focus on that. I'm not an expert on the theory of complexity, but it seems to me that designing a scalable parallel program (or algorithm) is innately much harder than ordinary program design.
A third source of problems are race conditions, deadlocks, livelocks, priority inversions and a plethora of other pitfalls and hazards. They make analyzing, testing, debugging and making guarantees about a program's behavior much harder.
Another hardship is performance. As it happens, naive ways of achieving concurrency can either lead to a lot of bugs due to lack of proper synchronization, or a performance penalty because of excessive and/or misplaced locking or flawed design. This performance hit (which mainly comes from bad design, but can be the from the overhead of the synchronization primitives) can be so huge that the parallelized version may even be slower than the serial version! Achieving (near) linear performance boost (linear in the number of hardware threads) is no simple task, even in the simplest and best cases (e.g. when data is not shared between the threads.)
Many programmers, faced with the task of parallelizing the design of a program, go the road of task parallelism, which means they divide that tasks a program has to do among the threads. The threads execute different operations on (the same or different) data. Pipelining is a variation of this method. This has several advantages. It's usually simple enough, it usually minimizes (or at least restricts) the data sharing between the threads and it can be fast and it can be generic and applicable to a broad range of situations.
But the approach is not scalable. There are not many situations that you can divide the program into 10 or more meaningful, mostly independent and orthogonal tasks and still keep the benefits of this approach. There's almost no way to divide a program into 1024 tasks!
Another approach is data parallelism and I will cover the meaning in a later post.
One way to evade many of the above problems is to go for a coarser-level of parallelism. That is, divide the program into many programs and not many threads. This can be used (most of the time) whether your design parallelizes tasks or data, but it's not applicable to many high-performance and real-time applications because whilst the design gets simpler and more manageable, the overhead of spawning a new process and interprocess communication can be noticeably higher than the same operations for threads. On some systems (namely Windows,) it's really significant. I will get a little bit more into this in the future.

Must We Multi-thread? (Part 2)

In the past decade, memory access has been the bottleneck in CPU-bound computing. With x86 family capturing the server market after the desktop market, we are stuck with CPUs that have small register banks (very small in fact.) You get 8 general-purpose registers in x86 (or 6 depending on what you count as general-purpose) and 16 on x86-64. Compare this to the 32-128 GPRs you get in RISC machines. Even Itanium has a whopping number of 128 registers! And the number of floating-point registers is shamefully low as well. It's either 8 or 16 (or 24?) depending on the instruction set you use. All this means is that we still need a lot of memory access, and memory buses and chips are not advancing as fast as CPU thread numbers and clock rates are. You may hear 800 or 1066MHz memory bus frequencies, or even 1600 and 2000 (for HyperTransport) but even then, the bandwidth is not enough. For a 128-bit wide, 1066 MHz memory bus (that's an Extreme Edition CPU with Dual-channel RAM!) you get the theoretical maximum throughput of 17GB per second (If you reach half that in best-case real-world scenarios, you're luckier than most anyone else!) If you have a single, plain 3GHz CPU, and only your CPU accesses the memory (which is absolutely not the case,) you'll have 5.7 bytes of memory bandwidth available to each executed instruction. That is, 5.7 bytes for the instruction and any data it might need. When your average instruction length is about 3 to 4 bytes (this is only an uneducated guess; anyone has more dependable data?) (your instructions can be as long as 17 bytes on x86) you can only read/write one word of data from/to memory every other instruction; otherwise your CPU will be stalled. This is a ridiculously low number. But, that's only a very simplified model. There are many other factors that I did not consider, for example: (The factors that will worsen the situation)

• Memories never perform to their theoretical maximums. The real number is a lot lower.
• I completely ignored the effects of memory latency.
• Memories and memory subsystems have many kinds of delays and stalls when accessed randomly (or even sequentially) or for mixed read/write access.
• Other systems in the computer can access memory and block off CPU's access (DMA, video card, ...)
• Your average instruction length can be longer than the number above. A simple instruction with a memory address in it will likely be at least 6 bytes long and access at least 4 bytes of data. That 10 bytes of non-sequential memory access in a typical instruction.
• CPUs (try to) issue more than one instruction per clock cycle.
• Branch prediction (if fails) will mean executing more instructions that is necessary.
• Some others that I don't know about.

(The factors that will help the situation)

• There is caching in the memory subsystem.

That's it! The only fighter against the disaster is the cache. And it's a lot of research goes into caching at all levels. In the above system, we had a single, very typical CPU, with (almost) high-end memory. And even there we ran into severe, severe memory throughput limitations. That's why every programmer needs to be aware of caching and design her algorithms/data structures/programs to be cache-friendly. Let me ask you this: When was the last time you stopped and asked your self, "Self! What pattern of cache-use this function you've just written is going to have? What's the effect of that random-access into a 200K element array in the deepest place of the innermost loop on the CPU cache?" And that's just a single CPU. Throw in another CPU or three, and watch the memory access slow to a crawl because of all the cache misses. Of course, the cores are going to have separate caches with very good caching, and cache-coherency algorithms, so the situation is not that desperate. But it's bad enough. Especially if you work in performance-sensitive areas of programming, like (I hope) I do.

The 2007 ACM-ICPC World Finals

It's finished, with the Warsaw University team, the only team with 8 solved problems, standing(!) at the top. Sharif and Amirkabir teams solved 5 and 4 problems respectively. Good job guys! Here's a more detailed standings at the end of the 4th hour. The problems are all geometric! Not that I could have solved even two, but at least I would have had ideas about them, had I've had attended, that is!

Must We Multi-thread? (Part 1)

Most of my work for the past years have been on multi-threaded applications. That is, most of the applications that I've worked on have been multi-threaded, and sometimes clustered. And I'm no stranger to small-scale concurrent programming (imagine a fourth cousin three times removed!) And I've come to dislike this multi-threading. Not because it's hard (I like this sort of hard,) but rather because it tends to make your code messy, hard to understand, hard to debug, in one word ugly To top it all off, the performance gain is not always even close to what you'd expect. On the other hand, the processor clock-rates are not on the mad rise anymore. All that remains for processor makers in this race is to increase the number of threads/cores/chips. First it was two, four or more CPUs in a system, but the desktop market didn't buy it. Then came SMT (Symmetric Multi-threading?) a.k.a Hyper-Threading, and now dual- and quad-core CPUs. I seem to remember reading somewhere that around 70% of the CPUs sold by Intel in 2006 were multi-core. I'm sure AMD has similar stats on its multi-core sales. What that means for me the programmer is that I can no longer think of multi-threading in terms of "one for IO, one for actual work." When you have a single CPU available, that means the only thing you can parallelize is IO (disk, network, graphics, sound.) (OK, I know that you can do a lot of "actual work" on the GPU too, but let's not complicate things anymore that they need to be.) I have to really think about partitioning my work over 2, 4, 6 (don't!) or even more hardware threads. Fortunately (or unfortunately) ordinary, end-user programs have yet to need to be able to scale up into the hundreds or thousands of CPUs (at least, not at a fine-grained level of parallelism) so we can still retain the same algorithms (mostly) and only restructure the programs. More on this later.

Straight Up Terrain Rendering

There are a multitude of methods for real time rendering of expansive outdoor scenes represented as height maps. Most of these methods are mesh complexity reduction algorithms (ROAM, SOAR, etc.) in many variants. What crossed my mind is that no one just gives the hardware a static regular vertex/index buffer and use a texture to manipulate height in the vertex shader (SM3 of course.) Many methods use the vertex texture methods, but the actual vertexes (verteces?) are generated on the CPU. Why not just dump it all on the hardware and let it do its job? 1-2 million vertexes should not pose any problems for current hardware. Of course, there can be a reason why no one does this. Namely that it doesn't work! I should mock something up and test it, if time permits.

ICPC - Tehran Regionals 2006

(Background: I have been a participant in and/or an interested bystander of almost all programming contests in Iran over the past 5 years. The ICPC Regional is the most important such event in Iran on the course of a year. The latest one (2006) concluded this past Friday.) The problem statements seem quite manageable this year (last year's was good too, only a bit numerous at 10.) I really believe 8 to be the ideal number of problems though (this year had 9,) for three-member teams in a 5-hour contest. Aside from the number, this year's was the first time in the past 6 (7?) years that a team solved all the presented problems during the contest. And unfortunately, it wasn't an Iranian team. (Congratulations to the Singaporean team, by the way!) Anyways, since I was not involved in this year's contest in any way, I feel left out! So I've decided to try and solve as many of the 9 as I can, and I'll post the codes here. I have to do it during my really busy days, and I don't think I can do all in less than a week. In any event, I want to try my hand at them before the judge data come out. I'm trying to measure myself, so I won't read any more of the problems, until I have time to implement each one (I have read the first four, oops!) Actually, two of them are already done. I'll post the codes in individual... posts.

A Breach in the Hull

The Convex Hull code I posted earlier on this blog has a bug. When the points are all have the same X component, the implementation will misbehave. I may post a fix later; I'm off to work now, but I had meant to write and mention this for so long that when I remembered the matter in the shower I didn't postpone the writing in fear of forgetting it once more.

Python 2.5 is Final

Long time since I've written anything useful here (18 bn years, according to some estimates!)
Anyway, Python 2.5-final has been released. Go get it. Also, while you're at it, Firfox 2.0-beta has been out for some time now. Get that as well!

Chat Rooms in KOPCS

I've just uploaded the new KOPCS build 1335, and the most notable feature added is a chatroom. I have used a simple AJAX-based model (that's not a good name, because I don't use XML) which is lightweight, but could have been better. I use JSON for data transport formatting, which is way simpler to work with, especially in JavaScript. The chat room still leaves many features to be desired, but it's functional and usable. The first thing that I'm going to add (in a few weeks!) is a "who's here" list. If anybody is interested in the source code for KOPCS, I can provide it. See ya!

Change in KOPCS Judgment Model

For those people who might be interested, I'm going to write a fully automatic, no-supervision-required online programming contest judge to integrate with KOPCS. We had the first full-scale KOPCS-based contest today (rather, yesterday) and while the supervised judgment script worked well enough, I realized the inherent limitation of supervised judgment. This kind of judgement is not bad, it's just limited. The first step in AJK (working title) is going to be writing a jail or sandbox or whatever for executing user programs in. Since I know no way for writing it portable, I'm gonna focus on Linux. I'm going to write this sandbox in C++, but I may use Python for the rest, or I may just write everything in C++. After that, I'll just have to figure out a way to implement a simple but flexible queueing scheme, to allow for all the different situations that arise in a programming contest (for example, KOPCS in its current form, does not provide a way for changing only the input or output of a problem after it's set.)

IAUM CCC 3

As I have mentioned in passing before, we are holding the third "IAUM CCC" this year. Basically, it's a programming contest for individuals who live in Iran (or understand Farsi in general.) The tournament consists of one online round, and two on-site rounds. For dates and info check out the official site. The official website is at http://www.csc.ir/ccc3/, so be sure to check it out if at all interested. Also, you have to signup on KOPCS (the Kludgy Online Programming Contest System!) which is located here.

IEEE 754

That's the floating point number format standard. What do you know about how floating point numbers are stored? (We are not talking about arithmetic.) My experience with programmers is that many of them don't know anything about these formats. Sure, they know that the real numbers are stored as sign, fraction and exponent triplets, but nothing more. After all, who needs to know how computers actually work these days, right? Well, if you think like that, I'm sorry for you. These line of thought may be practical (I hate that fact,) but it's not at all part of the hacker/geek spirit. Here's a brief description about how floating point numbers are stored, according to IEEE-754. I thought there were 3 formats for floats, but as it turns out, there's four. They are 32, 43, 64 and 80 bits (who've ever heard of a 43-bit float? Honestly?) The most widely used form is the 64-bit, or "double precision" one. This format (and all others) have a single sign bit (the MSB), with "0" for positive and "1" for negative numbers. Then comes an 11-bit exponent field. And after that, a 52-bit fraction part, for a total of 64 bits (it's 8 and 23 bits for the 32-bit single precision format.) As you know, floating point numbers are stored as some for of scientific notation, with base 2. Basically, that means that the value is the result of the multiplication of a M by two to the power of E. But that's not the whole story. First of all, you have to realize that every number you write in binary, has a '1' as it's leftmost bit. Think about it! Without zero-padding on the left, every number must have a non-zero digit at its left, and in radix-2, that means a 1. So we omit that 1 and save one bit. In our scientific notation, the M must be normalized to be greater or equal to 1, and less than 2. Second of all, the E is not the exponent, but the exponent minus 1023. That is, if you want 2 as E, you have to set the exponent to be 1025. This way, you can accommodate negative values as well. You might wonder why the common two's-complement method why not used. Well, I don't know all the reasons, but one of them probably has been the side effect that using this method, and the field layout being what it is (first exponent, then fraction) you can compare normalized floating point values just as integers, using the bit pattern! (not considering the sign bit, of course.) More precisely, the final number is calculated like this:

value = -1sign bit * 2exponent - 1023 * (1 + fraction / 252)

The above is used when 0 < exponent < style="font-style: italic;">normal number. There are also a few special case values that you need to know about as well:

• If exponent is 0 and fraction is 0, the value is ±0.0;
• If exponent is 0 but fraction is nonzero, the value is denormal and equal to ±F/21022+52;
• If exponent is 2047 and fraction is 0, the value is ±∞;
• If exponent is 2047 and fraction is nonzero, the value is ±NaN (Not a Number. There are 252-1 of these!)

Single-precision format is similar to the above, except that -127 is added to the exponent, and other changes to accommodate the smaller size.

Convex Hull

I don't know how do mathematicians define a Convex Hull, but informally, the (planar) convex hull of a set of point on the plain is defined as the smallest convex polygon that includes all the points. If you think about it, the verteces of such polygon will have to be in the given set, and the convex hull will be unique (if we add the restriction that no three consecutive vertecs of the resulting hull can be on the same line. Which is not much of a "restriction", because if they are, we just simply remove the middle point of the three and voila!) So, the problem becomes finding the smallest area, convex polygon one can construct with the vertices from the set that encompasses all the given points. Finding a convex hull is an interesting problem by itself, and quite useful in many other planar geometry and pattern recognition problems. Now, many algorithms exist for finding the convex hull efficiently but not too simple (except the divide and conquer one which I'm not going to go into here.) When it comes to implementing, most people may try the naive O(n2), which is not easy to get right in one go (if you're that kind of person who tries that and gets it right in the first try, leave my weblog immidiately. I can't stand people better than I here!) The other easy-to-comprehend-but-hard-to-implement method is "Graham's Scan", but that needs a special and none-trivial sort. Graham's Scan runs in O(n log n). The method I'm going to discuss here is a O(n log n), and easy to implement algorithm. I first saw it in a Python book, the title of which I can't remember. It starts with a straightforward sorting of the points, based on the X coordinate then the Y coordinate. Then, we'll start from the leftmost point (least X) and work our way to the rightmost point, maintaining two lists of points. One is the botton run of the points between the min- and max-X points, and the other is the top run. Here's C++ code that implements the algorithm:

#define TURN_DIR(p1,p2,p3)  (p1.x * p2.y - p1.y * p2.x + \
                             p2.x * p3.y - p2.y * p3.x + \
                             p3.x * p1.y - p3.y * p1.x)
#define LAST(cntnr)         (cntnr).back()
#define BEFORE_LAST(cntnr)  (cntnr)[(cntnr).size() - 2]

vector<Point> ConvexHull (vector<Point> & pts)
{
    sort (pts.begin(), pts.end());

    vector<Point> lower, upper;
    for (unsigned i = 0; i < pts.size(); ++i)
    {
        while (lower.size() >= 2 &&
         TURN_DIR(BEFORE_LAST(lower), LAST(lower), pts[i]) <= 0
        )
            lower.pop_back ();
        while (upper.size() >= 2 &&
         TURN_DIR(BEFORE_LAST(upper), LAST(upper), pts[i]) >= 0
        )
            upper.pop_back ();

        lower.push_back (pts[i]); upper.push_back (pts[i]);
    }

    lower.insert (lower.end(), upper.rbegin() + 1, upper.rend() - 1);
    return lower;
}

You should be able to make sense of this code without much difficulty, but be warned, I changed my implemented code to put it here, and I have not tested it (my data structures for points and for return values were different, and I removed the comments! >:-) ) So use at your own risk. Now, the challenge is this. Can you make it shorter? (It's possible to use recursion to do so, I think.)

Eureka!

Some time ago, I implemented AES along with SHA-256 as a practice and because it was needed in some other project of mine (namely KOPCS, which I still may decide to unleash on the world!) You may wonder why I didn't use one of the many free, gratis, fast and high-quality implementations out there. Well, that's me! I like to make my own wheels, and since I'm still in the learning phase, I need the practice. Anyway, I implemented the thing and expanded it into a useful package by adding CTR mode and one-shot file and buffer en/decryption. In short, all was well and good. A few weeks back, just before a trip, just out of nowhere it came to me to asses the performance of the library. In the process of this evaluation, I discovered something utterly strange. The library couldn't decipher what it encrypted! And only when doing multiple blocks in one go! Of course, I had tested the thing before, but those tests were done in CounTeR mode and as you know, in counter mode you only use one way of the algorithm, encryption or decryption, not both. Unfortunately, I had to leave on business when I encountered this bug. It almost ate me alive, the "why". Just now, I finally found the bug! It was a stupid pointer (mis)calculation. I had to advance some pointer 128 bits (the block size) while I did it 32 bits instead. The point of this story is never try to get clever in your code. You'll get too clever for your own good one of these days. And, always test your code thoroughly!

People Don't Care About What They Don't Get (ICPC)

I have been involved in programming contests for several years now, as contestant, problem setter, judge or executive (*shudder*.) My point is that nothing has helped my programming and engineering skills as much as this. Now, the most prestigious of all the programming contests is the ACM International Collegiate Programming Contest (ICPC.) Each year, in some 34 regions around the world, thousands of teams from all major universities compete and around 70 of them advance to the world finals. This is a really big deal. One of the ICPC regionals, is held each year for 7 years now in Sharif University of Technology. It is one of 11 sites in Asia. I myself have participated in the last 5 of them, and our team's placements have been 5th, 13th, 6th, 3rd and 4th. It is also interesting to know that in 2003 and 2005 (when we finished 6th and 4th respectively) 3 teams advanced from Tehran site but normally (including in 2004, when we were 3rd) two teams do. Anyway, I said all that to arrive at this. In my opinion, the ICPC World Finals is the single most important team-oriented event that a student in any technology-related field can participate in. It is more important than RoboCup or IEEE design competitions because it's accessible, it's entry barrier is not too high and for those reasons, people actually like to participate in the regionals or similar contests. And now this (in Farsi.) Through all the years that Sharif University has held a regional, Dr. M. Ghodsi has been the site director. I have seen that each year, while the excitement of the students and their participation levels have grown significantly, the support of the university officials (with the exception of a few, including Dr. Ghodsi) has diminished. As a result, each year the quality of the contest (execution-wise, not scientific) has gone downhill. I don't know what it takes to bring these type of events to government officials', industry sector managers' and media's attention. But I hope somebody thinks of something soon!

Dancing Links

I've recently came across Knuth's Algorithm X, and the implementation he calls "Dancing Links" (in the context of a Sudoku solver, but that's a whole other story.) This is a back-tracking method for a wide range of problems (problems reducible to an instance of the Exact Cover problem.) While Knuth's DLX is still not a deterministically polynomial-time algorithm (I just invented a concept! Hurray!) (or is it?) the algorithm is beautiful and very efficient in practice.