Will the Destructor Be Called?

| Comments

Here’s a C++ quiz for all of you: somefunc() will be called from a thread. Do you think this destructor will be called?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class A {
public:
  A () {
      printf("Constructor\t");
  }

  ~A() {
      printf("Destructor\n");
  }
};

int somefunc () {
  A inst;
  int* a = 0
  *a = 1;
  return 0;
}

Idioms

| Comments

What if

1
2
3
4
5
6
7
8
9
10
11
for (int i=0; i<100; i++)
{
  doSomething();
}

// and

for (int i=0; i<100; i+=2)
{
  doSomethingElse();
}

Was

1
2
doSomething() for 1..99;
while (i=1,2..99) { doSomethingElse(); };

Would the world be a better place?

That’s Not the Point

| Comments

Today I read an interesting chapter in Writing Solid Code, and it showed an example where a supposed optimization led to code bloat:

To represent the hierarchical window structure, Character Windows used a binary tree in which one branch pointed to subwindwos, called “children” and the other branch pointed to windows with the same parent, called “siblings”:
1
2
3
4
5
6
7
8
9
typedef struct WINDOW
{
  struct WINDOW *pwndChild;    /* NULL if no children */
  struct WINDOW *pwndSibling;  /* NULL if no brothers/sisters */
  char *strWndTitle;
  .
  .
  .
} window;        /* Naming: wnd, *pwnd */
You can turn to any algorithm book and find efficient routines to manipulate binary trees, so I was a bit shocked to when I reviewed the Character Windows code for inserting a child window into the tree. The code looked like this:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* pwndRootChildren is the pointer to the list of top-level windows
 * such as the menu bar and the main document windows.
 */
static window *pwndRootChildren = NULL;

void AddChild(window *pwndParent, window *pwndNewBorn)
{
  /* New windows may have children but not siblings... */
  ASSERT(pwndNewBorn->pwndSibling == NULL);

  if (pwndParent == NULL)
  {
      /* Add window to the top-level root list. */
      pwndNewBorn->pwndSibling = pwndRootChildren;
      pwndRootChildren = pwndNewBorn;
  }
  else
  {
      /*  If Parent's first child, start a new sibling chain;
      *  otherwise, add child to the end of the existing
      *  sibling chain.
      */
      if (pwndParent->pwndChild == NULL)
      {
          pwndParent->pwndChild = pwndNewBorn;
      }
      else
      {
          window *pwnd = pwndParent->pwndChild;
          while (pwnd->pwndSibling != NULL)
          {
              pwnd = pwnd->pwndSibling;
          }
          pwnd->pwndSibling = pwndNewBorn;
      }
  }
}
Despite the fact that the windowing structure was designed to be a binary tree, it hadn’t been implemented that way. Since the root window (the one representing the entire display) never has siblings and never has a title and since you can’t move hide or delete it, … (cut short for tl;dr)… that led somebody to decide that declaring an entire window structure was wasteful, and the wndRoot structure was replaced with pwndRootChildren, a simple pointer to the top level windows. Replacing wndRoot with a pointer may have saved a few bytes of data space, but the cost in code space was enormous.

Forgive me for copying all that out verbatim, but I think that the complete background is needed to make the point clear. Here’s the code that was supposed to be written that’s found later in the article:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* pwndDisplay points to the root-level window, which is
 * allocated during program initialization
 */
window *pwndDisplay = NULL;

void AddChild(window *pwndParent, window *pwndNewBorn)
{
  /* New windows may have children but not siblings... */
  ASSERT(pwndNewBorn->pwndSibling == NULL);

  /*  If Parent's first child, start a new sibling chain;
  *  otherwise, add child to the end of the existing
  *  sibling chain.
  */
  if (pwndParent->pwndChild == NULL)
  {
      pwndParent->pwndChild = pwndNewBorn;
  }
  else
  {
      window *pwnd = pwndParent->pwndChild;

      while (pwnd->pwndSibling != NULL)
      {
          pwnd = pwnd->pwndSibling;
      }
      pwnd->pwndSibling = pwndNewBorn;
  }
}

Any experienced programmer in C would have noticed two things:

  • There was a forced special case
  • The cost of the optimization was greater than the yield of the optimization

But anyone can see that. Its obvious because he said it. However, mentioned this common mistake to a couple of colleagues and said that I did make the same kind of mistake, and this is what they said:

Sometimes code that was written back then may be correct back then, but may not be correct now. Just as I wrote an optimization once because computers were not fast enough to handle a certain operation at the time. They do now so that piece of code actually slowed the program down. Also, Opera recently made its engine less memory intensive but more CPU intensive, but after complaints that Opera was taking too much memory, they changed it to be less CPU intensive and more memory intensive. It’s also a balancing act with more input from your users.

The first thing that came to my mind was “Are you listening?” I am not sure if they were trying out of kindness to make me feel better that I make these bugs because of very good reasons and that the badness is unforseeable or that they were just in their own world going off in a skew. Besides the fact that its clearly the latter and that this is not a tradeoff problem nor was it a “we needed it at the time” problem, since it should have been obvious that the supposed optimization was going to cost more than it was worth in memory space alone at the time of writing the code.

