Josef “Jeff” Sipek

May 1, 2012

MongoDB - First Impressions

Filed under: open-source rants — JeffPC @ 15:36

I just ssh’ed into a server that’s running MongoDB to see if it was doing anything and if there were any cool commands to get stats from it. (I’ve never used MongoDB.) I accidentally ran mongod as non-root. It died because it didn’t have the right permissions — good. However, something in the output seemed completely and utterly retarded.

warning: 32-bit servers don't have journaling enabled by default. Please use
	--journal if you want durability.

[initandlisten] MongoDB starting : pid=12682 port=27017 dbpath=/data/db/
	32-bit host=hkn2012
[initandlisten] 
[initandlisten] ** NOTE: when using MongoDB 32 bit, you are limited to about
	2 gigabytes of data
[initandlisten] **       see http://blog.mongodb.org/post/137788967/32-bit-limitations
[initandlisten] **       with --journal, the limit is lower

Was it the 2 GB data limit? Nope! Was it the fact that 32-bit systems default to non-durable mode while 64-bit default to durable? Bingo! Seriously, that is retarded. Why would anyone think that it is a good idea to cripple 32-bit systems like that? Was performance so bad with journaling that to avoid gaining a reputation for being slow the developers decided to keep the data unsafe by default? I doubt it. Was it to squeeze in a couple more MB of addressable data? Probably. Good job, folks.

For what it is worth, I decided to see if the 2 GB limit was something silly (i.e., using an int in some on-disk structure). It turns out that mongod likes to mmap the data for fast access. This is reasonable. (More so than using architecture specific integral types in on-disk structures.)

I wonder what other gems are hiding in this software.

April 18, 2012

Adobe Lightroom 4

Filed under: photography — JeffPC @ 16:27

In my previous post I mentioned that I have more or less settled on using Adobe Lightroom 4 for my photo management and editing needs. After getting a comment from someone about his trouble with image management software, I decided to write a blahg post just about why I decided to go with Lightroom.

Adobe
Some people love Adobe while some hate it. Regardless of your feelings for the company, you’ve got to agree, they have a lot of experience when it comes to making photo editing and management software. If you want to get serious with digital photo management and editing, they probably got it right. It turns out that a fair amount of professional photographers use Lightroom during their workflow. So, if this program is good enough for people that rely on it for their livelihood, it is probably good enough for me. :)
catalog
I talked about this a bit in my previous post already, but I will repeat it here. Lightroom lets me do most things the same way I did before it except for the parts I didn’t like. So, I get to keep my <year>/<event> directory structure that I like, but all the photos are indexed and searchable. The catalog stores all the metadata and lets me quickly see thumbnails of only the photos I want to see.
tagging
This is a very common feature of photo management software, but I am including it here since I did not have anything like it with my previous workflow. One can associate arbitrary text strings with a photo and then filter based on that.
geo-tagging
One special metadata field that Lightroom handles is the GPS location. It also lets you select photos based on location on a nice map (pulled from Google Maps).
captions
Every photo can have a title and a caption. I haven’t experimented with this feature all that much but it is rather self explanatory.
ratings
Lightroom offers several ways to “rate” photographs. There is a very straight forward 5-star scale (you can set zero to five stars) as well as each photo can have a “pick” flag or a “reject” flag. After I first import photos from a new event, I display all the thumbnails to get a quick glance at what I shot. Then I view every photo individually and mark every photo that is utterly useless (e.g., blur-y) as a “reject” and every photo that seems promising as “pick”. Then, I look at just the rejects and delete them completely. Now, I just have ok photos (un-flagged) and good photos (flagged as “pick”). I use the stars to rate post-processed photos from mediocre (1-star) to ones I am proud of (5 stars).
DNG
Lightroom supports a variety of image formats — JPGs, TIFFs, PSDs, even various camera raw formats. I used to occasionally shoot in raw (NEFs) but viewing and editing them was a pain. With Ligthroom, I can use them just like any other file format. They just work. Interestingly, I no longer store NEFs. Instead of importing them and storing them as is, I let Lightroom convert them to Wikipedia article: DNGs. I won’t go into NEF vs. DNG, but what tipped the scale in DNG’s favor in my case were sidecar files.
Wikipedia article: sidecars
I do not know what most photo management applications do, but Lightroom stores all the metadata changes in its (SQLite) database. Additionally, it lets you tell it to store all metadata changes along with the original images as well. For every NEF file, it creates a sidecar Wikipedia article: XMP file. That is, next to foo.nef it will create foo.xmp which contains all the metadata changes. JPGs store the metadata in the EXIF tags. DNGs also store the metadata internally. So, if you want raw files because of their quality, you can either use the camera manufacturer’s native raw format and have to keep the XMP files around, or convert them to DNG (which is lossless conversion by default) and then not worry about sidecars.
misc
There are many other cool features that Lightroom offers — from being able to quickly batch process hundreds of photos to being able to generate web galleries and upload them via sftp with a single click. The list of features is way too long, and I am certain that I haven’t found them all yet.

