Double trouble

The key point to understanding the tricky syntax is to realize that when you’re creating a String literal in Java, backslashes are used to form escape sequences as well. Most people are familiar with this concept, when, for example, constructing a String that spans multiple lines:

final String multiline = "A String...\nOn two lines";

When calling Pattern.compile, you pass in a String literal that is the regular expression. However, regular expressions also use the backslash character to begin escape sequences. So, to ensure that the regular expression engine in Pattern gets the correct syntax, you must replace every backslash in your regular expression with two backslashes. This is to prevent Java from interpreting the single backslash as just a String escape sequence.

Or, put another way, if you wanted a String with the contents "\n", that is a String with a backslash followed by the letter ‘n’, you’d have to define it as:

final String newLineEscapeSequence = "\\n";

This is the gist of it; we need to pass in the preserved backslashes into the Pattern regular expression engine, so you have to create a literal backslash by using a double-backslash in your String literal. This information is in the Pattern Javadoc, but it’s sort of buried beneath loads of regular expression syntax.

Keep this in mind when constructing your regular expressions outside of Java in a tool like RegExr. These principles also apply when using other classes/methods that use Pattern, such as String.split() or Scanner.useDelimiter()

An example

Here’s a simple example where we try to find the word “The” at the beginning of a String, delimited by a word boundary matcher.

public class PatternExample {
  private static final Logger LOGGER =
      Logger.getLogger(PatternExample.class);
  private static final String TEST_STRING =
      "The quick brown fox jumps over the lazy dog";

  public static void main(final String[] args) {
    System.out.println(TEST_STRING);

    final Pattern wordBoundaryWrong = Pattern.compile("^The\b.*");
    Matcher matcher = wordBoundaryWrong.matcher(TEST_STRING);
    LOGGER.debug(matcher.matches()); // false.

    final Pattern wordBoundaryCorrect = Pattern.compile("^The\\b.*");
    matcher = wordBoundaryCorrect.matcher(TEST_STRING);
    LOGGER.debug(matcher.matches()); // true.
  }
}

The key point here is that the word boundary matcher (\b) must be passed in as a String literal of "\\b" so that the backslash is properly interpreted. In the incorrect Pattern, "\b" maps to a backspace character literal.

I think the reason this concept is somewhat tricky is that you have to deal with two levels of escaping – the Java String literal syntax and the Regular Expression syntax.

Long story short, I just had to implement it (albeit a simple version) in JavaScript. The result is available on my website and I suggest you give it a try; a good pattern to start out with is the F-pentomino.

The reason I find emergence so interesting is that it provides a possible framework or explanation for the complexity and order seen in our universe, based on a fairly simple or rudimentary set of rules.

One to rule them all

The interactions seen in Conway’s Game of Life can be fairly complex and are not straightforward to predict. However, they all result from a simple set of rules:

• Each square is labeled as a cell, and has eight neighbours.
• A cell can either be “dead” or “alive”.
• A dead cell turns alive on the next turn if it has exactly three alive neighbours.
• A live cell continues to live on the next turn if it has 2 or 3 alive neighbours.

Thus, during each iteration, the state of a cell (alive or dead) is determined from the state of its neighbours on the previous turn.

Complexity from simplicity

Despite this limited ruleset, complex behaviour can be seen in the interaction between cells. In fact, quite a lot of study has been put into understanding the interactions and categorizing the various “structures” that have emerged in game.

Simulating the game on a large scale can take a lot of CPU power, so some interesting dynamic programming techniques have been utilized to increase the iteration speed. One of them is Hashlife, which exploits the repeatability and determinism in the game.

For example, if a pattern shows up an in an early stage of the simulation, it’s “evolution” can be tracked and stored so that if the same pattern ever shows up again, it’s long(er) term fate will already be known, since it was already computed earlier. This prevents unnecessary iterations in the simulation. This sort of technique is called memoization.

In Real Life

Obviously, our universe is probably more complex than the Game of Life. (It would likely have to be, since the simulation exists within our universe) But it’s also likely that all the complex interactions and structures observed in our universe boil down to some set of rudimentary rules. The point of science, in many respects, is connecting the dots that allow us to understand how these higher-level properties emerged from lower-level interactions. I’m not saying that it will provide all the answers or explain things like self-awareness, but to me, that sort of emergence is the real beauty of our universe.

The astute among you will know that one way is by implementing the Fisher-Yates shuffle algorithm. But, let’s investigate what happens when other, seemingly adequate solutions, are used instead.

Shuffler’s dilemma

One example that highlights the implications of using seemingly random and unbiased “shuffling” involves the Windows EU Browser Ballot.

The purpose of the Browser Ballot was so that Microsoft could comply with an EU directive that ordered them to provide users with a clear choice of which browser to use with Windows. The ballot was supposed to have been carefully designed; the first section contained the five most common browsers (Chrome, Firefox, Internet Explorer, Opera and Safari) with the second section containing seven lesser-used browsers.

Since it is generally considered an advantage to be placed first in a ballot (because users who don’t care one way or another might just pick the first option), the EU directed Microsoft to randomize the order in which the browsers appeared on the ballot in each of the sections. Thus, when users visited the ballot page, they were supposed to get a random ordering of the top five browsers followed by a random ordered of the lesser seven.

Looking into the cards

