How big are PHP arrays (and values) really?
nikic.github.com
nikic.github.com
> then you should use one of the many alternative structures available. Some of them were explicitly designed to store integers in an efficient manner.
From the article:
> But if you do want to save memory you could consider using an SplFixedArray for large, static arrays. ... It basically does the same thing, but if you run it, you’ll notice that it uses “only” 5600640 bytes. That’s 56 bytes per element ...
EDIT: formatting.
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.
It is.
> I don't see any references to threading
Wow. I always thought it was threaded. My mistake. It seems it launches multiple child processes. There is some form of memory sharing going on, though. Looks like it's some sort of a hybrid. Now I'm just thoroughly confused ...
If doing it on your webapp, don't! You're doing it wrong. Otherwise why would you need php specifically? I mean I guess you could, but what advantage does it poses comparing to other languages available in pretty much every *nix system nowadays (perl, python)?
For the record, I have a nice collection of downvotes for defending PHP on point-and-laugh-at-PHP threads here at HN. I just don't see how the use case you're presnting is realistic.
That's the only place it's useful. Once the request comes in, I would split it off to a separate PHP CLI process. When the analysis is complete, I can transfer it to the user via web sockets.
So they would request a report. I would tell them great, it'll take a bit, keep working on something else and we'll let you know when it's ready. When it's ready, a notice shows up telling them to check it out.
> I mean I guess you could, but what advantage does it poses comparing to other languages available in pretty much every *nix system nowadays (perl, python)?
For something like this, the advantage would only be that you're sticking to the same language as the rest of your code base. It would make things simpler. So if you're using PHP, stick with that. If Perl, Python, etc. stick with that. It doesn't really matter. They can all do the work.
As to why you would want to do that in real life -- if you have written a large system with accompanying libraries, objects, or other infrastructure, then even if you pass of some sort of calculation to background or crontab tasks, you still might want to use your PHP code. I do this for some of the Drupal sites I work on - I setup drush commands that will do intensive calculations like most-related-article and etc to run behind the scenes have the results cached.
The best solution would be to improve PHP's memory usage so that the benefits may be had on page loads as well. I suspect (but have little hard evidence) that the size of PHP code and data structures impedes performance as threads and processes get pulled in and out of the CPU.
A secondary solution would be to take some of the libraries out there for doing specific operations, like scientific commputing and numerical libraries, and make them available to your code as a PHP extension. Obviously that doesn't solve as many problems as fixing PHP does.
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)
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 :)
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.
Still, the current standard says it's not legal so it seems like a bad idea to rely on undefined behaviour...
Things about which I have stumbled somewhat recently:
* restrict-qualified pointer-to-const parameters do not guarantee that the pointed-to object won't be modified as restrict only applies if the pointer is actually used to access the object, which calling code can't know (ie restrict only enables optimizations in the called code and not reordering in calling code)
* functions with differently qualified, but otherwise compatible parameter types have compatible type (which is only mentioned in the last, parenthesized sentence of section 6.7.5.3)
When PHP needs to convert a type it does it properly, not through the union.
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."
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 :)
EDIT: and for Hash with h[i] = i, it's ~6Mb
Inlining integers in pointers by shifting up and adding 1 is a quite common trick though and I have seen it in more programming language implementations than MRI. I think at least some Prolog implementation and older versions of Spidermonkey (newer versions use a similar trick with doubles).
Yeah, I know about it, I just did not think MRI had bothered with it anymore than CPython.
This trick was already used in Smalltalk-80, btw. A more recent variant of this is NaN tagging, made popular by LuaJIT.
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.
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.
EDIT: Sorry, I misread you. Ruby MRI and CPython are indeed similar.
At least in Ruby MRI (the mainline) arrays are implemented as a struct with a size and a pointer to a normal C array which contains the object references (references in MRI are pointers to object structs which use the lower bits to inline integers of <= 31 or 63 bits, true, false, nil and symbols).
Hashes in MRI I have not looked that much into but I believe they are a hash tables which in ruby 1.9 retain insertion order using pointers like a singly linked list.
From its context, I'm guessing samdk is saying:
> Ruby's hash and array implementations are similar [to Python's dict and list]
not that they're similar to one another, which would make absolutely no sense considering his comment starts with:
> Python and Ruby both have separate arrays and hashes.
so I'd say you agree with him and misread his comment.
It's nice that Python and Ruby have data structures that trade some features for some memory and/or performance gain.
Yeppers, since 2.7/3.1: http://docs.python.org/library/collections.html#collections.... http://docs.python.org/py3k/library/collections.html#collect...
And if you optimize at all, memory usage must be a top priority. Lack of memory is a lot more costly in terms of performance than a couple of C based heuristic checks. Creating and then garbage collecting an array full of individual integer objects doesn't just use a lot more memory, it's also orders of magnitude slower. The array doesn't have to be very large for that to matter as there may be large numbers of arrays.
"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
http://morepypy.blogspot.com/2011/10/more-compact-lists-with...
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.
Even more so in some areas, for instance a Python `int` is not a machine integer but a full-blown object.
(My point is that not having unboxed types does not imply being a memory hog. You just need a smarter implementation.)
Objects in a collection (which is what we're talking about here) escape kind-of by default.
Until type-specialized collections are merged in PyPy (if they are not yet), it'll have the same issue as CPython.
You can do things like
$arr = array(1 => 10, "1" => 11);
$arr = array('他妈的我的生活' => 5);
$arr = array();
$arr[] = 1;
$arr[] = 2;
$arr[] = 3;
$arr[] = 'dog';Its just the price you have to pay for not caring about the type of your "array" keys.
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
)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).
$arr = array();
$arr[0] = 'cat';
$arr[2] = 'dog';
$arr[1] = 'fish';
krsort($arr);
var_dump($arr);
array(3)
{
[2]=> string(3) "dog"
[1]=> string(4) "fish"
[0]=> string(3) "cat"
}Is there an append operator, or something more explicit ? '+=' seems to do something strange..
`array_merge` will append all numeric keys from the right array to the left, under new key values, as if you used [] one-by-one; for string keys, all keys from the right are copied into the left, possibly overwriting what was there.
In real code, I either have all-numeric or all-string keys, and `array_merge` does what I want in bulk operations: it's essentially equal to Python list.extend and dict.update, respectively. `+` on arrays is basically useless for me.
$x = array();
$x['asfd']=123;
$x[] = 4;
var_dump($x);
array(2) {
["asfd"]=>
int(123)
[0]=>
int(4)
} $arr = array(1 => 10, "1" => 11);
echo $arr[1]; // >> 11I 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.
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.
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.
Use "long" names and use unset() if worried about memory consumption. And more on topic, you can use unset on a array item !