Skip to content

laziness in default graph implementation creates a hazard for concurrent reads #520

@jsichi

Description

@jsichi

Consider this scenario:

  1. Create a graph and populate it.
  2. Spawn two threads A and B. These threads run read-only algorithms on the graph, without making any modifications, but with no synchronization.
  3. Currently, undefined behavior may result due to certain lazy implementations in the default graph implementations. See for example
    protected DirectedEdgeContainer<V, E> getEdgeContainer(V vertex)

This is not a bug since we don't currently make any concurrency guarantees at all for these implementations, but it seems less than ideal, especially since the laziness really only optimizes the case of isolated vertices, which seems like an edge case (or should I say edgeless case?).

This also required some hackiness in the implementation of AsSynchronizedGraph to allow readers to share a lock: #500 (comment)

I'd like to hear opinions (@jkinable @d-michail @Yimismi) on how/whether we should address this. One resolution would be to just remove the laziness. Another would be to allow it to be controlled via a graph parameter of some kind.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions