Unexpected behavior of std::bitset in visual studio 2008

I was writing code for generating prime numbers up to 10^9 (one billion) by sieve of Erathosthenes. So I created a class containing a member of type std::bitset<1000000000> and created an instance of the sieve class within the main function (i.e., allocated on the stack).

When I ran the program, it crashed with stack overflow. Since VC in debug mode implements stack overflow checking, the stack trace was not very helpful -- the program crashes within the _chkstk function. But in my simple test program, the only possible cause of stack overflow could be the instance of the sieve class which contains the bitset member. After lowering the sive's limit to 1000, the program worked fine. It was kinda surprising to learn that std::bitset, unlike std::vector, internally uses an array instead of dynamically allocated storage. (I confirmed this conjecture also by reading the source code of in the corresponding header file.)

Git's way to the thrashcan

I tried to use git-svn and git for a while, only to get fed up with it today and going back to just using subversion. The thing that pissed me off is that I did git rm on wrong files. With subversion, if you do svn revert before commit, the old copy of the file gets restored (and, of course, removal will not be scheduled for commit).

With git, git checkout should, in theory, do the same. Googling about the problem, I found a tip that I should use git reset. However, neither did that restore the accidentally deleted files. Finaly, I experimented a bit and found out that git reset --hard does the trick. Before experimenting, I did, of course, make a backup of the whole repository to another place.

Now, I'm going back to subversion, which is much more intuitive to use. My work is too valuable to be stored in version control system with which I must experiment to achieve even the simplest of operatons. Yes, I found the --hard option in the documentation, but its explanation was so opaque that I wasn't sure whether it would achieve what I wanted.

Next time I'll be wanting to use a DVCS, I'll use Mercurial, as before.

Win32 threading API anomaly

I like to split my code into a series of simple helper functions. When developing for multithreaded environment, some of these functions have to be called while a certain mutex is held by the current thread. In POSIX, it's easy to test for a weaker condition, namely that the mutex is locked:

assert(pthread_mutex_trylock(&mtx) == EBUSY)

There is no way to check that the current thread holds the mutex. However, if another thread has locked the mutex, one may hope that pthread_mutex_unlock will return EPERM error code (I don't think that the pthread library is obliged to check for every possible error condition).

Take Win32, and the TryEnterCriticalSection function which returns, according to the documentation: "If the critical section is successfully entered or the current thread already owns the critical section, the return value is nonzero. If another thread already owns the critical section, the return value is zero."

Since I actually expect that the current thread already owns the mutex, the "or" clause in the first sentence makes it impossible to implement even the (weaker) sanity check which is possible under POSIX. Kinda shame.

New CSPIM release

I have released v1.0 of my CSPIM MIPS simulator. This release includes some previously outstanding issues, and the simulator can now simulate itself.

Windows Vista and Visual Studio

I've bought a new laptop, got 64-bit Vista business with it, so I said - heck, let's give it a try. After one month of using Vista, I don't miss linux desktop at all. I have power management that works all of the time (and that locks the screen after wakeup, without any special configuration!), Flash that does not crash at least once a day (crash on linux manifested most often in the flash plugin eating 100% of CPU), sound system and mixing which works out of the box (no need for mysterious sound daemons that will enable multiple sound applications running simultaneously), plus availability of software for gadgets (garmin gps, nokia phone). I have even found a nice and free virtual desktop manager (VirtuaWin). One month after using Vista.. I won't be installing linux on the laptop anytime soon :-)

You have probably heard that User Access Control (UAC) is PITA, and there are a bunch of cookbooks on the net instructing on how to disable it. Coming from UNIX background, I find it rather natural that you have to type in admin password before performing system-critical tasks. Suggesting to people that they turn off UAC is rather irresponsible, and I have not done it. I like being warned when some operation requires elevated privileges. Oh, and I have turned off the sidebar - gadgets there are mostly useless and they just increase the startup time (which is, I must say, rather decent).

I have found replacement for all of the tools that I used under linux, except one -- development tools. And now, my comparison standard is not linux, but Solaris, with Sun's native developmet tools, CMake and dbx. (BTW, Solaris dbx just rocks! gdb is a poor match for it.) I have installed Visual Studio 8 Professional (I have free license through MSDNAA), and it has several shortcomings in comparison with Solaris tools.

