Kevin's Weblog

I had lunch today with a couple former co-workers. It’s a little funny how many people who used to work for Overture are now working in the SEO/SEM biz. Personally, I plan to get completely away from advertising when I do decide to move on. At any rate, it’s interesting to hear some perspectives from the other side of the checkbooks. One thing that came up was that they really dislike the short title and description limits on Google because it takes a lot more effort to write them. Also, people click on short ads more often, but don’t convert as frequently (because the ads don’t contain as much information for readers to use to decide relevance). From the advertiser point of view, this is a negative, since they’re getting less well-qualified traffic.

Over on the publisher side of things, there’s been a lot of people mentioning that YPN has lower CTR, but higher PPC than Google, and that the net revenue is about the same or slightly higher. There are probably a number of factors behind that. (I suspect that we have somewhat different ad selection strategies, for example.) But, part of it may be due to the difference in creative lengths. Assuming the market is reasonably efficient, if shorter ads on AdSense result in users making more clicks but no more purchases, than advertisers ought to respond by lowering their bids. If conversions stay constant, then we expect the total advertiser spending, and publisher revenue, to balance out as observed. If we refine the analysis a little further, we would actually expect revenues on Google to be somewhat lower as advertisers should demand a risk discount for less predictable user referrals. However, one should take that with a grain of salt, since there are other differences present as well, and I’m not sure if I actually believe that most advertisers are quite that rigorously economically rational.

A couple months ago, Marc noticed that valgrind reports errors in GD. Recently, I was finding that a modest test suite was producing as many as 2 million of these errors, so I finally got motivated to dig in and figure out what’s going on. This unearthed two bugs in the library’s support for FreeType fonts. (All line numbers that follow refer to GD version 2.0.28, but the bugs still exist in the most recent version of the library.)

The problem is demonstrated by this simple test program:

#include <gd.h>
#include <string.h>

int main (void)
{
  gdImagePtr imgPtr = gdImageCreate (480, 60);

  int brect[8];
  int gdColor = 2;
  char *fontPath = strdup ("/usr/share/fonts/truetype/verdana.ttf");
  int pointSize = 9;

  gdFTStringExtra ex_struct;
  memset(&ex_struct, 0, sizeof(ex_struct));
  ex_struct.flags = gdFTEX_LINESPACE;
  ex_struct.linespacing = 0.95;

  gdImageStringFTEx (imgPtr, brect, gdColor, fontPath, pointSize,
                     0, 5, 15, 
                     strdup (""),
                     &ex_struct);

  gdImageStringFTEx (imgPtr, brect, gdColor, fontPath, pointSize,
                     0, 5, 30, 
                     strdup ("Blah Blah Blah"),
                     &ex_struct);

  return 0;
}

(You may need to change the path to your fonts). When run under the valgrind memcheck tool, there are two sets of errors detected:

==97185== Memcheck, a memory error detector for x86-linux.
==97185== Copyright (C) 2002-2004, and GNU GPL'd, by Julian Seward.
==97185== Using valgrind-2.1.0, a program supervision framework for x86-linux.
==97185== Copyright (C) 2000-2004, and GNU GPL'd, by Julian Seward.
==97185== Estimated CPU clock rate is 3136 MHz
==97185== For more details, rerun with: -v
==97185== 
==97185== Use of uninitialised value of size 4
==97185==    at 0x2D0FCDE6: gdImageStringFTEx (gdft.c:1304)
==97185==    by 0x1002992: main (testgdvalgrind.c:23)
==97185== 
==97185== Use of uninitialised value of size 4
==97185==    at 0x2D0FCDF1: gdImageStringFTEx (gdft.c:1304)
==97185==    by 0x1002992: main (testgdvalgrind.c:23)
==97185== 
==97185== Use of uninitialised value of size 4
==97185==    at 0x2D0FCE8F: gdImageStringFTEx (gdft.c:1306)
==97185==    by 0x1002992: main (testgdvalgrind.c:23)
==97185== 
==97185== Use of uninitialised value of size 4
==97185==    at 0x2D0FCF0D: gdImageStringFTEx (gdft.c:1308)
==97185==    by 0x1002992: main (testgdvalgrind.c:23)
==97185== 
==97185== Conditional jump or move depends on uninitialised value(s)
==97185==    at 0x2D0FB924: gdCacheGet (gdcache.c:108)
==97185==    by 0x2D0FC525: gdft_draw_bitmap (gdft.c:863)
==97185==    by 0x2D0FCDA1: gdImageStringFTEx (gdft.c:1280)
==97185==    by 0x10029C8: main (testgdvalgrind.c:28)
==97185== 
==97185== ERROR SUMMARY: 591 errors from 5 contexts (suppressed: 0 from 0)
==97185== malloc/free: in use at exit: 119002 bytes in 182 blocks.
==97185== malloc/free: 437 allocs, 255 frees, 133057 bytes allocated.
==97185== For a detailed leak analysis,  rerun with: --leak-check=yes
==97185== For counts of detected errors, rerun with: -v

The first four errors come from the first call to gdImageStringFTEx and occur only in the case where the user requests the bounding box when rendering an empty string. In this case, two variables are never initialized, and the bounding box ends up containing junk from the stack, rather than the correct result (which is just the single pixel where the empty string was requested to be located).

The last error, which is much more common, comes from the anti-aliasing cache. Because these calculations are fairly expensive, the results are saved in an LRU cache. Unfortunately, when the calculation is made, there is a field in the structure that stores the results which is not populated. When a new calculation is requested, the lookup compares this field, leading to the valgrind error. Unfortunately, it also means that the cache lookup always fails.

Both of these require relatively minor changes to fix. Here’s a patch:

--- gdft.c.orig Fri Oct 21 10:12:09 2005
+++ gdft.c.patched      Fri Oct 21 16:51:23 2005
@@ -642,7 +642,7 @@
   pixel = a->pixel = b->pixel;
   bg = a->bgcolor = b->bgcolor;
   fg = a->fgcolor = b->fgcolor;
-  im = b->im;
+  im = a->im = b->im;
 
   /* if fg is specified by a negative color idx, then don't antialias */
   if (fg < 0)
@@ -995,6 +995,13 @@
     }
   face = font->face;           /* shortcut */
   slot = face->glyph;          /* shortcut */
+
+  /* Initialize the bounding box */
+  if (brect) 
+    {
+      total_min.x = total_min.y = 0;
+      total_max.x = total_max.y = 0;
+    }
 
   /*

With these changes in place, there are no more valgrind errors. Also, I found that for our usage patterns there was about a 20% performance boost in this function from fixing the caching bug. I’ve done regression tests with a modest set of real-life input as well as a much larger set of random-ish input and they show no changes to the output.

Hopefully these fixes will make their way into the next release of GD, but in the meantime perhaps this will be useful to someone.

Update: Users of GD and valgrind may also notice some memory errors coming from zlib. In this case, the cause is understood by the Zlib developers, but they do not plan to fix the problem. The errors come from a spot where they believe they can do manual loop unrolling and beat the compiler. While the errors are legitimate, they don’t actually use the bad bits of memory in the end.