Page MenuHomeSoftware Heritage

Implement new graph API
ClosedPublic

Authored by haltode on Jun 30 2019, 3:12 PM.

Diff Detail

Repository
rDGRPH Compressed graph representation
Branch
new-api-implem
Lint
No Linters Available
Unit
No Unit Test Coverage
Build Status
Buildable 6631
Build 9259: arc lint + arc unit

Event Timeline

seirl added inline comments.
api/server/src/main/java/org/softwareheritage/graph/Edges.java
1 ↗(On Diff #5576)

Rename that to AllowedEdges.java?

api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
22

If you have the time, could you compare that with TreeSet? I'm not 100% convinced that LinkedHashSet would be faster.

This revision is now accepted and ready to land.Jul 2 2019, 1:22 PM
api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
22

TreeSet add operation is O(log(N)) while LinkedHashSet is O(1). The javadoc [1] seems to go with LinkedHashSet being faster too: "This implementation spares its clients from the unspecified, generally chaotic ordering provided by HashSet, without incurring the increased cost associated with TreeSet".

In practice this can of course vary, I found some benchmarks [2] where TreeSet is faster on smaller entries and LinkedHashSet faster on bigger ones. I guess we would need to do benchmarks in our specific case but that would be a bit overkill.

[1] https://docs.oracle.com/javase/10/docs/api/java/util/LinkedHashSet.html
[2] https://github.com/ThreaT/Java-Collections-Benchmark

  • Rename Edges class to AllowedEdges
  • Add unit tests for walk/ endpoint
  • Add unit tests for nodes sub-endpoint in visit/

Rename 'EdgesTest' to 'AllowedEdgesTest'

This revision was automatically updated to reflect the committed changes.