codenode

"A designer achieves perfection when nothing is left to remove." —Saint-Exupéry

Perl memory usage

with one comment

perldebguts says,

Perl is a profligate wastrel when it comes to memory use. There is a saying that to estimate memory usage of Perl, assume a reasonable algorithm for memory allocation, multiply that estimate by 10, and while you still may miss the mark, at least you won’t be quite so astonished. This is not absolutely true, but may provide a good grasp of what happens.

I’m going to look deeply into Perl memory usage because people want mk-query-digest to use less memory. The code, presently, uses 75.02M rss, 116.33M vsz to process a 96M slowlog. Theoretically, (1) there should not be a one-to-one correlation between input log size and memory consumption and (2) memory consumption should not grow if the number of unique queries (i.e. classes) does not grow. Theory (1) is true in most cases but (2) is in debate.

Scalars

Using Devel::Size, Devel::Peek and a good understanding of perlguts, let’s start with some simple measurements (64-bit platform):


$i = 42
#  24 bytes of memory
SV = IV(0x919bd0) at 0x919bd8
  REFCNT = 1
  FLAGS = (PADMY,IOK,pIOK)
  IV = 42

$s = "42"
#  56 bytes of memory
SV = PV(0x8f1b68) at 0x919b60
  REFCNT = 1
  FLAGS = (PADMY,POK,pPOK)
  PV = 0x913ab0 "42"\0
  CUR = 2
  LEN = 8

So an integer requires 24 bytes of memory when stored as a Perl SvIV. This makes sense because the SV struct is:


struct sv {
    void* sv_any;      /* pointer to something */
    U32   sv_refcnt;   /* how many references to us */
    U32   sv_flags;    /* what we are */
};

On my 64-bit platform each of those members will be 8 bytes (64 bits), hence 24 bytes total.

The string, $s, has two structs: the SV struct which points to:


struct xpv {
    char * xpv_pv;   /* pointer to malloced string */
    STRLEN xpv_cur;  /* length of xpv_pv as a C string */
    STRLEN xpv_len;  /* allocated size */
};

The reported size 56 – 24 for the SV struct – 8 bytes (LEN) for the string leaves 24 bytes which, I presume, corresponds to the xpv struct, each member of it also being 8 bytes. When the string is increased to 8 characters Perl takes 16 bytes of memory:


$s = "42abcdef"
SV = PV(0x16dcb68) at 0x1704b90
  REFCNT = 1
  FLAGS = (PADMY,POK,pPOK)
  PV = 0x16feab0 "42123456"\0
  CUR = 8
  LEN = 16

A null byte (\0) is stored, too, so more memory is used for the string at 8 visible characters because it’s really 8 + 1 for the null-byte, therefore exceeding the 8 bytes allocated previously.

A simple test shows that Perl increases a string’s allocated size in 8 byte increments: 16, 24, 32, 40, 48, etc. And, as we should expect, if $s = '' or undef, the memory is not deallocated.

Arrays

Let’s look at an array:


my $ar = [];
# 176 bytes of memory
SV = RV(0xa7bbe8) at 0xa7bbd8
  REFCNT = 1
  FLAGS = (PADMY,ROK)
  RV = 0xa56df0
  SV = PVAV(0xa57fb0) at 0xa56df0
    REFCNT = 1
    FLAGS = (RMG)
    MAGIC = 0xae3ab0
      MG_VIRTUAL = &PL_vtbl_arylen_p
      MG_TYPE = PERL_MAGIC_arylen_p(@)
      MG_FLAGS = 0x02
        REFCOUNTED
    ARRAY = 0x0
    FILL = -1
    MAX = -1
    ARYLEN = 0x0
    FLAGS = (REAL)

An interesting thing happens when we push an integer value to the array: its size increases by 56. Subtracting 24 bytes for the SvIV pushed onto the array, 32 mystery bytes remain. These bytes are four 8 byte pointers corresponding to four array elements that Perl auto-creates: one for the SvIV just pushed and three in anticipation of more values.

Something else interesting happens when we push an array’s FILL beyond its MAX: Perl auto-extends the array thusly:

  • First push to empty array: auto-extend by 4 pointers/elements, use element 0, 3 elements free, MAX=3
  • First push past MAX: auto-extend by 2 pointers, use element 4, 1 element free, MAX=5
  • Subsequent pushes past MAX: auto-extend by 2^pushno pointers, where pushno=3++

