Showing posts with label programming. Show all posts
Showing posts with label programming. Show all posts

Monday, April 2, 2012

GCC lossy conversion warnings for C and C++

Have you ever been bitten by the bug where you, for example, return a long long from a function, but set the return type of the function to int (by mistake)? I sure have, and off the top of my head, I can remember this bug costing me a failed solution at least twice at TopCoder. Just to make this more concrete, here's a simple example function that has this problem.

int foo() {
  long long x = 1LL<<42;
  return x;
}

This kind of conversion is actually perfectly legal (for example, by section 4.7 of C++11 n3337), and the result is implementation-defined if the target type (here int) is signed and can't represent the value of the source type (here long long). GCC defines the result to be the value modulo 2^n such that it fits into the type, but what they actually mean is that the lower however-many bits are kept and the rest is discarded, which makes sense in two's complement (which is what GCC and the large majority of "conventional" systems use). So if int is 32-bit, and long long is 64-bit, you get the lower 32-bits of the original value. In this specific case, the result would therefore be zero.

Now, you'd really like to be warned about this kind of thing (at least I would :), but you don't get that with neither -Wextra (a.k.a. -W) nor -Wall. It turns out you have to explicitly ask for it using -Wconversion. The argument they make for code that intentionally does these kinds of conversions (without casts) is definitely valid, but I will be adding this flag to my default set for sure, at least for TopCoder :).

Thursday, March 22, 2012

Fun with bugs

I encountered a fairly interesting bug a few days ago. I will not post the minimal code snippet that reproduces the bug, but rather something similar to the actual code that I had the bug in so that you might try to find the bug for fun (preferably just by looking at the code :). Note however, that the bug I'm going to write about is not really a logic error, but more of a "language issue" (I don't want to be too specific yet because a hint will quickly ruin the fun :).

First, a bit of introduction about what the code does, or is supposed to do. I was implementing an interval tree that would efficiently find the maximal value in an interval of keys. When creating an empty tree (with no values yet inserted), you'd want to initialize all the values to some very small value that I'll call -INF. Basically, the intent of initialization is the set up the M vector that represents the intervals that the tree will be storing directly. So here is the initialization code.

class IntervalTree {
  public:
  IntervalTree(int maxval): n(maxval), M(2*maxval+1) {
    init(0, 0, n);
  }

  private:
  int n;
  std::vector M;
  
  int init(int node, int l, int r) {
    while (node >= (int)M.size()) {
      M.push_back(0);
    }
    if (l == r) {
      return (M[node] = -INF);
    } else {
      int mid = l + (r-l)/2;
      return (M[node] = max(init(2*node + 1, l, mid),
                            init(2*node + 2, mid+1, r)));
    }
  }
};

The constructor is pretty minimal. It stores the rightmost interval boundary (the leftmost one is implicitly zero) and tries to initialize the vector that holds the tree nodes. Now, unfortunately, the maximum index of a node in the tree might be bigger than 2n if the tree is not complete, i.e. the number of keys is not a power of two. An example of this case is n=5 when the maximum index of a node is 12 (the node representing the interval [4,4]).

One way to fix this problem would be to use the first larger power of two, but that can potentially waste space. So what I did here was in the recursive init phase add on additional nodes as necessary. The remaining code is fairly straightforward: if the interval contains only one key then initialize that leaf node (here you might use A[l] if you were initializing the tree with an initial array of values); otherwise, recursively initialize the left and the right halved subintervals and assign this node the maximum of those. Again, in this case it would be OK to just assign M[node] to be -1, but if we were using an initial value array, this is pretty much how you do it.

So, where's the bug? :) This code actually has undefined behavior and is fairly likely to fail spectacularly (with a segfault). If you don't want to try to find the bug, then read on for the answer. Before that, here's a hint - the bug is related to std::vector. Can you spot it now? :)

