Improving my C++ time queue

Another code snippet that can be found in a few of my projects is the “time queue”, which is a simple ‘priority queue’ style data structure that I use to defer actions to a later time.

With this specific data structure, I have multiple implementations that clearly came from the same source. One indicator for that is a snarky comment in both about how std::list is clearly not the best choice for the underlying data structure. They have diverged a bit since then though.

Requirements

In my use case not use time points, but only durations in standard-library nomenclature. This is a pretty restrictive requirement, because otherwise any priority queue (e.g. from boost or even from the standard library) can be used quite well. On the other hand, it allows me to use floating-point durations with predictable accuracy. The queue has two important functions:

  1. insert to insert a timeout duration and a payload.
  2. tick is called with a specific duration and then reports the payloads that have timed out since their insertions.

Typically tick is called a lot more frequently than insert, and it should be fast. The payload is typically something like a std::function or an id for a state-machine that needs to be pulsed.

The basic idea is to only keep the duration difference to the previous item in the list. Only the first item keeps its total timeout. This way, when tick is called, usually only the first item needs to be updated. tick only has to touch more items when they time out.

Simple Implementation

One of the implementations for void insert(TimeType timeout, PayloadType payload) looks like this:

if (tick_active_)
{
  deferred_.push_back({ .remaining = after, .payload = std::move(payload) });
  return;
}

auto i = queue_.begin();
for (; i != queue_.end() && timeout > i->remaining; ++i)
  timeout -= i->remaining;

if (i != queue_.end())
  i->remaining -= timeout;

queue_.insert(i, { .remaining = after, .payload = std::move(payload) });

There is a special case there that guards against inserting into queue_ (which is still a very bad std::list) by instead inserting into deferred_ (which is a std::vector, phew). We will see why this is useful in the implementation for template void tick(TimeType delta, Executor execute):

tick_active_ = true;
auto i = queue_.begin();
for (; i != queue_.end() && delta >= i->remaining; ++i)
{
  delta -= i->remaining;
  execute(i->payload);
}

if (i != queue_.end())
  i->remaining -= delta;

queue_.erase(queue_.begin(), i);
tick_active_ = false;

while (!deferred_.empty())
{
  auto& entry = deferred_.back();
  insert(entry.remaining, std::move(entry.payload));
  deferred_.pop_back();
}

The timed out items are reported via a callback that is supplied as Executor execute. Of course, these can do anything, including inserting new items, which can invalidate the iterator. This is a common use case, in fact, as many deferred actions will naturally want follow ups (let’s ignore for the moment that the implementation is nowhere near exception safe…). The items that were deferred to deferred_ in insert get added to queue_ after the iteration is complete.

This worked well enough to ship, but the other implementation had another good idea. Instead of reporting the timed-out items to a callback, it just returned them in a vector. The whole tick_active_ guard becomes unnecessary, as any processing on the returned items is naturally deferred until after the iteration:

std::vector<PayloadType> tick(TimeType delta)
{
  std::vector<PayloadType> result;
  auto i = queue_.begin();
  for (; i != queue_.end() && delta >= i->remaining; ++i)
  {
    delta -= i->remaining;
    result.push_back(i->payload);
  }

  if (i != queue_.end())
    i->remaining -= delta;

  queue_.erase(queue_.begin(), i);
  return result;
}

This solves the insert-while-tick problem, and lets us use the result neatly in a range-based for-loop like this: for (auto const& payload : queue.tick(delta)) {}. Which I personally always find a little bit nicer than inversion-of-control. However, the cost is at least one extra allocation for timed-out items. This might be acceptable, but maybe we can do better for very little extra complexity.

Return of the second list

Edit: The previous version of this article tried to keep the timed-out items at the beginning of the vector before returning them as a std::span. As commenter Steffen pointed out, this again prevents us from inserting while iterating on the result, as any insert might invalidate the backing-vector.

We can get rid of the allocation for most of the tick calls, even if they return a non-empty list. Remember that a std::vector does not deallocate its capacity even when it’s cleared unless that is explicitly requested, e.g. via shrink_to_fit. So instead of returning a new vector each time, we’re keeping one around for the timed out items and return a const-ref to it from tick:

std::vector<PayloadType> const& tick(TimeType delta)
{
  timed_out_.clear();
  auto i = queue_.begin();
  for (; i != queue_.end() && delta >= i->remaining; ++i)
  {
    delta -= i->remaining;
    timed_out_.push_back(std::move(i->payload));
  }

  if (i != queue_.end())
    i->remaining -= delta;

  queue_.erase(queue_.begin(), i);
  return timed_out_;
}

This solution is pretty similar to the deferred list from the first version, but instead of ‘locking’ the main list while iterating, we’re now separating the items we’re iterating on.

Why I give lectures in software engineering

I’m often asked why I give lectures in software engineering, as they appear to not pay off for me. I think they do and here is why.

<a href="http://de.fotolia.com/id/21746212" mce_href="http://de.fotolia.com/id/21746212" title="" alt="">falcn</a> - Fotolia.com

For more than eight years, I give lectures in software engineering, object oriented programming and software development “best practices”. I have to spend nearly a day every week for six months in the year to prepare and hold the classes. My normal work schedule is always very stuffed with tasks, I have to affront my other duties sometimes in order to show up in front of the students. On many occassions, I’ve been asked why I keep giving lectures despite pressing liabilities, inferior payment and generally better alternatives elsewhere.

