demerphq has asked for the wisdom of the Perl Monks concerning the following question:

Greeting Monks,

I have a module that uses a data structure that is a packed array of long integers to represent a tree. (The string is in fact a Tie::Array so it is used as though it were a real perl array.) Each "node" of the tree comprises of a sequence of 11 long's. When building the tree each insert into the tree typically adds several nodes to the tree. Currently this occurs one node at a time, meaning that the string grows 44 bytes at a time. Now if my understanding of Perls string memory management is correct, the string will have to be reallocated and copied every time a new node is added.

Aside: Please don't suggest that I use an array instead. I have already looked into this and it is unsuitable to my requirements. First off I need to have the array in packed form to be able to pass it into an Inline::C function. Furthermore the number of entries in the array can grow very large and the overhead of storing the values as SV's becomes unacceptable. A runtime overhead of copying the data around occasionally is a far more acceptable scenario than the memory wastage involved in using a perl array for this purpose.

So what id like to do is to use some form of preallocation to reduce the number of times the string has to be extended. What I'm unsure about however is what a good strategy for this should be. On one hand I dont really want to allocate too large a chunk as this will result in quite a bit of wastage when the structure stops growing, nor do I want to allocate in small chunks as this just leaves me in the same situation as before. I was thinking perhaps of a strategy where the chunk size allocated doubles each time up to some maximum where it then stays.

Im curious as to what the monks out there think would be a good strategy for this. Any suggestions or links or whatever would be much appreciated.


---
demerphq

<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...

Replies are listed 'Best First'.
Re: Memory allocation strategies
by Abigail-II (Bishop) on Sep 01, 2003 at 22:08 UTC
    You can do the preallocation by extending the string, and then shrinking it again. Extending the string results in new allocation, the shrink is fast (just setting a pointer) and subsequent additions to the string don't result in new allocation - until you've reached the end of your preallocated memory.

    You may have to do some bookkeeping, keeping track of how far you have preallocated, and how long the current string is. If you run out of preallocated space, allocated another chunk.

    Abigail

[reply]

      You can do the preallocation by extending the string, and then shrinking it again.

      Ahah! An excellent suggestion. Thank you. I wonder though if you have any thoughts on the determining of a suitable chunk size? Should it be fixed size? Or dynamically sized? Or should I provide more information? Im not sure whats relevant. :-(


      ---
      demerphq

      <Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
[reply]
[d/l]

        The good thing about the doubling strategy is it keeps the number of reallocations to a minimum. The bad things are

        • You are copying more and more each time.
        • It requires more and more shuffling of heaps at each level--perl internal, C-runtime, OS--to find a big enough chunk of contiguous memory to satisfy the reallocation.
        • When you are approaching your maximum size, adding 1 more element to your array that takes you over the current 'power of 2' is going to double your memory usage of which just under half is wasted in the extreme case.

        I think I would use a different strategy. I would modify Tie::Array to (hold your breath:) use an array! Not for the individual elements, but for an array of dynamically grown but fixed maximum size 'buckets'. With array indices, working out which bucket to use to retrieve any individual element of the actual array is simple math.

        Preallocate the first bucket to say 16k minimum and use the doubling strategy to reallocate it up to a maximum of say 64k or 128k. Then, allocate a second bucket and follow the same strategy. You can also preallocate the size of the array to some reasonable starting point.

        This strategy minimises both the total memory allocation when the array is fully completed by keeping the wasted space to a maximum of your bucket size. It also keeps the amount of memory that needs to be copied each time reallocation occurs to that half of that same value. It also minimizes the 'perl array' overhead.

        The values of 16k and 64k are just examples. Choosing the right initial and maximum sizes for your buckets will depend very much on your rate of growth etc. One interesting number is 180224. This is 44 * 4096. Using this as your maximum bucket size means that you would prevent any wastage within each bucket and simplify the math as 44 fits in an exact number of times. You could use the doubling strategy starting with an initial allocation of 11* 4096 = 45056; and double until you reach 44 * 4096 = 180224. This keeps the maximum wastage at completion reasonable and allows an integral number of your 44 byte blocks to fit at each stage.

        Using 44 * 4096 as the maximum bucket size to store 100 MB of data would use a bucket array of 582 elements (buckets). Preallocating a 582 element array of null scalars uses around 132k gving an overhead of just 0.13% which doesn't seem to bad.

        The reason for using 4096 is because Win32 tends to round up memory commits to the nearest page size which is 4096 on intel. However, it is quite likely that perl adds some overhead bytes to each allocation beyond those of the user data-structures in order to manage its internal heaps. It is also quite likely that if your perl is calling the compiler runtime to alloc its heaps, that they are also adding a few bytes to each allocation for their internal use.

        Overall, working out the actual overheads on any given allocation given the documented overhead of perls scalars and array chains, the undocumented overhead of perls and the runtimes heap management is pretty impossible, so using the 4k OS pagesize as the basic unit seems as good a way to go as any. On other OSs and platforms this would probably be different.

        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
        If I understand your problem, I can solve it! Of course, the same can be said for you.
[reply]
        I wouldn't use fixed size, but a chunk size that's linear in the current size. BrowserUK mentions doubling, but that may be a bit extreme. For arrays, Perl uses a "20% more" strategy. Perhaps that works well for your problem as well; but you may have to experiment with different values to come to suitable value.

        Abigail

[reply]
        a nice idiom for preextending strings is 
        substr($a, length($a), 100, "")

        [download]
        At least I think it works. This came up on p5p when I was arguing that you should be able to do 
        length($a) = 20;

        [download]
        to truncate a string to 20 chars. Due to a less than clear initial posting, most people thought I was looking for pre-extension and someone said I should just use the above.
[reply]
[d/l]
[select]

Back to Seekers of Perl Wisdom