The fable of mashed potatoes

Once upon a time in a faraway land in a kingdom much like ours lived a carpenter. Every day he worked for a small company with his fellow carpenters. This company produced book shelves. The recent increase in population literacy rates had made books very popular so there was a growing need for bookshelves.

The bookshelves they manufactured were quite popular, and their customers really seemed to appreciate their quality. Obviously making bookshelves was not rocket science, mostly because rocketry had not been invented yet, but also because it was all in all a fairly well understood problem. The company's success made it possible for them to hire a few more carpenters. And then a few more.

Eventually someone in the management chain started wondering about how to make things better. Faster. More organised. So he went looking for a bookshelf expert to lead this voyage towards unknown bookshelf frontiers. Eventually such a person was found, hired and initiated. Soon thereafter he gathered all of the carpenters of the company into one room, for he had an announcement to make.

The bookshelf expert gathered everyone around him in a tight circle. He was giddy and excited to spring forth his major plan. All the carpenters were excited as well, there was electricity in the air. Then the expert finally started talking. First he talked about the past, then the present and finally came time for the future of all of storage space.

- From now on, we shall make all of our bookshelves ...

Every carpenter in the room leaned forward. They held their breath.

- ... out of mashed potatoes!

They kept holding held their breath, but for a different reason.

No-one can really remember how the rest of the talk went. One imagines the expert talked about the glorious future this would bring about. Then he congratulated everyone and left, presumably for a meeting with other mashed potatoes furniture specialists.

Our friend the carpenter felt puzzled. He wondered about the workshop for a while and then talked to his boss. He was frankly completely baffled. You couldn't even make a pencil stand out of mashed potatoes, let alone a bookshelf.

- He's a world class expert on potatoes, the boss said, he knows what is best so we should be doing what he says.

- What? This has nothing to do with potatoes at all. There's no way to make a bookshelf out of mashed potatoes, for starters it won't hold any weight, and also ...

The boss waved his hand at the carpenter.

- Have you ever tried doing a bookshelf out of mashed potatoes? I mean actually, really in practice?

- No, but, the carpenter tried to continue before being interrupted

- Well that's a very negative attitude to be having. Why are you being so negative? It affects poorly on your co-workers. Look around you, they are all working on their next projects and getting shelves done.

The carpenter tried to think of something to say, but the sheer absurdity of the situation got the better of him.

- Well back to work, we have products to ship, the manager said and left the workshop.

The sun went down and came back up the following day. Our carpenter had decided to make the best of this situation. Surely, he thought, someone would notice the flaw inherent in a mashed potato based storage unit. He didn't have long to wait. Soon the expert tapped him on the shoulder and asked him to come to the next room.

- I have been told, he said in a slightly judgmental tone, that you have raised some issues with my new plan.

The carpenter tried to follow up but was cut short.

- Apparently you have been telling people that my potatoes have mildew.

- Err, what? I have said nothing of the kind.

- I will have you know that all of these potatoes are the finest in the world. I have grown them myself with my own two hands. I have won several awards for potato farming.

- I'm sure you have, but ...

The expert cut him off again. He would not have any dissenting voices here. He went on explaining in great length how potatoes are the best nutritional source, how much time and effort he had put in each single potato and a blurry of other potato related facts.

- Now I'm going to let this infraction against potatoes go unnoticed, but do remember that a negative attitude such as yours will cause problems sooner or later. I highly recommend you fix it. Now, back to work.

And to work he went, among with all the rest of the team. They started producing mashed potato bookshelfs as planned and even scrapped already made but not yet delivered wooden shelves for new potatoe'd ones. And they were terrible. Upon seeing them their customers immediately demanded their money back. Some shelves did make it into customers apartments where they did not hold books but mostly just stank and attracted flies. Which caused the customers to demand their money back with interest.

As all sources of income dried up and management refusing to go back to wood based shelves (because "we have spent so much on this technology" and because "going back now would make us look weak"), it did not take long for the company to shut down. When the workshop was being cleaned for the last time, the carpenter's boss spoke with a sad timbre in his voice.