So there you have it. That is what I do with Lightroom. Other software packages had various deficiencies. As an added benefit, with Lightroom I get to use more open formats (DNG & XMP) than without it.

As a technical side-note, all my photos are on a ZFS dataset that I access via CIFS. Yes, compression is enabled (Wikipedia article: lzjb).

April 17, 2012

Post Processing + 2005 Memorial Day Airshow

Filed under: photography events — JeffPC @ 02:19

As some of you know, I do enjoy running around with my camera. It really is a lot of fun wandering aimlessly around, taking a photo or a dozen of something that looks interesting or funny. Unfortunately, there is more to photography than just capturing photons. Once you have the “raw” images, you need to post-process them. Digital cameras make the photon capture part super-easy, however they don’t simplify post processing all that much. (Yes, I know, you no longer need to deal with darkrooms and chemical baths. My point is, the amount of improvement in photo taking is way greater than the amount of improvement in post processing.)

About two weeks ago, I decided to give Adobe Lightroom 4 a go. Up until then, I just had a super-simple organizational scheme: a directory for every year (2004, 2005, …, 2012) and inside each, a directory for each “event”. For example, the 2005 Ottawa Linux Symposium was in 2005/ols while the 2006 one was in 2006/ols. In each event directory, I just had a bunch of jpegs or NEFs. If I wanted to modify an image, I’d open it in Gimp or Photoshop, and save whatever variants I wanted to in a subdirectory called pp — which stands for post-processed. A very simple scheme, but it doesn’t scale. Over the years, I moved my photo collection from computer to computer, trying to keep a backup on an external disk whenever possible. Sadly, this resulted in my having a 130 GB directory with the per-year scheme and “temp” directories with various amounts of the same images, as well as some “I need to empty the CF card now, so I’ll just dump it somewhere temporarily” directories. I suspect that I have about 70–80 GB of unique content.

With this mess on my hands, I decided to try some photo management software. A while ago, I looked at digiKam and I was not impressed. Then about two weeks ago, I gave Picasa and Lightroom a try. Picasa didn’t quite do what I wanted it to do — keep a very similar workflow to what I have now (keep the per-year and per-event directories) but make it really easy to make powerful edits to the images non-destructively. That is, I want to keep the original as they are, but associate the edited images with the original. Lightroom hit the spot right on. At this point I am still using the 30-day trial, but I’m going to spring for the $150 full version.

Anyway, I’ll talk more about Lightroom at some later time. Today, I just want to share 25 photos from an air show I went to on Memorial Day in 2005. (Photos that have been “rotting” in my giant pile of photos until I imported them into Lightroom.) I generated a photo gallery with all 25. Below are the better ones.

February 21, 2012

FAST 2012

Filed under: events filesystems — JeffPC @ 21:58

Last week I went to FAST ’12. As always, it’s been fun attending. Overall, the talks were good and gave me a couple of ideas. There was definitely a lot of flash and SSD related work — both of which I don’t find all that exciting. There was however a bunch of work related to dedup and backup.

Anyway, here’s my reading list. I’ve skimmed most of the papers, but I want to take a closer look at these.

  • Characteristics of Backup Workloads in Production Systems
  • WAN Optimized Replication of Backup Datasets Using Stream-Informed Delta Compression
  • Recon: Verifying File System Consistency at Runtime
  • Consistency Without Ordering
  • ZZFS: A Hybrid Device and Cloud File System for Spontaneous Users
  • Serving Large-scale Batch Computed Data with Project Voldemort
  • BlueSky: A Cloud-Backed File System for the Enterprise
  • Extracting Flexible, Replayable Models from Large Block Traces
  • iDedup: Latency-aware, Inline Data Deduplication for Primary Storage

January 8, 2012

Outage and data-loss

Filed under: miscellaneous sysadmin — JeffPC @ 17:05