So empty arrays are auto-extend by 4, 2, 8, 16, 32, 64, 128, 256, 512, 1024, etc. pointers when pushed to. This is kind of odd and I don’t know why it works this way but that’s what my tests show. What is learned is that Perl becomes exponentially more aggressive in auto-extending an array when you push it to the limit. E.g. when MAX=509, the next push will increase MAX=1021. In a certain sense, this means 511 pointers are unused and, at 8 bytes each on a 64-bit platform, that accounts for 4088 bytes of unused memory.

If an array is pre-initialized with one value (i.e. defined at its declaration) then Perl auto-extends it differently. $rr = [42] creates an array 208 bytes large: 176 minimum, 8 byte pointer, 24 byte SvIV. What happens we push to an array pre-initialized with on value? The first push (i.e. the 2nd element, index 1) does not cause Perl to auto-extend the array; it just increases both FILL and MAX to 1. But, strangely, the second push causes Perl to auto-extend the array, increasing MAX to 5. From here on, Perl begins exponentially auto-extending the array by 2^pushno pointers. So arrays pre-initialized with one value are auto-extended by 1, 4, 8, 16, 32, 64, etc. pointers at each push.

If the array is pre-initialized with more than one value, it begins with only that many pointers/elements, and begins auto-expanding when the third or greater element is pushed. For example, if the array is pre-initialized with 2 elements, pushing a third causes MAX to auto-expand to 5; or, if the array if pre-initialized with 6 elements, pushing the seventh causes MAX to auto-expand by 8, from MAX 5 to 13. Whenever an array is pre-initialized with more than 6 values, the first push auto-extends the array to appropriate bucket size (explained next) and subsequent pushes past MAX are exponentially auto-extended.

Therefore, we observe in general that Perl has exponentially (2^N) increasing bucket sizes with zero-index/MAX boundaries at 3, 5, 13, 29, 61, etc. Pushing values to any array (empty or pre-initialized) eventually causes Perl to auto-extend MAX to these bucket boundaries when/if FILL is pushed beyond MAX. Memory for pointers to the auto-extended array is “wasted” until unused. (This is, of course, done for speed: keep extra pointers/memory available so they don’t have to be allocated when needed.)

Hashes

An empty hash requires 136 on a 64-bit platform, slightly smaller than an empty array, but–more realistically–the most minimal hash requires 194 bytes:


$hr = { "" => undef };
# 194 bytes of memory
SV = RV(0x8ecbe8) at 0x8ecbd8
  REFCNT = 1
  FLAGS = (PADMY,ROK)
  RV = 0x8c7df0
  SV = PVHV(0x963b78) at 0x8c7df0
    REFCNT = 1
    FLAGS = (OOK,SHAREKEYS)
    ARRAY = 0xa12670  (0:7, 1:1)
    hash quality = 100.0%
    KEYS = 1
    FILL = 1
    MAX = 7
    RITER = -1
    EITER = 0x0
    Elt "" HASH = 0x0
    SV = NULL(0x0) at 0x8c7fe8
      REFCNT = 1
      FLAGS = ()

So each hash entry costs at least 194 – 136 = 58 bytes; we’ll confirm this later but first let’s expand the key character by character and see how the hash’s size grows. Using this code,


for my $key_len ( 1..4_096 ) {
   my $key = 'x' x $key_len;
   my $hr  = { $key => undef };
   print "$key_len char key = ", total_size($hr), " hash\n";
}

we get results like,

1 char key = 195 hash
2 char key = 196 hash
3 char key = 197 hash
4 char key = 198 hash
...
4094 char key = 4288 hash
4095 char key = 4289 hash
4096 char key = 4290 hash

So each key’s size is added to the hash’s total size. If each hash entry is 58 bytes and each key adds its length to the total hash structure size, then two, single character keys with undef values should result in a total hash size of 136 + 58 + 1 + 58 + 1 = 254. This exactly what Devel::Size::total_size() reports for


my $hr = {
   'a' => undef,
   'b' => undef,
};

Notice that Perl stores a pointer to the “scalar value that was hashed”. Hence the key’s length adds to the hash’s total size. This is seen in the hash entry structure:


struct he {
    HE      *hent_next; /* next entry in chain */
    HEK     *hent_hek;  /* hash key */
    SV      *hent_val;  /* scalar value that was hashed */
};

hent_val, I’m told, is used for collision detection/resolution. Since it’s a pointer to the original scalar value, that SV should have its reference count increased by one (because the hash is referencing it) which means that even if the original SV goes out of scope, the hash will keep it alive. So if we do (pseudo code),


