Mesh stored as a linked-list or array

[vitorvas]

Hello Germán,

Any reason to store mesh data in a linked list instead of an array?
Just wondering if feenox tampers too much with the mesh or if it is mostly kept untouched after data is read. (talking about a gmsh mesh here).

Thank you!

[jeremyonscale]

Awesome question. Some things are stored in linked lists and some are stored in arrays.
The rule is: if I already know the total number of items, use an array. Otherwise, use a list.
Also, lists are used in "small" sets and arrays in "big" sets.
So the nodes and elements are stored as arrays. The physical groups and materials are stored in lists.

But everything can be improved!

I was always entertaining the idea of going back to data-oriented organization, i.e. instead of having an array of structs (say for the element), having several arrays of element ids, element types, connectivities, etc.

Sorry for the generality of the answer but the question was also general?
Maybe if you elaborate I can give you better directions.

[vitorvas]

Germán, by the way, could you share here the read_mesh.fee file? If we are comparing things I want to do it as close as you do. Thanks.

[gtheler]

Yes, sorry about that.

gtheler@tom:~/codigos/feenox/examples$ cat read_mesh.fee 
READ_MESH $1
PRINT elements
PRINT nodes
gtheler@tom:~/codigos/feenox/examples$ cat bunny.geo 
// https://upload.wikimedia.org/wikipedia/commons/4/43/Stanford_Bunny.stl
Merge "Stanford_Bunny.stl";
angle = 40;
includeBoundary = 1;
forceParametrizablePatches = 0;
curveAngle = 180;

ClassifySurfaces{angle * Pi/180, includeBoundary, forceParametrizablePatches, curveAngle * Pi / 180};
CreateGeometry;

// Create a volume as usual
Surface Loop(1) = Surface{:};
Volume(1) = {1};

Physical Volume("bunny") = {1};
Physical Surface("rest") = {3};
Physical Surface("base") = {2};

Mesh.MeshSizeMin = 0.8;
Mesh.MeshSizeMax = 0.8;
Mesh.ElementOrder = 1;
Mesh.MeshSizeExtendFromBoundary = 0;

gtheler@tom:~/codigos/feenox/examples$ 

[vitorvas]

vitors@DT32528CDTN-LX:~/workspace/feenox$ time feenox read_mesh.fee bunny.msh 
2.46555e+06
408867

real	0m14,735s
user	0m13,608s
sys	0m0,816s

It is not your big bunny, but mine.
Yet, no considerable difference between your test and mine. That's not what I expected.

I will dig into my notes and come back with the test I did. (What annoys me is that I only find time to "play" with feenox once here and there and I'm always coming back to remember what I was doing the last time...)

Regards,

Vitor

[vitorvas]

Just for completeness, the profile of read_mesh.fee

[gtheler]

Yes, one needs a couple of hours to enter into flow state.

Maybe your mesh is finer than mine. Feel free to comment out the call that adds elements to the node's lists and re-profile.

[gtheler]

Hey @vitorvas . Where are we on this subject?

[vitorvas]

Hello German, Didn't touch it since your explanation. Unfortunately, I have no plans at this time. Sorry. Regards, Vitor Em sáb., 28 de dez. de 2024 às 11:22, jeremy theler < ***@***.***> escreveu:

…

Hey @vitorvas <https://github.com/vitorvas> . Where are we on this subject? — Reply to this email directly, view it on GitHub <#22 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADFKFQX6KU55ONRUSRPXYBT2H2XYRAVCNFSM6AAAAABNIKHL56VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTCNRYGUYDSMQ> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[gtheler]

I was thinking that maybe replacing a list with a dynamic array or even hash would speed things up.
Then I realized that I was appending to a list each time a new element arrived, while I could directly prepend since I do not care about the order in the list: b3b4312

Theoretically, that should change $O(n)$ into $O(1)$.

@vitorvas can you run your test again and see if that profile improves and that 79% goes down?

[vitorvas]

Hi Germán, Sorry for the delay. Well, the machine I was using to test it is gone. I had it replaced and I do not even have a proper Linux on the new one. Actually, there are no Linux options anymore to work with. I will check if I still have access to the data on the old machine (if the machine is still physically on the premises) Sorry about that. Unfortunately, I work in a research center where the IT department works as if we were an ordinary business. It is a nightmare. I will let you know if I get it. Regards, Vitor Em qua., 12 de mar. de 2025 às 12:19, jeremy theler < ***@***.***> escreveu:

…

I was thinking that maybe replacing a list with a dynamic array or even hash would speed things up. Then I realized that I was appending to a list each time a new element arrived, while I could directly prepend since I do not care about the order in the list: b3b4312 <b3b4312> Theoretically, that should change $O(n)$ into $O(1)$. @vitorvas <https://github.com/vitorvas> can you run your test again and see if that profile improves and that 79% goes down? — Reply to this email directly, view it on GitHub <#22 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ADFKFQV6J2Z5N4KQJW7E2OL2UBGBBAVCNFSM6AAAAABNIKHL56VHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTENBXGY2TOMI> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[gtheler]

Don't worry. I'll profile with cachegrind before and after the fix.
I'll post the results here.