Here's the explanation. The bug is actually in the line that recursively calls init and assigns the max of the two calls to the tree node. As you might have guessed by now, there are two issues in interplay here. First of all, when you push_back to a std::vector, you will get a reallocation if the previous size of the vector equaled the capacity (i.e., all the preallocated memory was exhausted). When that happens, all pointers and references to the elements of the vector are invalidated, for obvious reasons (meaning you must not use them). This is why you should always be wary of taking pointers (or references) to vector elements, i.e. carefully consider if it is logically possible for the vector to grow which might cause it to get reallocated.

However, one might wonder, where are the pointers or references in this code? The answer is, fairly obviously, vector's operator[]. The thing is, the compiler is free to evaluate M[node] before, between or after both init calls are made, i.e. it is free to evaluate the left side of the assignment before the right. Since init uses push back on the same vector it's assigning to, it might happen that the reference returned by operator[] in M[node] gets invalidated and you assign to it, breaking the program.

The manifestation of this bug was actually quite entertaining. I got a segfault for many executions, but sometimes I got a std::bad_alloc (for minute trees of a dozen or so nodes :). Quite spectacularly, it actually caused my AV to flag the executable as a trojan on one run (though that is, I suspect, not really closely related to this particular bug).

It is fairly easy to fix this problem in this case... just use a temporary to store the max of the recursive calls and then assign it to the appropriate location in the vector. Another solution would be to determine how many nodes there will be in the constructor and avoid having to extend the vector. Both of these solutions are either uglier or more complex than this one, but they are correct while this one is not :). However, I think this bug is generally fairly subtle and I wouldn't be surprised if it "leaked out" (in the abstraction sense) of some libraries that use std::vector internally.

Saturday, February 4, 2012

Why Vim is great (Exhibit 2: Vim is scriptable)

One great feature of Vim is that it is scriptable, which allows pretty much infinite customizability. I already blogged about a plugin I wrote for speeding up C++ coding, but there are many other far more useful plugins out there. The point is, if you're a programmer and you want to speed up something you're doing often, you can easily do it yourself if an appropriate plugin doesn't already exist or you can't find it. My example above is obviously covered by some excellent plugins, but they are much more heavyweight than what I wanted to do.

Another example where an existing script (probably) doesn't exist and that I encountered recently was reformatting some context free grammars encoded in LaTeX. I was helping organize all the exam problems from the last several years of our compiler design course into a problem book to give out to students for practice. There were probably more than 50 grammars in these problems, written in several different styles of marking nonterminals, listing rules etc. For example, these were three of the styles we had originally:

S \(\to\) aAbBa | bBaAb
A \(\to\) AaBb | Ba | a
B \(\to\) Ab | b

S \(\to\) A a A b
A \(\to\) A b
A \(\to\) d B
A \(\to\) f
B \(\to\) f

S \(\to\) AB | dC     A \(\to\) aCB | \(\varepsilon\) 
B \(\to\) eS | bC     C \(\to\) c | aB

We obviously wanted to have a uniform style for all these grammars, so I wrote a short script that reads in a grammar in any of the original styles and reformats it. Obviously, you could write a program in any language to do that, but since these grammars were part of a large document, you'd have to delimit them somehow for the external program or copy/paste them around. If you think about it, the problem was an exact fit for an editor because it is part of editing a document. Also, it's not really possible to do this with a macro that doesn't itself contain some code. In any case, writing the script took probably less than 20 minutes; far less than it would have taken me to manually convert all the grammars, not to mention far less error prone.

So how do you write these scripts? Vim has a buit-in scripting language (commonly referred to just as Vimscript) which is a dynamic language that feels sort of like Python, but has somewhat clunky syntax. I'm not going to talk about the language very much here because it's covered well elsewhere, for example in a series of IBM DeveloperWorks articles, and in Vim's help by typing :help script.

The other thing to note is that you can actually script Vim using several other (better) languages, namely Python, Ruby, Perl, Scheme and Tcl. You can find great info on these in Vim's help under python, ruby, perl, mzscheme and tcl, respectively. I've only tried the Python interface myself and found it more enjoyable than using Vimscript. However, there are some unfortunate caveats. First, you'll need Vim compiled with the appropriate flag set to enable each interface (for example +python or +python3). This in itself motivates people to write plugins in Vimscript since it is the only language guaranteed to be supported (I read somewhere that Python was supposedly included in all the binaries after Vim 7.0, but I haven't been able to verify that right now). Furthermore, debugging these external scripts is a lot harder as the error messages you get aren't very helpful.