You may have noticed that about a week ago my webserver went down. It started off as having to deal with two failed disks in a Wikipedia article: RAID6, but quickly turned into a system reinstall. There was no data-loss because of hardware failures, but I am sad to say that I accidentally nuked all the blahg post titles and publication times. Additionally, all the comment times and author names are gone. The content for both posts and comments is safe.

I’ll try to restore as many posts as possible as soon as possible. It might involve going through archive.org and copying the metadata over.

How did the data-loss happen? I forgot to backup extended attributes. My blahging software uses them to store the post metadata. Oops.

Sorry for the inconvenience.

November 5, 2011

DTrace: The utmp_update Debugger

Filed under: programming openindiana open-source — JeffPC @ 21:54

For the past 2 years, I am a happy user of rxvt-unicode, aka urxvt. Recently, I noticed that my logs contained rather mysterious error messages:

Nov  3 22:46:03 meili utmp_update[1613]: [ID 845426 user.error] Wrong number of
	arguments or invalid user 

Sometimes, there were a dozen of these. Of course I filed a bug with the Illumos folks. Rich Lowe suggested using DTrace to figure out what is actually going on. It was time to look at the exit codes for utmp_update.

syscall::rexit:entry
/execname=="utmp_update"/
{
	printf("utmp_update exited with code %d", arg0);
	@[arg0] = count();
}

tick-60sec
{
	printa(@);
}

Since utmp is involved, it had something to do with terminals, so I tried to open some terminals and close them. That did it!

# dtrace -s catch-errors.d 
dtrace: script 'catch-errors.d' matched 2 probes
CPU     ID                    FUNCTION:NAME
  0     49                      rexit:entry utmp_update exited with code 0
  1     49                      rexit:entry utmp_update exited with code 0
  0     49                      rexit:entry utmp_update exited with code 7
  0     49                      rexit:entry utmp_update exited with code 7
  1     49                      rexit:entry utmp_update exited with code 0
  5     49                      rexit:entry utmp_update exited with code 0
  1     49                      rexit:entry utmp_update exited with code 0
  2     49                      rexit:entry utmp_update exited with code 0
  3     49                      rexit:entry utmp_update exited with code 7
  1  67549                      :tick-60sec 
                7                3
                0                6

It turns out that every time I closed a terminal, utmp_update exited with error 7. A quick glance at usr/src/cmd/utmp_update/utmp_update.c reveals:

/*
 * Return codes
 */
#define	NORMAL_EXIT		0
#define	BAD_ARGS		1
#define	PUTUTXLINE_FAILURE	2
#define	FORK_FAILURE		3
#define	SETSID_FAILURE		4
#define	ALREADY_DEAD		5
#define	ENTRY_NOTFOUND		6
#define	ILLEGAL_ARGUMENT	7
#define	DEVICE_ERROR		8

Aha! It really is an invalid argument. At this point, Rich pointed me to setutxline in libc.so. Sadly, for whatever reason, the probe pid*:libc.so.1:pututxline:entry didn’t work (it didn’t match anything). Rich suggested the following DTrace script:

proc:::exec
/strstr(args[0], "utmp") != NULL/
{
	trace(execname);
}

Pretty straightforward — the output told me that it was urxvt causing all this trouble.

Now, I knew to watch out for pututxline in urxvt. I tried to set a probe pid$target::pututxline:entry and use the new print function in DTrace, but due to a user error (read: sometimes I write stupid code) it didn’t work. Rich helped me navigate through mdb to get a print-out of the utx structure. At this point, it was a bit too late in the night and so I went to bed.

The next morning, I tried the print function again and this time I used it right and it printed out the structure:

struct utmpx {
    char [32] ut_user = [ "" ]
    char [4] ut_id = [ 'v', 't', '0', '2' ]
    char [32] ut_line = [ "pts/2" ]
    pid_t ut_pid = 0x193ec
    short ut_type = 0x8
    struct exit_status ut_exit = {
        short e_termination = 0
        short e_exit = 0
    }
    struct timeval ut_tv = {
        time_t tv_sec = 0x4eb55d2a
        suseconds_t tv_usec = 0x18adc
    }
    int ut_session = 0
    int [5] pad = [ 0, 0, 0, 0, 0 ]
    short ut_syslen = 0
    char [257] ut_host = [ "" ]
}

