Red-black tree appears to be slower than std::multimap

Question

I've written a red-black tree in C as an exercise. The tree works and it is not bad, but it is about 10% slower than std::multimap from libstdc++ which I'm comparing it against.

Full code of my implementation is here. libstdc++'s red-black tree written in C++ is here and here.

I'm using the following code to compare implementations:

void
test_torture() {
    std::vector<uint64_t> v;
    std::multimap<uint64_t, uint64_t> map;
    uint64_t range = 10 * 1000 * 1000 * 1000LL;
    uint64_t count = 10 * 1000 * 1000;
    for (uint64_t i = 0; i < count; i++) {
        uint64_t key = rand() % range;
        map.insert(std::make_pair(key, key));
        v.push_back(key);
    }
    for (uint64_t i = 0; i < count; i++) {
        uint64_t key = v[i]; 
        map.erase(key);
    }
    assert(map.size() == 0);
}

So it adds 10m random nodes to the tree, then deletes them all again. My code is almost exactly as fast as std::multimap when doing the insertion part, but it lags behind when it comes to erasing nodes. When profiling, the hottest part of my code is my loop for inserting nodes:

rbtree *
rbt_add(rbtree *me, ptr key, ptr value) {
    // Find insertion point.
    rbtree **addr = &me;
    rbtree *parent = NULL;
    while (*addr) {
        parent = *addr;
        addr = &parent->childs[key >= parent->key];
    }
    *addr = rbt_init(parent, key, value);
    return rbt_add_fixup(me, *addr);
}

But I can't think of any way to improve that. My functions for rebalancing the tree after addition and deletion (which I think are the most interesting part) are below.

static rbtree *
rbt_add_fixup(rbtree *root, rbtree *x) {
    while (x != root && x->parent->is_red) {
        bstdir dir = BST_DIR_OF(x->parent);
        rbtree *y = x->parent->parent->childs[!dir];
        if (y && y->is_red) {
            x->parent->is_red = false;
            y->is_red = false;
            x->parent->parent->is_red = true;
            x = x->parent->parent;
        } else {
            if (BST_DIR_OF(x) != dir) {
                x = x->parent;
                root = rbt_rotate(root, x, dir);
            }
            x->parent->is_red = false;
            x->parent->parent->is_red = true;
            root = rbt_rotate(root, x->parent->parent, !dir);
        }
    }
    root->is_red = false;
    return root;
}

static rbtree *
rbt_remove_fixup(rbtree *root, rbtree *x, rbtree *x_parent) {
    while (x != root && IS_BLACK(x)) {
        bstdir dir = BST_DIR_OF2(x, x_parent);
        rbtree *w = x_parent->childs[!dir];
        if (w && w->is_red) {
            w->is_red = false;
            x_parent->is_red = true;
            root = rbt_rotate(root, x_parent, dir);
            w = x_parent->childs[!dir];
        }
        if (BOTH_CHILDREN_BLACK(w)) {
            if (w) {
                w->is_red = true;
            }
            x = x_parent;
            x_parent = x->parent;
        } else {
            if (IS_BLACK(w->childs[!dir])) {
                w->childs[dir]->is_red = false;
                w->is_red = true;
                root = rbt_rotate(root, w, !dir);
                w = x_parent->childs[!dir];
            }
            w->is_red = x_parent->is_red;
            x_parent->is_red = false;
            w->childs[!dir]->is_red = false;
            root = rbt_rotate(root, x_parent, dir);
            x = root;
        }
    }
    if (x) {
        x->is_red = false;
    }
    return root;
}

I'd be very grateful for suggestions on how to increase the performance of the code.

The definition of the node type is:

typedef struct _rbtree {
    struct _rbtree *parent;
    struct _rbtree *childs[2];
    bstkey key;
    bool is_red;
    ptr value;
} rbtree;