Rust Projects

I’ve been having a lot of fun recently learning Rust. It’s a breath of fresh air in so many ways compared to C++: for instance the standardised package management, a consistent way of building projects, and simple-to-add unit tests. These are in addition to the much-touted safer memory management. We won’t be giving up with C++ at work, but we will be using Rust for several new projects.

As a learning exercise, I’ve re-written a game I first wrote for the ZX-Spectrum forty years ago, called Xtarda Rescue. It’s not the cleanest code – there was a lot of learning along the way, and I’d definitely refactor parts of it if I had the time, but it plays really well and, while I tried to keep it retro, it’s far more advanced than the original.

I also wrote probably about the millionth version of Conway’s Life.

There’s also a tiny little CLI utility called Temperature I’ve just created, which is a good example of how to do async calls, in this case to a couple of REST APIs, one for IP-based geolocation (so not very accurate!) and then, given that location, a call to get localised weather information.

I’m definitely looking forward to continuing learning more Rust.

Non-Metric Threads on the Lathe Using C++

I continue to improve the lathe application I’ve written – it’s working really well. Several major improvements recently include a graphical user interface to allow better display of information, stepper control of the X axis, and the ability to cut tapers by controlling the Z and X axis simultaneously.

Yesterday I wanted to cut a non-metric thread (normally I use metric exclusively) – specifically 3/8″ x 16 TPI. I needed a part for an old engineer’s clamp I’ve had kicking around for ages; it was missing one of its two screws. I have very few imperial dies, and not that one.

Now I can cut threads programmatically, that’s no problem – I just added the thread dimensions to my program, ground up a 55° tool, and started cutting. The test thread (not the finished replacement bolt) is shown above. It fits beautifully!

Update: here’s a picture of the finished version, in situ on the old clamp which I’ve never been able to use owing to the missing screw (the new one’s on the left). I guess the next project is cleaning the thing!

Controlling a Rotary Table with C++

