jrgemignani opened a new pull request, #2421:
URL: https://github.com/apache/age/pull/2421
Replaces the per-graph adjacency map with a Robin Hood open-addressing
hashtable (agehash) and an embedded flat-array edge list, removing the hottest
dynahash path on IC1 and shrinking the largest hashtable AGE keeps. Stages land
as one commit:
S1 MurmurHash3 fmix64 for graphid hashtables (replaces tag_hash)
S2 Precompute graphid hash; share across paired DFS lookups
S3 Replace ListGraphId adjacency with embedded flat-array
VertexEdgeArray (single palloc, contiguous iteration)
S4 Batched MLP lookup pipeline in add_valid_vertex_edges
S5/C1 agehash library: INLINE Robin Hood hashtable with
_with_hash API, freeze, iter, and a regress-only selftest
S5/C2 Wire global graph edge_hashtable through agehash;
drop edge_id from edge_entry (key lives in slot header);
AGEHASH_MAX_LOAD=0.85; MemoryContextAllocHuge for SF10+
Performance (SF3 LDBC SNB, 5 runs/3 warmup, vs clean master baseline_v2):
IC1 8,625 → 7,117 ms −17.49 % (the headline; hashtable-bound)
IU1 40 → 35 ms −11.86 % (heaviest update; lookup-bound)
IC sum 198,958 → 197,367 ms −0.80 % (suite-level noise)
IS sum 1,009 → 1,028 ms +1.86 % (IS3 jitter; sub-ms)
IU sum 77 → 72 ms −6.64 %
IC2/3/4/5/6/7/8/9/10/11/12: parity (within ±3.3 %, mostly ±1.5 %)
The VLE-DFS-heavy queries (IC3/5/6/9/11) sit at parity: with
hash_search_with_hash_value at ≤1 % inclusive on their baseline flames, no
hashtable swap can recover meaningful wall-time on them.
Memory: removing edge_id from edge_entry saves ~416 MB on SF3 and ~1.4 GB on
SF10 for the global graph's edge_hashtable. Slot capacity uses
MemoryContextAllocHuge so SF10+ edge tables can be built.
Adds:
src/backend/utils/cache/agehash.c, src/include/utils/agehash.h
regress/sql/agehash.sql + expected/agehash.out (boundary selftest)
_agehash_self_test() in both fresh-install and upgrade SQL
Tested on PostgreSQL 18.3 (REL_18_STABLE): all 35 regression tests pass
(installcheck), warning-free build.
Co-authored-by: Claude <[email protected]>
modified: Makefile
modified: age--1.7.0--y.y.y.sql
new file: regress/expected/agehash.out
new file: regress/sql/agehash.sql
modified: sql/age_main.sql
modified: src/backend/utils/adt/age_global_graph.c
modified: src/backend/utils/adt/age_vle.c
new file: src/backend/utils/cache/agehash.c
modified: src/include/utils/age_global_graph.h
new file: src/include/utils/agehash.h
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
