Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

PHP 7's new hashtable implementation

nikic.github.io

Post reply on HN
Print view View original

121–130 of 137 posts

Re: PHP 7's new hashtable implementation

#121

Post by oldmanjay »

overgard wrote: post #110
bcheung wrote: post #107

You mean they are not using strlen as the hash function anymore? http://news.php.net/php.internals/70691

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. 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…

at least he has the good sense to be arrogant about his lack of basic skill.

Re: PHP 7's new hashtable implementation

#122

Post by chriswarbo »

fleetfox wrote: post #55
cranklin wrote: post #46

Earlier quoted context omitted.

Those aren't primitive types

What are those called then? Wikipedia definition of primitive type is pretty vague. I don't think collections/containers can't be called primitive.

I'd call them "composite types".

"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.

Re: PHP 7's new hashtable implementation

#123

Post by krapp »

oldmanjay wrote: post #121
overgard wrote: post #110

Earlier quoted context omitted.

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. 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…

at least he has the good sense to be arrogant about his lack of basic skill.

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.

Re: PHP 7's new hashtable implementation

#124

Post by gsnedders »

Arnavion wrote: post #112
gsg wrote: post #97

Earlier quoted context omitted.

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 cle…

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. [1] http://code.google.com/p/v8/issues/detail?id=164

Who doesn't do "hidden classes" (or maps, or inferred-classes, or whatever else we're calling them today)? All major JS engines certainly do.

Re: PHP 7's new hashtable implementation

#125

Post by gsnedders »

gsg wrote: post #71
esailija wrote: post #65

Earlier quoted context omitted.

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 i…

> 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. (Might not apply to numeric keys, though.…

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).

Re: PHP 7's new hashtable implementation

#126

Post by gsnedders »

the_mitsuhiko wrote: post #39
dsp1234 wrote: post #35

Earlier quoted context omitted.

Adding non-numeric keys does not remove an Array's "arrayness" in JavaScript 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…

It does internally. Pretty sure that's even defined in the standard.

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.

Re: PHP 7's new hashtable implementation

#127

Post by username223 »

allendoerfer wrote: post #23

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…

> 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?"

Re: PHP 7's new hashtable implementation

#128

Post by Retra »

ionforce wrote: post #103
skrebbel wrote: post #41

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, bu…

Given no other information, I'm also in the "disagree with your unique opinion" camp. What are the use cases that you would need an ordered dictionary?

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.

Re: PHP 7's new hashtable implementation

#129

Post by gsnedders »

bzbarsky wrote: post #34
bhouston wrote: post #19

How does this compare to the optimized hashtable implementations in the various JavaScript runtimes? I imagine their requirements are similar?

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…

> 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).

Re: PHP 7's new hashtable implementation

#130

Post by gburt »

overgard wrote: post #110
bcheung wrote: post #107

You mean they are not using strlen as the hash function anymore? http://news.php.net/php.internals/70691

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. 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…

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.

Post reply on HN