• From: Gothenburg, Sweden
  • Registered: 08-09-2009
  • Posts: 1,419

Topic: Local numering is a headache

Short version
If we used a unordered_map instead of AList/vector to store Nodes and Elements, we could stick to global numbering everywhere!
With ranged-based for loops, most of the code would stay the same.

Long version
The local numbering we have is quite the headache, in particular, when it comes to load balancing.

Understanding the details of the innocently looking "Domain :: commitTransactions" function took me several days. I only had to do this because I wanted to switch out the container "AList<>" to a "vector<unique_ptr<>>" for the nodes and elements.
That function is so very sensitive to the order of which the operations occur.
We, of course, have to send the nodes in their global numbering, but now we have the old elements keeping track of the old local numbering, and the new elements keeping track of the global number. It's caused me many headaches.



All of these problems would instantly disappear if we just stuck with the global numbering all the time.
This would mean switching the vector to a unordered_map for storing Nodes and Elements. Moving nodes would be trivial. No renumbering anywhere. "Domain :: commitTransactions" would be just a few lines of code (removing or adding values to the existing maps).

It would of course come with the computational cost instead. Is the hash expensive? OOFEM does call "giveNode(int n)"  a lot, and it could have a noticeable effect (though, considering we have to dereference several layers of pointers each time to access our data, a hashing function might be insignificant).

It's an idea worth considering.

  • From: Gothenburg
  • Registered: 25-06-2013
  • Posts: 26

Re: Local numering is a headache

I agree, it's an idea worth considering. The fact that we currently have to keep track of if an element index refers to the element number or the index in the element array is error prone. Sticking to global numbering all the time avoids this risk for unnecessary bugs.

To evaluate the performance, could we (just as a test) replace the dofManagerList with an unordered_map (keeping the rest of the code unchanged) and run some benchmarks? What I mean is, change
std :: vector< std :: unique_ptr< DofManager > > dofManagerList;
to
std :: unordered_map< std :: unique_ptr< DofManager > > dofManagerList;
change nothing else, and run some benchmarks. Then, we will quickly see if the lookup time for unordered_map becomes
a bottleneck in this case.

/Erik

  • From: Gothenburg, Sweden
  • Registered: 08-09-2009
  • Posts: 1,419

Re: Local numering is a headache

Yes,
Though I just realized that it won't be as straight forward replacement as i first thought. Iterating over a map will give a std::pair<key, value>, and not only the values.
Unfortunately, there doesn't seem to be any good way to just say   "for element in elements.values():" as you would in Python, unless you use Boost, e.g.

#include <boost/range/adaptor/map.hpp>

for(auto&& i : foo | boost::adaptors::map_values){
  i->bar();
}

4 Reply by bp

  • bp
  • Administrator
  • Offline
  • From: Prague, Czech Rep.
  • Registered: 02-03-2007
  • Posts: 1,026

Re: Local numering is a headache

I agree that it would simplify a lot of stuff.
But we should keep in mind the price for that, in terms of performance decrease, that has been already mentioned. The tree search complexity is in optimal case proportional to  O(log n) for balanced trees. When the problem gets bigger, the impact of this change would be bigger. Unfortunately, this is exactly where the efficiency  plays important role.
So at least we should consider several benchmaks of increasing complexity.

Borek

bp's Website

  • From: Gothenburg, Sweden
  • Registered: 08-09-2009
  • Posts: 1,419

Re: Local numering is a headache

It would probably be a std::unordered_map (ammortized O(1) access for a good hash)  if anything, to make sure we have decent performance for larger meshes.
Also, with the range-based for-loops, looping over all elements would be O(n) as before.