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 Mar

Displayed 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
20m
Talk
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
20m
Talk
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
20m
Talk
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