This paper introduces a technique for synthesizing hash functions specialized to particular byte formats. This code generation method leverages three prevalent patterns: (i) fixed-length keys, (ii) keys with common subsequences, and (iii) keys ranging on predetermined sequences of bytes. Code generation involves two algorithms: one identifies relevant regular expressions within key examples, and the other generates specialized hash functions based on these expressions. Comparative analysis demonstrates that the synthetic functions outperform the general-purpose hashes in the C++ Standard Template Library and the Google Abseil Library when keys are given in ascending, normal or uniform distribution. In applications where low-mixing hashes are acceptable, the synthetic functions achieve speedups ranging from 2% to 11% on full benchmarks, and speedups of almost 50x once only hashing speed is considered.
Tue 4 MarDisplayed time zone: Pacific Time (US & Canada) change
10:00 - 11:00 | Program Analysis & SynthesisMain Conference at Casuarina Ballroom (Level 2) Chair(s): Jose Nelson Amaral University of Alberta | ||
10:00 20mTalk | Automatic Synthesis of Specialized Hash Functions Main Conference Renato B Hoffmann PUC-RS, Leonardo Gibrowski Faé PUC-RS, Dalvan Griebler Pontifícia Universidade Católica do Rio Grande do Sul - PUCRS, David Li Google, Fernando Magno Quintão Pereira Federal University of Minas Gerais | ||
10:20 20mTalk | Stack Filtering: Elevating Precision and Efficiency in Rust Pointer Analysis Main Conference Wei Li UNSW, Dongjie He Chongqing University, China, Wenguang Chen Tsinghua University; Pengcheng Laboratory, Jingling Xue UNSW Sydney | ||
10:40 20mTalk | SkipFlow: Improving the Precision of Points-to Analysis using Primitive Values and Predicate Edges Main Conference David Kozak Brno University of Technology & Oracle Labs, Christian Wimmer Amazon Web Services, Codrut Stancu Oracle Labs, Tomas Vojnar Masaryk University |