The team in charge of the ballot design came up with a solution to use a sorting function with a randomized comparator. In this way, they hoped to apply a randomized sort to the list of browsers, producing a random ordering that met the rules of the EU. While this did produce a random ordering, (and thus technically was in compliance with the EU directive), it did not produce unbiased results, as the ordering of some browsers came up more often than others. This lead to allegations that Microsoft was trying yet again to stifle its competition to unscrupulous practices.

However, this probably wasn’t the case, and was likely an instance of a seemingly adequate solution being used without proper testing/analysis.

To understand the problem, we first have to understand sorting algorithms, specifically those that use comparisons as their basis. (i.e. comparison sorts) An example of a comparison sort is Insertion sort. Through each step of the sorting process, the sorted portion of the list increases by one as we take the next element from the unsorted portion and position it properly within the sorted portion. This is done by comparing the element to be inserted with each element in the sorted portion until we find the correct position.

A comparator is simply a function that compares two objects, and tells us which one is greater than the other, or whether they are equal. In Java, the general structure of a Comparator would be:

new Comparator<T>() {
  @Override
  public int compare(final T o1, final T o2) {
    // If o1 is "less than" o2, return a negative integer.
    // If o1 is "equal to" o2, return 0.
    // If o1 is "greater than" o2, return a positive integer.
  }
};

In this way, the exact semantics of comparisons can be tailored to meet the needs of the application. In the case of the Browser Ballot, the team implemented something akin to the following: (Though the language was JavaScript, not Java, as the Browser Ballot was a website)

new Comparator<T>() {
  @Override
  public int compare(final T o1, final T o2) {
    return Math.random() < 0.5 ? 1 : -1;
  }
};

In this comparator, the objects being compared are not even considered; instead the either -1 or 1 is returned with equal probability. Using this sort of “comparison” with a sorting algorithm might seem to provide random, unbiased results – but in reality, such “common sense” did not make so much sense after further analysis.

Looking deeper

To look at the problem a bit more in-depth, I decided to write an example in Java that would test the results of a “random sort” on a set of four objects, using the following sorting algorithms: A modified Merge sort (provided by Java’s Collections.sort()), Quicksort, Insertion sort and Selection sort. These results would then be compared to using the proper method, a Fisher-Yates shuffle.

Some more details:

• The list to be shuffled started off with the ordering of [1, 2, 3, 4]
• I used my own implementation of Quicksort that just selected the pivot from the middle of the list.
• Bubble sort was not considered, since with a randomized comparator, the algorithm may never terminate!

Here are the results:

As you can see, the Fisher-Yates shuffling algorithm produces the expected near-uniform distribution, represented by the almost-straight line. The “randomized” sorting algorithms most definitely did not produce a uniform distribution. Interestingly, the modified merge sort used by Collections.sort() produced the same distribution as Insertion sort; This may mean that this specific implementation of merge sort uses an insertion sort when the collection size is sufficiently low.

Of the sorting algorithms tested, Quicksort had the least difference between the “peaks” and “troughs”, though the bias was still very evident. I’ve heard that Quicksort may produce a near-uniform distribution when used with a randomized comparator, but I’m guessing that would depend greatly on the choice of pivot.

Conclusion

Randomization is never an easy thing; one must fully consider the effects of a specific algorithm before jumping to conclusions as “common sense” doesn’t really make much sense in this area. Come to think of it, “common sense” is rarely sensible.

Careful analysis is always needed whenever dealing with distribution of random variables. In general, for a random variable A that has a certain distribution, f(A) is not guaranteed to have the same distribution. This is the point that was missed when designing the ballot.

Analysis of the Fisher-Yates algorithm is fairly easy: The reason why it works is that at each step of selecting an element from the collection, each remaining element has an equally-likely probability of being selected. Analysis of each of the randomized sorting algorithms to understand why each distribution was produced is more difficult, and is left as an exercise to the reader.

It’s also worthwhile to note that the correct shuffling algorithm (Fisher-Yates) runs in O(n) time, while all of the randomized sorting algorithms have a longer asymptotic run time.

This isn’t going to be an indictment of bad programming; in fact, I think it’s good if you can look back at your old code and see where it could be improved. Such a process suggests that you are continually self-improving, a skill crucial in software development. Besides, all of us have made a mistake or two at times when we were stressed, tired or just plain not thinking straight.

However, there’s one mistake that I’ve seen that I think warrants bringing to light, and that is the misuse of the Flyweight pattern.

Who wants to be a Flyweight?

Flyweight is typically used to describe one of the smaller weight classes in boxing or other fighting sports. This “minimal” aspect is what is shared with the design pattern of the same name. Simply put, a Flyweight object is one that reduces memory use by sharing common data with other objects. Despite this plain definition, implementing the Flyweight pattern can be tricky.

Perhaps this is why I have seen examples like this: (Java pseudo-code below; may not compile, but you shouldn’t use it anyways)

public class WidgetWithManyFields() {
  private Data field1;
  private String field2;
  private int field3;
  // A lot more fields...
  private SomeOtherData fieldN;

  // Getters and setters...
}

Now, obviously the memory footprint of WidgetWithManyFields can be quite large, and since not all aspects of an application will need access to all data fields, it was decided that a “Flyweight” was needed:

public class WidgetFlyweight() {
  // Only these fields are needed.
  private Data field1;
  private String field2;

  public WidgetFlyweight() {
    // Default constructor.
  }

  // Constructor to make one from the regular widget class.
  public WidgetFlyweight(WidgetWithManyFields widget) {
    this.field1 = widget.getField1();
    this.field2 = widget.getField2();
  }
  // Getters and setters...
}