Everything looks right, except that the ut_user field is blank. I wonder if this could be the cause of it. Time to look at the urxvt code! (The ustack() action in a DTrace probe for pututxline:entry will tell you where to look.) Here’s a snippet from rxvt-unicode-9.12/libptytty/src/logging.C:

/*
 * remove utmp and wtmp entries
 */
void
ptytty_unix::logout ()
{
  ...
#ifdef HAVE_STRUCT_UTMPX
  setutxent ();
  tmputx = getutxid (utx);
  if (tmputx && tmputx->ut_pid == cmd_pid)
    pututxline (utx);
  endutxent ();
#endif
  ...
}

Ok, so it gets a utx struct and then it puts a different one. Let’s see how different those two are:

# cat getutxid.d
#include <utmpx.h>

pid$target::getutxid:return
{
	ustack();
	print(*(struct utmpx*)copyin(arg1, sizeof(struct utmpx)));
}
# dtrace -Cs getutxid.d -p 103403
dtrace: script 'getutxid.d' matched 1 probes
dtrace: pid 103403 has exited
CPU     ID                    FUNCTION:NAME
  4  67555                  getutxid:return 
              libc.so.1`getutxid+0xf1
              urxvt`_ZN11ptytty_unixD0Ev+0x16
              urxvt`_ZN9rxvt_termD1Ev+0x59b
              urxvt`_ZN9rxvt_term10destroy_cbERN2ev4idleEi+0x70
              urxvt`_ZN2ev4baseI7ev_idleNS_4idleEE12method_thunkI9rxvt_termXadL_ZNS5_10destroy_cbERS2_iEEEEvPS1_i+0x27
              urxvt`ev_invoke_pending+0x35
              urxvt`ev_run+0x520
              urxvt`main+0x29b
              urxvt`_start+0x83
struct utmpx {
    char [32] ut_user = [ "jeffpc" ]
    char [4] ut_id = [ 'v', 't', '0', '2' ]
    char [32] ut_line = [ "pts/2" ]
    pid_t ut_pid = 0x193ec
    short ut_type = 0x7
    struct exit_status ut_exit = {
        short e_termination = 0
        short e_exit = 0x2
    }
    struct timeval ut_tv = {
        time_t tv_sec = 0x4eb55d1f
        suseconds_t tv_usec = 0x18adc
    }
    int ut_session = 0
    int [5] pad = [ 0, 0, 0, 0x303a0005, 0x302e ]
    short ut_syslen = 0
    char [257] ut_host = [ "" ]
}

Ok, it’s more or less the same. It does, however, have a username filled in. I wonder what would happen if I filled in the username. (The urxvt code seems to fill it in only on login updates and it leaves the field empty on logout updates.) Now, I had 3 choices…

  1. Change the urxvt code to fill in the username on logout updates.
  2. Set a breakpoint in gdb or mdb and then tweak the structure before it is passed to utmp_update.
  3. Use DTraces “destructive” option to allow me to modify the process’s memory.

I chose #3.

Here’s the script in all its glory:

#pragma D option destructive

#include <utmpx.h>

pid$target::getutxid:return
{
	ustack();
	print(*(struct utmpx*)copyin(arg1, sizeof(struct utmpx)));
}

pid$target::pututxline:entry
{
	ustack();
	print(*(struct utmpx*)copyin(arg0, sizeof(struct utmpx)));
	printf("\nFIXING...\n");
	copyout("jeffpc\0", (uintptr_t)&((struct utmpx*)arg0)->ut_user[0], 7);
	print(*(struct utmpx*)copyin(arg0, sizeof(struct utmpx)));
}

pid$target::pututxline:return
{
	printf("pututxline returned %p", arg1);
}

And here’s the output:

# dtrace -Cs foo.d -p 103403
dtrace: script 'foo.d' matched 3 probes
dtrace: allowing destructive actions
dtrace: pid 103403 has exited
CPU     ID                    FUNCTION:NAME
  4  67555                  getutxid:return 
              libc.so.1`getutxid+0xf1
              urxvt`_ZN11ptytty_unixD0Ev+0x16
              urxvt`_ZN9rxvt_termD1Ev+0x59b
              urxvt`_ZN9rxvt_term10destroy_cbERN2ev4idleEi+0x70
              urxvt`_ZN2ev4baseI7ev_idleNS_4idleEE12method_thunkI9rxvt_termXadL_ZNS5_10destroy_cbERS2_iEEEEvPS1_i+0x27
              urxvt`ev_invoke_pending+0x35
              urxvt`ev_run+0x520
              urxvt`main+0x29b
              urxvt`_start+0x83
