Indelible Blue Pen

Jason C. McDonald (CodeMouse92)


June 20, 2017

3 Cool Things To Do With PawLIB

I should probably slap a huge disclaimer on this post: I helped write PawLIB, a new C++ programming library from MousePaw Media. It contains some of my favorite code I ever wrote. Besides wanting to build high-performance data structures, we really wanted to make C++ fun again.

Instead of trying to describe what makes the library cool (I’ve already tried in the official press release), I’d rather demonstrate some of my favorite little tricks.

#1: Trilean Conditionals

Most of us are pretty adept at boiling down our programming logic to yes-and-no statements, but not always. There always seems to be that one pesky exception where the logic goes three ways instead of two.

There are many hacks around this: exceptions, enumerations, treating “null” as a value (please, for the love of all things digital, don’t do this last one!), but those workarounds usually feel pretty clunky when you come down to it. Yeah, you could rewrite the logic into a two-step process, but most of us like brief code. Enumerations are often nice, but now we’re adding extra code for that three-way stop.

PawLIB 1.0 introduces a new atomic data type called trilean, which contains three distinct states: true, false, and maybe. Ours isn’t the first such data type, but it probably has the most predictable behavior.

Let’s implement a simple example. Imagine a number guessing game with a twist: three numbers are “poison,” and if you guess any of those, the game is over. Otherwise, you have unlimited attempts.

Obviously, I could have implemented this just as easily with a ‘break’ statement, instead of a trilean, but this makes for a good example.

We start by setting up our variables.

tril status = maybe; // the outcome and loop control variable
int attempts = 0; // the number of guesses
int number = 42; // the number to guess
int poisoned[3] = {11, 48, 57};
int guess = 0; // the player's guess

For brevity, I went ahead and hardcoded values for the answer and poisoned numbers, but in a real game, you’d want to randomly generate this.

The ‘status’ variable is the trilean. It is set to ‘maybe’ by default, meaning in our case that the outcome is still undetermined. ‘true’ will be for a win, and ‘false’ for a death.

We can use the trilean’s “maybe” state in our while loop, so we won’t be needing a ‘break’.

// while the status is 'maybe', the player can still guess
while(~status)
{
  std::cin >> guess; // get the guess
  ++attempts; // increment the number of guesses

  // If the player guessed right
  if(guess == number)
    status = true; // report success, thereby exiting loop

  // Else if the player guessed a poison number...
  else if(guess == poisoned[0] || guess == poisoned[1] || guess == poisoned[2])
     status = false; // report death, thereby exiting loop

  // Else if the player below target...
  else if(guess < number)
    std::cout << "Your guess is too low." << std::endl;

  // Else if the player above target...
  else if(guess > number)
    std::cout << "Your guess is too high." << std::endl;
}

The rest is pretty simple: we just check the true or false state of the ‘status’ variable.

if(status)
  std::cout << "You won in " << attempts << " attempts." << std::endl;
else if(!status)
{
  std::cout << "You guessed a poison number and died." << std::endl;
  std::cout << "The answer was " << number << std::endl;
}

Here’s the entire code.

Trilean is fully compatible with boolean and its constants, so we could just as easily compare via the ‘==’ operator.

#2: Memory Dump

When working with C++, sooner or later you wind up dealing with pointers and memory. ‘std::cout’ certainly allows you to print out pointers and any atomic data type, but not raw memory without a lot of extra work. If you want to see raw memory, you generally need a debugger or some such tool.

IOChannel is, among other things, a feature-rich wrapper around iostream. One of its many features is in allowing you to output just about anything intelligently…including raw memory dumps.

Let’s say we have a class, such as the following.

class SomeMagicThing
{
  public:
    SomeMagicThing(int n1, int n2, bool b1)
    :foo(n1), bar(n2), baz(b1)
    {}

    ~SomeMagicThing(){}
  private:
    int foo;
    int bar;
    bool baz;
};

Let’s also say we have an instance of that object in our code.

SomeMagicThing* thingy = new SomeMagicThing(123, 456, true);

Now let’s say we are having some sort of trouble, and need to view that memory straight. Given only our pointer, we can use IOChannel to print out the memory.

ioc << ptr_memory << read_size(sizeof(SomeMagicThing)) << thingy << io_end;

Like magic, the complete memory of ‘thingy’ is printed out. Let’s break that down…

‘ptr_memory’ tells IOChannel to print out the memory at the pointer. To prevent memory access errors, we only read one byte by default, so we need to specify a ‘read_size’. We can use the ‘sizeof’ operator with our type to pull this off.

When we run this, we see…

7b000000c801000001000000

However, that’s still not quite as readable as we might like, so let’s use IOChannel’s formatting tools to make it prettier.

Personally, I like uppercase letters in my hexadecimal, so I’ll turn that on (num_upper). I also would like to split by words and bytes (mem_allsep). Just for fun, let’s also output this text as bold (ta_bold) and blue (fg_blue).