In any case, scriptability is a great feature that opens up a lot of opportunities for increased productivity, and that's what we're all after :). Happy Vimming!

Monday, February 22, 2010

Top 25 Most Dangerous Programming Errors and what we're doing about them in education

The other day I stumbled upon this list of 25 most dangerous programming errors. The list was supposedly compiled based on data from 20 different organizations. Of course, this doesn't really tell us anything and by no means implies that the list is "correct", but it is somewhat in line with what is commonly talked about in the computer security literature.

The point of this post is not to discuss these errors in detail, but to see what we can do about them in CS college education. The common denominator of most of these errors is assuming user input is safe and friendly, yet this is something that I feel is not talked about during education nearly enough. At the same time, the two last items on the list (broken/risky crypto algorithm and race conditions) are something we devote a lot of time to. Specifically, a large part of the operating systems course talks about avoiding race conditions and we have a specialized course that deals with cryptography. Additionally, there's a post-graduate computer security course that also fails to address any of the errors in the "user input" category, but also focuses on cryptography and authentication. To make matters worse, the "user input" errors are much easier to understand and deal with than these more "advanced" errors.

There are other aspects to this that I won't go into now, but I'm sure that every person with a CS college degree should know about all of these errors so we need to start covering them all in class (it is too important to be left for self-study).

Friday, April 17, 2009

Using vector and deque "the right way"

If you're using the STL, chances are you're using vector and deque a lot. They are two of the three sequences defined in section 21.1.1 of the C++ standard (the third one being list which I won't talk about in this post).

The nice thing about dealing with these sequences is that they manage their memory automatically when you're using push_back and pop_back and you don't really have to think about it. Naturally, I did a search to see if this has been beaten dead, and sure enough, I found a great article about it by Andrew Koenig and Barbara Moo of Accelerated C++: Practical Programming by Example (C++ In-Depth Series) fame (also see Koenig lookup).

Instead of repeating everything that's in there, I'll just recap the main point. The C++ standard (in section 23.2.4.1) guarantees amortized constant time insert and erase at the end for vector. This basically means that you can grow a vector from empty to size O(n) in O(n) time using push_back, although some individual push_back calls might take linear time (the ones that cause reallocation, which consists of allocating a new block of memory, copying the old objects, destroying them and deallocating the old memory block). One subtle thing to note here is that reallocation (which should mostly be transparent and not something you worry about) invalidates pointers and iterators into the sequence.

The vector class offers some facilities that let you take a more active role in this memory management process. These first function is void reserve(size_type n) which makes the vector allocate enough memory for at least n items, effectively making all push_back calls up to n items take constant time. The other function is size_type capacity() const that lets you know the currently allocated memory for the vector.

The standard doesn't define how this is to be implemented, but by reading around and looking and source code, it seems most implementations grow the vector exponentially, with factor between 1.5 and 2 (although there might be others). Fortunately, even if you can't access the source of your implementation, you can easily test it out with a program like this:

#include <cstdio>
#include <vector>

int main() {
std::vector<int> v;

std::vector<int>::size_type old_capacity = v.capacity();
for (int i=0; i<1000; ++i) {
v.push_back(i);
const std::vector<int>::size_type new_capacity = v.capacity();
if (old_capacity != new_capacity) {
std::printf("%4u %4u\n", (unsigned)v.size(), (unsigned)v.capacity());
old_capacity = new_capacity;
}
}
std::puts("growth done");
for (int i=0; i<1000; ++i) {
v.pop_back();
const std::vector<int>::size_type new_capacity = v.capacity();
if (old_capacity != new_capacity) {
std::printf("%4u %4u\n", (unsigned)v.size(), (unsigned)v.capacity());
old_capacity = new_capacity;
}
}
std::puts("shrink done");

return 0;
}


On my machine, this outputs

1 1
2 2
3 4
5 8
9 16
17 32
33 64
65 128
129 256
257 512
513 1024
growth done
shrink done


As you can see, the factor here is obviously two. Two other points are of interest. First, the vector starts out with no allocated memory. Secondly, the memory is not released when the size shrinks. This means that the memory will be allocated until the object is destroyed, unless you explicitly call clear or resize. Also, if you use reserve with some amount just before the loop, you'll basically seed the sequence with something other then one. The point here is that you get a lot of small reallocations at the start, which does seem like a waste.

The standard actually recommends using vector "by default" (section 23.1.1.2). Browsing around Herb Sutter's Guru of the Week I stumbled upon an entry where he recommends using deque as the default. So, for a bit of background, a deque is a sequence that supports constant time insert and erase operations on both the front and the end (via push/pop front/back). It also supports random access iterators and random access via operator[] and at(), but random access is not constant time since a deque is basically a linked list of fixed size memory chunks. This works quite well for memory management as the memory chunks are small and no reallocations are required when the sequence needs to grow. Still, the point Herb is making is kind of defeated by the timing data he includes in the post since vector outperforms deque in pretty much everything (I'd say, as expected). Still, deque is a great sequence and is actually used by both stack and queue by default (for good reason) and is a great structure for implementing 0-1 BFS.

