Concurrent Graph Construction with Thread Pools

Why Not Just Create Threads on Demand?

Your interest in high-frequency trading and performance systems makes this a particularly relevant topic. In such systems, predictability and resource management are paramount. Spawning a new thread for every incoming task—whether it's a market data update or a vector to be inserted—is inefficient and dangerous.

Operating systems incur significant overhead when creating and destroying threads. If tasks arrive in a rapid burst, creating a thread for each one can overwhelm the system, leading to resource exhaustion and a crash.

A thread pool pre-allocates a fixed number of worker threads and reuses them. This amortizes the cost of thread creation over the lifetime of the application, providing a resource-efficient and scalable way to handle a dynamic workload.

The Anatomy of Our Thread Pool

To build our thread pool, we'll need to define a few key data structures. The design needs to be generic enough to handle any kind of task, which is a hallmark of good system library design.

The Task (thread_job)

First, we need a way to represent a task. A task should consist of two parts: the function to execute and the arguments for that function. Using function pointers and void pointers allows us to create a completely generic task structure. For our vector database, one task might be insert_node, while for another application, it could be process_network_packet.

Our task struct, which we'll call tpool_work, will look something like this:

typedef struct {
    void (*func)(void *arg); // Pointer to the function to execute
    void *arg;               // Pointer to the arguments for the function
} tpool_work_t;

The Pool (thread_pool)

Next, the main thread_pool struct will encapsulate all the components: the threads themselves, the task queue, and the synchronization primitives.

Our pool struct, tpool_t, will integrate the task queue you already built and manage the worker threads:

typedef struct tpool {
    tpool_work_t *work_queue; // The task queue (from previous lesson)
    size_t work_count;
    size_t queue_size;

    pthread_t *threads;       // Array of worker threads
    size_t thread_count;

    pthread_mutex_t lock;     // Mutex for the queue
    pthread_cond_t notify;    // Condition variable to signal workers
    bool shutdown;            // Flag to signal shutdown
} tpool_t;

Implementation: From Blueprint to Reality

Now let's walk through the three main functions required to operate the pool: creation, task submission, and destruction.

1. Creating the Pool (tpool_create)

This function initializes the entire structure. It needs to:

1. Allocate memory for the tpool_t struct itself.
2. Allocate memory for the array of pthread_t workers.
3. Initialize the mutex and condition variable.
4. Create the threads. This is done in a loop, calling pthread_create for each worker.

The most important part is the function we pass to pthread_create. This is the "worker function"—the code that every thread in the pool will execute for its entire lifetime. We also need to pass each thread a pointer to the pool structure so it can access the shared queue and synchronization primitives.

2. The Worker's Loop

The worker function is the engine of the thread pool. It's a simple, elegant, and powerful loop that dictates the life of a worker thread.

1. Enter an infinite loop that only breaks on a shutdown signal.
2. Acquire the lock to safely access the task queue.
3. Wait for work. This is where the pthread_cond_wait logic from our last lesson comes in. The thread will sleep efficiently until the queue is not empty or a shutdown is signaled. The while loop is essential to handle spurious wakeups.
4. Check for shutdown. If a shutdown is signaled and the queue is empty, the thread should exit.
5. Get the task. If work is available, the thread pops a task from the front of the queue.
6. Release the lock. This is critical! The lock is released before executing the task. This allows other threads to get work from the queue while this thread is busy, achieving true parallelism.
7. Execute the task. The thread calls the function pointer from the task struct, passing it the void* argument.
8. Clean up the task struct and loop back to wait for the next job.

3. Submitting a Task (tpool_submit)

This function is what the "client" of the thread pool (e.g., our main thread) calls. Its job is simple:

1. Allocate a new task struct.
2. Populate it with the function pointer and argument.
3. Add the task to the pool's queue.

The push operation on our thread-safe queue will handle locking the mutex, adding the task, and then calling pthread_cond_signal to wake up one of the sleeping worker threads.

4. Destroying the Pool (tpool_destroy)

A graceful shutdown is a non-trivial but essential feature for robust systems programming. We can't just kill the threads; we need to let them finish their current work and exit cleanly.

1. Signal shutdown: Set the shutdown flag in the pool struct.
2. Wake everyone up: Call pthread_cond_broadcast. This wakes up all threads waiting on the condition variable. They will see the shutdown flag is true and begin to exit their loops.
3. Join the threads: Call pthread_join for every thread in the pool. This makes the main thread wait until each worker thread has completely finished execution. This is a crucial synchronization step.
4. Clean up memory: Once all threads are joined, it is safe to free all dynamically allocated memory: the task queue, the thread array, and the pool struct itself.

Applying the Thread Pool to HNSW Construction

With our thread pool implemented, we can now use it to parallelize the most expensive part of our project so far: building the HNSW graph.

The original, sequential approach would be:

// Sequential
for (int i = 0; i < num_vectors; ++i) {
    insert_vector_into_hnsw(graph, &dataset[i]);
}

With the thread pool, the logic changes. The main thread becomes a pure "producer":

// Parallel with Thread Pool
tpool_t* pool = tpool_create(num_cpu_cores);

for (int i = 0; i < num_vectors; ++i) {
    // Package data for the task
    insertion_args* args = malloc(sizeof(insertion_args));
    args->graph = graph;
    args->vector = &dataset[i];

    // Submit the task to the pool
    tpool_submit(pool, insert_vector_into_hnsw, args);
}

// Wait for all tasks to finish (if needed) and destroy the pool
tpool_destroy(pool);

Each call to tpool_submit returns almost instantly. The actual work of finding neighbors and adding connections to the graph is performed concurrently by the worker threads. This will drastically reduce the total time it takes to build the index.

Conclusion

In this lesson, we've assembled a complete and reusable C thread pool, a powerful tool for any performance-sensitive application. You've gone from the core synchronization primitives to a high-level concurrency pattern.

Key Takeaways:

• Thread pools manage a fixed set of worker threads to avoid the high cost of creating and destroying threads for each task.
• The worker thread's main loop is a cycle of locking, waiting for a task (using pthread_cond_wait), grabbing the task, unlocking, and executing it.
• Generic tasks using function pointers and void* arguments make the thread pool a versatile and reusable component.
• A graceful shutdown procedure is critical for correctness, involving setting a flag, broadcasting to all threads, and joining them before freeing resources.
• By decoupling task submission from execution, a thread pool is the perfect tool to parallelize our HNSW graph construction.

In our next lesson, we will address a new challenge. Our thread pool speeds up insertions, but what if we want to search the graph while it's being modified? This introduces new race conditions. We will tackle this by implementing read-write locks (pthread_rwlock_t), which allow for multiple concurrent readers but ensure exclusive access for a writer, further enhancing the performance and utility of our vector database.