How big are PHP arrays (and values) really?

http://nikic.github.com/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

by there • 15 years ago

150 86 15 years ago

nikic.github.com

maratd6• 15 years ago

As the author mentions, if you run into a use-case where you need to store 100000 integers in memory, then you should use one of the many alternative structures available. Some of them were explicitly designed to store integers in an efficient manner. Arrays weren't designed to store integers efficiently or anything else for that matter. They were designed to be fast and easy to use.

mbell• 15 years ago

I wouldn't call using 56 bytes to store 8 bytes of actual data efficient.

dangrossman2• 15 years ago

That'd be why he said "arrays weren't designed to store integers efficiently".

skeptical2• 15 years ago

Considering PHP's scope and its limitations (lacks things like threads for example) I would say that is an extremely rare scenario. If you're storing 100.000 integers on a PHP data structure you're most likely doing it wrong.

maratd6• 15 years ago

> Considering PHP's scope and its limitations (lacks things like threads for example)

Please look up PHP-FPM. I use it in production, with great success.

> If you're storing 100.000 integers on a PHP data structure you're most likely doing it wrong.

What if I had a ton of price points and I needed to do statistical analysis? Well, those would be floats, but you get my point.

PHP is capable of doing the work efficiently, you just need to put a little thought in it first or you'll very quickly trash your box.

rorrr3• 15 years ago

PHP arrays are not really arrays, they are sort of hash-maps.

You can do things like

    $arr = array(1 => 10, "1" => 11);

Or even

    $arr = array('他妈的我的生活' => 5);

But at the same time you can treat them as regular zero-based arrays.

    $arr = array();
    $arr[] = 1;
    $arr[] = 2;
    $arr[] = 3;
    $arr[] = 'dog';

fhars2• 15 years ago

And once you relalize that they are really hashes you also realize that a fast and memory efficient representation will use at least nine machine words or 72 bytes per value: 1 + x for the pointer in the bucket array (you don't want 100% occupancy to avoid hash collisions), 2 for the cons cell of the list stored in the bucket (the second element of which will usually be NULL if you have a good hash function and low occupancy), 2 for the key-value pair pointed to by the first element of the cons cell representing the index and the value, and two each for the integer key and value plus their tag words). And you may also want to store some metadata (like the length of the list stored in each bucket) with the hash, so the PHP array in the example is within a factor of two from the naive optimum for a dynamically typed language without specialized arrays.

Its just the price you have to pay for not caring about the type of your "array" keys.

obtu3• 15 years ago

That or specialize. Lua, Javascript, and PyPy all have more efficient storage of integer-keyed hashes. Lua's solution is particularly simple and could easily be transferred to PHP.

birken• 15 years ago

A PHP array is in fact just an ordered hash-map (IE.. hash map with an associated linked list which tracks the iteration order).

When you do an array append, the logic PHP runs is it tries to guess what the most logical key would be, add that to the hash-map and then to the end of the linked list.

  $a = array();
  $a[] = 'A';
  $a[] = 'B';
  print_r($a);

  Array
  (
      [0] => A
      [1] => B
  )

  $b = array();
  $b[5] = 'A';
  $b[100] = 'B';
  $b[] = 'C';
  print_r($b);

  Array
  (
      [5] => A
      [100] => B
      [101] => C
  )

rorrr3• 15 years ago

I think they are a little more complex than regular hash maps.

1) They keys can be integers or unicode strings (ordering works differently for these two cases)

2) The keys are not necessarily ordered (see ksort and krsort functions, for example).

Wilya• 15 years ago

It's funny. I don't have much experience with php, and I had to actually run your last example to know that it appended the values (instead of recreating the array with a single value each time).

Is there an append operator, or something more explicit ? '+=' seems to do something strange..

ars4• 15 years ago

[] IS the append operator. And += only works right if both sides are arrays. If not the right side will be converted. += is really intended for hashmaps, not integer indexes, for those use [].

MindTwister• 15 years ago

If you want something more explicit you probably want array_push($array,$val1,$val2,$val....);

pacmon4• 15 years ago

Not sure exactly what you were trying. Using the [] syntax is common for appending elements (using the next available key). Otherwise you can use the array functions (array_push/pop/etc). As for plain operators, here is how PHP handles array operators: http://www.php.net/manual/en/language.operators.array.php