First, I've heard many windows developers say that VS debugger is one of the best, but I find it rather mediocre compared to dbx. VS debugger does not recognize C++ overloaded iterators (so you can't persuade it to show you *it where it is some C++ iterator class) and it is a pain to display deeply nested data structure (just print -r in dbx). VS has even its own embedded command-line interface, but nothing indicates that these features are available through it. Sure, VS debugger is nice for single-stepping through the code, but this is not the way I usually debug the code. (What usually happens in my debugging session is that some assertion/check triggers a crash, I inspect the core dump, put a breakpoint near the offending place, and quickly print few variable values.) On the upside, the VS debugger understands STL containers and can display them in a nice form. But I'd go for dbx any day, only if it were available for Windows.

Oh yes, changing command-line arguments through IDE for debugged programs is PITA :-) If I run the program from the shell and it crashes, it takes several seconds to drop into the debugger, which is kinda annoying.

Another complaint is that VS does not seem to come with a decent profiler such as gprof on Solaris. Most people recommend to use Intel VTune, which costs money. Sun has recently released (free!) SPOT tool which produces a nice report of hot-spots over several runs of your program, in the form of cross-linked HTML pages and graphs.

Then there's DTrace which is currently unique to Solaris and some BSD variants (OS X, FreeBSD?).

Lastly, project configuration management is easier with CMake. I have not yet figured out how I can persuade VS to inherit project properties from the master "solution" properties. Given that projects have parent projects, I should probably play with a deeper project hierarchy. (But why can't I set master settings in the "solution"?! Bleh.)

IntelliSense is nice, but.. it doesn't work all of the time (I see rather often a message in the status bar that IntelliSense couldn't find a completion.. ). Though, when it does work, it sometimes saves me a lookup of member name.

In conclusion - Vista is a rather nice environment for everyday work and it is very stable. However, Microsoft's C and C++ development tools are no match to Solaris's tools, at least when it comes to lower-level stuff. (Maybe not so surprising, UNIX is traditionally C and C++ oriented environment, while MS is moving towards .NET). I'm definitely somewhat less efficient in development with VS (though not drastically); I don't know (yet) whether this is because I haven't learned all the features, or because Solaris tools simply are superior and have no match in functionality in VS.

New code release: ext2frag

A master student of mine has developed a FUSE filesystem as a part of his master thesis. He needed to compare several fragmentation metrics of his own FS with that of EXT2. However, no decent programs for calculating EXT2 fragmentation statistics are available, so I set out to code one since the student was really short on time. You can get the program here.

MIPS CPU simulator, CMake

Today I've published the first version of a MIPS CPU simulator; you can read more about it here. Even though the version number is 0.9, the program is not in any case beta: it is quite stable, CPU torture tests pass in 32-bit and 64-bit environments, and there seems to be no open security holes, though error "reporting" is sometimes unfriendly: the simulator shall call abort() if the simulated program tries to access memory outside of its allocated range.. but I think that's still way better than doing random stuff to random memory. Work on better error handling is the top priority right now.

I'm also using this opportunity to learn about the CMake build system.

MIPS CPU

Things have been pretty hectic here, so I haven't had much time to post anything. Recently, I've begun a new personal project: writing a simulator for the MIPS I CPU arhcitecture. I chose this particular CPU because it's the simplest architecture for which gcc can generate code. There are many other MIPS CPU simulators out there, but all of them do more than I need, so I decided to write my own as simple as possible. The ELF loader and symbol lookup are finished, and now I'm working on developing test vectors for the simulator (a very boring part).

As for why I'm doing this - the answer will hopefully be clear soon :-)

Java leaks memory

Now, this is something to laugh at: when first launching Java, Sun boasted about garbage collector and that programmers will never again have to cope with memory-management problems. Fast-forward to 2008. to read Sun's presentation on avoiding memory leaks.

Some regexps

I have started to develop some CRM114 scripts to classify Usenet articles. Internally, it uses the TRE regexp engine and I needed a regexp splits article into headers and body; the separation happens at the first empty line. So here's the regexp; it seems to work :)