This isn’t really the Flyweight pattern at all. In fact, I don’t even know if it is a pattern at all. It might be considered something like the Proxy pattern, if the “Flyweight” class contained an instance of the regular class. But I don’t really know.

So what is a Flyweight?

Consider the example of a document that can have images embedded in it. There might be multiple copies of the same image present in the document, but each copy would be sized and positioned differently within the document.

In this case, you wouldn’t want to load and store the data in memory for multiple copies of the same image as that would be wasteful. However, each instance of the image displayed in the document might be formatted or positioned differently. How might this be done?

Firstly, some assumptions:

• An image is uniquely identified by some resource path.
• The underlying image data does not change during the lifetime of the application.

With these assumptions, we can define three classes that allow us to implement the Flyweight pattern.

Firstly, an ImageData class that encapsulates the actual image data. There should be only one canonical instance of this class for each unique resource path. Because of this, we can pool these objects for reuse.

However, the ImageData objects won’t be directly used by other parts of the application. Instead, we create an ImageFlyweight class that is manipulated. Each instance contains a reference to a canonical ImageData object and also stores information about how to format and position the image.

In this way, there can be multiple ImageFlyweight instances that reference the same image and hence the same ImageData instance, but each instance would define separate formatting and positioning details.

Tying everything together is a factory (ImageFlyweightFactory) that maintains the pool and is the access point for getting instances of ImageFlyweight.

Below is the code: (Sorry, it’s a lot of code to throw at you at once, but I didn’t feel like breaking it down into separate chunks, and you can just copy & paste it into your favourite IDE for inspection/compilation)

/**
 * Copyright (c) 2012 Peter Chng, http://unitstep.net/
 */
package net.unitstep.examples.flyweight;

import java.util.HashMap;
import java.util.Map;

/**
 * In order for the Flyweight Pattern to be effective, ImageFlyweight instances
 * should only be obtained via ImageFlyweightFactory.getImageFlyweight().
 *
 * This ensures that for each unique resource path, there is only one instance
 * of the backing ImageData existing in the application.
 *
 * @author Peter Chng
 */
public class ImageFlyweightFactory {
  private Map<String, ImageData> imageDataPool =
      new HashMap<String, ImageData>();

  public ImageFlyweight getImageFlyweight(final String resourcePath) {
    // This will return a new ImageFlyweight object each time; however, the
    // backing ImageData might be shared across multiple ImageFlyweight
    // instances.
    return new ImageFlyweight(this.getImageData(resourcePath));
  }

  private ImageData getImageData(final String resourcePath) {
    ImageData imageData = this.imageDataPool.get(resourcePath);
    if (null == imageData) {
      imageData = new ImageData(resourcePath);
      this.imageDataPool.put(resourcePath, imageData);
    }
    return imageData;
  }

  /**
   * @return the current count of ImageData instances in the pool; only for
   *         testing purposes.
   */
  public int getImageDataPoolCount() {
    return this.imageDataPool.size();
  }

  /**
   * Will contain the data representing an image loaded from some resource, i.e.
   * the file system.
   *
   * This is a private inner class because it should never need to be used
   * externally by callers. It is considered an implementation detail.
   *
   * We assume that the resource path is the uniquely-identifying aspect of an
   * image and that the underlying image resource/data will not change over the
   * lifetime of the application.
   *
   * Thus, only one instance of the ImageData class is needed for each image
   * uniquely identified by its resource path.
   *
   * @author Peter Chng
   */
  private class ImageData {
    private final byte[] data;
    private final String resourcePath;

    public ImageData(final String resourcePath) {
      this.resourcePath = resourcePath;

      // Image data would be loaded here based on the resource path supplied.
      // For brevity, it's not really done.
      this.data = new byte[] {};
    }

    public byte[] getData() {
      // Note: If we really intend to make this class immutable, we should
      // return a defensive copy instead so that callers cannot modify the
      // data stored in this instance.
      return this.data;
    }

    public String getResourcePath() {
      return resourcePath;
    }

    // Note: Not strictly necessary to override equals() and hashCode() for this
    // example, but it's done to indicate we only consider the resource path
    // in determining equality.
    @Override
    public boolean equals(final Object object) {
      if (null == object) {
        return false;
      }
      if (object == this) {
        return true;
      }
      if (object.getClass() != this.getClass()) {
        return false;
      }
      return this.resourcePath.equals(((ImageData) object).getResourcePath());
    }

    @Override
    public int hashCode() {
      return this.resourcePath.hashCode();
    }
  }

  /**
   * The ImageFlyweight object contains a reference to a canonical ImageData
   * object containing the actual image data we wish to render.
   *
   * By making this a static inner class of {@link ImageFlyweightFactory} and
   * the constructor private, instantiation of this class can be controlled and
   * limited to only the {@link ImageFlyweightFactory}. Callers MUST obtain an
   * instance of the ImageFlyweight through the factory and not by direct
   * instantiation.
   *
   * It also contains other properties that will affect the rendering of the
   * image in the application, such as height, width and position.
   *
   * Reusing the same ImageData object across different ImageFlyweight instances
   * allows us to display the same image in different ways within the
   * application, without having to load (or store in memory) the image data
   * multiple times.
   *
   * @author Peter Chng
   */
  public static class ImageFlyweight {
    private final ImageData imageData;

    private int height;
    private int width;
    private int positionX;
    private int positionY;

    private ImageFlyweight(final ImageData imageData) {
      this.imageData = imageData;
    }

    public byte[] getData() {
      return this.imageData.getData();
    }

