Programming | Probably Dance

May 3, 2014

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 »

7 Comments

April 5, 2014

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 »

3 Comments

February 8, 2014

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 »

4 Comments

January 16, 2014

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 »

2 Comments

October 5, 2013

Type-safe Pimpl implementation without overhead

I like the pimpl idiom because I like to keep my headers as clean as possible, and other people’s headers are dirty. Unfortunately the pimpl idiom never feels like a good solution because it has runtime overhead that wouldn’t be needed if I didn’t care about clean headers so much.

If you’re not familiar with the Pimpl idiom, it stands for “pointer to implementation” and you use it in C/C++ headers to use a class without having to include the other header in your header. You can also use it to hide your implementation from your users so that you can change the internals of your class and nobody has to know. It’s used all over the place but it has one disadvantage: You always need an extra heap allocation and every method performs an extra pointer dereference.

This code fixes that, so that there can be zero runtime overhead. Here’s how to use it:

class btRigidBody;
class MyRigidBody
{
    // ...
    ForwardDeclaredStorage<btRigidBody, 768> bulletBody;
};

And the code is below:
Read the rest of this entry »

20 Comments

August 27, 2013

Source to Source Optimization

In April Olaf Krzikalla Gave a talk titled “Performing Source-to-Source Transformations with Clang” (Videos available here)

In that talk he showed an auto vectorizer that doesn’t perform the optimization in the assembly, but which instead spits out new source code that performs the optimized operations. Here is a picture from his talk:

And I want to explain why all compiler optimizations should do this.

Read the rest of this entry »

2 Comments

May 13, 2013

4GB per Vector

I recently had a problem where I had a vector that was growing once, being iterated over once, and then deallocated. And it was bothering me how much time I spent on reallocating. The problem was that I also could not predict well how big the vector would be ahead of time. It could vary by orders of magnitude for input that looked similar at first.

As I was researching the minor page faults that I was hitting during the reallocations I came across this stack overflow question. There’s a person there who speaks of resizing an array by requesting a lot of memory from the OS, but then only actually committing the memory as he wants the array to grow.

Which is smart, and I wonder why nobody has taken it further. I think all vectors should operate like that all the time. Thus I wrote my own vector class which always requests 4GB of memory from the OS, and which then only actually commits that memory one page at a time. After all we have this enormous address space in 64 bit that we won’t be using for a long time.

Read the rest of this entry »

7 Comments

February 20, 2013

Handmade Coroutines for Windows

In a previous post I implemented coroutines using the ucontext.h header. In this post I will show a replacement that should be much faster. I will also provide a Windows implementation.

I like to start off with some code, so here is the complete code for switching the stack in Linux:

switch_to_context:
    pushq %rbp
    movq %rsp, %rbp
    // store rbx and r12 to r15 on the stack. these will be restored
    // after we switch back
    pushq %rbx
    pushq %r12
    pushq %r13
    pushq %r14
    pushq %r15
    movq %rsp, (%rdi) // store stack pointer
switch_point:
    // set up the other guy's stack pointer
    movq %rsi, %rsp
    // and we are now in the other context
    // restore registers
    popq %r15
    popq %r14
    popq %r13
    popq %r12
    popq %rbx
    popq %rbp
    retq

Read the rest of this entry »

8 Comments

February 2, 2013

The problems with uniform initialization

C++11 made the {} syntax for initializing aggregates more widely usable. You can now also use it to call constructors and to initialize with a std::initializer_list. It also allows you to drop the type name in some circumstances. The general recommendation seems to be that you use it as much as possible. But when I have started doing that I have found that it sometimes doesn’t do what I want, and that it may make maintenance more difficult.

Here’s what it looks like:

#include <iostream>

struct Widget
{
    Widget(int m) : m{m} {}
    operator int() const { return m; }
    int m;
};

Widget decrement_widget(Widget w)
{
    return { w - 1 };
}

int main()
{
    int a{1};
    std::cout << a << std::endl; // "1"
    Widget w{5};
    std::cout << w << std::endl; // "5"
    std::cout << decrement_widget({5}) << std::endl; // "4"
}

It can be used to initialize everything (hence the name uniform initialization) and as you can see it makes some code more convenient because I don’t even need the name any more if the compiler should know it.

It makes your code look a bit weird at first because you have squiggly braces everywhere, but after a while I found that I prefer it because it sets initialization apart from function calls.

But I have stopped using it and I recommend that you don’t use it either.

Read the rest of this entry »

4 Comments

January 13, 2013

A faster implementation of std::function

As I wrote in my last post, I consider std::function to be a very important class that will change how you design your code, because it means that you have to use inheritance less often. In that post I was very impressed with the performance of std::function when compiled with optimizations. Unfortunately std::function can be far slower than a virtual function call in debug.

I wanted a std::function implementation that doesn’t have too big of a performance impact on your application when debugging it, so I wrote my own. It is also faster than all other implementations that I could find in release mode.

The code is in the public domain (I want all library writers to start using it) and here is a download link.

Read the rest of this entry »

27 Comments

Category: Programming