As part of the project to control my metalworking lathe with a stepper motor (see https://www.martyndavis.com/?p=726), I’ve decided it would be useful to make some additional gears to step down the speed of the rotary encoder in relation to the lathe’s spindle.

Here’s the first one I created (I haven’t cut a keyway in it yet).

A z45 module 1.0 gear I cut with this software

To cut gears, typically people use a rotary table, which has a worm drive on it to allow for accurate turning of the workpiece via a handwheel which is marked with a vernier scale. I figured it would be easier to get a computer to do that for me.

Creating the software was simple, because I had all the components already created for the previous project. Unlike the lathe project, there are no microsecond-critical timing issues – just rotate, cut, rotate, and repeat until you’ve turned 360°. See it in action at https://youtu.be/4pt8MZhDIB4 – quite literally this was my first test, and it all just worked as expected.

The code can be found at https://github.com/md81544/electronicRotaryTable

Update: here’s a new video showing the code in action for real, cutting an aluminium z40 spur gear. The result is shown below:

Controlling a Lathe with C++

This is a quick post – I’m intending on going into far more detail about this at a later stage – but recently, for fun, I’ve been working on automating some functions on a metalworking lathe. It’s been a really interesting project – I’ve been driving a fairly powerful stepper motor to give accuracy of positioning of tooling down to near-micron level, and measuring the position of the lathe’s spindle (via a rotary encoder) while it spins, at an accuracy required to start a cut at the same position over multiple passes, for cutting threads. I’ve been driving all this from a Raspberry Pi 3 Model B. It’s working beautifully, as you can see from the thread I cut below:

From a C++ perspective, this has required microsecond-level accuracy, and plenty of multi-threading to get suitable real-time performance – it’s interesting to have a real-world requirement for this kind of coding outside of my normal work, and incredibly rewarding to see the lathe chuck spinning in a blur but knowing that the code can determine exactly what its rotational position is at any moment.

Usage of mock objects and unit tests have allowed me to develop large chunks of the code without access to the hardware when I’m away from my workshop.

The code can be found at https://github.com/md81544/electronicLeadScrew

See the thread cutting in action at https://www.youtube.com/watch?v=VlhPiRscNeY

Using libjpeg in C++

Just for fun I thought it would be interesting to write a quick program to convert .jpg images to an ASCII representation. Here’s a sample output:

I was surprised that there are not more examples online showing how to use libjpeg, and even fewer wrapping it in a more cpp-friendly manner.

I decided to make the functionality re-usable, so if you have a need to read in a .jpg file, modify it, and save it, then this is going to be useful to you.

One point of interest, the shrink() member function – initially I wrote it very simply. I went through each (new) pixel in turn and calculated it as the average of a box of pixels in the original, larger, bitmap. This worked fine, but at the time I knew it was inefficient. Jumping around a surrounding box means cache misses galore. The best way to do this is one line at a time – this means we’re processing data already in processor cache lines, and is simpler for the CPU to do correct branch prediction. The version you see in the current source was my more considered version – it ended up three times faster than the initial version (and as it’s on github you can compare it to the old version in the history). I’ve left the getAverage() member function in, in case it is useful for anyone, but no longer use it in shrink().

If you’re on a linux distro you’ll undoubtedly have libjpeg (or one of its forks) installed. To use it and my source, you’ll need to install the header files for it, with:

sudo apt install libjpeg-dev

You can also install it on Windows, as a test I used Microsoft’s vcpkg to get the header files.

You can see the code at https://github.com/md81544/libjpeg_cpp -you’ll want a C++11-compatible compiler for it. I’ve tested the latest version with both g++ and clang++.

Rubbish Interview Questions

I came across this photo in my archive from quite a few years ago. I was taking one of those awful online C++ tests as an initial pre-interview screener. I took a photo of this question as an example of the standard of questions this particular company was asking.

What do you think the answer is?

When you’ve gone through a series of timed questions like this, you start to second-guess the person who wrote it.

Clearly the variable “o” is a stack-based variable, a pointer, so will be destroyed at the end of its scope. So technically the answer is “a”.

But I have a feeling the person that wrote this dubious question actually means to ask about what o points to, especially as it’s a memory leak (unless the mysterious bar() function deletes what o points to). I remember being in a quandary about this one… do you answer entirely correctly? Or do you try to answer the question you think is being asked?

Obviously in a face-to-face or telephone interview one could discuss this. I’ve always preferred, when being the interviewER, to sit down with someone in a real-world situation, give them access to Stack Overflow and Google (which, as we all know, are essential tools of the trade these days), and ask them to explain their thought processes.

If you’re turning down potential candidates on the strength of questions like the above, I’d argue you’re doing it wrong.

Getting Started with Boost MultiIndex

Note: this is an introduction to / overview of Boost MultiIndex. It is not intended to be in-depth.

So. Containers.  99% of the time, std::vector, out of all the choices you have in the STL, is the right choice. The next most obvious is std::map if you need to “index” access to data: for example if you store 1,000,000 phone numbers and you want to quickly find one given a name, a std:map will give you “indexed” access – you look up your data in O(log n) time (or potentially quicker if you’re using a std::unordered_map) as opposed to O(n) time for an unsorted std::vector. (Obviously these are theoretical complexities – see a previous post which advocates actual benchmarking, as processor cache and branch prediction can have a huge effect).

Continue reading “Getting Started with Boost MultiIndex”

Big O – Theory vs Practice

I saw a question online recently which basically asked whether big-O notation always holds true in practice. For example, in theory, searching through a vector for an item should be O(n) whereas searching a map should be O(log n). Right?

Let’s imagine we create a vector with 100,000 random integers in it. We then sort the vector, and run two different searches on it. The first search starts at the beginning, compares the element against the value we’re searching for, and simply keeps incrementing until we find it. A naive search you might say. Without resorting to std:: algorithms, how might you improve it?

A worthy idea might be a recursive binary, or bisection, search. We might, for example, make 15 bisections to find a value in the upper quadrant of our range, compared to, say 75,000 comparisons in the brute force approach.

That’s fairly safe to say that the binary search is going to be much faster, right?

Not necessarily. See the results below:

100000 random numbers generated, inserted, and sorted in a vector:
 0.018477s wall, 0.010000s user + 0.000000s system = 0.010000s CPU (54.1%)

Linear search iterations: = 75086, time taken:
 0.000734s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

Binary search iterations: 17, time taken:
 0.001327s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

Are you surprised to see that the binary search took (very) slightly longer than the brute force approach?

Welcome to the world of modern processors. What’s going on there is a healthy dose of branch prediction and plenty of valid processor cache hits which actually makes the brute force approach viable.

I guess the moral of this story is, as always, don’t optimise prematurely – because you might actually be making things worse! Always profile your hot spots and work empirically rather than on what you think you know about algorithm efficiency.

The code used here is reproduced below – it should compile on VS 2015, clang and g++ without issue. You’ll need Boost for the timers. You may see wildly different timings depending on optimisation levels and other factors :)

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <string>

#include "boost/timer/timer.hpp"

const int MAX_VAL = 100'000;

