PHP 7's new hashtable implementation
nikic.github.io
nikic.github.io
Its main distinguishing property, as mentioned in this article, is that values can be indexed by key, but are still iterated in the order they were set. This is "do what I want" in so many cases that it's just nuts.
Sure, just as often it's just needless overhead, but as a programmer who prefers to reason about domain and not performance, I often don't care about that. I hate that many other languages, including C#, Ruby and Python, force me to choose between either an unordered map or a list of (key, value) tuples. EDIT: clearly, i'm behind the times with that remark. thanks commenters :-)
I wish more languages had a native data type like this. It scares me that in practice JS objects have the same property, but officially the iteration order is not specified.
(that said, PHP's choice to mix regular arrays and associative arrays into a single type strikes me as a bit odd. i've also never seen a good use case of arrays with mixed string/int keys)
Another commenter mentioned Python's OrderedDict, and Ruby's hashtables are ordered (from 1.9+): https://www.igvita.com/2009/02/04/ruby-19-internals-ordered-... It looks like C# also has an OrderedDictionary class: http://msdn.microsoft.com/en-us/library/system.collections.s...
I never had to use any of these classes even if I do use hashmaps all the time, so IMHO the Python way is best (default to a 'normal' unordered hashmap, offer an ordered alternative)
I find myself needing this surprisingly often:
An array of elements in a certain order which I also want to lookup by Id.
Sometimes the order is defined by configuration, sometimes by some other criteria that is not accessible for this particular component, so I can't resort to a SortedHashMap.
Still, I need a 1) fast and 2) convenient way of lookup by some key. Convenience is often more important to me than performance in those cases, since the data size is not huge, but I hate it when I have to write array.find(e => e.Key == myKey) instead of orderedLookup[myKey].
Don't get me wrong, it's actually a bug I've run into in the past, and you're right, the non-deterministic issue makes it harder to debug. But when I discovered it I blamed myself for not being explicit with my constraints.
Java's LinkedHashMap provides this as well ( http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHas... )
This might just be me, but I don't think an ordered hash is a particularly easy data structure to reason about. Almost all the code that I've seen depend on it in either language has been too clever by half.
There are probably other analagous circumstances. Maybe even some I could think of that I've encountered.
I've never wanted this though. I just discovered OrderedDict when I was looking for something like std::map.
When it's not the default normal thing, you don't build solutions around it, so you never see what you're missing :)
In PHP I make lots of tiny uses of it in many places. I really missed it when I switched to Python (sure, there's OrderedDict, but it's a second-class citizen: there's no syntax for literals and standard APIs don't explicitly take advantage of it).
* It's very useful for deduplicating things without losing order (especially when you have a bigger algorithm that collects data from multiple sources or a tree structure into one array).
* It's neat for sorting objects without having to mutate them to add a key or wrap them in a key/value object.
* It's great for configuration with JSON-like structures, but key order gives extra flexibility in the design, e.g. instead of [{id:"foo"},{id:"bar"}] you can use ["foo"=>[],"bar"=>[]].
It's not a major feature, but it makes things nicer. I've never had arrays accidentally randomized in PHP, but had bugs due to careless list->dict->list conversions in Python.
> In PHP I make lots of tiny uses of it in many places. I really missed it when I switched to Python (sure, there's OrderedDict, but it's a second-class citizen: there's no syntax for literals and standard APIs don't explicitly take advantage of it).
Missing syntax sugar makes it a second-class citizien? How? Also what advantages could standard API (<- what does that even mean?) take?
> It's neat for sorting objects without having to mutate them to add a key or wrap them in a key/value object.
It's called set()
> It's great for configuration with JSON-like structures, but key order gives extra flexibility in the design, e.g. instead of [{id:"foo"},{id:"bar"}] you can use ["foo"=>[],"bar"=>[]].
...and the reason you cant use OrderedDict here is you dont like it.
About ordering stuff: after years I can still remember the problems I had with ordering in PHP. There's more than a dozen of sorting methods, which is mess. No one can remember if they all behave the same way and what's the order of its parameters. In Python you've sorted() and that's it. You cant do any advanced stuff with these array, because sometime they act as lists and sometime they act as hashmaps. I'll take this example from "Fractal...": $first = array("foo" => 123, "bar" => 456); $second = array("foo" => 456, "bar" => 123); array_diff($first, $second);
var o = {
key: 3,
1: 4,
value: 10,
0: 2
};
Object.keys(o)
["0", "1", "key", "value"]
Do you have a reference for this? I clearly recall a Lars Bak interview in which he says that adding a property .x and then .y results in an object of different hidden class than adding .y and then .x exactly because people want to rely on iteration order.
(Might not apply to numeric keys, though.)
Integer keys are not practical to treat as fixed because they are used as array indices 99% of the time which are dynamic. So they should be optimized differently, and they are. They are backed by a dynamically resized array (so it's implemented like Java's ArrayList). And it's not possible to track insertion order in this representation, so integer keys have different iteration order from named keys.
Note that doing hash-tabley things with the objects (like changing their property order constantly, deleting named keys and so on) will change the backing representation to ordered hash table. The ordered hash table emulates the same order that results from the nature of the above optimizations to make it less surprising for user when the representation changes. If it wasn't ordered, it would be very surprising when the iteration order suddenly changed from ascending integer keys and insertion ordered named keys to something completely random.
The only difficulty I can see with doing that is that is insertion order.
My point is that if the most optimal way would result in some other iteration order, that would be the iteration order experienced by users and that it is just a coincidence that the most optimal way results in insertion order.
Sketch out an example of hidden class transitions and it should be clear:
In the order preserved case (what JS engines actually do):
start with {} of hidden class <empty>
add .x, transition to hidden class <A> with field .x at 0
add .y, transition to hidden class <B> with field .x at 0 and field .y at 1
start with {} of hidden class <empty>
add .y, transition to hidden class <C> with field .y at 0
add .x, transition to hidden class <D> with field .y at 0 and field .x at 1
start with {} of hidden class <empty>
add .x, transition to hidden class <A> with field .x at 0
add .y, transition to hidden class <B> with field .x at 0 and field .y at 1
start with {} of hidden class <empty>
add .y, transition to hidden class <C> with field .y at 0
add .x, transition to hidden class <B> with field .x at 0 and field .y at 1
So yes, while all major browsers use hidden classes today, that itself is not sufficient to explain why insertion-order enumeration is not maintained.
Link: <http://cdn.example.com/stylesheet.css>; rel=stylesheet; type=text/css
[
[0] => <http://cdn.example.com/stylesheet.css>
[rel] => stylesheet
[type] => text/css
]
php > $link = 'http://example.com/';
php > preg_match('#http://(?P<domain>[^/]+)/#', $link, $matches);
php > print_r($matches);
Array
(
[0] => http://example.com/
[domain] => example.com
[1] => example.com
)
Tie::IxHash [1] is available on Cpan.
I have a routine that plucks key/value pairs out of one associative array and builds another, and allows you to rename the resulting key names at the same time. Using mixed keys allows you to be more terse if you don't want to change the name:
$json = $data->valuesForKeyPaths(array( 'foo' => 'path.to.foo', 'bar', 'baz' => 'path.to.baz', ));
json = data.valuesForKeyPaths([('foo', 'path.to.foo'), 'bar', ('baz', 'path.to.baz')])
What are the use cases that you would need an ordered dictionary?
It would be nice to have separate types for arrays and maps though. I don't understand why they were combined to begin with. Simplicity? Seems like there are more edge cases and gotchas the way things are now.
Stack - http://php.net/manual/en/book.spl.php Queue - http://php.net/manual/en/class.splqueue.php PriorityQueue - http://php.net/manual/en/class.splpriorityqueue.php Real Maps - http://php.net/manual/en/class.splobjectstorage.php
It's a shame some people are not aware of these.
The SPL types are definitely a welcome addition to the language, but they feel like add-ons. Definitely not first-class. The standard array functions don't work with SPL types (array_map, etc.) even though the SPL types are iterable.
More to my point, missing from SPL is a dynamically-sized array that's not based on linked lists. Linked lists don't have O(1) lookup. This type of array really should be first-class, but it’s completely missing from the language. Please correct me if I’m overlooking something!
That said, I believe having separate, first-class, dynamic arrays and maps would strike a better balance of dynamism, performance, and predictability compared to the single existing first-class array/map.
In any event, Lua 5.2 will respect the __len, __pairs and __ipairs metamethods, so you can tweak this behavior if you need to store nils in your tables and iterate over them.
Um, Javascript?
--
Clarification edit: Creating a new key on an array using arr['key']=1 creates a property on the arr Object but does not add an element to the standard array.
http://stackoverflow.com/questions/8630471/strings-as-keys-o...
var x = [];
console.log(Object.prototype.toString.call(x));
//[object Array]
x[0] = 1;
console.log(x[0]);
//1
x["test"] = 2;
console.log(x["test"]);
//2
console.log(Object.prototype.toString.call(x));
//[object Array]
x.map
//function map() { [native code] }
var y = {};
console.log(Object.prototype.toString.call(y));
//[object Object]
y.map
//undefined x = [1]; x["test"] = 555; x.map(function (y) { return y; });
// [1]
var x = {};
x[0] = 1;
x.length = 1;
x.map = Array.prototype.map;
x.map(function(y) {return y;});
//[1]That is the whole reason prototype.js library broke the use of for (var x in somearray) because the library set properties on Array.prototype.
Array are objects,but all objects aren't Arrays.
var a={};
a instanceof Array // false
"Tuple" tends to refer to fixed-size collections where each element may have a different type. The tuple type is the (cartesian) product of those types. For example, the type "a tuple containing 3 Booleans" can be written as `Boolean * Boolean * Boolean`.
Since Boolean is type 2 (ie. it contains 2 elements, `True` and `False`), this makes our 3-Boolean tuple `2 * 2 * 2 = 8`. True enough, it has 8 elements: `(True, True, True)`, `(True, True, False)`, `(True, False, True)`, `(True, False, False)`, `(False, True, True)`, `(False, True, False)`, `(False, False, True)` and `(False, False, False)`.
Likewise, a tuple like `(1, "hello", True)` has type `Int * String * Boolean`.
That's why tuples are "composite types", they're the product of other types.
Arbitrary-length collections are more complicated, since they require recursion. The simplest is a singly-linked list with all elements of the same type `T`, which is given by the equation `list(T) = 1 + (T * list(T))`. `1` is the unit type `void`, which has one element (`NULL`), which represents the "nil" at the end of the list. The `T * list(T)` is a tuple containing a `T` and a `list(T)`, ie. it's a "cons cell". The `+` is a (tagged) union.
We can solve recursive equations like this using the greatest-fixed-point combinator `mu a`,to get `mu a. list = 1 + T * a` (see http://debasishg.blogspot.co.uk/2012/01/learning-type-level-... ).
For heterogeneous collections, where the element types can differ, things get more complicated, since we need to establish the (potentially infinite) structure of the type, and where each component type fits in.
Dynamic languages use one big recursive type, so all of these types just-so-happen to be the same, and we get tuples-of-tuples(-of-tuples, etc.) via the "top-level" recursive nature of that single type.
In contrast, a "primitive type" is one that's not made up out of other, simpler types. We can usually treat the empty type 0 and the unit type 1 as "primitive", since we can't define them out of simpler types. We don't have to use those as our primitives though, since we could choose some 'larger' type, like 5 (the type with 5 elements) as primitive, then use quotients and subtraction to define the others (eg. `5 / 5 = 1` and `5 - 5 = 0`) but it's much more elegant to take 0 and 1 as primitive.
Particular languages may choose to make other types primitive, eg. Int32 or Float64, eg. if they want to treat them specially with hardware optimisation and such.
Combining arrays and maps in one type was the cause for a remotely exploitable vulnerability in Drupal this year, https://www.drupal.org/SA-CORE-2014-005.
I commented on that at https://lwn.net/Articles/618530/. Quoting from that comment:
"[...] most uses will treat it either as an array (list of items) or as a key/value store (map from key to value, or sometimes set of values), but rarely as both at the same time. [...] In this vulnerability, the programmer expected a sequence, and was handed a mapping. [...] all uses of a single variable should be consistent (never use a sequence method on a mapping variable or a mapping method on a sequence variable). As shown in this vulnerability, "foreach ($data as $i => $value)" is a mapping method; it should never be used on a sequence, even if it works."
There is no "hash table" type in PHP user land.
There are only hash tables that are called "array" for simplicity.
This "bucket" also handles the collisions by using separate chaining. There is actually two "next" pointers, one for the chains, and one for the next element in order of insertion. Very confusing and requires reading through the code and playing with it.
That's why the lend themselves to the same syntax so well.
This is interesting. In fact, I believe object properties share the same mechanism as associative arrays, that is, $a->b will actually lookup the hash of "b" in $a. Does this new hashtable layout influence object properties/methods too? That would be huge!
Not sure, but I don't think so. Ppl often think object properties and arrays are much alike, but the array's HashTable struct and the object's store struct are very different. The main performance gains are not about the buckets (which are simple and quite alike) but the array's hashtable idea.
Often objects (php>=5.4) have a better performance than arrays; arrays have an undefined length while with good code, all object properties are defined at compile time. Because of this, you don't need to store the data in a hashtable. Nikic has a post about this subject too: https://gist.github.com/nikic/5015323
But then again, PHP itself being stateless between requests is quite fast already, nice to see even more performance getting squeezed out. Imagine the decrease in global energy consumption due to this change. :D
"Code in haste, repent at leisure." PHP was designed with some unholy amalgam of an array and a hash table as its only data structure, so there's plenty of room for repentance.
It makes me feel old to remember learning about (singly-) linked lists, arrays, and hash tables, plus some other nice things, in a freshman course called "Introduction to Algorithms and Data Structures." Each had its advantages and disadvantages, and I quickly learned which to choose in which situation. Does this course still exist, or is the modern equivalent "Algorithms and HashArrayLists?"
When i was in college and visited said lecture, I was quite surprised, what an array actually is. But on the other hand, if it had not been for PHP and its small step from HTML, I imagine many young programmers like me would know neither the false nor the right array.
> PHP uses hashtables for all arrays. However in the rather common case of continuous, integer-indexed arrays (i.e. real arrays) the whole hashing thing doesn’t make much sense. This is why PHP 7 introduces the concept of “packed hashtables”.
> [...] We keep these useless values around so that buckets always have the same structure, independently of whether or not packing is used. This means that iteration can always use the same code. However we might switch to a “fully packed” structure in the future, where a pure zval array is used if possible.
It's nice that they're starting to consider the fact that "real" arrays are unnecessarily mixed with hashtables, which comes with a pretty significant overhead. Let's hope they'll soon add that different separate type for arrays (or "fully packed hashtables" if they prefer :)).
Could be good as long as it can be inferred whether compiler should use it or not, without additional clutter in the code.
To the extent that it is often viable to run another programming language's implementation of your code operating as a service for your PHP code.
Out of interest, can you give a few more details of what you were storing, and how?
I've seen serialise() used surprisingly often (WordPress comes to mind!), which is always going to be pretty verbose:
How many items were you storing / how big was the data in each item?
I wonder if the ->pDataPtr vs ->pData confusion has been resolved.
I'm probably a few years behind, but a lot of my confusion working with hashes has been that pair of void* pointers.
The ->pDataPtr was the one thing behind 90% of the bugs I caused with exts (obviously stuff like the frozen_array hashtable handling was a completely odd-ball case).
I read deeper and found that you also fixed the "void * *" in zend_hash_find(), which is another pain point in the old API - you cannot rely on the compiler type-checking at all.
I no longer work with PHP, but avenge me for the hair I've lost over the IS_REF madness (copy_ctor vs separate_zval) :)
Anyway I'm just going to leave this here because it's great fun: http://en.wikiquote.org/wiki/Rasmus_Lerdorf
Some favorites:
"There are people who actually like programming. I don't understand why they like programming."
"I'm not a real programmer. I throw together things until it works then I move on. The real programmers will say "Yeah it works but you're leaking memory everywhere. Perhaps we should fix that." I’ll just restart Apache every 10 requests."
Ladies and gentlemen, the author of pretty much the most popular web programming language out there!
Context: "This was circa late 1994 when PHP was a tool just for my own personal use and I wasn't too worried about not being able to remember the few function names."
That might not be the right attitude for all programming languages, but it is working for PHP in at least some sense.
tl;dr: They made some bad decisions about Unicode and everyone got burned out.
They skipped 6 because 7 contains none of the Unicode changes and didn't want to confuse people.
https://www.google.com/#q=php6+book
Basically a lot of authors thought they'd get 'ahead of the game' and publish PHP6 books very early. If a 'real' PHP6 was released now, there would be confusion.
e: Actually wasn't there a blog post posted to HN suggesting Perl skip to 7 too?
[1] http://perl6.org
So this non-production code is using about twice as much RAM as HHVM production.
Past that, even if you start defining non-integer names you still store the integer-named properties in a contiguous chunk of memory and store the named properties separately. This is why in V8 and SpiderMonkey the property order for an object (as seen by a for-in loop, say) doesn't match property addition order. Instead, the integer-named properties are enumerated first (in SpiderMonkey up to a certain limit) and then the other properties in addition order. So yes, the requirements are similar and JS engines throw some of them (property order preservation) under the bus to improve performance.
In SpiderMonkey, even once you have lots of properties (and are sparse and whatnot) and have converted to a hashtable, things are not that simple. The values are still stored in a contiguous memory buffer. There is a linked list of property descriptors which contain things like the property name and an index into the buffer, as well as metadata like whether the property is readonly and whatnot. This list is shared across objects that have the same property names added to them in the same order (though possibly with different values). What's stored in the hashtable, which can also be shared across objects is a mapping from property name to nodes in this linked list.
In practice, objects that have a dedicated hashtable just for that one object instead of sharing property descriptors with multiple other objects end up being pretty rare.
Lastly, JS engines are at least experimenting with unboxed storage for arrays. That is, instead of having a memory region filled with JS values, which might be of any type, detect at runtime that your array happens to only contain integers and have a memory region filled with integers; storing a non-integer will then cause a realloc and boxing of the data.
FWIW, Carakan had typed "classes" for non-integer properties (often unboxing the majority of properties) from ~11.60, given it made relatively large memory savings when compared with the amount of RAM many TVs have (I've not paid enough attention around object representation to know if others are doing similar now?), and certainly unboxing arrays was talked about as part of the work to do that (though I'm not sure if we ever got around to implementing it; but one can probably see through performance side-channels).
There are no userland changes here.
I thought there was a big hooha about PHP and other dynamic languages using ill-suited hash functions and ultimately most runtimes moved to SipHash?
I don't think that's quite true for their data structure. Consider a full hash table which is repeatedly used like a queue (first element removed; another added). (I'd bet some PHP code out there is doing this.)
"The arHash array has the same size (nTableSize) as arData and both are actually allocated as one chunk of memory." As arData (and thus the arHash) becomes full, the arHash IS_UNDEF optimization becomes useless. Every insertion is O(n) because every element has to be moved up one. On the other hand, if there were 2n slots, all 2n would have to be touched only once every 2n insertions, which means insertion requires amortized constant time.
On the other hand, that'd perhaps cause there to be n-1 IS_UNDEF values at the beginning, so iteration could be problematic. They could do various things to avoid long runs of IS_UNDEF, but given that they could occur anywhere in the hash (not just at the beginning), I think the best might be to use an unrolled linked list as well. Then they could bound the number of consecutive IS_UNDEF values while still getting much of the benefit of fewer pointers and better locality. They could still put all the nodes in one allocation if they were so inclined; there would just be some extra pointers and not strictly linear iteration.
using php_array_t = multi_index_container<
int64_t,
indexed_by<
random_access<>,
hashed_unique<identity<int64_t>>
>
>;
dev@aerilon ~/dev $ php --version
PHP 5.5.20-pl0-gentoo (cli) (built: Dec 22 2014 13:44:21)
dev@aerilon ~/dev $ hhvm --version
HipHop VM 3.5.0-dev (rel)
dev@aerilon ~/dev $ php memusage.php
13.97 MBs [14649088 bytes]
dev@aerilon ~/dev $ hhvm memusage.php
2 MBs [2097152 bytes]
Great job, PHP internals team...
dev@aerilon ~/dev $ hhvm memusage.php
2 MBs [2097152 bytes]
Please try and be less apologistic and use some reading comprehension. It makes you look more intelligent and puts less stress on other people to accommodate your intellectual laziness.
And the result shows PHP 7 reduced memory usage by hashtables threefold since 5.5. Yes, this is pretty good. No reason to be bitter or sarcastic.
The code you pasted shows PHP 5.5.20-pl0-gentoo
How much more is 4MB compared to 2MB?
The answer, you'll find, is very close to 100%.