Use Hashtbl and mutable back edges to improve Graph construction time
Use Hashtbl and mutable back edges to improve Graph construction time

Summary:
This is a followup to D18580785, which dramatically reduced the time spent doing dependency graph operations in preparations for rechecks. This improvement came at the cost of maintaining a larger Graph data structure which includes backwards edges. The most significant portion of this cost is paid at startup, when we have to do the initial construction of a large structure.

This optimizes startup time by doing two things:

1. Makes the backwards dependency edges mutable, so that we don't have to allocate a new entry and update the Map with it (which causes allocations up the spine of the tree) each time we add a backwards edge. This change on its own was a modest, but measurable performance improvement.
2. Puts all the entries in a Hashtbl, so that we can access them in constant time to then mutate them. This led to an additional performance improvement.

I don't believe that any other similar scheme will be faster. The obvious choice is to build up the whole initial structure as a hashtbl and then convert it to a map after we've populated all the edges. However, the conversion to a map would likely be relatively costly, as we would have to build it back up using `Map.add` or similar. This would trigger a lot of key comparisons and tree rebalancings. Compare this to the `Map.map` call that we currently use to construct the map: the tree structure is already known, so no rebalancing, key comparisons, or searching is required. In other benchmarks that I have run, I have found that this effect means that `Map.map` is able to construct a map about **3x faster** than other equivalent construction methods.

This approach means that we allocate one map, with the fastest method of map construction I am aware of, exactly one entry per key, and the hashtbl. The lookups for backwards edges take advantage of the fast hashtbl lookups, and the backedge updates don't need to do any reallocation (save for the sets themselves).

Reviewed By: gabelevi

Differential Revision: D18924111

fbshipit-source-id: 7eedc42f3ee253516ab88e9ce4ceccbf1742a05e

facebook/flow,mroch/flow,samwgoldman/flow,facebook/flow,samwgoldman/flow,facebook/flow,samwgoldman/flow,mroch/flow,mroch/flow,facebook/flow,facebook/flow,samwgoldman/flow,samwgoldman/flow,facebook/flow,mroch/flow,mroch/flow,mroch/flow,samwgoldman/flow,facebook/flow,mroch/flow,samwgoldman/flow