Memory footprint of maps & sets

[OneOfTheDans]

Sometimes when I'm developing, it's useful to know How LabVIEW Stores Data in Memory. However, that article predates maps and sets, and I haven't been able to find details about how they're stored in memory. Can anyone point me to documentation on that, or describe it here if there's nothing publicly available?

Thanks,

Dan

[rolfk]

I don't think such documents officially exist. It is however safe to assume that the actual data is stored according to its binary data type so the information you found is pretty accurate. For the Set and Maps there is of course some additional information needed to manage the data. Since we know that the Variant attributes are stored as a red-black tree I would pretty much bet that this is also done here, which would mean a few extra pointers for each element in there.

[OneOfTheDans]

So you're describing that each element of the map or set is essentially a bundle of [key, value, pointer(s)] and each element could go sparsely anywhere in memory. This might explain some slow performance I've seen trying to copy large or complex maps. Depending on the key/value types, these could use a lot more memory than the key/values alone.

[rolfk]

It's a sort of linked list, and while there are certainly potential problems in corner cases with that, it is one of the most performant ways of storing such information, albeit not the most simple in terms of code to deal with them. You may be able to shave off a few bytes here and there by using linear arrays to store information but the performance for that is usually always a lot worse for most operations and linear memory spaces quickly can fragment memory to a point where things get unmanageable for large datasets.

If both your keys and values are simply integers, then yes the overhead for the linked list type storage can be quite heavy, like potentially quadrupling the necessary memory compared to the pure key/value storage, but what are we talking about here? Are you saying you make maps with millions and millions of key value pairs? If so you may be actually abusing them. You won't have significantly better performance in any other Map implementation, be it .Net, Java or similar, which all are build in many ways around the idea of Maps and Sets for a lot of things.

Unfortunately there isn't an egg laying wool sheep milk cow in software that does everything from being super memory savy, easy to use and performant all at the same time.

[OneOfTheDans]

---

@rolfk wrote:

Unfortunately there isn't an egg laying wool sheep milk cow in software that does everything from being super memory savy, easy to use and performant all at the same time.

---

😅 I didn't mean to complain about the Maps or Sets, I know there are always tradeoffs to different structures. It would be nice if NI provided official documentation so we can assess the tradeoffs without assuming the details. Anyway, until that exists I'll work with your description of the sparse linked list of bundles of key/value/pointers. Thanks for the explanation!

[rolfk]

---

@rolfk wrote:

Unfortunately there isn't an egg laying wool sheep milk cow in software that does everything from being super memory savy, easy to use and performant all at the same time.

---

Actually I misspoke. There is such a thing, it is called FINO (First In Never Out) also sometimes referred to as /dev/null. Uses virtually zero memory, is super fast and very simple to program. 😁

[wiebe@CARYA]

I have noticed that maps\sets can be expensive. I haven't run extensive tests, but intuitively relatively small maps in classes make copying the classes sluggish. And that makes sense, as there is memory overhead in maintaining the structure.