template <typename T>
T LinearSearch(typename std::vector<T>::iterator begin,
    typename std::vector<T>::iterator end, T value)
{
    // While not ostensibly efficient, branch prediction and CPU cache for the
    // contiguous vector data should make this go like greased lightning :)
    size_t counter{0};
    while (begin < end)
    {
        if (*begin >= value)
        {
            std::cout << "\nLinear search iterations: = " << counter;
            return *begin;
        }
        ++begin;
        ++counter;
    }
    return 0;
}

template <typename T>
T BinarySearch(typename std::vector<T>::iterator begin,
    typename std::vector<T>::iterator end, T value)
{
    // The return value is not exact... just interested in getting close to the
    // value.
    static size_t counter{0};
    size_t mid = (end - begin) / 2;
    ++counter;
    if (begin >= end)
    {
        std::cout << "\nBinary search iterations: " << counter;
        return *begin;
    }
    if (*(begin + mid) < value)
    {
        return BinarySearch(begin + mid + 1, end, value);
    }
    else if (*(begin + mid) > value)
    {
        return BinarySearch(begin, begin + mid - 1, value);
    }
    else
    {
        std::cout << "\nBinary search iterations: " << counter;
        return value;
    }
}

int main()
{
    // Fill a vector with MAX_VAL random numbers between 0 - MAX_VAL
    std::vector<unsigned int> vec;
    vec.reserve(MAX_VAL);

    {
        boost::timer::auto_cpu_timer tm;
        std::random_device randomDevice;
        std::default_random_engine randomEngine(randomDevice());
        std::uniform_int_distribution<unsigned int> uniform_dist(0, MAX_VAL);
        for (int n = 0; n < MAX_VAL; ++n)
        {
            vec.emplace_back(uniform_dist(randomEngine));
        }
        // Sort the vector
        std::sort(vec.begin(), vec.end());
        std::cout << MAX_VAL
                  << " random numbers generated, inserted, and sorted"
                     " in a vector:" << std::endl;
    }

    {
        boost::timer::auto_cpu_timer tm2;
        LinearSearch(
            vec.begin(), vec.end(), static_cast<unsigned int>(MAX_VAL * 0.75));
        std::cout << ", time taken:" << std::endl;
    }
    {
        boost::timer::auto_cpu_timer tm2;
        BinarySearch(vec.begin(), vec.end() - 1,
            static_cast<unsigned int>(MAX_VAL * 0.75));
        std::cout << ", time taken:" << std::endl;
    }

    return 0;
}

C++ Custom Deleters: unique_ptr vs shared_ptr

C++11 gives us two useful indispensable smart pointers, std::unique_ptr and std::shared_ptr. So much has been written about these that there’s no point me re-hashing anything other than to re-iterate that if you are using “naked” owning pointers in your code these days, you are simply doing it wrong.

I wanted to mention briefly the use of custom deleters with smart pointers. If you haven’t looked at this aspect of smart pointers before, it basically gives us a way to specify what should happen when the smart pointer goes out of scope.
Continue reading “C++ Custom Deleters: unique_ptr vs shared_ptr”

C#, Mono, and System-Wide Mutexes on Linux

Here’s another little “gotcha” from my experimentations in running C# apps cross-platform. The following code implements a system-wide mutex to ensure that only one instance of the program is running at any one time:

public static void Main(string[] args){
	Mutex mutex = null;
	try{
		mutex = Mutex.OpenExisting("test.martyndavis.com");
		// if we *can* open it we're an ADDITIONAL instance
		Console.WriteLine("Application is already running");
		return;
	} catch(WaitHandleCannotBeOpenedException){
		// if we get in here then the mutex doesn't exist,
		// so we are the only instance running on this machine
        mutex = new System.Threading.Mutex(true, "test.martyndavis.com");
	}
	try{
		Console.WriteLine("Doing stuff... press a key");
        Console.Read();
	} finally{
		// Although mutex implements IDisposable, it doesn't
		// call Release Mutex when being Disposed(),
		// hence usage of try/finally instead of 'using'.
		mutex.ReleaseMutex();
	}
}

Running this on Windows it behaves as one would expect. Run one instance you get “Doing stuff… press a key” output, and, if you try to run a second instance in another DOS box you get “Application is already running”.

On Linux though it’s a different story – each instance runs as if it’s the only copy on the machine.

Doing some digging turns up this note in Mono’s release docs – you can see that shared handles are now turned off by default – you can turn them on by setting the environment variable MONO_ENABLE_SHM, but for the application I’m working on I think I’ll simply avoid mutexes and use something else to ensure one instance – a lock file in the application’s data directory will be simple, and work cross-platform.