Reproduce “Towards Efficient Hash Maps in Functional Array Languages” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
William Henrich Due, Martin Elsman, Troels Henriksen
Researchers at the University of Copenhagen demonstrated an asymptotically work-efficient hash map implementation within a functional array language, significantly outperforming in-language comparison-based data structures. Their Futhark-based solution, however, revealed a performance gap compared to highly optimized low-level CUDA implementations, primarily due to limitations in expressing non-deterministic concurrent algorithms.
Key insights
- Complex, theoretically work-efficient data structures like Fredman et al.'s (FKS) two-level hashing can be systematically derived and implemented within a functional, data-parallel programming model.
- High-level functional array languages, despite their abstractions, can deliver substantial practical performance improvements for hash map operations over comparison-based alternatives like binary search.
- A key challenge for functional array languages is their current inability to easily express and leverage the controlled non-determinism required by highly optimized concurrent data structures on GPUs, such as open addressing with atomic operations.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.