[MOAB-dev] Sparse vs. dense tags

[Paul Wilson]

Hi Iulian,

I was thinking more about memory performance.  A dense tag will allocate 
extra memory for every entity.  For n (entities that need the tag) << N 
(total number of entities) sparse tag is better on memory and also 
doesn't incur an access performance penalty.

So I think we agree...

Paul

On 12/15/2010 05:12 PM, Iulian Grindeanu wrote:
> 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.

-- 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ --
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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3369 bytes
Desc: S/MIME Cryptographic Signature
URL: <http://lists.mcs.anl.gov/pipermail/moab-dev/attachments/20101215/03bd11d6/attachment.bin>