gcb• 15 years ago

N.B. when he says at the same, it's really at the same time.

   $x = array();
   $x['asfd']=123;
   $x[] = 4;

   var_dump($x);

   array(2) {
     ["asfd"]=>
     int(123)
     [0]=>
     int(4)
   }

qixxiq• 15 years ago

I think its important to note your first example actually isn't valid. Part of PHP's type-mixing means strings that consist of an integer representation as array keys are automatically casted to int.

  $arr = array(1 => 10, "1" => 11);
  echo $arr[1]; // >> 11

dspillett2• 15 years ago

It is the same for Javascript: even though you have an Array object that you can instantiate instead of the more generic Object, they are much the same thing under the hood with both arrays and objects being hash maps [you can use the two interchangably to an extent (if you don't need the extra functinos defined by the array prototype) - references object properies in an hash-like manner or array contents the same way as object properties].

I suspect a number of languages have simiar memory (in)efficiency with their array types because the arrays are implemented this way (and the stuff stored in each slot is untyped so you'll not just store that integer, at very least the engine will need a marker that identifies it as an integer rather than something else).

The high memory use is one of the prices you pay for the type flexibility.

cygx5• 15 years ago

While this is true if you only consider language semantics, implementions do use actual arrays to store dense properties with integer names, ie arrays are backed by both flat and sparse storage with some heuristic algorithm to determine when to use what.

nestlequ1k• 15 years ago

Interesting. Wonder how this compares to python and ruby memory handling.

InfernalH• 15 years ago

I tried with a "pure" Array - for Ruby it's 1Mb for 100 000 elements

EDIT: and for Hash with h[i] = i, it's ~6Mb

masklinn7• 15 years ago

Does that account for the size taken by the integers themselves?

fhars2• 15 years ago

Since PHP arrays are within a factor of two for the theoretical optimum for a dynamically typed language that unifies arrays and hashes, all these languages (add javascript to the list) should have roughly comparable behaviour unless they do some ugly special casing for hashes where all keys are integers. [edit: see the comment by InfernalH for a measurement that indicates that ruby seems to do this.] You have to look that up in the relevant documentatio and/or source code. Perl on the other hand should fare better, as it distinguishes arrays and hahes. If you want performance, use a real programming language.

ars4• 15 years ago

Javascript also distinguishes arrays and hashmaps.

ootachi• 15 years ago

JavaScript engines have many types of arrays. They do indeed resort to "ugly special casing" for objects in which all keys are integers: for instance, SpiderMonkey calls them "dense arrays". V8 has a similar optimization. Likewise, Lua stores a hashtable part and an array part for all objects.

V8 and SpiderMonkey have optimizations for the values, too. When a value is a 31-bit integer (in the case of V8) or any number (in the case of SpiderMonkey), the value itself is optimized to avoid heap allocation. In V8's case optimized values take 32 bits, while in SpiderMonkey's case optimized values take 64 bits. So an array consisting of 100,000 integers will take 400K plus a negligible amount of malloc/GC slop in V8 and 800K in SpiderMonkey.

JavaScript also has typed arrays, which allow the programmer to use fine-grained, optimized array buffers. Performing this experiment with a typed array will yield a 400K buffer in all engines that support the feature.

samdk• 15 years ago

Python and Ruby both have separate arrays and hashes. They're completely different data structures in both cases.

Python's dict type is a hash table like you'd expect. Python's list is a pointer-array-backed list. (it may inline ints/similar things--I don't remember if CPython does, and exact details are implementation-dependent), and raw arrays are in the standard library if you need them.

From a very quick check, a list of 100k ints in CPython is ~1.5mb, and a dict of 100k ints -> other ints is ~6mb.

Ruby's hash and array implementations are similar, I think, although I don't know Ruby as well, so I don't know the specifics.

fauigerzigerk2• 15 years ago

As I see it, doing the ugly special casing for you is exactly what any competent dynamic language implementation should do.

dchest• 15 years ago

Lua is actually closer to PHP in how arrays are used in it.

"Until Lua 4.0, tables were implemented strictly as hash tables: all pairs were explicitly stored. Lua 5.0 brought a new algorithm to optimize the use of tables as arrays: it optimizes pairs with integer keys by not storing the keys and storing the values in an actual array. More precisely, in Lua 5.0, tables are implemented as hybrid data structures: they contain a hash part and an array part. Figure 2 shows a possible configuration for a table with the pairs "x" → 9.3, 1 → 100, 2 → 200, 3 → 300. Note the array part on the right: it does not store the integer keys. This division is made only at a low implementation level; access to table fields is transparent, even to the virtual machine. Tables automatically and dy- namically adapt their two parts according to their contents: the array part tries to store the values corresponding to integer keys from 1 to some limit n. Values corresponding to non-integer keys or to integer keys outside the array range are stored in the hash part.

When a table needs to grow, Lua recomputes the sizes for its hash part and its array part. Either part may be empty. The computed size of the array part is the largest n such that at least half the slots between 1 and n are in use (to avoid wasting space with sparse arrays) and there is at least one used slot between n/2 + 1 and n (to avoid a size n when n/2 would do). After computing the new sizes, Lua creates the new parts and re-inserts the elements from the old parts into the new ones. As an example, suppose that a is an empty table; both its array part and hash part have size zero. If we execute a[1]=v, the table needs to grow to accommodate the new key. Lua will choose n = 1 for the size of the new array part (with a single entry 1 → v). The hash part will remain empty."

From "Implementation of Lua 5.0" -- http://lua.org/doc/jucs05.pdf

obtu3• 15 years ago

Python has lists and dicts, and lists don't get the per-item overhead of GC-ed keys. PyPy does better than CPython and implements specialised, low-overhead storage for some dicts, lists and sets of uniform type (in 1.6, nightly builds, and a branch respectively).

http://morepypy.blogspot.com/2011/10/more-compact-lists-with...

baby• 15 years ago

I'm kinda hijacking this thread because I always wonder how to handle vars in PHP. Should we use short named vars like $a, $b? Should we avoid always using the same var and changing its type? $a = 30; $a = "thing";

ars4• 15 years ago

Someone downmodded you for being offtopic, but I'll answer you anyway.

The name of the var doesn't matter at all. And you can change the type of a var at will. There is nothing at all in PHP that will be better if you avoid changing the type, so just do what is clearest for your program.

conradfr• 15 years ago

I don't think someone picking up your code will be pleased with all variables named $a :)

Use "long" names and use unset() if worried about memory consumption. And more on topic, you can use unset on a array item !

pacmon4• 15 years ago

Did anyone else even try running his suggested code? I think maybe he has a problem with his setup. I don't get those numbers.

  My numbers for PHP 5.3.8:
  Windows 7 -
  8524568 bytes (using range)
  3600584 bytes (using SplFixedArray)
  
  Fedora 14 -
  7724600 bytes (using range)
  3200568 bytes (using SplFixedArray)

*edit - Added numbers for SplFixedArray

Robin_Message• 15 years ago

Are you on 32-bit, because all his numbers are for 64-bit, except the large table near the beginning, which matches roughly with the numbers you give.

pacmon4• 15 years ago

Yes and No. I run a 64-bit Windows 7 machine, but oddly enough the Fedora 14 machine is 32 bit. Yet it yields similar numbers to the 64-bit Windows.

nikic2• 15 years ago

Yep, I already got some comments on that. You are either using a 32 bit system or a 32 bit binary (at least I think that the binaries PHP distributes for Windows are compiled for 32 bit, so even if you are on a 64 bit Windows you'll still get 32 bit numbers).

The Windows number still is 8 bytes per element larger than the number I wrote (76 per element). This might have various reasons, one could be that it was compiled with head protection :)

pacmon4• 15 years ago

Ah. Yes. I think you're right. I think PHP is still complied for 32-bit on Windows. That makes more sense.

wvenable• 15 years ago

Has anyone run similar tests on the soon-to-be-released PHP 5.4? From what I understand, one of the changes in that release is reduced memory consumption. Andi Gutmans has said that PHP 5.4 could lower PHP's memory footprint by as much as 35%.

nikic2• 15 years ago

I actually did most of my tests with PHP 5.4 and trunk binaries, but also tested PHP 5.3 and the numbers didn't change. PHP 5.2 used 8 bytes less, because the circular GC was introduced only in PHP 5.3.

By the way, you can test that yourself too. The codepad I posted the same on has a switch for PHP 5.2, 5.3 and 5.4, so you can easily see for yourself :)

lang• 15 years ago

php is not unique in having big memory footprint. AFAIC Python and Ruby are also memory hogs. An interesting question is how memory efficient a dynamic PL can be. Given that in modern computers memory access (cache misses) is fairly expensive it probably makes sense to trade instructions for memory.

masklinn7• 15 years ago

> AFAIC Python and Ruby are also memory hogs.

Even more so in some areas, for instance a Python `int` is not a machine integer but a full-blown object.

lvh• 15 years ago

It's only always a full-blown object in CPython. Smarter implementations, notably PyPy, will do escape analysis, and never actually end up allocating those objects.

(My point is that not having unboxed types does not imply being a memory hog. You just need a smarter implementation.)

legooolas4• 15 years ago

> A union is a means to make some value accessible as various types. For example if you do a zvalue_value->lval you’ll get the value interpreted as an integer. If you use zvalue_value->ht on the other hand the value will be interpreted as a pointer to a hashtable (aka array).

This is not valid C usage of unions. They are _only_ for use as a method to save space, not for conversion between types, despite it being a very common usage of unions.

This can cause all manner of problems when compiler optimizations such as type-based alias analysis are used.

EDIT: Turns out I'm completely wrong on this and it's fine from C99 onwards.

jronkone• 15 years ago

I don't see how unions could save space, care to explain?

legooolas4• 15 years ago

If you have multiple items of which you're only going to store one at a time but want them in the same "structure" then you use a union. (i.e. temporally disjoint)

chadaustin• 15 years ago

Actually, the upcoming C1X standard makes type punning via union legal. In C99, alias analysis works behaves exactly as you said, but using unions to convert between floats and ints is so common that it's legal in C1X, VC++, and I believe gcc.

legooolas4• 15 years ago

gcc does in some cases but not all (see http://gcc.gnu.org/onlinedocs/gcc-4.1.1/gcc/Optimize-Options... but not all).

Still, the current standard says it's not legal so it seems like a bad idea to rely on undefined behaviour...

cygx5• 15 years ago

Type-punning through unions is already legal in C99, but there's a known error in Annex J, listing it incorrectly as unspecified behaviour.

See http://stackoverflow.com/a/8513748/48015

ars4• 15 years ago

PHP isn't using it for type punning, they are using it to save space. The article author was a bit unclear here.

When PHP needs to convert a type it does it properly, not through the union.

cygx5• 15 years ago

This is not valid C usage of unions. They are _only_ for use as a method to save space, not for conversion between types

That's incorrect. The following footnote was added to section 6.5.2.3 with TC3 in 2007 to clear up this particular misconception:

"If the member used to access the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called "type punning"). This might be a trap representation."

noselasd• 15 years ago

What does memory_get_usage() actually do ? Does it report the "heap" size assigned to the process, or does it use PHP internal counters for the allocated user data/variables ? A C malloc subsystem will assign a whole lot of virtual memory, in steps of pages, or more if it decides to attach a piece using mmap().

In order to make this test case relevant, I'd say one have to know what memory_get_usage() does - it's at least meaningless to determine the overhead of an array based on it, if for whatever reason creating the 1. PHP array in a program also initializes "big" memory pools that count towards the memory usage.

ezyang• 15 years ago

This is easy to check in the source. memory_get_usage() calls zend_memory_usage(), which accesses the size field on a global structure mm_heap, which is updated by PHP's memory allocation system (e.g. if you call *_zend_mm_alloc_int)

hardtke• 15 years ago

I was debugging a php memory issue yesterday, and noticed that at some point my get_memeory_usage() value became much, much smaller than the memory footprint recorded by top (20 MB in get_memory_usage(), 500 MB in top RES). It was a sudden jump during a loop execution according to top. Does top give accurate memory estimates for php scripts?

iampims• 15 years ago

A coworker just pointed me to: http://us.php.net/SplFixedArray

How big are PHP arrays (and values) really?

Related Stories