[MOAB-dev] Sparse vs. dense tags

[Iulian Grindeanu]

I still have a question about the performance.
Down deep, it seems that a sparse tag data is stored with a std::map. Do I understand that right? (src/SparseTagCollection.hpp)
A dense tag is stored using arrays "parallel" to the sequences.
So when we have many handles (let's say, N entity handles that are set with a sparse tag value), access time to the data would be about O(log(N)). For a dense tag, access time is closer to O(1), there is still some searching of the right "sequence"

In this case, (geometric surfaces in a model), N is relatively small, so sparse tags would not incur a significant performance penalty.

If N is large (number of mesh nodes in a model), then sparse tags are more expensive in terms of CPU time and memory.

Iulian

----- Original Message -----
> So to make sure we have all the issues ...
> 
> * I don't think the inconsistency causes problems because the tags
> have
> the same interface regardless of what type they are. (Other than
> performance) it doesn't matter how they are created because they will
> be
> used with the same interface either way.
> 
> * In this case we want to use sparse tags because we only need to tag
> surfaces. There are very few surfaces and many entities, so sparse
> tags
> are better.
> 
> Paul
> 
> On 12/15/2010 04:23 PM, Tim Tautges wrote:
> > It should be sparse. The crucial difference is that when a dense tag
> > is given a value, all the entities in the same sequence as the one
> > whose tag is being set are also allocated storage for that tag. In
> > the case of many sets, this would waste some storage. It's a bigger
> > problem when tagging entities, though.
> >
> > - tim
> >
> > On 12/15/2010 03:09 PM, Steve Jackson wrote:
> >> The "GEOM_SENSE_2" tag, used to record the volumes on either side
> >> of
> >> a surface, is not consistently created as either sparse or dense.
> >> When created from DagMC and its utility tools, the tag is created
> >> as
> >> dense, but when created from GeomTopoTool (via ReadCGM), the tag is
> >> sparse.
> >>
> >> Questions:
> >>
> >> * How big a problem is this inconsistency? It doesn't seem to cause
> >> any errors or disruption.
> >>
> >> * Should the tag be dense or sparse? The tag is only used on entity
> >> sets that represent surfaces, so my guess is that it ought to be
> >> sparse, but I don't understand the implementation difference deeply
> >> enough to be sure.
> >>
> >> ~S
> >
> 
> --
> -- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
> --
> Paul Wilson ~ UW-Madison ~ 608-263-0807 ~ cal: http://bit.ly/pphw-cal
> Associate Professor, Engineering Physics. ~ http://cnerg.engr.wisc.edu
> Chair, Energy Analysis& Policy Program ~ http://nelson.wisc.edu/eap
> Note: I will be on sabbatical for the 2010-2011 academic year.