cedar-policy / cedar

Implementation of the Cedar Policy Language
https://www.cedarpolicy.com
Apache License 2.0
889 stars 80 forks source link

Speed Improvement: Make incoming entities Arc<Entities> like schema entities #1296

Closed tomlikestorock closed 2 weeks ago

tomlikestorock commented 3 weeks ago

Description of changes

This provides a 3x speedup based on local benchmarking with a large schema that has big action entity hierarchy relationships. Today Entities.entities is a HashMap of <EntityUID, Entity>. When from_entities brings in the entities and actions from a given schema, it currently relies on Arc::unwrap_or_clone, which frequently ends up being clone. For a large set of very interrelated Actions, this repeated clone becomes expensive.

Changing Entities.entities to be a HashMap of <EntityUID, Arc<Entity>> allows us to keep the clone cheap, and Arc'ing the incoming Entities becomes cheap as well.

Changing the interface of the HashMap means altering what create_entities_map returns, adding an implementation of TCNode for Arc<Entity>, and udpating how IntoIterator works to return values from the Arc's.

Issue #, if available

This contributes to 1285.

Checklist for requesting a review

The change in this PR is (choose one, and delete the other options):

I confirm that this PR (choose one, and delete the other options):

I confirm that cedar-spec (choose one, and delete the other options):

I confirm that docs.cedarpolicy.com (choose one, and delete the other options):

cdisselkoen commented 2 weeks ago

Thanks for this work!

tomlikestorock commented 2 weeks ago

Protobuf tests updated to use Arc wrapped entities in 857509b.