On 24/08/2017 14:30, David Gibson wrote: >> >> Ideas what to tweak or what valgrind tool to try? > valgrind probably isn't that useful at this point. I think we need to > instrument bits of the code to find what the O(n^2) algo is and fix it. > > Seems to me checking if the address_spaces list is growing to O(n^2) > entries would be a good place to start.
The address spaces are O(n) (and so are the FlatView and the dispatch tries), but each of them has O(n) size. Eventually we use O(n^2) memory, but we build them O(n) times---which is expensive and also means, due to RCU, that there can be a short amount of time where it is between O(n^2) and O(n^3). The scheme I suggested elsewhere in the thread should cut one "n", by sharing one FlatViews and dispatch trie across all AddressSpaces. Paolo