Going back to vector, I'm wondering how people use reserve in "real life". Often, I'll have a pretty good idea of how big a vector will end up after a loop, and using reserve in those cases seems like the right thing to do.

std::vector<int> v;
v.reserve(n);
for (int i=0; i<n; ++i) {
v.push_back(i);
}

Should be better then

std::vector<int> v(n);
for (int i=0; i<n; ++i) {
v[i] = i;
}

because the latter actually initializes n ints to zero in the constructor (and the benefit would increase when the items in the vector are objects with more state and possibly elaborate default constructors).

Now the strange bit. Even though I've been programming in C++ for about five years now and I feel I know it really well and consider it my "main language", I've never used it on a multi-person project. In fact, I've never done a project over a few thousand lines in it, although doing a quick grep on the code I have on my home machine shows about 95k lines of C++ code I wrote. Due to strange circumstance, I've only had a chance to work on smallish sized projects (~5k lines) in C#, JavaScript, Python, PHP and Java, and on a medium (~30k lines) project in Java. So, I'm asking you, C++ developers, what are your experiences with using vector and deque in real projects? Is reserve used and how do you estimate the right size to use? Thanks!

Tuesday, April 7, 2009

Vim C++ macro-like expansion script

Hi again!

Today I'll release a Vim script I wrote a few weeks ago (and have been planing to write for a long time). What it does is enable fast typing of idiomatic things like for loops, STL container declarations etc. The philosophy behind using a script like this is in line with the general philosophy of Vim, which is to make editing as fast as possible (fewest keystrokes to achieve a result). Also, writing idiomatic code is known to be error prone (ever typed ++i in an inner loop instead of ++j?) and is definitely tedious.

Another reason for writing this script are TopCoder competitions. Unlike most algorithm competitions, at TopCoder speed is a big factor. You only have 75 mintes to solve 3 problems (of increasing difficulty) and your submissions are timed from the moment you open the problem statement. Also, there is no partial credit for problems. After the coding phase, there's a short intermission and then a 15 minute challenge phase where other coders get a chance to view your source code and construct legal inputs that will break it (thus getting additional points for themselves and bringing your point total for that problem to 0). Finally, if your code survives the challenge phase, it has to pass all the automated system tests (some of which are "random", and some of which are specifically constructed to trip up wrong approaches). Some people at TopCoder use macros to achieve pretty much the same effect as this script. The main problem I have with this option is that it makes the code look ugly (sort of obfuscated). This makes it unnecesarilly hard for other people to challenge (although that's probably not the main intention) and, more importantly, it's bad style. Of course, using this script (or the macro method) probably won't increase your TopCoder rating; TopCoder algorithm competitions are primarily about quicky inventing (or applying) the correct algorithm, and the implementing it correctly and with reasonable efficiency. Still, being able to type code faster is always a good thing :).

