Page MenuHomeSoftware Heritage

Implement new graph API
ClosedPublic

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

Diff Detail

Repository
rDGRPH Graph service
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

haltode created this revision.Jun 30 2019, 3:12 PM
seirl accepted this revision.Jul 2 2019, 1:22 PM
seirl added inline comments.
api/server/src/main/java/org/softwareheritage/graph/Edges.java
2

Rename that to AllowedEdges.java?

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

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
haltode added inline comments.Jul 2 2019, 3:33 PM
api/server/src/main/java/org/softwareheritage/graph/algo/Visit.java
21

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

haltode updated this revision to Diff 5622.Jul 2 2019, 5:09 PM
  • Rename Edges class to AllowedEdges
  • Add unit tests for walk/ endpoint
  • Add unit tests for nodes sub-endpoint in visit/
haltode updated this revision to Diff 5623.Jul 2 2019, 5:12 PM

Rebase on master.

haltode removed a reviewer: zack.Jul 2 2019, 5:12 PM
haltode updated this revision to Diff 5624.Jul 2 2019, 5:20 PM

Rename 'EdgesTest' to 'AllowedEdgesTest'

This revision was automatically updated to reflect the committed changes.