Let the Circle Buffer Be Unbroken (PR 2934).

In Be the Worst Person in the Band I explained one of my guiding development principles: it’s easier to figure out what the right thing is if we can all explore something concrete, even if it’s wrong in some way.

I won’t repeat what I wrote already, except to say that we saw a user interface element that did the wrong thing and we changed it to do the right thing. Or, at least, ReverseControl saw that it did the wrong thing, and Michi made it do the right thing. That counts as a team effort! Go team!

The core of the problem was that the code that shows the pretty network graphs was also the same code that captured the data behind those graphs. In software design terms, these two separate concerns were too tightly coupled. A flaw in one produced a flaw in the other, even if wasn’t obvious.

A Model Citizen

The problem is obvious if you think about it another way. Suppose you pull up Dogecoin Core and look at your list of transactions. Then you close that window and go about your day, and tomorrow you do the same thing.

Should the Core rescan the entire blockchain every time you open the transaction list?

Should the Core go out to the network and ask every node it can find if they know of a transaction in your wallet, every time you open the transaction list?

The answer is probably no, for lots of reasons, mostly because it makes a lot more sense to trade some disk space and memory to make this kind of operation faster and cheaper.

In other words, no matter if the window is open or closed or if you’re running the GUI at all, the Core should have some way of keeping track of your transactions in a way that’s cheap and easy to use. The world of software sometimes calls this a data model, because that implies something both discrete and formal.

The problem with the network graph is that it didn’t have a discrete data model, and so it couldn’t do what a data model should.

The Inward Spiral

The original code threw away the data it tracked every time anyone moved the graph slider to change the graph’s scale. Even if this was an accident and you immediately put the slider back where you found it, the data was gone. Poof. No Ctrl-Z or Escape-lowercase-u would help you. It was gone.

I undid that as the first commit on what would become PR 2934.

The result wasn’t worse, but it also wasn’t better. It was different, but it was differently wrong in a way that made the right behavior obvious, at least to Michi, who explained it to the rest of us in a way that made it obvious to everyone.

Here’s the magic: lines 17 - 19 in src/qt/trafficgraphwidget.cpp.

We display 800 samples. We store samples for 60 seconds per minute for 60 minutes per hour for 24 hours per day, or 86,400 seconds. We take a sample every thousand milliseconds (that’s every second).

That’s it. That’s the magic.

That’s sort of the magic, anyway. The correctness of this solution is that the sample rate does not change. It’s fixed to one second, every second, for one full day, regardless of the slider in the GUI. That’s not much, but that’s all we need to have a real data model now.

The rest of the work is implementation.

There’s a lot to see here, but pay close attention to the new body of the paintPath() method. This code has a pattern in a couple of places (lines 136 - 139, for example) that looks like:

        samplesIndex++;
        if (samplesIndex >= samples.size()) {
            samplesIndex = 0;
        }

Here, samplesIndex is an index into a vector (a list) of data representing those 86,400 samples: one per second for the past day. This is a circle buffer.

If you’ve never used one before, you’re in for a treat. It’s a clever idea that’s easy to implement but incredibly useful.

How does it work? First, answer me this question: what’s the index of the vector representing exactly 86,400 seconds ago?

It could be 0. That’s a reasonable data structure, but that means every second you’ll have to check and see if you have a day’s worth of data. If so, you drop what’s at position 0, shift everything down a slot, and put your new item at the last position.

That’s expensive, at least with the simple vector-based implementation. Sure, you could use a linked-list, but then you have to keep track of the list size and you’ll probably not want to allocate a float and a pointer every second and put pressure on your memory system, so you’ll end up re-using these objects, and you still have to keep track of the head and tail item anyway, so….

Please Take a Number

With these circle buffers here, we always have a vector of the right size. The index of the oldest element doesn’t matter because it can be any position in the vector. The newest element overwrites the oldest element, and the index just keeps looping through positions in the vector until it hits 86,400 and the loop resets it to 0.

Painting the last day of results means traversing the iterator from the oldest item, looping around, and hitting the newest item. It’s just an index bump and a bounds check to find each element (and it could be optimized to be cheaper if necessary; use subtraction to figure out the pivot point and use two loops to traverse the entire vector).

Sure, it looks like a little bit more overhead to manage than walking a linked list, but it’s not much more code and it’s a lot more efficient and with the comment in lines 44 - 54 of src/qt/trafficgraphwidget.h, the implementation is straightforward.

I’m a lot pleased with that comment, mostly because I insisted it be there because I know I’ll probably forget why the code looks the way it does. At least in this case, I have only myself to blame for not reading the comment first. It’s a good comment!

We’re Just Hitting Our Stride

You may ask “This is all well and good, but the goal wasn’t only to avoid throwing away data. The goal is to be able to redraw the graph when people change the slider.”

Look at the use of variables called stride. Like the length of your step (your stride) as you’re walking, this determines how much ground you cover in each step. If you had a stride of 86,400 and a very wide monitor, you could see the value of each second’s worth of data. With a stride of 43,200 you’d see the average of two seconds worth of data, and so on.

By decoupling the data model from the visibility, the data collection can continue one second at a time while the display can do whatever it wants. The visual representation gets a little bit more complicated because it has to average samples over the stride, but this is high school math so it’s not too bad.

There’s more goodness to mine from this code, if you want to dig in further, but this should give you enough to understand what’s happening, why it’s better than the previous version, and the general design principles.

This is a good PR because it solves a real problem in a sensible way, makes things easier for users, makes the code better, and was a good collaboration between several people.

This will be available in 1.14.6 in early July 2022. Look for it!