Hardcore Project for Internships

Configure a CMake build system for a multi-file C project.

Implement custom arena memory allocators to manage memory contiguously and bypass standard malloc overhead.

Identify memory leaks, invalid memory access, and data races using Valgrind.

Profile CPU usage, cache performance, and branch prediction using the Linux 'perf' tool.

Explain the use of high-dimensional vectors and distance metrics (Euclidean, Cosine) for similarity search.

Implement naive C functions to calculate Euclidean distance and Cosine similarity between two vectors.

Explain the concepts of instruction-level parallelism and SIMD (Single Instruction, Multiple Data).

Rewrite the Euclidean distance function using AVX2 SIMD intrinsics to process multiple floats simultaneously.

Implement a function to calculate the dot product of two vectors using AVX2 fused multiply-add (FMA) intrinsics.

Implement a function to calculate the squared L2 norm of a vector using AVX2 intrinsics.

Combine the dot product and L2 norm functions to create a final, SIMD-accelerated Cosine similarity function.

Benchmark the performance difference between naive and SIMD distance calculations.

Explain the performance benefits of memory-mapped I/O (`mmap`) over standard `read`/`write` calls for large datasets.

Implement file creation and pre-allocation to a specific size using `ftruncate` and POSIX file descriptors.

Map a pre-allocated file into the process's virtual address space using `mmap` for direct memory access.

Design a file layout for storing vector data and metadata contiguously for efficient access.

Implement functions to write vector data directly into the memory-mapped region.

Use `msync` to control the synchronization of in-memory changes to the underlying physical disk.

Implement a brute-force (sequential scan) search to find the k-nearest neighbors for a query vector.

Analyze the impact of CPU cache lines on data access patterns and performance.

Implement a cache-line aligned memory allocator using `posix_memalign`.

Refactor the vector storage to use aligned memory to optimize sequential scan performance.

Use a bounded max-heap data structure to efficiently track the top 'k' candidates during a search.

Contrast exact k-NN search with Approximate Nearest Neighbor (ANN) search, explaining the tradeoff between speed and accuracy.

Describe the data structure of an NSW graph, including nodes, edges, and the concept of 'long' vs. 'short' range links.

Design C structs for graph nodes and edges, allocated from a contiguous memory pool for data locality.

Implement the greedy search algorithm to traverse the graph and find an approximate nearest neighbor.

Implement the algorithm for inserting a new vector into the graph by connecting it to its `k` nearest existing neighbors.

Implement the full graph construction process by iteratively inserting all vectors from a dataset.

Explain how HNSW improves upon NSW by introducing a hierarchical, multi-layer graph structure.

Describe the probabilistic layer assignment for new nodes, drawing parallels to skip lists.

Design the in-memory data structures for an HNSW graph node, supporting a variable number of connections on multiple layers.

Implement the `SEARCH-LAYER` algorithm for finding `k` nearest neighbors within a single layer of the graph.

Implement the top-level search algorithm that traverses from the top layer down to find optimal entry points for lower layers.

Combine the search algorithms to perform a full k-NN search, using the `efSearch` parameter to control the candidate list size.

Implement the probabilistic function to assign a random maximum layer for a new vector upon insertion.

Implement the main insertion algorithm, which finds neighbors for the new node from its top layer down to layer 0.

For each layer during insertion, use the `SEARCH-LAYER` algorithm to find candidate neighbors.

Implement the neighborhood selection heuristic to choose the best `M` neighbors for the new node from the candidates.

Implement the logic to create bidirectional connections between the new node and its selected neighbors.

Implement connection pruning to ensure nodes do not exceed their maximum connection limit (`M_max`) after an insertion.

Explain race conditions and the need for synchronization in a multi-threaded context.

Implement a thread pool to parallelize graph construction by processing multiple vector insertions concurrently.

Use a `pthread_rwlock_t` (Read-Write Lock) to allow multiple concurrent searches while ensuring exclusive access for graph modifications.

Refactor graph data structures to use C11 atomic types (`<stdatomic.h>`) for lock-free counters and flags where appropriate.

Analyze and prevent potential deadlocks in concurrent search and insertion scenarios.

Design a binary serialization format to save the HNSW graph and vector data to a single file.

Implement a function to serialize the in-memory graph state to a memory-mapped file.

Implement a function to load a serialized graph from a file back into memory, reconstructing the data structures.

Design and implement a Write-Ahead Log (WAL) to record operations like vector insertions before they are committed to the main graph structure.

Implement a recovery routine that replays the WAL upon startup to restore the database to a consistent state after a simulated crash.

Write a test to verify the integrity of the restored data after a crash and recovery cycle.

Design a C API using opaque pointers (`void *`) to hide internal data structures from the end-user.

Implement the core API functions for creating/loading an index, inserting vectors, and performing searches.

Write a comprehensive C header file with include guards and `extern "C"` blocks for C++ compatibility.

Configure CMake to compile the project as a dynamically linked shared library (`.so` or `.dylib`).