my $hr = {};
for ( ... ) {
   my $key = ...
   $hr->{$key} = ...;
}

then the hash will keep alive all the scalars created in the loop via its references to them. These scalars are no longer directly accessible in Perl, but they’re lurking there in memory nonetheless. The vast majority of keys created by mk-query-digest are created in loops; that explains my interest in this point.

Briefly, tests show that key => undef is identical to "key" => undef, so all hash keys become scalar strings.

If we add real values to our keys, we should get a predictable increase in size. A single entry, single character key hash is 195 bytes when the key’s value is undef. If the key’s value is an integer scalar, there is no increase in size because undef is a special type of SV so the two require the same amount of memory. If we add a string value, the hash size increase by 24 for the xpv struct and the string’s length. Since every key must have a value, there is already 24 bytes for the SV that the key points to figured into the size of the hash. So the original 195 byte hash with a value like “hello” should be 195 + 24 + 8 = 227, and this is exactly what is reported.

Subroutines/Coderefs

A scalar can point to a subroutine/coderef/CV. A minimal CV like $sub = sub { }; requires 6189 bytes. The xpvcv struct is large and complex, so we won’t devel into it here. What’s interesting is how the CV size grows when the size of the subroutine’s code. The next minimally valid sub is sub { 1 }; which causes a 40 byte increase in size to 6229. The increase is not directly related to the text length of the code in the sub because sub { 123 }; is still 6229 bytes large. Rather, the increase is due to the code itself, specifically the Perl opcodes which comprise the code a lower level (see perlguts). For example, sub { print "hello, world"; return; }; reports a size of 6429 and that’s a 240 byte increase for only 29 characters of code. What’s really being counted are various opcode structures.

How does the size of coderefs scale? A more “complete” subroutine like,


sub {
   my ( $arg ) = @_;
   return unless $arg;
   $arg =~ s/ /_/g;
   print "$arg\n";
   return $arg;
};

reports a size of 7117 bytes–a 928 byte increase for roughly 83 characters of code. Adding a for() loop around the print() increase the size by 128 bytes to 7245.

How much memory does a real subroutine require? Here is the first subroutine in mk-query-digest’s pipeline, the one responsible for parsing the input:


push @callbacks, sub {
   my ( $event, %args ) = @_;
   return $parser->parse_event(%args);
};

Care to venture a guess on that coderef’s size? … It’s 311579 bytes large. That single line, return $parser->parse_event(%args); represents a lot of opcodes.

The lesson is that coderef sizes are practically impossible to predict or calculate a priori.

On a side node: if total_size() is segfaulting Perl on your box, apply my patch.

Devel::Size::total_size() and complex data structures

As far as I know, Devel::Size::total_size() is the only way to ascertain the true size of Perl variables, so it’s important to know how accurate it is. All the above shows that it’s perfectly accurate for scalars, arrays and hashes, but let’s double check that it’s equally accurate with a “complex” data structure like:


my $d = [
   undef,
   "",
   42,
   "42",
   [ undef, 42, ],
   {
      foo => "bar",
   },
];

The reported size is 837 bytes. Let’s verify:

  • Array pre-initialized with 6 elements: 176 min size + (6 * 8) pointers + (6 * 24) value SVs = 368 bytes
  • Scalar values undef 42: 0 extra bytes
  • Empty string (element 1): 24 xpv struct bytes
  • Array pre-initialized with 2 elements: 176 min size – 24 value SV + (2 * 8) pointers + (2 * 24) SV values = 216 bytes
  • Hash structure: 194 min size – 24 value SV + 3 key len + (24 + 8) value = 205

Our total is 813 but Devel::Size::total_size() report 837, which is 24 bytes more. So one of us is off by a 24 bytes scalar value. The difference is negligible so I’ll call this good enough.

Conclusion

Yes, Perl uses a lot of memory, but at least we can see where and why–for the most part, at least. We’ve only covered Perl variables, but I suspect there’s more we could investigate. Perhaps, with enough hacking, we could illuminate some “dark memory”–memory that Perl is holding but not currently using.

With this knowledge, a fixed/patched Devel::Size, and some more hacking, I was able to profile mk-query-digest’s memory usage, find the memory hog, and reduce its memory usage by 90%. I hope you can now do the same, too, with your code!

Written by Daniel Nichter

April 21st, 2010 at 7:27 pm

Posted in

One comment on “Perl memory usage

  1. Pingback: An EPIC Perl in Eclipse? | The Hollow Dreamer

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>