It was a no-go. There was a lot of difficulties in getting it out the door, so I'm guessing they're pushing on with PHP7 to get rid of any social/political baggage that comes with the 6 release.
the non-unicode bits slated for 6.0 got rolled into 5.4, which was a pretty messy release given the extreme conservatism they adhere to even for major version changes.
The suggestion was that a future release of Perl5 should be named Perl7. Perl6 is a "spunky little sister"[1] to Perl5, not the next evolution of Perl.
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.
This is great news. PHP doesn't have many structured data types, so arrays (aka maps) are basically used for everything. Any improvement to them will impact the entire application.
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.
> It would be nice to have separate types for arrays and hash tables 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.
You put things in order by memory address and they stay in order when you access them. An array is just a special case of a hash map -- one with a trivial hash function.
That's why the lend themselves to the same syntax so well.
By using a doubly linked list, where the first element in the "bucket", contains the next pointer to the next element in the hash table. Read zend_hash.h & zend_hash.c It is fairly complicated and explaining it in depth is beyond the scope of this comment.
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.
While I agree with you, Erlang for instance has collections as primitives (lists/tuples), but then offers more complex collections (such as gb_tree) as part of the stdlib.
"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.
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.
Well, yeah, I agree that the SPL types are nice to have. My complaint is that PHP's only first-class array type is a weird array/map combo. Have you ever seen anything like that in another language?
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.
Lua also have hybrid array, maps and object. It does work well when implemented in a sane way. Lua has different way of iterating the table if you want an array or maps.
... though I wouldn't necessarily call Lua's way of doing things "sane". E.g. if Lua encounters a `nil` somewhere in your table, it will stop iterating.
It's certainly sane in the sense that it was an intentional, if perhaps unusual, design decision. I personally like it since it results in an efficient implementation of sparse arrays.
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.
The world would be a beautiful place if everything intentional were sane :-) It's bitten me a couple of times (e.g. when unpacking arguments in a function to feed them to another function, where one of the arguments is nil) but I can see how it could be the desired behavior in some cases.
Javascript's arrays cannot be used as maps or associative arrays. Arrays require numeric, consecutive keys. Otherwise it's an Object.
--
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.
No, it doesn't. The only magic per spec is about the "length" property (which is essentially a getter/setter pair, despite being a data property and not an accessor pair). That's the only thing special about arrays in JS.
The array prototype functions are only specified by the standard to deal solely with numeric keys, but the lines between and object and array are still pretty blurry. The use case for each is different, but the original question far above was "array/map combo. Have you ever seen anything like that in another language?", and clearly JavaScript is very similar even if not exact.
var x = {};
x[0] = 1;
x.length = 1;
x.map = Array.prototype.map;
x.map(function(y) {return y;});
//[1]
> arrays (aka maps) are basically used for everything.
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!
> Does this new hashtable layout influence object properties/methods too?
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
> 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.
"[...] 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."
Yes, pData and pDataPtr are no more. They have always been pretty pointless - both could have been dropped even retaining the rest of the previous implementation by using a struct hack layout. In the new implementation they aren't needed because it's specialized to zvals (our 99%-or-so use case).
Nice work. I read deeper into the changeset and I like.
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) :)
First off, JavaScript runtimes (or at least V8 and SpiderMonkey, which are the ones I've looked at) don't convert their arrays to hashtables unless they really have to. If your array is not sparse and has no properties defined on it with non-integer names, then it's an actual array of values in memory.
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.
> 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).
It is both nice and concerning, that an ubiquitous element of a ubiquitous language has that much potential for performance optimizations after 19 years of development. The optimizations were not even complicated hacks for edge cases, just a simpler implementation overall.
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
> a ubiquitous language has that much potential for performance optimizations after 19 years of development.
"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?"
You are right. That PHP actually runs is a small wonder. They actually rewrote the engine every few years.
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.
Awesome, but I still don't think it's enough. In benchmarks we did the memory usage of PHP array() was horrific. Sorry I don't have actual numbers to post, but we ended up using pack() and unpack() to store stuff that should have been in an array because it would grow to 100's of megs using PHP's array() and using a binary structure it stays under 10 megs. I just don't think a 2.5X improvement is going to come close to as efficient as it could and should be.
> we ended up using pack() and unpack() to store stuff that should have been in an array because it would grow to 100's of megs using PHP's array() and using a binary structure it stays under 10 megs.
How many items were you storing / how big was the data in each item?
Check the part about packed hashtables (in case you're not storing key/value pairs). They said they're considering a more compact type for actual arrays.
This is my experience benchmarking the same as well. That, combined with a bug in SPLFixedArray that results in it acting like a non-fixed array past some size, makes it very difficult to consider PHP for anything that requires high performance on tight loops/data crunching.
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.
This is probably not a popular opinion, but I believe that PHP's associative array is one of the best-designed data structures in programming languages.
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)
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.
What I read is "if all you have is a hammer, everything looks like a nail."
> 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);
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)
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].
I think there is one reason to default to something ordered, which is that iterating through unordered hashmaps can be non-deterministic from one run to the other. For instance, if you hash by id, the same objects may be assigned different ids from a run to the next, meaning that the map will be iterated in a different order. If there is a bug that's sensitive to iteration order, it will not be reproducible and that can be very annoying to debug.
If you've got bugs due to iteration order you have a whole other issue. If you know that iteration order is important, it should be explicit in the way you prepare/store/handle the data. If your code only works when you iterate in a specific order and you didn't deliberately define that order, it's only really working by accident.
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.
JS objects don't have the same property, whatever order you see from iterating JS objects is only a side effect of the standard hidden class optimization, not because there was intention of having a certain order. In fact if you mix integer keys (which are represented differently) you will not get the "expected" iteration order:
var o = {
key: 3,
1: 4,
value: 10,
0: 2
};
Object.keys(o)
["0", "1", "key", "value"]
If iteration order was specified you couldn't do those optimizations, note how even PHP7 is still paying a lot for the iteration order: the 100k element array only takes roughly 25% of the memory in JavaScript. And what is it even for? How often do you even need to iterate integer keys in insertion order over value order?
> only a side effect of the standard hidden class optimization, not because there was intention of having a certain order
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.
It results in different hidden class because the whole point is to be able to reference named fields by fixed offsets from the object location in memory (same as for example reading struct fields in C). If the order changes, so will the offsets too, so same names with different order must have different hidden classes.
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.
I don't think your explanation makes much sense. Hidden classes describe the layout of objects: if two insertion orders produced the same hidden class, it would mean they have the same layout, with the same fixed field offsets.
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.
I'm saying that argument is wrong, because there is no efficiency loss due to different insertion orders mapping to the same hidden class. In fact there are efficiency advantages because more objects would pass through class-based guard checks into favourable paths. The only reason I can see to not do that is because it would lose iteration 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
In the order discarded case:
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
In the second case the field .y changes offset, but that's fine because the hidden class also changes to indicate the difference in structure. The only problem is that the order of the fields changes.
By the way, JS runtimes used to have insertion order for enumerating properties long before the hidden class optimization or V8 was a thing. V8 was the first to break the insertion-order enumeration for some kinds of objects [1] and eventually other browsers followed suit, even those that don't do hidden classes.
My point was that hidden classes is not a reason to keep nor break insertion-order enumeration. The example I gave was V8 breaking insertion-order enumeration, but for a reason entirely unrelated to its use of hidden classes - it implements Arrays as Objects with consecutive numeric keys, so Objects with consecutive numeric keys get enumerated like Arrays.
So yes, while all major browsers use hidden classes today, that itself is not sufficient to explain why insertion-order enumeration is not maintained.
Yes, the requirement to preserve order predates V8 by years (I believe all the way back to SpiderMonkey, though maybe it was JScript?). Certainly it's long been the case the web de-facto relies on insertion order being preserved (except V8 found that it didn't really for numeric keys, where there was far more variety between implementations, and Carakan and Chakra followed by similarly dropping order for numeric keys).
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:
Yes, and I think I can safely say I've never used this feature (in either Ruby or PHP) for anything more serious than a code golf challenge.
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.
I've used it when I want to parse query params from a URL into a hash, and then possibly modify them, and then write them back out to query params -- in the same order they came in, so the query params will be identical if I didn't end up modifying them, and identical but for what I modified otherwise, etc.
There are probably other analagous circumstances. Maybe even some I could think of that I've encountered.
There's some utility to it, but it can provide unexpected results if you blindly iterating through the match array (though I can't see any reason to do so if you know what offsets you want).
Perl used to let you do this, btw, but they moved away because apparently some denial of service issues were found regarding hashmaps, and so there are security reasons not to. I think you can tell Perl still you don't want that security and it will behave in this way. THere are other ways to do this only on some hashes but they have something of a performance penalty.
IIRC a Perl hash has never been in the order of key add order, but rather that two hashes, with its keys added in the same order, returned their keys in the same order, even in separate executions. Now hash key order is always "random".
I just used one to make a sorted map between names of colors and their RGB values. The order isn't necessary, but it is far more convenient than pulling out the keys and values as a list and then sorting them.
> 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 :)).
So, the only thing I'm actually interested is: API for it stays the same? That is it's the same old "all in one" data structure with the same behavior for all standard functions, with all old gotchas left in place and no new added, right?
The funny thing 5.5 isn't even the current stable version of PHP, which is 5.6. Let alone the whole post is about PHP 7. It's like you're not even paying attention, just doing the whole post for the last phrase.
That is using the same benchmark that nikic is using, and it's using half the RAM of her PHP 7 example.
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.
An important variable determining memory consumption is going to be the maximum bucket load factor. Does anyone know what it is as currently implemented?
> The maximum load factor is 1. A lower load factor only makes sense if open addressing is used.
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.
Wow, I constantly think that nothing about the horribleness of PHP can surprise me, and then Rasmus says something even more insane than his already insane statements. I mean choosing function names based on length because you didn't bother to write an actual hash function? AMAZING.
"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!
>I mean choosing function names based on length because you didn't bother to write an actual hash function? AMAZING.
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."
I think he has a bit of a right to be arrogant and self-deprecating, given that he managed to half-assedly bootstrap something more successful than most other, better programmers will ever achieve.
To be fair, his "get things done" attitude is a big part of why PHP is so popular. It avoids all pedantry and nerdiness (even when it absolutely shouldn't), erring entirely on the side of "let's just get something working."
That might not be the right attitude for all programming languages, but it is working for PHP in at least some sense.
136 comments
[ 3.5 ms ] story [ 216 ms ] threadtl;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.
e: Actually wasn't there a blog post posted to HN suggesting Perl skip to 7 too?
http://blogs.perl.org/users/ovid/2013/02/perl-7.html
http://www.slideshare.net/andy.sh/perl7-light
https://www.youtube.com/watch?v=E_8bjsimLsk
[1] http://perl6.org
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.
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.
There is no "hash table" type in PHP user land.
There are only hash tables that are called "array" for simplicity.
That's why the lend themselves to the same syntax so well.
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.
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.
"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.
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...
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.
Furthermore,Javascript objects aren't maps.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
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."
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) :)
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).
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.
How many items were you storing / how big was the data in each item?
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:
http://uk.php.net/serialize
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.
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)
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);
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... )
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):
In the order discarded case: In the second case the field .y changes offset, but that's fine because the hidden class also changes to indicate the difference in structure. The only problem is that the order of the fields changes.[1] http://code.google.com/p/v8/issues/detail?id=164
So yes, while all major browsers use hidden classes today, that itself is not sufficient to explain why insertion-order enumeration is not maintained.
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')])
http://www.ruby-doc.org/core-1.9.3/Hash.html
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.
Tie::IxHash [1] is available on Cpan.
[1] https://metacpan.org/pod/Tie::IxHash
What are the use cases that you would need an ordered dictionary?
> 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.
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?
So this non-production code is using about twice as much RAM as HHVM production.
There are no userland changes here.
Great job, PHP internals team...
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%.
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.
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.
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.