AMGraph should use unordered collections

[cakarsubasi]

Right now, AMGraph uses std::map to store adjacency information. This is mostly unnecessary since abstract node identifiers don't have any logical lexicographical order and changing it to std::unordered_map will improve performance and memory usage. NodeSet type should also be changed to unordered_set.

The exact performance impact of this is difficult to say but right now it appears to be around 10% for the RsR which is too good to pass up. Other parts of GEL might benefit more especially if the average valency is very high.

Some quick and dirty benchmark runs:

n = 34834

# Ordered sets:

### Lazily generated neighbors
Spent 2156 milliseconds on Algorithm
Spent 554 milliseconds on Split components
Spent 293 milliseconds on Estimate and smooth normals
Spent 730 milliseconds on Correct normal orientation
Spent 3735 milliseconds on Whole process

### Eagerly generated neighbors
Spent 2232 milliseconds on Algorithm
Spent 543 milliseconds on Split components
Spent 280 milliseconds on Estimate and smooth normals
Spent 742 milliseconds on Correct normal orientation
Spent 3798 milliseconds on Whole process


# With unordered versions:

### Lazy:
Spent 2042 milliseconds on Algorithm
Spent 371 milliseconds on Split components
Spent 261 milliseconds on Estimate and smooth normals
Spent 653 milliseconds on Correct normal orientation
Spent 3330 milliseconds on Whole process

### Eager:
Spent 2104 milliseconds on Algorithm
Spent 393 milliseconds on Split components
Spent 291 milliseconds on Estimate and smooth normals
Spent 623 milliseconds on Correct normal orientation
Spent 3412 milliseconds on Whole process

The problem of course is that the graph algorithms in GEL have a very large API surface.

Some parts assuming sorted data structures:

• AMGraph::shared_neighbors
• Geometry::test_intersection
• Geometry::NodeSet (typedef)
• There are probably others but it's a bit hard to tell at a glance if a piece of code is assuming something is sorted.

It is of course possible that there are no other places since neighbors sorted by ID are not very useful unless you are using the C++ set operations. In which case, this is probably doable in a few hours.

There is also an issue that there are two definitions of Geometry::connected_components that are disjoint solely because of the difference in types. Making AMGraph::NodeSet unordered means we have a duplicate definition so one of them has to be removed. Although they do appear to do exactly the same thing so this shouldn't be a problem.

---

I would like to also add a way to lazily acquire the neighbors of a graph node since this is called quite a few times across RsR (in 9 places by my count) and doing so would reduce allocations. This one is fairly simple to add:

        [[nodiscard]] std::ranges::borrowed_range
        auto neighbors_lazy(const NodeID n) const
        {
            return edge_map[n] | std::views::keys;
        }

Util::Range should also be removed and replaced with iota_view.

[cakarsubasi]

As a further note, std::unordered_map is still quite slow largely due to how it is implemented. It is possible to get a much greater performance improvement using a flat hash map. For example using the flat_hash_map here: greg7mdp/parallel-hashmap

Spent 1954 milliseconds on Algorithm
Spent 189 milliseconds on Split components
Spent 292 milliseconds on Estimate and smooth normals
Spent 402 milliseconds on Correct normal orientation
Spent 2840 milliseconds on Whole process

Now, vendoring an external hash map would of course be a more elaborate process (in terms of licensing) but given the relatively significant performance impact, I wanted to bring this up.

[janba]

These are (several) good points.

I think there is no good reason to use map rather than unordered_map, and indeed I already changed much of the skeletonization code to use unordered node sets, so having unordered be default would make the code cleaner. As you probably guessed, I am less keen on introducing an external dependency or adding more code from other people, so sticking to unorderd_map would be my preference.

As you point out, the two functions shared_neighbours and test_intersection (both computing intersections) will need to be rewritten for unordered collections. This is trivial, but I am not sure about the efficiency ramifications. Probably, they will have similar efficiency and I am almost sure that they are the same asymptotically. Do you have thoughts on this?