    // Getters/setters for height, width, positionX, positionY...

    public int getHeight() {
      return height;
    }

    public void setHeight(int height) {
      this.height = height;
    }

    public int getWidth() {
      return width;
    }

    public void setWidth(int width) {
      this.width = width;
    }

    public int getPositionX() {
      return positionX;
    }

    public void setPositionX(int positionX) {
      this.positionX = positionX;
    }

    public int getPositionY() {
      return positionY;
    }

    public void setPositionY(int positionY) {
      this.positionY = positionY;
    }
  }
}

Everything is contained within the ImageFlyweightFactory class, because the ImageData class does not need to be visible to outsiders and callers should not be able to instantiate ImageFlyweight instances on their own.

With this code, we have a simple test harness to verify whether it’s working:

/**
 * Copyright (c) 2012 Peter Chng, http://unitstep.net/
 */
package net.unitstep.examples.flyweight;

import net.unitstep.examples.flyweight.ImageFlyweightFactory.ImageFlyweight;

import org.apache.log4j.Logger;

/**
 * @author Peter Chng
 */
public class ImageFlyweightTest {

  private static final Logger LOGGER =
      Logger.getLogger(ImageFlyweightTest.class);

  public static void main(final String[] args) {
    final ImageFlyweightFactory factory = new ImageFlyweightFactory();

    final String resourcePath1 = "/path/to/images/someImage.png";
    final String resourcePath2 = "/path/to/images/anotherImage.png";

    final ImageFlyweight image1 = factory.getImageFlyweight(resourcePath1);

    displayImageDataCountInPool(factory);

    final ImageFlyweight image2 = factory.getImageFlyweight(resourcePath2);

    displayImageDataCountInPool(factory);

    // Should not create an new ImageData instance in the pool.
    final ImageFlyweight image3 = factory.getImageFlyweight(resourcePath1);

    displayImageDataCountInPool(factory);
  }

  private static void displayImageDataCountInPool(
      final ImageFlyweightFactory factory) {
    LOGGER.debug("Current number of ImageData instances: "
        + factory.getImageDataPoolCount());
  }
}

Running the code yields the following results:

DEBUG ImageFlyweightTest - Current number of ImageData instances: 1
DEBUG ImageFlyweightTest - Current number of ImageData instances: 2
DEBUG ImageFlyweightTest - Current number of ImageData instances: 2

The key point is that after the third ImageFlyweight object is created, the count in the ImageData pool does not increase since the same image has already been “loaded”.

Other examples

Note that Java itself implements something similar to the Flyweight pattern for Strings; this is known as string interning and many other languages support this feature as well.

Basically, because Strings are immutable, Java can store each distinct value in a pool and then reuse these instances when appropriate. As an example, the following code displays “EQUAL”:

String string1 = "A test of the string intern pool.";
String string2 = "A test of the string intern pool.";
// Note that we are comparing object identity, NOT equality.
if (string1 == string2) {
  System.out.println("EQUAL");
} else {
 System.out.println("NOT EQUAL");
}

Note that this doesn’t work if you directly create a String using the new keyword.

Conclusion

I know that this was a fairly contrived example (aren’t they all?), but I hope it provided the basics of the Flyweight pattern to readers. There are a lot of holes and I don’t suggest you directly copy this example for production code, but instead learn the skills to effectively develop the pattern on your own.

As always, I welcome questions or comments and especially corrections if I’ve made a mistake! Thanks for reading!

They’ve fallen off of my face more than once, have tumbled many times to the hardwood floor from my nightstand while I fumbled for them in the dark, been lost in my bed covers and rolled onto during numerous occasions, and of course I’ve fallen asleep with them on more times than I can remember. Despite all of this, they not only held together, but retained much of the original lustre and remain in excellent condition.

Only one of the earpieces is starting to look worn, the nose pads are looking a little old and one of the lens screws had to be replaced when it fell out and got lost, but other than that, they’re as good as new. This was the first “thin” pair of glasses I had ever worn and I initially had some reservations about durability, so I’m more than pleased with how well they’ve held up. (I think the frames are made up of some titanium, but I can’t remember)

But this past weekend, I decided it was time to finally replace them.

We’ve had a good run, old friend, but I’m afraid it’s time to part ways.

I went down to the local Pearle Vision since it was close and seemed to have a decent selection of frames. In fact, I found there was just too many options. Many of them were easily ruled out, but I still ended up spending over an hour trying on frames with fingerprints and smudges all over the lenses in an effort to find the right pair. Or, rather, the right pairs, since they had this screwed up pricing that basically forced you to buy two pairs at once since you hardly saved anything by buying a single pair.

The problem with selecting glasses (besides my indecisiveness, aggravated by the multitude of options) is that it’s hard to know how well they’ll do or look over the long run. Durability is important to me, and certainly some frames “felt” more durable than others, but that’s not really a sound way of assessing things. I guess I’m just expecting these new frames to last as long as the previous ones did, because I find it hard to change “styles”.

The other problem is that it’s hard to tell what you look like in them if you don’t wear contacts – thankfully this isn’t a problem for me; I’d be nearly blind without corrective vision.

Eventually, if you try on enough frames and stay in the store for long enough, almost all glasses start to look acceptable. This is because style and attractiveness are both subjective and tend to be swayed one way or another by overexposure. It’s almost as if your subconscious is overriding your critical thinking in an effort to get you out of the store and on your way.

