poor performance in exodus.get_block_id_map()

[jessejcarter]

I'm trying to look up the element ids of a given block id using the exodus.get_block_id_map() method and getting poor performance on my mesh with > 1000 blocks. (I suspect it is doing a linear lookup and I'm doing this for all N blocks, so O(N^2) performance). Is there a better way to get the block that an element belongs to or vice versa?

[gsjaardema]

If there are going to be many queries of this type or lots of blocks, I usually get all of the block ids via elem_blk_ids = exo.get_elem_blk_ids() and then for each block, get the element count via count[i] = get_entity_count(objType, elem_blk_ids[i]) and then create a sum of those running from 0 ... num_element_block+1 such that for block i, the range of elements is count[i] ... count[i+1] and then you search that block to see if the element you want is in the range.

given element with index X, find i such that count[i] <= X < count[i+1] and then that element is in block i.

[jessecarterMOOSE]

I see. Thanks. Is the ordering of elements from exo.get_elem_id_map() going to align with the count? In other words, what if I'm trying to do the opposite of your example, that is, given a block id i, what element ids exist on that block? I'm guessing if I sub-divide the element id map into sections based on the count of each block, each piece will correspond to the elements of the corresponding block - but want to verify.

[gsjaardema]

I don't think that elem_id_map buys you much in this case. If you are using the element INDEX, then elem_id_map just runs from 1..number_elements. If you don't mind using storage of size num_elements, you can do something similar to what I had above, create an array of size num_elements, and then fill the first count[0] elements with the value of elem_blk_ids[0], similarly for i = 1 .. number_element_blocks (the next count[1] elements have elem_blk_ids[1], ...) and then you have a direct mapping that block_id = array[element_index]

[gsjaardema]

And rereading your comment, I think what I originally gave you does what you want. Once you do the sum of the counts, then given block_id id, you search for that id in elem_blk_ids and that gives you an index i into count which says that element block id has the elements from count[i] to count[i+1]

For example, if elem_blk_ids[] = 100, 200, 300 and there are 11, 22, and 33 elements in those blocks, then count[] = 0, 11, 33, 66`

So If I have id =200, I search and see that it is at index 1 in elem_blk_ids and it contains elements count[1] to count[2] which are 11 to 33

Hope that makes sense and I am reading the question correctly.

[jessecarterMOOSE]

I think that makes sense if the element IDs are contiguous. That won't be the case for my application, so I'm trying to back out the original IDs. That's what I thought the elem id map was for.

[gsjaardema]

Yes, if you have "global ids" which are not the 1..number_elements, then you have to do something like you were doing to map global element id to index and then can use the index in some of the options I showed above. Sorry, didn't realize you were using the global ids.

[jessecarterMOOSE]

Yeah, sorry, I should have mentioned that sooner.

What about the original question on performance? Will this new method have similar issues?

[gsjaardema]

I think the main performance cost in this is the reverse lookup of converting from a "global" id (gid) to the elements index. There are multiple ways to do this --

1. sequential searching through the block_id_map for gid
2. Using a map with the gid as the key and the index as the value
3. convert block_id_map to storing pairs of <gid,index> and then sort on gid and use binary search to return the index...
4. Create a hash-map with 'gid' as the key and index as the value.

Each of these has tradeoffs on memory / speed and the best choice probably depends on the number of elements and the number of queries...

In our C++ code that does something similar to this, we do a binary search into a sorted vector of <gid,index> pairs usually since that seems to give the best performance on large models due to cache locality -- in most of our uses, the queries end up close to the previous query...

[jessejcarter]

I can get O(N) runtime performance using this new method with the same results. 👍