Loop Unrolling: While ⇒ If-While

Loop unrolling is a performance optimization where you repeat the inside of a loop to reduce the looping overhead. It’s also a way to get rid of loops, and we’ll look at an example from a test.

While ⇒ If-While

I’ve mentioned programming language semantics before. This equivalency for a while loop is an example:

while condition do statement
    ≡ 
if condition {
   statement ;
   while condition do statement
}

This recursive transformation lets us peel off an “if” statement. (See References articles on semantics.)

An Example Test

Amitai Schleier runs a PubMob session to work on legacy code for the notqmail application. (The last session of 2021 is Friday Nov. 26th – see if there’s room for you!:)

Last week, we were working on a test for priority queues. We wanted to make sure a one-item queue is handled correctly, by adding an item to the queue, making sure it was the first item, and deleting it.

The test code used a loop, counting to make sure that only one item would be retrieved. This code is in C, so let me sketch it out in pseudo-code. (This is from memory, and somewhat idealized so I don’t have to explain parts; please forgive any mistakes.)

// a test
pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

count = 0
element.data = 0
while (prioq_containsMin(&pq, &element)) {
  count++
  prioq_deleteMin(&pq)
  check(element.data == 7)
  element.data = 0
}

check(count == 1)

Unrolling Once

Let’s apply the “while => if-while” rule once:

pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

count = 0
element.data = 0
if (prioq_containsMin(&pq, &element) {   
  count++
  prioq_deleteMin(&pq)
  check(element.data == 7)
  element.data = 0

  while (prioq_containsMin(&pq, &element)) { 
    count++
    prioq_deleteMin(&pq)
    check(element.data == 7)
    element.data = 0
  }
}

check(count == 1)

Unrolling Twice

The only way the check in the last statement can succeed is if the first prioq_containsMin() is true and the second is false.

This is a test case. I don’t particularly care about the order of checks; if a variant passes or fails whenever the original does the same, that’s what counts. So I feel justified to add an early check that the first prioq_containMin() is true, and unroll the loop again.

pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

count = 0
element.data = 0
var hasFirstElement = prioq_containsMin(&pq, &element)
check(hasFirstElement == true)   // replaces first "if"

count++
prioq_deleteMin(&pq)
check(element.data == 7)
element.data = 0

if (prioq_containsMin(&pq, &element)) {  // newly unrolled "while"
  count++
  prioq_deleteMin(&pq)
  check(element.data == 7)
  element.data = 0

  while (prioq_containsMin(&pq, &element)) { 
    count++
    prioq_deleteMin(&pq)
    check(element.data == 7)
    element.data = 0
  }
}

check(count == 1)

Check the Condition

Let’s extract the second prioq_containsMin() to another variable. We said before that this value must be false for count to be 1 at the end. That means the “if” statements boils down to “if (false) { do a bunch of stuff }”, which can be deleted.

Here’s what that looks like:

pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

count = 0
element.data = 0
var hasFirstElement = prioq_containsMin(&pq, &element)
check(hasFirstElement == true)

count++
prioq_deleteMin(&pq)
check(element.data == 7)
element.data = 0

var hasMoreElements = prioq_containsMin(&pq, &element)
check(hasMoreElements == false)

// deleted "if" with its contained "while"

check(count == 1)

Dead(ish) Code

Now, there is no more conditional logic about the count. If all the checks pass, and we get to the bottom, count will be 1. That tells me we don’t need count any more, so we can delete it. We can also see that the final assignment to element.data is never looked at, so we can delete that too. (We did peek inside prioq_containsMin(); nothing there that would make that risky.)

pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

element.data = 0
var hasFirstElement = prioq_containsMin(&pq, &element)
check(hasFirstElement == true)

prioq_deleteMin(&pq)
check(element.data == 7)

var hasMoreElements = prioq_containsMin(&pq, &element)
check(hasMoreElements == false)

Some Final Cleanup

Three things stand out to me at this point:

We’re reusing element both to put data in and then check it; we can make a new variable.
The check for element.data comes after prioq_deleteMin() but conceptually it belongs before it.
Names need work. (There are some constraints there I won’t get into, but I’ll leave the renames to your imagination.)

Let’s do the first two:

pq = prioq_new()
element = prioq_newElement(7)
prioq_add(&pq, &element)

var fetchedElement = prioq_newElement(0)
var hasFirstElement = prioq_containsMin(&pq, &fetchedElement)

check(hasFirstElement == true)
check(fetchedElement.data == 7)

prioq_deleteMin(&pq)

var hasMoreElements = prioq_containsMin(&pq, &element)
check(hasMoreElements == false)

You could split this into two tests, arrange-act-assert style, but I wasn’t put off by it being a sort of “lifecycle” characterization test: create a queue, add an element, check it’s there, delete it, and check that it’s gone.

Conclusion

To unroll a loop, we can use the semantics of a while loop to make the “while → if-while” transformation.

By applying that transformation a couple times and adding a couple extra checks, we were able to simplify the test and remove all loops and conditionals. Our test has become much easier to reason about.

References

“3A – Arrange, Act, Assert“, by Bill Wake. Retrieved 2021-11-22.

“Operational Semantics“, by Roy Ganor and Uri Juhasz. (Page 9 describes “while” loops.) Retrieved 2021-11-22.