So let me finally give you a short tour of what exaclty the script does (for the full list, see the comment on top of the file). The current functionality can be seperated into two groups: loop/block expansion and containers and type expansions.

Very often, you'll want to loop through an STL container, or repeat something n times. To do this, you'll write something like this:

for (int i=0; i<(int)my_vec.size(); ++i) {
// per-item code goes here
}

Note that in "real" code you might use size_t or, better yet, vector<int>::size_type. Also notice the int cast on the container size. Comparing a signed to an unsigned value is not entirely safe in C++ (The int gets converted to an unsigned (assuming vector<int>::size_type is size_t and size_t is a typedef for unsigned, as is common on PCs) in what is called the usual arithmetic conversions. This can cause problems if the value of the int is negative, in which case, on a 2s complement machine, becomes a positive number and you get the "wrong answer".). Still, in idiomatic code like this, using a cast is an OK option IMO.

Anyway, to write the above loop with this script, you'd write:

@f i #my_vec

and press <F2> (I'll talk about the keyboard mappings in a sec). Vim will then expand the line to the above code (without the // per-item code goes here comment, of course :) and (if you were in insert mode) position the cursor at the "right" place (one indent level inside the block) so you can continue hacking.

If you want to loop to a value (or variable), and not trough a container, you'd write something like this:

@f i n

and get

for (int i=0; i<n; ++i) {

}

You probably guessed it, but the general syntax is:

@f index_var_name upper_limit

Where the upper limit can be preceded by a # to produce the size of a container.

If you want the loop condition to be less than or equal, prefix the upper limit with an equals sign like:

@f index_var_name =upper_limit


There's also a version that lets you specify a non-zero lower limit

@f index_var_name lower_limit upper_limit


and versions for looping downward

@fd index_var_name [lower_limit] upper_limit

(the square brackets indicate that the lower_limit is optional).

Finally, there are similar expressions for while and do-while loops, as well as for if branches:


@w expression
@d expression
@i expression


Finally, there is also support for for loops with iterators through containers. The syntax for this is (I'll explain what <container_expression> and <expanded_container_expression> are in the next paragraph):

@iter iter_name <container_expression> container_name

which generates

for (<expanded_container_expression>::iterator iter_name=container_name.begin(); iter_name!=container_name.end(); ++iter_name) {

}

There's also a @iterc version that generates a ::const_iterator iteration.

The second part of the functionality is container and type expansions. Basically, for:

@vi

(and <F2>) you get:

vector<int>

This works in all parts of the line (except in double quotes and comments), unlike the loop/block expansions that only work on the start of lines (modulo whitespace characters). I won't list all the supported expansions, but all the vector, set, map and pair that I tend to use frequently are supported. A few examples:

@vvi
@sd
@msi
@pllll

expands to:

vector< vector<int> >
set<double>
map<string, int>
pair<long long, long long>

Keyboard mappings are defined at the end of the script (so you can easily change it, if you like).

nmap <F2> :call BudaCppExpand()<Enter>
imap <F2> <Esc>:call BudaCppExpand()<Enter>A


I have some further ideas that I'm going to add in the short term. Since this post has gotten very long, I won't discuss them here except to say that you can read about them in the comment on top of the script :).

One important thing in Vim is making a habit out of things (so you don't have to think about whether or not you're going to press 'i' or 'a' or 'A' etc.). Since this script is pretty new I still haven't really gotten into the habit of using it as much as I'd like, but I'm trying :).

Without further ado, you can get the script here. To use it, you can put it into the ftplugins Vim directory.

If you find the script useful, have any suggestions about improvements and possible further additions or find a bug, please let me know!


Edit:
While writing this post, I noticed that it might be useful (and in line with the style of the script) to be able to expand things after } else to form if/else blocks properly which wasn't possible with the version I posted. I fixed that now so you should be able to do things like


if (a > b) {
// do something
} else @i a+b+c > 42

and get it expanded into

if (a > b) {
// do something
} else if (a+b+c > 42) {

}