struct utmpx {
    char [32] ut_user = [ "jeffpc" ]
    char [4] ut_id = [ 'v', 't', '0', '2' ]
    char [32] ut_line = [ "pts/2" ]
    pid_t ut_pid = 0x193ec
    short ut_type = 0x7
    struct exit_status ut_exit = {
        short e_termination = 0
        short e_exit = 0x2
    }
    struct timeval ut_tv = {
        time_t tv_sec = 0x4eb55d1f
        suseconds_t tv_usec = 0x18adc
    }
    int ut_session = 0
    int [5] pad = [ 0, 0, 0, 0x303a0005, 0x302e ]
    short ut_syslen = 0
    char [257] ut_host = [ "" ]
}
  4  67556                 pututxline:entry 
              libc.so.1`pututxline
              urxvt`_ZN11ptytty_unix6logoutEv+0x15c
              urxvt`_ZN11ptytty_unixD0Ev+0x16
              urxvt`_ZN9rxvt_termD1Ev+0x59b
              urxvt`_ZN9rxvt_term10destroy_cbERN2ev4idleEi+0x70
              urxvt`_ZN2ev4baseI7ev_idleNS_4idleEE12method_thunkI9rxvt_termXadL_ZNS5_10destroy_cbERS2_iEEEEvPS1_i+0x27
              urxvt`ev_invoke_pending+0x35
              urxvt`ev_run+0x520
              urxvt`main+0x29b
              urxvt`_start+0x83
struct utmpx {
    char [32] ut_user = [ "" ]
    char [4] ut_id = [ 'v', 't', '0', '2' ]
    char [32] ut_line = [ "pts/2" ]
    pid_t ut_pid = 0x193ec
    short ut_type = 0x8
    struct exit_status ut_exit = {
        short e_termination = 0
        short e_exit = 0
    }
    struct timeval ut_tv = {
        time_t tv_sec = 0x4eb55d2a
        suseconds_t tv_usec = 0x18adc
    }
    int ut_session = 0
    int [5] pad = [ 0, 0, 0, 0, 0 ]
    short ut_syslen = 0
    char [257] ut_host = [ "" ]
}
FIXING...
struct utmpx {
    char [32] ut_user = [ "jeffpc" ]
    char [4] ut_id = [ 'v', 't', '0', '2' ]
    char [32] ut_line = [ "pts/2" ]
    pid_t ut_pid = 0x193ec
    short ut_type = 0x8
    struct exit_status ut_exit = {
        short e_termination = 0
        short e_exit = 0
    }
    struct timeval ut_tv = {
        time_t tv_sec = 0x4eb55d2a
        suseconds_t tv_usec = 0x18adc
    }
    int ut_session = 0
    int [5] pad = [ 0, 0, 0, 0, 0 ]
    short ut_syslen = 0
    char [257] ut_host = [ "" ]
}
  4  67557                pututxline:return pututxline returned fef6ecf0

We can see the getutxid return a reasonable utmpx. Then we see pututxline get a utmpx without a username set. Then there is the fixed up tmpx. Finally, we see that the pututxline returned a non-NULL pointer. (It returns NULL on error — which does indeed happen without the fix-up.)

There you have it, folks. DTrace let me debug an issue without annoying change-compile-install cycles. Now, all I have to do is fix up urxvt in OpenIndiana and possibly, if it applies to other systems, push the fix upstream.

October 28, 2011

Timesavers: ZFS & BE

Filed under: sysadmin filesystems openindiana — JeffPC @ 16:12

I’ve mentioned Boot Environments before. Well, earlier this week BEs and ZFS snapshots saved me a bunch of time. Here’s what happened.

I was in the middle of installing some package (pkg install foo) when my laptop locked up. I had to power cycle it the hard way. When it booted back up, I retried the install, but pkg complained that some state file was corrupted and it didn’t want to do anything. Uh oh. I’ve had similar issue happen to me on Debian with aptitude, so I knew that the hard way of fixing this issue was going to take more time than I’d like to dedicate to it (read: none). Thankfully, I use OpenIndiana which has ZFS and BEs.

  1. Reboot into a BE from a while ago (openindiana-3). The latest BE (openindiana-4) was created by pkg about a month ago as a clone of openindiana-3 during a major upgrade.
  2. Figure out which automatic ZFS snapshot I want to revert to. A matter of running zfs list -t all rpool/ROOT/openindiana-4 | tail -5 and picking the latest snapshot which I believe is from before pkg messed it all up. I ended up going an hour back just to make sure.
  3. Revert the BE. beadm rollback openindiana-4@zfs-auto-snap_hourly-2011-10-25-19h11
  4. Reboot back into openindiana-4.

