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

In reply to Memory allocation strategies by demerphq

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.