Iterate over active descendants

[Felipe Ponce]

I iterate a collection of cells, and for each one I have to iterate the active descendants.

Given a coarse cell, I use a FilteredIterator to iterate active descendants, but the method set_to_next_positive significantly slows down the code. Something I'd expect runs in 0.1 s takes 10 s. The filter is:

<start C++ code>
class ActiveChild
{

public:

  // Use CellId to check if is ancestor.

   CellId parent;

   ActiveChild(const CellId &parent)
   : parent(parent) {}

  template <typename Iterator>

  bool operator()(const Iterator &cell) const

  {

    // cell is the potential descendant.

    return parent.is_ancestor_of(cell->id());
   }
};
<end C++ code>

I iterate active descendants like:

<start C++ code>

using ChildIt = FilteredIterator<typename DoFHandler<2, 3>::active_cell_iterator>;

Triangulation<2, 3> tria;

unsigned int level; // level of coarse cell.

unsigned int coarse_cell_index;

CellAccessor<2, 3> coarse_cell(&tria, level, coarse_cell_index);

ChildIt cell(ActiveChild(coarse_cell.id()));

ChildIt endc(ActiveChild(coarse_cell.id()), dof_handler.end());

// This method, set_to_next_positive, is very slow.

cell.set_to_next_positive(dof_handler.begin_active());
for (; cell != endc; ++cell)

{

  // I use DoFHandler accessor to get global dof indices.

  cell->get_dof_indices(global_dofs);

  // Do stuff ...

}

<end C++ code>

Is there a better alternative to iterate active descendants? Why is  set_to_next_positive so slow here?

[Wolfgang Bangerth]

On 5/24/24 15:24, Felipe Ponce wrote:
> *
> *

> Is there a better alternative to iterate active descendants? Why is

> /set_to_next_positive/ so slow here?//

Is it? I would also expect it to be fast, but have also learned that you can't
judge where a code is slow without benchmarking it. So: Have you run your code
through a profiler to see where it's actually slow?

Best
W.

--
------------------------------------------------------------------------
Wolfgang Bangerth email: bang...@colostate.edu
www: http://www.math.colostate.edu/~bangerth/

[Felipe Ponce]

When I noticed that the preparatory steps took much longer than actually solving the system, I profiled by hand: commenting and uncommeting the code, and measuring elapsed times.

The first point where there is significant slow down comes at that method set to next positive.

I attach a simplified code where I use three methods. The second is the one I use. The third is a naive implementation, slower, and the first is the faster, but works for a special case where the descendants are direct children.

Probably, the problem is not the filtered iterator, but maybe I should re-think the algorithm, to avoid a costly search for active descendants.

--
The deal.II project is located at http://www.dealii.org/
For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
---
You received this message because you are subscribed to the Google Groups "deal.II User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/6cea45c8-6774-4cf6-909a-da8bd11a87f9%40colostate.edu.

[Wolfgang Bangerth]

On 5/27/24 00:28, Felipe Ponce wrote:
>
> Probably, the problem is not the filtered iterator, but maybe I should
> re-think the algorithm, to avoid a costly search for active descendants.

Yes. The three methods you show in your code are doing very different things:

// Method I: Iterate using indices.
for (index_t i = 0; i < coarse_cell.n_children(); ++i)
{
const index_t id_child = coarse_cell.child(i)->index();
}

Here, for each of the 384 coarse mesh cells in the outer loop (not shown) you
are only looping over the 4 children. So you are touching 384*4 = 1536 cells.


// Method II: Iterate using filter.

ChildIt cell(ActiveChild(coarse_cell.id()));
ChildIt endc(ActiveChild(coarse_cell.id()), dof_handler.end());

cell.set_to_next_positive(dof_handler.begin_active());
for (; cell != endc; ++cell)
{

cell->get_dof_indices(global_dofs);
}

Here, for each of the 384 coarse mesh cells, you are looping over *all* 1536
fine mesh cells. So you are touching 384*1536 = 589,824 cells in either the
set_to_next_positive() call or in the ++cell calls where you need to test
whether a cell is a descendant of the current coarse cell.


// Method II: Iterate without using filter.
for (const auto &cell : dof_handler.active_cell_iterators())
{
if (coarse_cell.id().is_ancestor_of(cell->id()))
{
cell->get_dof_indices(global_dofs);
}
}

And here you do the same, just by hand.

So you are doing fundamentally different things. I'm not surprised you get
fundamentally different run times :-)

[Felipe Ponce]

Thank you for looking at the code, I thought that the filter would do something magic (I was naive), but of course it cannot defied logical rules.

I ended up refactoring most of the code, looping first over the active cells, and now it is going much better.

--
The deal.II project is located at http://www.dealii.org/
For mailing list/forum options, see https://groups.google.com/d/forum/dealii?hl=en
---
You received this message because you are subscribed to the Google Groups "deal.II User Group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to dealii+un...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/dealii/c501a2b0-69c9-430d-87d0-eef1d765ab35%40colostate.edu.