Compacting Points-To Sets Through Object Clustering
summary
Maps memory objects to integers so bit-vector points-to sets shrink; formulates an optimal mapping as an integer linear program but falls back to fast hierarchical clustering on Andersen flow-insensitive results, then packs bit-vectors as core bit-vectors. Implementation in SVF uses fastcluster, runs clustering in ~10s, uses 64-bit words, and evaluates on 9 programs (>5.3M LLVM lines). Results show average ~1.3× speedup and ~2.35× memory reduction (reported up to 1.75× speedup and 3.25× memory savings).
AI-written summary · about
chapters (13)
- 0:00Introduction
- 0:17PointsTo Analysis
- 1:04SFS
- 2:22Bit vectors
- 4:25Mapping
- 6:00Problem Statement
- 6:45Constraints
- 7:29Pigeon Hole Principle
- 8:21Integer Programming
- 9:31Hierarchical clustering
- 10:48Auxiliary analysis
- 12:41Optimization
- 13:27Results
related talks
54mDissimilarity search...
25mHigh on Cardinality, Low on Memory
32mUnder the Hood: Key Algorithms Powering Vector Search
39mWhat's in a Vector Database?
34mThe Challenges of Making Vector Search Billion-scale
23mModular Construction and Optimization of the UZP Sparse Format for SpMV on CPUs
44mScaling Semantic Search in PostgreSQL
26mFast Erasure Coding for Data Storage: A Comprehensive Study of the Acceleration...