You need to know when this effect is taking a hold of you, so I suggest the following: Within five minutes of entering the store, identify and try on a pair of frames that look utterly ridiculous on you. Then, put these back; don’t worry, you definitely won’t be getting these. After you’ve been in the store for an hour or so, and you’re noticing that most frames you’re trying on are looking good, go back and try on the hideous pair.

If the hideous pair now look attractive or even slightly better than before, your judgment has already been compromised. Either leave and come back another day or take your chances with a pair that you found attractive early on during your search. This is what I did.

I should be getting the new frames within a few days. Hopefully I wasn’t judgment-impaired when I made my choice.

I took a new approach to training and really dedicated myself to it. There were many mid-week 4 AM mornings, followed by 1.5-2 hour runs in the dark, snow/rain and wind. I arrived at the starting line being as prepared for any race as I’d ever been.

However, I failed to meet my goal time of a sub-3:03 marathon, finishing in only 3:07:20. I made several mistakes early on and fell behind the pace within the first 10 km. However, I was most disappointed in myself for not pushing harder. I felt that I had mentally “checked out” after the first half, and consciously or not, believed that meeting my goal was now impossible due to the early mistakes. Because of that, I felt that I didn’t try as hard as I could and that I did not give 100% for fear of failure. It was almost as if I had sabotaged myself into thinking, “If I don’t give 100% and miss my goal, well at least then I will have an excuse.”

I fell into a pretty big slump after Boston and didn’t/couldn’t run for almost a week after. Even when I did start again, things just weren’t the same – my confidence had been shattered. I knew I had to break out of this slump, so I signed up for the Mississauga Half Marathon, which was about a month after Boston, to give me something to shoot for.

Why the half? Simply put, I didn’t think I’d be ready for another full so soon – not just physically, but mentally as well. If I were to run the full, I would have wanted to aim for a sub-3:05, in order to get in on the first week of registration for 2012. However, I didn’t feel that I would have the mental toughness required to meet that time and couldn’t deal with the heartbreak of another missed goal. So, I decided on the half, a distance I felt comfortable with.

Things turned out great – though the conditions were looking windy/rainy, things actually were not that bad, and I was able to pull of a huge PR, finishing in a time of 1:24:02 in the Mississauga Half Marathon, well ahead of any goal I’d had. This was good enough for 4th in my age group. Suffice to say, this was a huge confidence booster, something I sorely needed.

Edmonton Marathon

Coming off my performance at the Mississauga Half, I felt elated and immediately signed up for the Edmonton Marathon, which takes place on August 21st of this year. This would give me two weeks of downtime before I would have to start a 12-week training schedule for it. 12 weeks might seem a little short, but I actually think it’s pretty close to optimal considering my present situation. I felt that the 18-week program I used for Boston was perhaps a little long, and something between 14-16 weeks would have been better.

Given that I’m coming off a good base established by my Boston training (though not reflected in my performance there, but instead at the Mississauga Half), I feel that 12 weeks is more than enough to be ready for Edmonton, provided I stick to the plan, rest/recovery well and not over do things.

Edmonton will be my last chance to qualify for Boston 2012, since registration starts in early September. Technically, I’m already “qualified” for Boston 2012, but I don’t believe my time will be fast enough to actually allow my entry accepted. Complicated story aside, most runners I’ve talked to have thought that you’ll need to have at least BQ-5 (that is, your Boston Qualification time minus 5 minutes) in order to have a chance to get in, so I’ll be aiming for a sub-3:05 finish.

Running a marathon is no easy task. You train for months and basically have once chance to prove yourself. I don’t deal well with pressure, and I choked at Boston this year. I’m trying to avoid that this time in Edmonton.

Edmonton has the advantage of being a flat course, and the climate is not known for its hot summers. When I ran it back in 2009, the starting line temperature was only around 8C with a finishing temperature of 16C. This is pretty close to ideal. However, there are only so many things one can control.

Training doesn’t guarantee any performance; it can only increase the chances of reaching your desired goal. I have accepted the fact that I may give 100% this time and again fail to meet my goal – that is just part of the game. You can’t be afraid to fail if you want to achieve something.

Site updates

Yet again, I’ve fallen behind with keeping this site up to date with articles and guides. It’s not that I don’t have any ideas, it’s just that I’ve been lazy to make the time to put them together. A combination of work, training and life has yet again provided me with the excuse to not further this site with articles that may be of importance to readers.

Writing tutorials and other informational articles is as much a help to me as it is to those who read them, so I will be putting more effort towards this. I hope that you have enjoyed the few that I have written this year.

However, when I received the package from Dell, I was surprised at the size. It came in a huge 18″x13″ bubble envelope:

I thought it was just excess shipping packaging, but opening the enveloped made it clear that the packaging was only just big enough to hold the actual item:

For batteries with packaging that seems to imply they’re good for the environment, you think they would have made the packaging a little less excessive. The packaging is still 100% recyclable, but it still costs energy to make it.

At least Dell didn’t put the already-large item in a huge shipping box.

When calling methods, primitive data types are passed by value, while objects and arrays are passed by reference. This means when you call a method with an object as a parameter, you are merely providing that method a way to access/manipulate the same object via a reference; no copy is made. Contrast that with primitives: When calling a method that requires them, a copy of that value is put on the call stack before invoking the method.

In that way, references are somewhat like pointers, though they obviously cannot be manipulated by pointer arithmetic. But what about weak references? What are they, and how do they contrast with strong references?

Weakly understood