After the final reboot, everything worked just fine. (Since the home directories are on a different dataset, they were left untouched.)

Total downtime: 5 minutes
Ease of repair: trivial

Your Turn

Do you have a corrupt package manager war story? Did you just restore from backup? Let me know in a comment.

October 24, 2001

Jasmine Strikes Back

Filed under: photography — JeffPC @ 00:44

Everyone can appreciate a cute photo of a cat. Here’s Jasmine again:

Jasmine

October 13, 2011

Recursion with Sun Studio

Filed under: programming — JeffPC @ 23:30

I mentioned my post about recursion & DTrace in the #dtrace, and one of the folks there asked about Sun’s/Oracle’s compiler — Studio. I happen to have version 12u1, so why not have some more fun? :)

First things first, the results. With -O1, both variants recurse — 6 calls followed by 6 returns. With -O2, the naive code still recurses, while the explicitly-coded-as-tail-recursive code tail-recurses.

Here are the disassemblies (for -O2). Naive-recursive:

08050aa0 <fac>:
 8050aa0:	55                   	push   %ebp
 8050aa1:	8b ec                	mov    %esp,%ebp
 8050aa3:	53                   	push   %ebx
 8050aa4:	83 ec 04             	sub    $0x4,%esp
 8050aa7:	83 e4 f0             	and    $0xfffffff0,%esp
 8050aaa:	8b 5d 08             	mov    0x8(%ebp),%ebx
 8050aad:	83 fb 01             	cmp    $0x1,%ebx
 8050ab0:	7f 07                	jg     8050ab9 <fac+0x19>
 8050ab2:	b8 01 00 00 00       	mov    $0x1,%eax
 8050ab7:	eb 12                	jmp    8050acb <fac+0x2b>
 8050ab9:	83 ec 0c             	sub    $0xc,%esp
 8050abc:	8d 43 ff             	lea    -0x1(%ebx),%eax
 8050abf:	50                   	push   %eax
 8050ac0:	e8 db ff ff ff       	call   8050aa0 <fac>
 8050ac5:	83 c4 10             	add    $0x10,%esp
 8050ac8:	0f af c3             	imul   %ebx,%eax
 8050acb:	8d 65 fc             	lea    -0x4(%ebp),%esp
 8050ace:	5b                   	pop    %ebx
 8050acf:	c9                   	leave  
 8050ad0:	c3                   	ret    

and tail-recursive:

08050aa0 <fac>:
 8050aa0:	55                   	push   %ebp
 8050aa1:	8b ec                	mov    %esp,%ebp
 8050aa3:	8b 55 08             	mov    0x8(%ebp),%edx
 8050aa6:	8b 45 0c             	mov    0xc(%ebp),%eax
 8050aa9:	83 fa 01             	cmp    $0x1,%edx
 8050aac:	7e 0d                	jle    8050abb <fac+0x1b>
 8050aae:	8d 4a ff             	lea    -0x1(%edx),%ecx
 8050ab1:	0f af c2             	imul   %edx,%eax
 8050ab4:	8b d1                	mov    %ecx,%edx
 8050ab6:	83 f9 01             	cmp    $0x1,%ecx
 8050ab9:	7f f3                	jg     8050aae <fac+0xe>
 8050abb:	89 45 0c             	mov    %eax,0xc(%ebp)
 8050abe:	89 55 08             	mov    %edx,0x8(%ebp)
 8050ac1:	c9                   	leave  
 8050ac2:	c3                   	ret 

I find it fascinating that Studio produced nearly identical code to gcc. The big differences that you can see are: (1) Studio defaults to saving the frame pointer while gcc omitted it, (2) gcc inserted a no-op to 16-byte align the loop, and (3) Studio uses an extra register to perform the subtraction (the n-1).

The subtraction surprised me, and so I examined the code more closely. My guess is that Studio attempts to move the subtraction as far up as possible to start it early. This way, by the time we actually need the subtracted value (the cmp instruction) it’s already available. Compare that to gcc’s sub followed immediately by cmp. Some processors are designed in such a way that the result of sub will be available by the time cmp wants to execute. Others are not.