I, like many fellow humans am prone to thinking about the more negative side of this. Of course, this was meant to be a negative post, but on the flipside, I learned three mistakes about fellow programmers that I must remember not to make myself.

  1. Winging it
  2. Optimizing with a narrow view
  3. The code I write is always flawless. I’ll fix it later if I have to.

Firstly, winging it and not paying attention to the details of the problem is a fatal mistake I have been guilty of countless times, and have seen many people fall in to as well. our minds are complex-averse, and tend to try and group things into simple groups of things that share the same characteristics based off keywords in a conversation without really understanding it. In this case, my mention of optimization kicked off the ideas of past optimization and tradeoffs in my colleagues’ heads, and was unfortunately all that occupied their heads from that moment on.

Secondly, we programmers are often indulged in our own mindset and steamroll our way through because our egos are big and our power limitless. When we see something that could be good, like an optimization, we tend to bulldoze our way to make sure it gets done.

Thirdly, we programmers are idealists. Not just in the sense that we want everything to be perfect, but we see perfection in everything we write too. This blindness can cause a lot of grief, and the defence is usually “I had no choice at the time”, which is usually an excuse to cover up a more embarrassing mistake.

Finally, coming back to topic after a very very long strayoff, the whole idea of humans and sad facts of software is not the point. The point of the article from the book is to tell you someone’s mistake so you don’t make it, because if this one word of caution saved a bug in a simple subsystem, imagine the number of bugs that would be saved in a complex system of 100 subsystems. These are the kinds of articles books should be packed full of.

GWT: Next Level of Automation

| Comments

After playing a little with GWT, and attempting to add a map into my little webapp, I’ve found that this is really a very good idea. By applying a language to abstract all the small difficulties of programming a webpage for different browsers, you essentially move a larger percentage of the work into actually making the application.

Although GWT isn’t perfect, and to get my app up and running I had to spend about an hour or so searching the internet about fixing up some XMLs to import the libraries properly, once that was done, the source code that involved adding a map to the page and a little Javascript button coule fit on the screen, it is a huge step over having to deal with the difficulties faced by web programmers to make their sites both compatible with IE and Firefox.

Though I advocate using the minimum amount of cool new features on your site, GWT would be the next step toward progress with the current mess that is web application programming right now.

Attempt to Rush an RPG

| Comments

After reading an article on GameDev about a guy who managed to build an RPG in 40 hours, I decided I’d try my hand at doing an RPG 40 hours too, but in C#. So I started to write the first code on Saturday. After 10 hours of gruelling crunch and brainstorming, I was overwhelmed and realized that I had neither the skill nor discipline to actually make it in 40 hours. I didn’t even have the energy left to write a blog post about the start, much less record the process of doing it. However, I did get to the stage where I had a map and a character walking around somewhat and had a basic dialog system in place, but with no inventory, no stats, no objects, just character and some boring dialog box.

Thanks to the start however, I’ve now found myself with a half-complete RPG engine. I will upload an update sometime soon. Everything used to make the game is just the .NET framework and C# that comes with Visual Studio Express. Perhaps I should try going on for another 30 hours and see how far I can get…

Putting a Separator Between Your Elements

| Comments

Often when I’m programming, I’ll need to list a bunch of stuff and put commas between them. Like this:

1
1,2,3,4,5

Usually, this is what I, and most of my colleagues do:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
        List<int> nums = new List<int>();
        for (int i = 0; i < 5; i++)
        {
            nums.Add(i);
        }

        string msg = "";
        bool first = true;
        foreach (int num in nums)
        {
            if (first)
            {
                first = false;
            }
            else
            {
                msg += ",";
            }
            msg += num.ToString();
        }

After reading Eric Lippert’s little article about the horrid-seeming problem of commas and lists, I noticed him mentioning the method

1
String.Join

Needless to say, I went and tried it, and found that I could do the equivalent of the above, like this:

1
2
3
4
5
6
7
8
        List<int> nums = new List<int>();
        for (int i = 0; i < 5; i++)
        {
            nums.Add(i);
        }

        string msg = string.Join(",", nums.Select(x => x.ToString()).ToArray());
        Console.WriteLine(msg);

Its kinda amazing how after coding in C# for a good year now that I haven’t noticed the existence of such a method.

Okay, the lambda expression seems a bit messy with all the parens and all, but you get the idea. Still, its a lot better than writing a loop and having the evil “first” variable which kinda clutters the whole thing. Does anyone know an even better way of doing this?

Update: and for my answer to Eric’s next post:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
string msg = "{";
IEnumerable<string> s = something;

string[] arr = s.ToArray();

if (arr.Length > 1)
{
    string[] ar2 = {
               string.Join(", ", arr, 0, arr.Length - 1 ),
                arr[arr.Length - 1]
           };

    msg += string.Join(" and ", ar2);
}
else if (arr.Length == 1) msg += arr[0];

msg += "}";

Updated the B_pool!

| Comments