Based on my experience, the concept of weak references, or more generally reachability, is not one that is well-understood in the Java world. At least I did not have a good grasp of them until stumbling upon some sample code one day. It may be that the need to utilize them is outside the confines of most day-to-day programming tasks, as the concept is fairly low-level. Nonetheless, it’s an important concept to understand.

Basically, Java specifies five levels of reachability for objects that reflect which state the object is in, in relation to being marked as finalizable, being finalized and being reclaimed. They are, in order of strongest-to-weakest:

1. Strongly Reachable
2. Softly Reachable
3. Weakly Reachable
4. Phantom Reachable
5. Unreachable

An object’s normal state, as soon as it has been instantiated and assigned to a variable/field is strongly reachable. Chances are, these are the only types of objects you’ve worked with. We’ll first cover the concept of weakly reachable objects, as I believe it provides a good base for understanding the remainder.

Cleaning out the trash

Going by the API reference, a weakly reachable object is one that can be reached by traversing (i.e. going through) a weak reference. That’s a succinct definition to be sure, but it just raises the next question: What is a weak reference?

Simply put, if an object can only be reached by traversing a weak reference, the garbage collector will not attempt to keep the object in memory any more than it would an object with no references to it, i.e. an object that cannot be accessed. Thus, from the garbage collector’s point-of-view, a weakly-referenced object will eventually be cleaned from memory the same as an object no references to it.

So, if weakly-referenced objects are treated the same as completely non-referenced ones, what is the purpose of the weak reference? A good example is the WeakHashMap, a class provided by Java.

WeakHashMap

Unfortunately, WeakHashMap may also be poorly understood, probably as a result of weak references not being well known. WeakHashMap may at times be described as a “cache” of sorts, where objects/entries that are not used will be removed to decrease memory usage. This is not how WeakHashMap works at all.

The best way to describe a WeakHashMap is one where the entries (key-to-value mappings) will be removed when it is no longer possible to retrieve them from the map. For example, say you’ve added an object to the WeakHashMap using a key k1. If you now set k1 to null, there should be no way to retrieve the object from the map, since you don’t have the key object around any more to call get() with. This behaviour is possible because WeakHashMap only has weak references to the keys, not strong references like the other Map classes.

Note that for the WeakHashMap to work this way, as it was intended, the key objects must only be considered equal if they are actually the same object – i.e. object identity instead of mere equality. This is the default behaviour for Object.equals() and Object.hashCode(), so if these methods have not been overridden, the object is OK to be used as a key in WeakHashMap. Objects like Integer are not suitable for use in WeakHashMap, because it is possible to create two separate (non-identical) objects that are both equal:

final Integer i1 = new Integer(4);
final Integer i2 = new Integer(4);
LOGGER.debug("i1.equals(i2): " + i1.equals(i2)); // True.
LOGGER.debug("i1 == i2: " + (i1 == i2)); // False.

Another point of importance is that String is not a suitable key for a WeakHashMap as well. In addition to its overriding of equals() and hashCode(), String objects in Java are also interned (i.e. stored) in a pool by the JVM when created. This means that they may remain strongly referenced even after you have apparently gotten rid of your reference to them. Because of this, entries that you add to a WeakHashMap using String keys may never get dropped, even after you have apparently lost reference to the keys, since the Strings may remain strongly referenced in the string intern pool.

An example of String interning:

final String s1 = "The only thing we have to fear is fear itself.";
final String s2 = "The only thing we have to fear is fear itself.";
LOGGER.debug("s1.equals(s2): " + s1.equals(s2)); // True.
LOGGER.debug("s1 == s2: " + (s1 == s2)); // May also return true!

String objects are interned for performance reasons, so when you are going to create a new String, Java first checks if there is a String in the pool that is “equal” to the one you are creating. If such a String exists, the existing object is just returned instead of having to instantiate a new object. This is possible because Strings in Java are immutable, i.e. operations that appear to modify a String (such as concatenation, toUpperCase(), etc.) really return a new String object while preserving the original.

The last usage note is that even though the keys are weakly-referenced by WeakHashMap, the values remain strongly-referenced. Thus, you must take care to not use value objects that strongly reference the keys themselves, as if this happens, the keys/entries will no longer be automatically dropped because a strong reference may always exist to the keys. (This can be avoided by wrapping the value object in a WeakReference, so that both keys and values are weakly-referenced when in the WeakHashMap)

Example use of WeakHashMap

Here is a brief, albeit contrived example of WeakHashMap at work:

// SampleKey is just an object that holds a single int. (Use instead of
// Integer, since Integer overrides equals() and hashcode())
SampleKey key = new SampleKey(42);
SampleObject value = new SampleObject("Sample Value");

final WeakHashMap<SampleKey, SampleObject> weakHashMap = new WeakHashMap<SampleKey, SampleObject>();
weakHashMap.put(key, value);

// At this point, we still have a strong reference to the key. Thus, even
// though the key is weakly-referenced by the WeakHashMap, nothing will
// be automatically removed even if we give a hint to the GC.
System.gc();

LOGGER.debug(weakHashMap.size()); // Will still be '1'.
LOGGER.debug(weakHashMap.get(key)); // Will still be 'Sample Value'.

// Now, we if set the key to null, the entry in weakHashMap will eventually
// disappear. Note that the number of times we have to 'kick' the GC
// before the entry disappears may be different on each run depending
// on the JVM load, memory usage, etc.
key = null;
int count = 0;
while(0 != weakHashMap.size())
{
  ++count;
  System.gc();
}
LOGGER.debug("Took " + count + " calls to System.gc() to result in weakHashMap size of : " + weakHashMap.size());