Your Turn

Have you noticed any interesting compiler optimizations? Share them in a comment!

October 12, 2011

Recursion

Filed under: programming — JeffPC @ 17:47

Last night while reading about DTrace, I came across an example that involved tracing a simple recursive factorial program. I pointed it out to my girlfriend, Holly, since I thought that she’d find it interesting — the class she teaches has a section about recursion.

Here’s the original code:

extern int fac (int n);

int main(int argc, char **argv)
{
	int f;
	f = fac(6);
	return 0;
}

int fac (int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac (n - 1);
}

Pretty simple. I compiled it, and ran it with DTrace:

$ gcc -o fac orig.c 
$ cat fac.d 
pid$target::fac:entry
{
        trace (arg0);
}
pid$target::fac:return
{
        trace (arg1);
}
$ sudo dtrace -Fs fac.d -c ./fac
dtrace: script 'fac.d' matched 2 probes
dtrace: pid 1146 has exited
CPU FUNCTION                                 
  0  -> fac                                                   6
  0    -> fac                                                 5
  0      -> fac                                               4
  0        -> fac                                             3
  0          -> fac                                           2
  0            -> fac                                         1
  0            <- fac                                         1
  0          <- fac                                           2
  0        <- fac                                             6
  0      <- fac                                              24
  0    <- fac                                               120
  0  <- fac                                                 720

Cool! I thought I was done. Holly asked whether it would work with tail-recursion. Interesting, I thought…it might - depending on how gcc handles the function prologue and epilogue. The D script is a little different to dump both of the arguments. Here’s the result:

$ gcc -o fact tail.c
$ cat fact.d 
pid$target::fac:entry
{
        trace (arg0); trace(arg1);
}
pid$target::fac:return
{
        trace (arg1);
}
$ sudo dtrace -Fs fact.d -c ./fact
dtrace: script 'fact.d' matched 2 probes
dtrace: pid 1233 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6                1
  2    -> fac                                                 5                6
  2      -> fac                                               4               30
  2        -> fac                                             3              120
  2          -> fac                                           2              360
  2            -> fac                                         1              720
  2            <- fac                                       720
  2          <- fac                                         720
  2        <- fac                                           720
  2      <- fac                                             720
  2    <- fac                                               720
  2  <- fac                                                 720

You can see the values getting calculated and passed down versus them getting calculated on during the return. That was fun to see. But wait! If this function is tail recursive, why are we seeing all these returns? It should be just one return! Doh! I didn’t compile with optimizations so gcc emitted the stupidest possible code. Easy enough to fix:

$ gcc -o fact -O2 tail.c 
$ sudo dtrace -Fs fact.d -c ./fact
dtrace: script 'fact.d' matched 2 probes
dtrace: pid 1304 has exited

$

Huh… nothing happened! fac was never called. Let’s see what gcc emitted:

$ objdump -S fact
...
Disassembly of section .text.startup:

08050d10 <main>:
 8050d10:       31 c0                   xor    %eax,%eax
 8050d12:       c3                      ret  

Great, the main function turned into a return 0 because the value returned by fac() was never used. Easy enough, let’s just return the value from main.

$ cat tail.c 
extern int fac (int n);

int main(int argc, char **argv)
{
        return fac(6);
}

int fac (int n)
{
        if (n <= 1)
                return 1;
        else
                return n * fac (n - 1);
}
$ gcc -o fact -O2 tail.c 
$ objdump -S fact
...
Disassembly of section .text.startup:

08050d10 <main>:
 8050d10:       b8 d0 02 00 00          mov    $0x2d0,%eax
 8050d15:       c3                      ret    

Argh! Thanks gcc, you replaced my fac(6) function call with the value 720 — that is the factorial of 6. Fine, let’s do this the hard way: get an int from the first argument and print it out. Also, to prevent inlining, let’s put it in a separate file. So, now we have:

$ cat fac.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

extern int fac (int n);

int main(int argc, char **argv)
{
        printf("%d\n", fac(atoi(argv[1])));
        return 0;
}
$ cat fac_2.c
int fac (int n)
{
        if (n <= 1)
                return 1;
        else
                return n * fac (n - 1);
}
$ cat fact.c
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

extern int fac (int n, int v);

int main(int argc, char **argv)
{
        printf("%d\n", fac(atoi(argv[1]), 1));
        return 0;
}
$ cat fact_2.c
int fac (int n, int v)
{
        if (n <= 1)
                return v;
        else
                return fac(n-1, n*v);
}