/((?:(?n:.+):*:_nl:)+):*:_nl:(.+)/

Some peculiarities: the :*:_nl: is CRM114 literal for newline, and the ?n: is a TRE flag to tell it that dot (.) should not match the newline character (by default it does, and this makes TRE different from PCRE regexp). The headers will end up in the 1st matching group, and the article body in the 2nd.

Netbeans

Few days ago I started to write some Java code (I'm using the Choco constraint solver) and tried to use the Netbeans 5.5 IDE (and the version 6 should be out soon). I have to say that I was pleasantly surprised. It is simpler to use than Eclipse, and feels faster. Now I have started to use it for C and C++ development and I'm wondering like... WHY haven't I given it a chance earlier :)

How to raise SW patent hell

Today I got a nice idea on how to show that SW patents are either total crap or an idea that could put every major SW producer in trouble.

So the plan is this: find a good security engineer and a good patent lawyer. Make a patent titled something like "A method for covertly taking control over software". Make sure that the patent text covers buffer overflows. Next step: sue for patent violation every company whose software has at least one unpatched buffer overflow. I'm sure things would get pretty hilarious in the courts.

A critique of C++

The usenet article with message ID 13h30fshbtk53eb@corp.supernews.com (google groups has not yet picked it up, so I can't provide a direct link) analyzes in detail what is wrong with the current C++ language. Interesting read.

News and 3-d logic solver

I have set up a news feed so that you can track changes on my web site. Today's news: solver for the 3-D logic game.

DTrace and C++

Solaris DTrace isn't that C++ friendly. The SDT provider doesn't work with C++ programs. But I have fortunately managed to find a workaround. Not pretty, but it works.

More python brokenness: distutils

So I tried to compile Mercurial on Solaris with Sun's native compiler. I set CC and CFLAGS environment variables, but, as documented in distutils manual, the CFLAGS set in the environment are added to some predefined set of flags. This set of flags was adjusted to gcc, and Sun's compiler broke (no wonder) on some of gcc's options. It seems that compiler options are hardcoded in distutils at some obscure place. "Great" work!

After ca. 30 mins of fiddling around and searching on google, I recompiled the module using gcc.

Concurrent shared memory allocator

I have recently adapted Solaris's libmtmalloc(3) to satisfy allocation requests from shared memory segments; it works both with POSIX and SYSV shared memory. You can get the code here. I knew about a similar project, but I have no idea how well does it scale with increasing number of concurrent processes.

Prex, DTrace and linux lameness

Adam Leventhal has in his blog exposed the lameness of the SystemTap team (e.g. they claim that they weren't inspired by DTrace at all, but output format of some of their utilities is identical to that of DTrace). He also took an amusing photo showing that users are not very happy with SystemTap.

But I want to point to another very useful tool that got completely shadowed by DTrace: TNF tracing. In short, it is "printf() debugging" on steroids; read the tracing(3TNF) man page for more details. The TNF logging probes must be manually inserted in the source code at places where printf() would be put, and they produce no output by default. When you run the program under the control of prex(1) program, you may choose to log the otuput of all probes, or select just a subset of them (they are named!). The trace is later analyzed with the tnfdump(1) program. The best thing is that prex works also on running programs; it can attach to them, collect data and detach at later point.

TNF has been an enormous help in finding and correcting complex, time-dependent problems that I'd have much harder time to resolve otherwise.

A possible signal handling bug in Solaris

I know that combining threads and signals is a bad idea, but I just couldn't resist the temptation. It seemed like a nice solution until I've hit what seems to be a possible signal handling bug: sometimes the signal is not delivered on the alternate signal stack, even though a thread has requested so. You can read the full description here. I wonder whether I'll get a reply. In the mean-time, I'm abandoning threads in favor of multiple processes operating over a large shared memory segment.

Algorithm toolbox

I have released a preliminary version of an algorithm toolbox. The toolbox includes van Emde-Boas trees, intrusive AVL trees (thus, applicable in scenarios where there are no memory management facilities), and exhaustive permutation tester. The code is written in C++ and may be obtained here.