[C++-sig] Module import / type registration performance

[John Loy]

Hi Everyone,

I recently opened a pull request for a pair of changes to improve the
time and memory costs when registering types and I'd like to also
solicit feedback from the list.

https://github.com/boostorg/python/pull/62

The brief summary is that there are a couple of places in the
inheritance registration code that scale as O(N^2).  For us, N has
become large enough that Boost Python is showing up in our internal
performance profiles during module imports.

The larger of the two changes (b565ac4) switches the smart_graph
structures to use a sparse representation.  The original smart_graph
behaves nicely when N is small and the graph is dense, but as N becomes
large, the cost of initializing the table becomes significant.  The
sparse representation cuts memory usage from hundreds of megabytes down
to tens of kilobytes.

The second change (e1d2da5) is for those of us using standard libraries
that implement std::list::size() in O(N) time, which results in
num_edges on our graph also being in O(N).  Adding casts is effectively
quadratic due to the repeated calls to num_edges.

Combined, these changes save ~400ms of application startup time on a
2.3GHz Haswell Xeon.

Let me know if you have any questions or concerns, especially if you
have performance targets that might be affected by these changes.

John