Now, if we run the two variants compiled with -O2, we get:

$ sudo dtrace -Fs fac.d -c "./fac 6"
dtrace: script 'fac.d' matched 2 probes
720
dtrace: pid 1397 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6
  2  <- fac                                                 720

$ sudo dtrace -Fs fact.d -c "./fact 6"
dtrace: script 'fact.d' matched 2 probes
720
dtrace: pid 1399 has exited
CPU FUNCTION                                 
  5  -> fac                                                   6                1
  5  <- fac                                                 720

Weird, for both we can see only one function entry and return. Let’s try with -O1:

$ sudo dtrace -Fs fac.d -c "./fac 6"
dtrace: script 'fac.d' matched 2 probes
720
dtrace: pid 1393 has exited
CPU FUNCTION                                 
  6  -> fac                                                   6
  6    -> fac                                                 5
  6      -> fac                                               4
  6        -> fac                                             3
  6          -> fac                                           2
  6            -> fac                                         1
  6            <- fac                                         1
  6          <- fac                                           2
  6        <- fac                                             6
  6      <- fac                                              24
  6    <- fac                                               120
  6  <- fac                                                 720

$ sudo dtrace -Fs fact.d -c "./fact 6"
dtrace: script 'fact.d' matched 2 probes
720
dtrace: pid 1395 has exited
CPU FUNCTION                                 
  2  -> fac                                                   6                1
  2    -> fac                                                 5                6
  2      -> fac                                               4               30
  2        -> fac                                             3              120
  2          -> fac                                           2              360
  2            -> fac                                         1              720
  2            <- fac                                       720
  2          <- fac                                         720
  2        <- fac                                           720
  2      <- fac                                             720
  2    <- fac                                               720
  2  <- fac                                                 720

Ok, now were back to having call and return instructions for both cases — the tail recursive function is not actually tail recursing when it should. So, first moral of the story is: -O1 is not enough to make tail recursive functions tail recurse. The odd behavior of the non-tail recursive code with -O2 is still weird. Let’s disassemble it; first the simple recursive code:

08050d00 <fac>:
 8050d00:       8b 54 24 04             mov    0x4(%esp),%edx
 8050d04:       b8 01 00 00 00          mov    $0x1,%eax
 8050d09:       83 fa 01                cmp    $0x1,%edx
 8050d0c:       7e 0d                   jle    8050d1b <fac+0x1b>
 8050d0e:       66 90                   xchg   %ax,%ax
 8050d10:       0f af c2                imul   %edx,%eax
 8050d13:       83 ea 01                sub    $0x1,%edx
 8050d16:       83 fa 01                cmp    $0x1,%edx
 8050d19:       75 f5                   jne    8050d10 <fac+0x10>
 8050d1b:       f3 c3                   repz ret 
 8050d1d:       90                      nop    
 8050d1e:       90                      nop    
 8050d1f:       90                      nop    

Whoa! gcc turned the plain recursive code into a tail-recursive one. For comparison, here’s the disassembly of the explicitly-coded-as-tail-recursive function:

08050d00 <fac>:
 8050d00:       8b 54 24 04             mov    0x4(%esp),%edx
 8050d04:       8b 44 24 08             mov    0x8(%esp),%eax
 8050d08:       83 fa 01                cmp    $0x1,%edx
 8050d0b:       7e 0e                   jle    8050d1b <fac+0x1b>
 8050d0d:       8d 76 00                lea    0x0(%esi),%esi
 8050d10:       0f af c2                imul   %edx,%eax
 8050d13:       83 ea 01                sub    $0x1,%edx
 8050d16:       83 fa 01                cmp    $0x1,%edx
 8050d19:       75 f5                   jne    8050d10 <fac+0x10>
 8050d1b:       f3 c3                   repz ret 
 8050d1d:       90                      nop    
 8050d1e:       90                      nop    
 8050d1f:       90                      nop

Do you see it? It’s virtually identical to what gcc emitted for the naive code.

So there you have it folks. The compiler is smarter than you, more consistent than you, and less likely to screw up compared to you when converting a recursive function into a tail-recursive one. In general, you should not prematurely optimize.

In case you care, I’ve used gcc 4.6.1 for these experiments on OpenIndiana.

Your Turn

Do you have an interesting compiler optimization story? Share it in a comment!

Powered by a pile of c