Finishing up

In an upcoming article, I plan on covering the other types of references (soft and phantom) as well as the associated Reference classes in Java. I wanted to keep this post brief so that it provided a basic understanding of the situation.

Changes/Fixes

• 2011-04-10: Fixed numerous incorrect usages of the term “dereference”. Thanks to Ranjit for the explanation.

References

1. Package java.lang.ref
2. WeakHashMap
3. Understanding Weak References

Mercurial is my distributed revision control system of choice, a trait I picked up at my previous job. I haven’t had the opportunity to deal with Git for any period of time, so I can’t comment on the various “Why X is better than Y” arguments out there.

Most of you using Mercurial/Hg (or revision control in general) will be familiar with the concept of merging, where the changes in a source branch are merged into a target branch, creating a new revision or changeset on the target branch. But what about the times when you would like to combine two or more changesets/revisions into a single one that has the combined/overall changes of all of them? In that case, the Mercurial Queues extension provides for the concept of folding, which accomplishes just that.

Mercurial Queues

The Mercurial Queues extension (mq) is one of the most useful Hg extensions available, as it allows for much more than folding. Basically, mq allows you to import changesets to a patch queue, where they can be manipulated. In this way, previously immutable changesets can be modified. One such modification is the concept of folding, where one more more changesets are combined to produce a single changeset with the equivalent effect.

Proceed with caution

Because mq can directly modify changesets (i.e. revision history), it can have adverse on your Hg repository; data can be permanently lost, since the changes that can be made cannot be “backed out” or “reverted”. I strongly recommend cloning your Hg repo before undertaking any actions with Mercurial Queues for the first time, if only for peace of mind and the fact that cloning is such an easy operation with Mercurial.

The case for folding

Generally, it’s not a good idea to go and change revision history, which is what folding does. The purpose of revision control is to preserve history and provide a timeline for how the codebase has evolved. In the case of Mercurial, it’s especially troublesome to go and modify revision history on a central server that others are pushing to/pulling from, as this may cause inconsistencies. Having said that, there are times when combining multiple changesets into one may be beneficial.

Some examples that come to mind are:

• You have made many intermediate commits to your local Hg repository during development, but would like to combine them into a single one before pushing to a remote/central repository for clarity. (The multiple local commits were for your own sake)
• You accidentally committed some sensitive data (i.e. hard-coded passwords) to a repository, followed by some other changes that also removed that sensitive data. You don’t want to strip the intermediate (password-containing) revision because of the subsequent work. You can combine the two to one revision that contains the subsequent work but no record of the sensitive data.

Folding will help in both situations.

Tutorial

This tutorial will cover folding using TortoiseHg, the popular GUI front-end for Mercurial. Before getting started, you’ll have to ensure that you don’t have any uncommitted changes, as you won’t be able to accomplish some of the steps with outstanding changes.

Open up the Repository Explorer. Below, you can see the example one, with our initial commit, which contained the sensitive data, followed by another that removed it. We’ll merge them into one.

Next, you’ll need to enable the Mercurial Queues extension, either through the TortoiseHg UI or by manually editing your mercurial.ini file or per-repo setting file. (.hgrc) Below, I’ve shown it in the UI: You need to check off the “mq” box under “Extensions”.

You’ll need to close the Repository Explorer and re-open it for the mq extension to take effect in the UI.

Next, select the oldest changeset and then right-click the newest one; in the context menu, select “Import from here to selected MQ”.

Then, open the Patch Queue by clicking its icon or selecting View > Patch Queue from the menu.

You should be able to see the changesets in your patch queue on the left side drawer. They’ll be labeled 0.diff, 1.diff, etc. You can also see which patch corresponds to which changeset because the imported changesets will have be labeled in the UI with qbase, qtip, 0.diff, 1.diff, etc. (They are listed in the patch queue in opposite order)

Now, right-click the top/oldest one in the patch queue, and select “Goto”. This will bring you back to the oldest changeset and remove the previous ones from your repository. But don’t worry, the changesets still exist in your (mercurial) queue.

Now, right click the next oldest one (which was removed from your repository), click “Fold” and then “Yes”. This will effectively fold or combine the two changesets into a single one with the equivalent changes/effects. Please note that this operation cannot be reversed, so make sure you really want to do it. (You did clone/backup your repository before starting, right?)

You can now adjust the commit comment/message and username, if you like, by clicking “Commit” or by selecting Tools > Commit from the menu. You may need to select View > Advanced to change/show the username. By default the commit message of the folded/unified changeset is an aggregate of the changesets that were combined to form it. You’ll probably want to adjust this down to something more meaningful.

After you are done, be sure to click “QRefresh” before closing the window.

After you’ve done the folding and modifying the commit message, you can right click the patch file (0.diff in this case) and select “Finish Applied” to put the folded/unified changeset back into your repository.

Your MQ patch queue should now be empty and the repository browser should show only one changeset, with your updated comments and no MQ tags/labels on the changeset. You can close the patch queue sidebar now, if you’d like.

There! Now all evidence of your nefarious activities has now been removed. Only the beginning and the end remain. Use wisely.

With that in mind, I thought it’d be useful to provide an update on what I’ve been up to for the past few months, to keep things in perspective.

Changing roles

During the summer, I started a new job. As with any new job, there is an adjustment period and during that time I wanted to stay focused on getting up to speed and being able to deliver in the role I was hired for. I’m always apprehensive about new environments, so I wanted to take the time to properly learn the ropes and not be too assertive, while at the same time not being too withdrawn.