Also, it is embarrassing that I have two almost identical connected_component functions. Merging those into one would be great.

Agreed, Util::Range is just redundant at this point and should be replaced with iota.

Finally, I also agree that neighbours_lazy would be an improvement. I have a great deal to learn about C++20, but having grokked what it does, it seems to be the right way to go. Would we ever need the non-lazy version?

To the extent that you have already made some of these changes, a PR is appreciated, but don't feel compelled to refactor code that is not really needed for your project.

[cakarsubasi]

The built-in unordered_map uses buckets with linked lists which has one specific benefit (pointer stability) that is not really relevant to any of our use cases but comes at the expense of cache locality. What we usually want is just an open addressed hash table like the SwissTable. I'm bringing it up since the performance difference is quite large and it will most likely be much larger for algorithms that rely much more heavily on AMGraph. I can also write my own open addressed hash table but there are some tricky parts (namely re-hashing) where I don't want to reinvent the wheel. I'm writing it down for your consideration of course. With a little care, it is also possible to write code that is generic over both implementations and opt-into a third party hash table.

---

shared_neighbors does quite a bit of unnecessary work, eagerly calculating the neighbors of both nodes and returning a third vector, so it can be easily written to be way faster. ´test_intersection` will probably be slower but it is likely that rebalancing the RB-trees of std::set dominates the runtime. Asymptomatic runtime is unchanged.

---

I have noticed some minor ergonomic issues with iota_view. Namely, when the template arguments are both size_t, the difference_type of iota_view becomes 128-bits long which was not acceptable for "legacy iterators" under C++20, so you can't do this:

vector<NodeID> seeds(begin(g.node_ids()), end(g.node_ids()));

This is only used one time in GEL out of 30 or so calls to node_ids() however and it is easy to work around. It is also fixed in newer compiler versions. There are also other places where I can use iota_view and not Util::Range (without changes at least).

---

The eager versions let you modify the underlying collection since you are given a copy. Of course, you can always create a copy with the lazy version, and there is no place in GEL where we modify the graph while iterating over the neighbors (and it is generally a bad idea anyway).

The other advantage for eager functions is readability and being more debugger friendly. neighbors returns an std::vector<NodeID> and everyone knows what that is and you can look at what it contains in a debugger. neighbors_lazy which I wrote above uses a constrained auto return type. Because the actual return type is something like this:

std::ranges::elements_view<std::ranges::ref_view<const std::map<unsigned long, unsigned long>>, 0>

And it is not clear at first glance what this actually is. Now, of course it is possible to compensate for this by using a concept that also names the value type of the view and better documentation and examples but keeping the eager version does not hurt.

---

I will most likely merge most of these changes with the rest of RSR improvements but it's important to discuss some of them since they affect other core functionality. I can also split them if you'd like.

[janba]

I think it is fine to include them with the other RSR improvements. Perhaps the introduction of a new data structure should be a separate change, though, if you do that. Checking the skeletonization code is, of course, also important when the changes are applied.

[cakarsubasi]

I also looked into how phmap can be included and if we don't vendor it, the simplest way is to just let CMake install it globally.

# Include the parallel-hashmap library
include(FetchContent)
# Our headers depend on it, so we need to it alongside GEL
set(PHMAP_INSTALL TRUE CACHE INTERNAL "Install parallel_hashmap")
FetchContent_Declare(
    parallel-hashmap
    GIT_REPOSITORY https://github.com/greg7mdp/parallel-hashmap.git
    GIT_TAG        v2.0.0    # adjust tag/branch/commit as needed
)
FetchContent_MakeAvailable(parallel-hashmap)
# Pass the directory to GEL during a build
target_include_directories(
    GEL PUBLIC
    $<BUILD_INTERFACE:${parallel-hashmap_SOURCE_DIR}>
    )

This creates such a directory structure at installation:

FetchContent also tries find_package based on my understanding, so no download is performed if it is already installed.