Probably Dance

I can program and like games

The Curious Failure of Functional Programming for Parallel Applications

Long title, but it is interesting how functional programming has mostly failed to gain traction in parallel and concurrent applications. People think that functional programming should become more popular as we do more and more parallel programming, but that doesn’t happen. As an example this blog post made the rounds recently which has this quote in it:

However, the key to multicore programming is controlling mutation. This is why functional languages have been steadily gaining ground in concurrency and parallelism.

Which I would disagree with. Not the controlling mutation part, but the steadily gaining ground part. Let’s look at a few examples:

Read the rest of this entry »

format_it: Iterator based string formatting

format_it is my attempt at writing string formatting that is good enough that it could make it into the C++ standard. It’s not quite there yet but I haven’t gotten to work on it in a few months, so I will publish what I have so far. It is fast (much faster than using snprintf to write to the stack), type safe, memory safe, doesn’t truncate, extensible, backwards compatible for std::ostream and somewhat composable.

The syntax is a mix of printf, ostream and varargs. I’ll just show an example:

// format "100 and 0.5" into 1024 bytes of stack memory
fmt::stack_format<1024> format("%0 and %1", 100, 0.5f);

// print "Hello World" into 1024 bytes of stack memory
fmt::stack_print<1024> print("Hello", "World");

// prints "100 and 0.5\nHello World\n"
auto format_to_cout = fmt::make_format_it(std::ostreambuf_iterator<char>(std::cout));
*format_to_cout++ = format;
*format_to_cout++ = '\n';
*format_to_cout++ = print;
*format_to_cout++ = '\n';

Where the first and second struct mimic snprintf, and the third example introcues the formatting iterator that they use behind the scenes.

Read the rest of this entry »

Databases are Fucking Stupid

I’ve been trying to do some database programming and goddamnit do databases make my life difficult. I’m using PostgreSQL but it doesn’t really matter what you use. Let me get the most minor complaint out of the way: Why do I have to talk to databases using text?

Every time that I want to store a value in a database I have to convert it to a string and the database has to convert it back from a string. This is slow, lossy, leads to bugs (SQL injection) and is completely unnecessary. But I can accept that bit of stupidity.

My bigger issue is that databases don’t know how to do their job.

Read the rest of this entry »

I Wrote a Faster Hash Table

This is a follow up post to “I Wrote a Fast Hash Table.

And I’ll start off with a download link.

I’ve spent some time optimizing my sherwood_map implementation and now it is faster than boost::unordered_map and boost::multi_index. Which is what I would have expected from my first implementation, but it turns out that those containers are pretty damn fast.

If you don’t know what Robin Hood Linear Probing is I would encourage you to read the previous post and the post that I linked to from that one. With that said let’s talk about details.

Read the rest of this entry »

I Wrote a Fast Hash Table

As others have pointed out, Robin Hood Hashing should be your default hash table implementation. Unfortunately I couldn’t find a hashtable on the internet that uses robin hood hashing while offering a STL-style interface. I know that some people don’t like the STL but I’ve found that those people tend to write poorer interfaces. So I learn from that by not trying to invent my own interface. You can use this hash table as a replacement for std::unordered_map and you will get a speedup in most cases.

In order to reduce name conflicts I call it sherwood_map, because Robin Hood Hashing.

Read the rest of this entry »

Reinventing the Wheel for Better Compile Time

I have a new laptop on which everything compiles slowly. Which means I sometimes get really annoyed with C++ and its slow compile times. The two most common causes of slow compile times are large headers and complicated templates. Large headers are somewhat easy to identify, and you can usually improve your compile time by using precompiled headers, but it has traditionally been hard to find out which templates are hurting your compile time. Luckily there is a project called Templight which can tell you how much time Clang is spending on instantiating templates. Using Templight I have found that some templates take unnecessarily long to compile.

So I re-implemented std::unique_ptr, boost::flat_map, and await.

Read the rest of this entry »

How do you secure Bitcoin?

After the Mt. Gox thing the bitcoin course is going back up again. My initial response was “this is a Mt. Gox problem, not a bitcoin problem” and I think this seems to be the general opinion right now.

But then it looked like the most likely reason for the disappearance of the money is that some insider at Mt. Gox just ran away with it. And the more you think about it, the more you realize how easy this is. Let’s say you are an admin at a company which has a lot of bitcoins. One day you book a vacation to some Caribbean island, and the day before you leave you copy the private keys of all the big bitcoin wallets that the company has onto a thumb drive. As soon as you’re out of the country you use those private keys to transfer all of the company’s money to your account. You’re rich, and it’s not easy to see how that could have been prevented.

Read the rest of this entry »

Bitcoin Mining for Space Heating

When googling for the above words you find lots of people making jokes about how Bitcoin mining hardware will turn into an expensive space heater quickly after purchase because the mining difficulty increases so fast. But using Bitcoin mining hardware as space heaters is not necessarily a bad idea.

In my apartment we mostly heat with electric heaters. Which is a giant waste of money, but we don’t have a choice. And electric heaters are basically devices that try to waste as much electricity as possible, because the more electricity they waste, the more heat they generate. Sounds kinda like Bitcoin mining, right? When I realized that I turned off my electric heater and made my computer mine Bitcoin. By my estimates I will get something like 2 or 3 dollar worth of Bitcoin out of that by the end of the month. Which is 2 or 3 dollar more than my electric heater gives me.

If I had realized this at the beginning of the winter and had bought specialized mining hardware, I could have actually gone through the winter making a good amount of money. If I can’t convince my landlord to switch our heating solution by next winter, I’ll certainly be doing that next year.

Introducing the Asserting Mutex

Multithreaded code in C++ tends to become brittle over time. If you write your code well you’ll need almost no synchronization between different threads, but the price of that is that your code will be littered with undocumented conventions of when you can read or modify which state. In your average threaded C++ application there are countless potential race conditions, all of which never happen because people follow conventions about when to do what. Until someone doesn’t know about a convention that he has to follow or until you change the conventions and you forget to update one piece of code that you didn’t know about.

Enter the asserting mutex. The asserting mutex is a conditional breakpoint that triggers only if a potential race condition actually happens. I call it asserting mutex because you use it like a mutex to protect a critical section. It works very simply: If one thread locks the asserting mutex and a second thread attempts to lock the asserting mutex before the first thread unlocks it, you get an assert. And it guarantees that both threads will still be inside the critical section when you get the assert. The cost is one atomic increment and one atomic decrement, which is not free but cheap enough that you can place lots of asserting mutexes in your code before they cause problems. So you could use this to document many of your threading conventions. Used correctly this is a breakpoint that makes it very easy to find data races.

Here is the complete code:

Read the rest of this entry »

Alias templates with partial specialization, SFINAE and everything

Alias templates are a new way to do typedefs in C++11. You have probably seen them by now, but as a reminder here is what the standard considers to be an alias-declaration:

template<typename T>
using MyVector = std::vector<T, MyAllocator<T>>; // alias-declaration
MyVector<T> myvector; // instantiating with MyAllocator;

So that’s cool. Unfortunately the standard also says that “Because an alias-declaration cannot declare a template-id, it is not possible to partially or explicitly specialize an alias template.” (Paragraph 14.5/3) But that would be a terribly useful thing to have.

Read the rest of this entry »

Follow

Get every new post delivered to your Inbox.