I’m glad to report that things are going quite well. The new position suits me well, and most importantly, the people there are great to work with. My new team lead, and indeed many of my other team members have also been recently hired, so I was a little less intimidated as I was by no means the only “new guy”. Since then, we have all had to opportunity to learn, grow and adjust to the environment, so it’s been a great team-building exercise of sorts. (As you can tell, the company is very much in a growth phase at this point)

About the only thing I don’t like is having to drive to work, as the new workplace is out is Mississauga. It’s not a horrible commute (~30 minutes one-way), but it’s just that I don’t like driving.

Boston 2011 Training

The other big event in my life has been qualifying for the Boston Marathon, which I did last year in STWM 2010.

Luckily, I managed to get in the day registration opened, as all the spots for the 2011 Boston Marathon filled within 8 hours! The fast fill-up time can probably be attributed to a self-fulfilling prophesy, as the people who were locked out last year (when registration filled in “only” 2 months) vowed not to miss it again. This created rumours that things would fill up even faster, and likely created a “bank run” type scenario.

I quickly booked my hotel and flight down to Beantown for April this year, as I didn’t want to miss out because of something logistical. But my planning for Boston hasn’t been limited to administrative items though, as there is of course the training required.

For this next marathon, which will be my sixth, I decided that I need a new approach, one that involved following a proper training plan. Before this, my training had always been self-developed – that is, lacking structure and reason. I would basically run four times a week: One long run on the weekend, followed by three ~10 km runs during the week. All of these would be run at the fastest pace that I could sustain over the distance.

This seemed to work, at least for a while, as I managed at 3:02:50 performance in the 2009 Edmonton marathon. However, this was followed by a disastrous 3:27 finish in the 2009 Toronto GoodLife marathon, and a qualifying near-miss in the 2010 Mississauga marathon where I finished in 3:13. Having just barely qualified during the 2010 STWM with a time of 3:10:46 (and that was only due to sheer willpower during the last 2.2 km), I knew a different approach was required, one that was more regimented.

A new approach to training

So I bought a few books and began reading up online about exercise physiology. I quickly learned that I had simply been running all my training runs too fast, which seems contradictory to the goals of training. After all, to run a race fast, shouldn’t you train fast? It turns out, the truth is not so simple.

Basically, by running everything as fast as I could during training, I wasn’t giving my body time to properly recover. Strictly speaking, it isn’t the workout that improves your fitness – as after a workout, you are tired and your performance is actually decreased. It’s actually the supercompensation that happens during the recovery phase that improves your fitness. Without recovery, hard training will simply break down your body and leave you less capable.

That’s what was happening to me – I was “leaving my best race on the track”, as famed distance running coach Daniels would say. With all that hard running, each workout began to seem tougher and tougher – though the actual intensity was not getting harder. Soon, it got to the point where I could not complete my four runs per week, and had to switch to cross-training in a vain attempt to preserve my fitness. It turns out, this is a common pitfall of amateur runners as they attempt to devise their own “training plan.”

Rest and recovery

After all of this, I needed a recovery period. I took some downtime after my fall marathon, and when to physiotherapy for some issues I was having with my right knee. It turns out I had PFPS (Patello femoral pain syndrome), which is basically a kneecap-tracking problem caused by muscle imbalances and likely aggravated by all the hard running I was doing. I was given some exercises to do and also began some strength training for my quads, and during the past three months the pain progressively decreased and is now almost completely gone. During this time, I was never prevented from running.

But I also began to change how I ran. I no longer ran everything at the fastest pace possible. In fact, for two months, I reverted to a “base training” phase, where all my runs were done at < 70% HRR (Heart Rate Reserve). At first, it was painful to run this slow. But I stuck to the ideas that others had proven effective, and I was able to increase my weekly distance up to levels I’d never touched before, all while remaining injury free.

During this time, I also worked on shortening my stride and increasing my cadence, thus moving away from a heel-striking gait to more of a midfoot strike. I believe this has prevented my plantar fasciitis from returning, something I struggled with for over a year. At the end of this phase, I did a time trial on the treadmill, and I was no slower at 10 km than before. In fact, physically, I felt much more stronger and refreshed.

Marathon training

With recovery out of the way, the question of which training plan to follow came up. After consulting with the folks over at the RWOL Boston forums, it became clear that many of them were following the plan from Advanced Marathoning, by Pete Pfitzinger. Pftizinger and Daniels have very similar ideas – specific runs at specific paces to train different parts of your physiology necessary for the marathon – but Pfitzinger is a more specific with his training schedule, something I desired.

At first, things were a bit daunting – after all, the lowest-mileage plan (which I planned on following) has a maximum week of 88 km, something I’ve never done before. But the beauty of the plans is that while there’s a lot of mileage, there’s a selective use of hard running. Pfitz always places sufficient time between hard runs, filling them with slower-paced runs that keep your cardiovascular system in shape while allowing your legs to recover from the harder efforts. It’s a much more sane approach.

I’m following the 18-week plan that peaks at 88 km, (commonly referred to as “18/55″ since 55 miles is about 88 km) and have just finished the 5th week. I feel great – a lot stronger and most importantly, remain injury free. Hopefully things will remain that way.

Summing it up

Besides updates on my marathon training progress, I will aim to add a few more development/programming related guides. I have the beginnings of a few, but just need the motivation to put them together. Hopefully that will not be interrupted by laziness. But Lennon once said, “Life is what happens to you while you’re busy making other plans.”.