I’ve updated the b_pool again! This one has got some new features such as string functions (not yet complete) and a new b_resize function, which basically acts the same as realloc, except that if you are resizing the last block created on the pool, it will resize it without freeing. This makes it a lot faster and is perfect for string functions. I haven’t tested it yet and its too late at night for me to test it. If anyone would be so keen to write some tests that will break the b_resize function?

GIS Data for Topography and Shorelines and More

| Comments

I’ve found a site recently that provides data for free on the world’s shorelines and topography. They have got other datasets too that aren’t as complete, but would probably be of interest to those of you who wish to do research on it. For me, when I look at data like this I get the itch to write programs that process and present it. I might just do that eventually. keeps a note to self

Requesting Code Review

| Comments

So I’ve been working on a memory pool lately as a hobby project, and I’ve come across some things that I haven’t found a solution that would satisfy my gut yet. But, after reading this:

I started to realize that since I’m already on the internet, why not have people examine my code instead? To that effect, I’m asking everyone who’s not afraid of C and actually reads this blog to comment on my code. It can be found here:

http://bazaar.launchpad.net/~davidsiaw/bpool/trunk/annotate/head%3A/b_pool//b_pool.c

This is the center of the code development at the moment. I’ll add more comments later on how the pool is actually supposed to work. I’d like to know if there are any bad practices catchable from the outset. Thanks!

A Resource Pool Implementation

| Comments

After some interesting discussion with a friend, I’ve decided to try my hand at coding a resource pool like Apache’s APR pools. I’m gonna call my pool b_pool, which stands for bunny pool.

Its not going to be a copy of APR pools however, it will just by my idea of what a pool should be like. It will be able handle not only memory, but file handles, socket descriptors and other shared system resources and manage them. Thus, instead of calling it just a memory pool, I call it a resource pool.

You can check it out from LaunchPad using Bazaar version control.

1
bzr branch lp:~davidsiaw/bpool/trunk

Currently the only way to build bpool is by using Visual Studio 2008. I’ll check in some autogen scripts sometime later this week. Or someone can help me write a temporary makefile that I can merge into the tree ^_^.

This resource pool is meant to be used inside a subsystem that has a limited lifetime, but uses memory in a complex enough way to make tracking the lifetimes of objects allocated inside it difficult. The idea of a pool is that you create a pool just before you run the subsystem, and the subsystem will use the pool to allocate memory and other resources, in other words, allocate resources inside the pool. When the subsystem is no longer needed, the pool is destroyed, taking along with it all the resources it was used to allocate. The subsystem has the freedom to free memory if it wants to, or it can allocate memory to be used at a later time.

The b_pool is still in its infancy and I still have a lot of things I want to add to it such as string manipulation functions that use the b_pool, which would be tremendously useful if used together with a subsystem that uses strings a lot.

How do you use the pool?

Well right now there’s only one way to use it, and it can only pool memory at the moment. In order to create a pool, simply create a variable to hold a pointer to the pool and call b_create_pool

1
2
b_pool* pool;
b_create_pool(&pool);

When you are sure you are finished with it, you call

1
b_destroy_pool(pool);

This frees all the memory allocated in the pool.

In order for the subsystem to allocate memory in the pool, it needs to call the function b_alloc, which is basically a replacement for malloc, but it is used slightly differently.

1
2
3
4
5
void mysubsystem(b_pool* pool)
{
  char* mem1;
  b_alloc(pool, &mem1, 50);
}

b_alloc takes 3 parameters, it takes the pointer to the pool, a reference to the pointer to memory that it will assign to, and the size of memory requested. b_alloc will then fill in the pointer with an address where the requested memory has been prepared. It returns a number too, 0 for success and anything else for fail. I might add an enumeration later.

If you so wish to free the memory because you know you are finished with it, you can use

1
b_free(pool, mem);

Similar to free() in libc, b_free frees up memory to be allocated by somebody else again. Although this is optional as long as you destroy the pool when your subsystem has done its job, this is useful whenever you want to keep the memory usage to a minimum constantly, which is the case in memory-constrained environments like mobile phones.

So whats the difference between using a memory pool and malloc to allocate memory? Isn’t it just putting a big malloc and free around a set of function calls? It may seem absurd and unuseful on the outset, but the only rule you must definitely observe when using a pool is that you must Never make a global pool in your application, because that’s what your application address space already is. Essentially, yes. It is putting a big malloc and free around a set of function calls. But the usage of memory is simplified in the sense that you can ignore having to worry about trying to reuse memory that isn’t used anymore inside your subsystem, or resizing the amount of memory you allocated for your subsystem in order to let it store more data. All you need to do is ask for memory, which is one less worry in a low-level language.

It is also faster to have a userland routine manage your memory for you, since it does not incur the cost of changing privilege levels, which is expensive on most CPU architectures, and is required whenever you want to ask the OS to reserve memory for you. Eventually I will create more routines to allow the registration of destructors, deep copiers for other kinds of custom resources into the pool. I am also thinking of turning it into a layer over a set of OS resource requesting functions, so one can write subsystems that are platform-independant, and all one needs to do to use a subsystem on another platform is to implement the b_pool for that platform and use the subsystem.

So, have fun with experimenting with it and tell me what you think about it, or even, tell me your idea of what you think a resource pool should be like!