ioc << fg_blue << ta_bold << num_upper << mem_allsep
 << ptr_memory << read_size(sizeof(SomeMagicThing)) << thingy << io_end;

Running that, we see:

7b 00 00 00 c8 01 00 00 | 01 00 00 00

Just for convenience, I may also want to print out the address on the same line. It’s a bit tricky to reset some of IOChannel’s flags mid-stream, so we’ll create another stream statement just above the one we wrote.

ioc << "The memory at " << fg_green << ta_bold << ptr_address << thingy << io_send;

ioc << " is: " << io_send;

When we run this, we get…

The memory at 0x1236D80 is: 7b 00 00 00 c8 01 00 00 | 01 00 00 00

This may seem like a rather pointless thing, but consider this: with a few well-placed statements, we can now view specific memory in code which was compiled without debugging symbols! In some cases, it is also easier to use than your typical debugger. I have successfully used this pattern in debugging on multiple occasions.

Here’s the entire code.

#3: Benchmarking On The Fly

Does this sound familiar? You’re sitting in front of your computer, staring at the code, pondering which approach is going to be more efficient. Research has turned up nothing, and attempting a big-O analysis on both approaches is quite daunting.

In addition to being a full-fledged testing framework, PawLIB Goldilocks also has a full service comparative benchmarker. Using it is as simple as writing two tests.

Let’s say I want to compare bubble sort and selection sort. We obviously already know which is faster, but it’s a good example to play with. In my example code, I wrote functions for each (which I won’t bother reprinting here – see the Gist at the end of the section for the whole code.

Goldilocks tests require fairly little boilerplate, and the structure is well documented. It took me all of two minutes to type up a test for each.

class TestBubbleSort : public Test
{
  public:
    TestBubbleSort(){}

    testdoc_t get_title()
    {
      return "Bubble Sort";
    }

    testdoc_t get_docs()
    {
      return "Runs a bubble sort.";
    }

    bool run()
    {
      int arr[10] = {42, 57, 96, 21, 66, 17, 10, 97, 43, 86};
      bubblesort(arr, 10);
    }

    ~TestBubbleSort(){}
};

class TestSelectionSort : public Test
{
  public:
    TestSelectionSort(){}

    testdoc_t get_title()
    {
      return "Selection Sort";
    }

    testdoc_t get_docs()
    {
      return "Runs a selection sort.";
    }

    bool run()
    {
      int arr[10] = {42, 57, 96, 21, 66, 17, 10, 97, 43, 86};
      selectionsort(arr, 10);
    }

    ~TestSelectionSort(){}
};

Yeah, that’s literally all there is to the tests. Goldilocks tests have some additional functions for setup and teardown, but I really don’t need them here.

A word of caution – since the respective ‘run()’ functions are what get benchmarked, we need to ensure the only differences between them are what we’re measuring.

Goldilocks needs to be started within the code, our tests registered with it, and then we can call our comparison function. When we compare, we want to specify 1000 repetitions of each test per pass, with three passes always being run by the benchmarker.

int main()
{
  TestManager* testmanager = new TestManager();

  testmanager->register_test("BubbleSort", new TestBubbleSort);
  testmanager->register_test("SelectionSort", new TestSelectionSort);

  testmanager->run_compare("BubbleSort", "SelectionSort", 1000);

  return 0;
}

That’s all! When we run the code, the comparative benchmark runs and spits out complete statistics. This is ultimately what makes the Golidlocks benchmarker so useful: the statistical data helps you weed out “contaminated” results, such as where the CPU might have been doing something else during a measurement.

(GOTCHA ALERT: You should always compile as “release” when running a benchmark. Debugging symbols can throw off the results.)

There is a lot of info here. The three pass types – Mama, Papa, and Baby Bear – have to do with the effects of cache warming and cache misses on the benchmark. The “raw” numbers are derived from the complete set of measurements, whereas “adjusted” numbers are calculated after removing outliers from the set.

In short, when measuring code that always runs the same way, we want to look for lower RSD (relative standard deviations; the lower the RSD, the more precise the measurements. If any RSDs are highlighted in red, we should throw out the results. However, if the RSDs are low, or at least similar between the two tests, then we look at the verdict.

(A complete guide to the benchmark stats can be found here.)

In running this case, we are told that Selection Sort is faster by around 300-400 CPU cycles (per execution, obviously), which is precisely what we expected.

As promised, here is the entire code.

Summary

This is just the tip of the iceberg. PawLIB is not only one of my favorite projects I’ve ever worked on, but is now a regular tool in my programming arsenal.

You can download PawLIB from GitHub. Instructions for building and using it can be found on the official documentation.

There are more cool features coming in later versions of the library. If you find any bugs, have questions, or want to see a feature added, you’re welcome to join the MousePaw Media development community.

Facebooktwittergoogle_plusredditpinterestlinkedinmail

Leave a Reply

Your email address will not be published. Required fields are marked *