- Everything was going so well and now we have nothing. How can this be?

The carpenter had kept his opinions under his hat since the confrontation but as there was nothing left to lose, he figured he'd make one last appeal to sanity.

- Because making bookshelves out of mashed potatoes is a massively stupid idea that can not possibly work. Even a child can see that immediately. Remember how I tried to tell you this when things started?

The boss straightened his back and squinted. For a split second you could see tiny sparks shooting from his eyes.

- That's exactly it! You never gave our new strategy a chance! You had it doomed before it even started and then worked actively against it! Your negative attitude is the reason we are now all out of a job. You destroyed the livelihood of dozens of people! Are you proud of yourself?

The carpenter was not. He had failed. Miserably.

Failed to explain to a grown man that making a bookshelf out of mashed potatoes was a terrible idea.

How many is too many?

Trivia question: when you run a random configure scripts, how many processes does it spawn?

Before reading further, try to think of the answer by yourself. Just do it. Pick a number you think is the correct answer.

Measuring this is simple. You can do it with the following command:

strace -c -f -e trace=fork,vfork,clone,execve bash -c ./configure

Different configure scripts have different results, of course. I ran this on the configure script of RPM, which I happened to have handy.

And the correct answer is ...

... 6611.

Aren't you glad that processes are cheap?

Simple structure of arrays with C++ templates

One feature that has been getting more popular recently is called the structure of arrays. As an example Jonathan Blow's new Jai programming language should have built in support for that. The basic principle is very simple. Instead of having this:

struct Foo {

  int x;

  std::string name;

  FooObj bar;

};

std::vector<Foo> items;

You'd want to have something like this:

struct Items {
  std::vector<int> x;
  std::vector<std::string> name;
  std::vector<FooObj> bar;

  struct Foo& operator[](size_t index);
};

The reason for this is better cache locality. First of all you don't get padding holes between items. The second issue is that usually when you doing operations on elements of these arrays you only touch a subset of items. This data layout reduces cache misses as you can skip a large portion of data.

In C++ terms you would like to have a declaration like the following:

Soa<int, std::string, FooObj> items;

This would then create a data structure like the one discussed above with all basic operations such as push_back, capacity and so on. Then you could do things like items[0].name = "hello" or std::sort(items.begin(), items.end(), mypredicate).

C++ does not support this natively but with templates you can create this yourself. There are some things that you can't do (such as accessing elements by name) but other bits are fairly straightforward. The code for this example is on github. For simplicity this implementation only has two items in the struct and they must have the same type. Doing arbitrary items would require working with tuples and other fun stuff that is beyond my template-fu.

The core class contains the two vectors that hold the data. The core building block is this helper struct:

template<typename T>
struct SoaItemRef {
    T &item1;
    T &item2;
    // rest omitted for clarity
};

Whenever we need to access the underlying data we return this struct instead. The refs are initialised to point to the underlying data so all reads and writes get proxied to the actual data. Then there are a bunch of helper methods to assignments. In addition we need iterator definitions. Those can be found in the actual code.

This single struct gets you most functionality. You just need a swap method that does elementwise value copying between SoaItemRefs. The second addition is a value only type that looks like this:

template<typename T>
struct SoaItem {
    T item1;
    T item2;

    // stuff such as comparison operators omitted
};

This allows you to do things like std::find(items.begin(), items.end(), SoaItem<int>{1, 2}).

Missing functionality

There's quite a lot of it. The most obvious thing is that you should be able to specify an arbitrary amount of arbitrary types. The problem here is that this gets really complicated really fast. Another niggle is that the helper structs are standalone where they should actually be inner classes of Soa. I tried to make this happen for quite a while but I could not make std::swap resolve to these inner types. Moving them to standalone classes made everything magically work.

It is possible that you can't do items[2].name = "foo" without resorting to the preprocessor and possibly not even then. It's not going to be pretty in any case. Feel free to try it out, though.