Skip to content

Traverse relations graph right to left when checking relations#103

Merged
uatuko merged 4 commits intomainfrom
feature/rtl-graph-traversal
Jun 4, 2024
Merged

Traverse relations graph right to left when checking relations#103
uatuko merged 4 commits intomainfrom
feature/rtl-graph-traversal

Conversation

@uatuko
Copy link
Copy Markdown
Owner

@uatuko uatuko commented Jun 2, 2024 •
edited
Loading

This is a slight optimisation to reduce the BFS graph traversal cost with the expectation that the graph is narrower on the left and wider on the right. Most of the time this would be the case if principals are on the left.

e.g.
In the following example, to check user:jane -> reader -> doc:notes.txt with left to right BFS will require 10003 lookups whereas right to left will only take 3 lookups.

Relations graph, wider on the right

Benchmarks

Before 
-------------------------------------------------------------------------------------------
Benchmark                                 Time             CPU   Iterations UserCounters...
-------------------------------------------------------------------------------------------
bm_relations/check_graph/4/128     25076263 ns      3086440 ns          100 ops=323.998/s vertices=126.359k/s
bm_relations/check_graph/8/128     57364218 ns      7036899 ns           99 ops=142.108/s vertices=128.75k/s
bm_relations/check_graph/32/128   259431654 ns     33223300 ns           10 ops=30.0994/s vertices=120.458k/s
bm_relations/check_graph/4/512    101723773 ns     12166667 ns           57 ops=82.1918/s vertices=126.74k/s
bm_relations/check_graph/8/512    237103853 ns     27974560 ns           25 ops=35.7468/s vertices=128.474k/s
bm_relations/check_graph/32/512  1078407325 ns    137229800 ns            5 ops=7.28705/s vertices=115.908k/s
bm_relations/check_graph/4/2048   421086234 ns     51664538 ns           13 ops=19.3556/s vertices=119.037k/s
bm_relations/check_graph/8/2048   974933250 ns    118474000 ns            6 ops=8.44067/s vertices=121.09k/s
bm_relations/check_graph/32/2048 4466643000 ns    611284000 ns            1 ops=1.6359/s vertices=103.916k/s

-------------------------------------------------------------------------------------------
Benchmark                                 Time             CPU   Iterations UserCounters...
-------------------------------------------------------------------------------------------
bm_relations/check_graph/4/128       414345 ns        58750 ns        12076 ops=17.0214k/s vertices=102.128k/s
bm_relations/check_graph/8/128       646869 ns        91978 ns         7637 ops=10.8721k/s vertices=108.721k/s
bm_relations/check_graph/32/128     2107918 ns       321862 ns         2148 ops=3.10692k/s vertices=105.635k/s
bm_relations/check_graph/4/512       425155 ns        59755 ns        12022 ops=16.7349k/s vertices=100.41k/s
bm_relations/check_graph/8/512       664887 ns        92465 ns         7602 ops=10.8149k/s vertices=108.149k/s
bm_relations/check_graph/32/512     2142939 ns       311927 ns         2217 ops=3.20587k/s vertices=109k/s
bm_relations/check_graph/4/2048      430403 ns        58354 ns        12093 ops=17.1369k/s vertices=102.821k/s
bm_relations/check_graph/8/2048      678464 ns        91770 ns         7622 ops=10.8968k/s vertices=108.968k/s
bm_relations/check_graph/32/2048    2190622 ns       312404 ns         2219 ops=3.20098k/s vertices=108.833k/s

@codecov
Copy link
Copy Markdown

codecov bot commented Jun 2, 2024 •
edited
Loading

Codecov Report

Attention: Patch coverage is 88.88889% with 2 lines in your changes missing coverage. Please review.

Project coverage is 93.17%. Comparing base (bef3937) to head (c83821e).

Files Patch % Lines
src/svc/relations.cpp 88.88% 0 Missing and 2 partials ⚠️
Additional details and impacted files 
@@            Coverage Diff             @@
##             main     #103      +/-   ##
==========================================
+ Coverage   93.11%   93.17%   +0.06%     
==========================================
  Files          18       18              
  Lines        1307     1304       -3     
  Branches      161      160       -1     
==========================================
- Hits         1217     1215       -2     
  Misses         64       64              
+ Partials       26       25       -1

☔ View full report in Codecov by Sentry.
📢 Have feedback on the report? Share it here.

@uatuko uatuko marked this pull request as ready for review June 2, 2024 11:08
neculalaura
neculalaura previously approved these changes Jun 3, 2024
View reviewed changes
@uatuko uatuko merged commit 5714f1b into main Jun 4, 2024
@uatuko uatuko deleted the feature/rtl-graph-traversal branch June 4, 2024 05:56
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@neculalaura neculalaura neculalaura left review comments

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@uatuko @neculalaura