attractivechaos

Lessons from Hash Table Merging

Merging two hash maps seems like an O(N) operation. However, while merging millions of keys, I encountered a massive >10x performance degradation unexpectedly. This post explores why some of the most popular libraries fall into this trap and how to fix it. The source code is available here.

• The set up
• Merging hash tables may be slow

attractivechaos

Performance of generic hash tables in C

I often utilize hash tables in my projects, some of which handle billions of small keys. The performance of hash table –– both in terms of speed and memory usage –– is critical to these projects. I conducted two hash table benchmarks in [2008][2008-bench] and [2018][2018-bench], respectively. While they were among early popular benchmarks by then, they are now outdated and missing important modern implementations. This blog post serves as a follow-up, focusing specifically on C libraries.

attractivechaos

When to use a memory pool?

A [memory pool][mp-wiki] is a data structure for allocating fixed-size memory blocks. This definition has stayed same since I learned it around 2010. Although you can find more general definitions via Google, those are the minority.

The APIs of memory pool implementations vary, but they generally look like:

attractivechaos

// You need the following three files to compile:
//   https://github.com/attractivechaos/klib/blob/master/kavl.h
//   https://github.com/attractivechaos/klib/blob/master/kmempool.h
//   https://github.com/attractivechaos/klib/blob/master/kmempool.c
// Compile with: gcc -O3 -Wall test.c kmempool.c -o test
// Run with "./test" for raw malloc and "./test m" for memory pool

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

attractivechaos

What is an "arena" in memory allocation?

I first leanred about "arena" when I was trying to understand the internal of [glibc malloc][glibc-alloc] around 2010, but I [later realized][trend] the concept is narrowly defined [in][arena1] [other][arena2] [context][arena3]. This blog post explains the difference in definition and the limitations in the so-called "arena allocators" we use today.

Background: why is malloc needed?

attractivechaos

To compile:

gcc -O3 -DKE_MAIN kexpr.c -o kexpr

Examples:

./kexpr "2+5*2"                  # output 12 (simple arithmetic)
./kexpr "2+5*exp(-1)"            # output 3.8394 (builtin functions)
./kexpr "2+5*exp(x+y)" x=-2 y=1  # output 3.8394 (variables)
./kexpr "2^1" # output 3 (bit operation)

attractivechaos

/* The MIT License

   Copyright (c) 2019-2023 by Attractive Chaos <attractor@live.co.uk>

   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to

attractivechaos

// see also: https://github.com/attractivechaos/plb2/blob/master/src/c/matmul.c

#include <stdio.h>
#include <stdlib.h>

double **mat_alloc(int n_row, int n_col)
{
	double **mat, *a;
	int i;
	mat = (double**)malloc(n_row * sizeof(void*));

attractivechaos

Bouncing ball

A Pen by Attractive Chaos on CodePen.

License.

attractivechaos

/* The MIT License

   Copyright (c) 2008, 2011 Attractive Chaos <attractor@live.co.uk>

   Permission is hereby granted, free of charge, to any person obtaining
   a copy of this software and associated documentation files (the
   "Software"), to deal in the Software without restriction, including
   without limitation the rights to use, copy, modify, merge, publish,
   distribute, sublicense, and/or sell copies of the Software, and to
   permit persons to whom the Software is furnished to do so, subject to