Variable Size Arrays: Performance Question

malbrechtmalbrecht Fabric for Houdini Posts: 752 ✭✭✭

Moin,

since KL does not have double-linked lists (which I could implement myself, but I'd like to stay "canon"): What is the fastest (text speak: instant) way of extending an array "to the left"?

What I mean is this: When resizing an array to a larger size, new entries are created at the end of the array. But what if I need new entries at the beginning, so that all entries that were (1, 2, ..., n) now become (x+1, x+2, ... x+n)? I do not want to actually copy the values over, since that would become insane with a particle setup of a couple of million entries.

I could, of course, use a "0-index" in my global variable set, so that "resize to left" would actively become "standard resize, but increase 0-index". That would give me "add entries to the virtual left", but makes the code more complex, as I'd have to carry along the "0-index" or "offset" marker.

If there isn't a fast (read: instant) way of doing it, I may revert to double-linked lists, but I could imagine that this (performance) question is slightly more than a goof-ball-geek-thing ...

Marc


Marc Albrecht - marc-albrecht.de - does things.

Comments

  • malbrechtmalbrecht Fabric for Houdini Posts: 752 ✭✭✭

    May I add a subquestion to this, maybe easier to answer?

    What's the fastest way to clear out the data in an array (to 0)? Setting the values to 0 or doing a resize(0), resize(originalsize)?

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Hi Marc,

    I probably didn't have an answer because there's not obvious ones. For your 2nd question, my guess is that setting the values to 0 is faster than re-allocating the array (which would be what happen if resize to 0 and then back to N). The fastest of course would be to put in a small C++ EDK extensions a "memset" call and pass the array data/size, since we don't have a memset call in KL.

    As for your 1st question, there's nothing right there to do it. Using a double linked list with individually-allocated nodes would be much slower. Using one that allocates nodes in a packed array would already be much better in term of performance (some classes in Containers could help a bit here). Your suggestion, if I understand it well, could be good too. If you're only adding data (and not removing in the middle), using 2 arrays as growing stacks for both direction (positive and negative items) is probably the fastest, but adds a bit of complexity, but you can encapsulate that in methods.

    Jerome Couture-Gagnon

  • malbrechtmalbrecht Fabric for Houdini Posts: 752 ✭✭✭

    Hi, Jerome,

    thanks a lot - that both makes sense as it does help. Yes, individually allocated nodes are slower, true, but it is so much more convenient (those were the days on VC20 and C64).
    I thought about growing/shrinking arrays, but that would mean I have to handle two arrays instead of one (or use an additional function layer), so I guess that the offset idea might be the best approach, as it only requires every call to an index in the array to be offset by an additional variable, which, hopefully, gets cached anyway.

    Setting to 0 ... I'll PEX it then. :blush:

    Marc


    Marc Albrecht - marc-albrecht.de - does things.

  • jcgagnonjcgagnon Fabric Employee Posts: 122 Fabric Employee

    Double linked lists have the dual cost of allocation and memory cache misses (hopping at different places in memory when traversing), which are among the most costly things in term of performance.

    As for PEX, given that setting to 0 in an array is very fast and cache-coherent, you should do simple tests to see at which moment it becomes faster to PEX, might be only when you have millions of items.

    Jerome

Sign In or Register to comment.