Memoization explained part 2: the interface


20 March 2012, by

previous article in series

For those of you who have been on tenterhooks since my last post on memoization, I apologise for the delay. The rest of the posts shall now follow much more quickly!

Last time we explored the potential interface for such a library. But perhaps the best way to demonstrate precisely what my Memoizer will do, is to show you what a unit test would look like. So let’s indulge in a little Test-Driven Development

The first thing we need to think about when writing unit tests, is what are we testing for? Obviously, we’re testing to see that the methods work, but what else are we going to test?

Here are some simple situations we need to test.

  • If the function passed as the argument is null, we need to throw an ArgumentNullException.
  • If it throws an exception when called, we need to pass it through and not swallow the exception or return invalid values.

The functional situations are a bit more complicated to test for – we need to check that

  • the value returned is correct
  • the underlying function is not called again and again.

Let’s start with tests for the simplest memoizer method, GetMemoizer(Func<TResult>).

/// Check that when GetMemoizer is called with a null argument,
/// it throws an ArgumentNullException.
[TestMethod]
public void NullsAreChecked() {
  Func<int> f = null;

  try {
    f = Memoizer.GetMemoizer(f);
    Assert.Fail("ArgumentNullException was not thrown");
  } catch (ArgumentNullException) {
    // Great!
  }
}

/// Check that when the underlying method throws an exception,
/// the memoized function passes the exception on unaltered.
[TestMethod]
public void ExceptionIsPassed() {
  const string exceptionMessage = "Just some arbitrary exception I picked";

  Func<int> f = () => {
    throw new InvalidTimeZoneException(exceptionMessage);
  };

  f = Memoizer.GetMemoizer(f);

  try {
    f();
    Assert.Fail("Exception was not passed");
  } catch (InvalidTimeZoneException ex) {
    // Great! Let's just check that the exception came through unharmed.
    Assert.AreEqual(exceptionMessage, ex.Message);
  }
}

/// Check that result values are passed correctly and remain correct after
/// multiple calls to the memoized function.
[TestMethod]
public void ValuesArePassed() {
  Func<int> f = () => 7;

  f = Memoizer.GetMemoizer(f);

  // Call it a few times to see that we get the right result when data is memoized.
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
}

/// Check that the underlying function is only called once.
[TestMethod]
public void IsItReallyMemoized() {
  int numberOfTimesCalled = 0;

  Func<int> f = () => {
    // Remember how many times this function has been called.
    numberOfTimesCalled++;
    return 7;
  };

  f = Memoizer.GetMemoizer(f);

  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());

  // Check that the actual function was only called once.
  Assert.AreEqual(1, numberOfTimesCalled);
}

Okay, now that we got the simple tests out of the way we can continue thinking about the tests in a bit more detail. One of the nice things about thinking of unit tests before the code is that you can think of edge cases you would tend to ignore otherwise.

For example, when writing the unit tests I thought of this: if the method throws an exception, and we call the memoized method again, what happens?

A naïve implementation might return null or another default value because it remembers being calculated but doesn’t have a result value. That’s obviously wrong – if the underlying method threw an exception, the memoized one should throw as well.

If we take the example function x => 1 / x, we want to throw a DivideByZeroException every time x==0 and not just the first time the function is called. Otherwise, we’d get 1 / 0 == 0, which is a bit foolish.

So what do we do? Do we call the method again in exceptional circumstances, or do we cache the exception? I’ll choose to call the method again for two reasons: firstly, exceptional circumstances can change – if we had an I/O exception for example, it makes sense to try again later; then, once we get a result we’ll cache that as usual. Secondly, it’s far easier to implement, which is a low-priority consideration for me but still one that should never be ignored.

/// Test that functions that throw exceptions are called again.
[TestMethod]
public void ExceptionalMethodsAreCalledAgain() {
  // Create a function that returns the value 7 only on the third time it's called.
  int numberOfTimesCalled = 0;

  Func<int> f = () => {
    numberOfTimesCalled++;

    if (numberOfTimesCalled == 3) {
      return 7;
    }

    throw new IOException();
  };

  f = Memoizer.GetMemoizer(f);

  try {
    f();
  } catch (IOException) {
    // Expected.
  }

  try {
    f();
  } catch (IOException) {
    // Expected.
  }

  // Also test that the value is cached after the first time we got it.
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());
  Assert.AreEqual(7, f());

  Assert.AreEqual(3, numberOfTimesCalled);
}

I think that’s it for the unit tests of the simple memoizer. The tests for the ones that accept a parameter are similar, except they’re a little more complicated since they work with parameters as well.

Now we’ve written the unit tests, writing the code should be straightforward! Come back next time to find out if I’m right…

Tags: , , ,

Categories: Technical

«
»

Leave a Reply

* Mandatory fields


seven × = 7

Submit Comment