Here is a list with answers I’ve given to this questions over and over again. I do not want to convince you that giving lectures is the best thing right after sliced bread or that you will experience any of these if you manage to get in the same position. It’s just a rational explanation why the question still strikes me as odd.

  • It’s pure fun – This surely doesn’t count for everyone, but for me, speaking (ranting, raving, arguing) about software development counts as fun times. Being “on stage” in front of the students helps me to free my thoughts from dead freight and completely concentrate on the topics.
  • I’m being paid to recapitulate the basics – This are two advantages in one: being paid cannot be bad (albeit payment can always improve) and to repeat the basics of my craft on a regular schedule can be seen in the tradition of katas. I’m very bulletproof in discussions about fundamental topics of software engineering because I’ve heard most questions and had to answer them multiple times already.
  • I’m constantly learning new facets about well-known topics – My students always bring in unique and original thoughts about topics that I thought to have mastered. And then, a new way to access things emerges, at least for me. I feel very certain that I’m still learning more during the lectures than my students do. And feedback suggests that they learn a lot.
  • I’m honing my verbal abilities – Giving a lecture is all about speaking without script and responding to the audience. You have to make your points, but you cannot force them. Sometimes I feel like a stand-up comedian for technical knowledge. Having the ability to speak fluently while preparing the next topic in the back of your head is a great advantage in every situation including verbal communication.
  • Roughly 100 aspiring developers remember me every year – What they will remember me for can be debated about, but they will remember. This is all about “networking”, but focussed on members of my own profession. The reach of this network amazes me every time when it loops back.
  • I can contact every local company with job training – Due to the nature of the Cooperative State University where I’m giving my lectures, I can also establish contact to every software company in the vicinity. Many contacts would never happen without my function as lecturer.
  • I keep in touch with hypes – Students are easy prey for IT hypes. Their experience with different technologies isn’t embittered by analogies from the past. All I have to do is to listen to them when they tell me about their work and hobby projects. And then I can draw my own conclusions based on their first-hand experience.

All these reasons and some more are enough for me to stick with the job. You can see a lot of short term benefits and some aspects that might pay off at medium term. On the long run, I’m convinced that my personal advantages from this job will outweight the (sometimes serious) drawbacks. And then, I haven’t yet included the advantages that my students took along from my lectures, hopefully.

If you happen to give lectures too, I would be pleased if you blog about your reasons for doing so, and announce your post here. Or just use the comment section.

On teaching software engineering

Be sure to include current topics in your lectures when teaching software engineering. Here are some hints.

overheadIn my rare spare time, I hold lectures on software engineering at the University of Cooperative Education in Karlsruhe. The topics range from evergreens like UML to modern subjects like aspect oriented programming (AOP) or Test Driven Development (TDD).

One thing I observe is that students don’t have difficulty separating the old topics from the current ones, even if they hear both of them for the first time. It seems that subject matter ages by itself, just like source code does. So, I’m constantly searching for new topics to include in the lectures, replacing the oldest ones.

Three things to include in your lectures

Some months ago, I read a very good blog post written by Alan Skorkin, titled “3 Things They Should Have Taught In My Computer Science Degree”. Alan covers three points:

  1. Open Source Development
  2. An Agile Process (e.g. XP, Scrum)
  3. Corporate Politics/Building Relationships

The idea of missed opportunities to tell some fundamentals to my students struck me. I compared my presentations to the list, finding the leading two topics covered to a great extent. The last one, corporate politics, is a bit off-topic for a technical lecture. But nevertheless, it’s too important to omit completely, so I already had included some Tom DeMarco lessons in my presentations. Perhaps I can build this part up a bit in the future.

What they should have taught me

Soon afterwards, I though about things my lecturers missed during my study. Here’s the list with only two points in addition to Alan’s list:

  • Age and “maturity” of topic: When I was a student, I quickly identified old topics, like my students do nowadays. What I couldn’t tell was if a topic was mature (a classic) or just deprecated. It would have helped to announce that a topic was necessary, but of little actual relevance in modern software development craftmanship. Or that a topic is academical news, but yet unheard of in the industry and lacking wide-spread acceptance. Both extremes were blended together in the presentations, creating an unique mixture of antiquated and futuristic approaches. This is a common problem of Advanced Beginners in the Dreyfus model.
  • Ergonomics and Effectiveness: I still can’t believe I didn’t hear a word about proper workplace setup from my teachers. I had courses teaching me how to learn, but not a single presentation that taught me how to work. This topic ranges from the right chair over lighting to screen size and quantity and could be skimmed over in less than an hour. But it doesn’t stop with the hardware. Entire books like Neal Ford’s “The Productive Programmer” cover the software side of effective workplace setup. And even further, the minimal set of tools a software developer should use (e.g. IDE, SCM, CI, issue tracker, Wiki) wasn’t even mentioned.

I hope to provide all these topics and information to my students in a recognizable (and rememberable) manner. They deserve to learn about the latest achievements in software engineering. Otherwise you aren’t prepared to work in an industry changing fundamentally every five to ten years. Of course, hearing about the classic stuff is necessary, too.

Give me feedback. What are your missed topics during apprenticeship, study or even work?

Update: In case you can’t visit my lectures but want to know a bit about ergonomics, I’ve written two blog articles on this topic: