Packed array is not fast?

9 years ago by Yasuo Ohgaki — view source

unread

Hi all,

I've tried to see how packed array is faster with following code

I confirmed when start index is non-zero, hash is used by
zend_hash_index_find().
I got following result. (with much larger number of elements/loops)

Fedora 22 + current master without --enable-debug
1st "Time" is total execution time.
2nd "Time" is the time spent by "for loop"

Hash
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7903809547424
Time: 1.1529920101166
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.8049499988556
Time: 1.1719739437103

Packed
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7407248020172
Time: 1.1594388484955
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7248120307922
Time: 1.1530420780182

Packed array is not so fast, even if zend_hash.c seems much
faster with packed array.

Just FYI.

Regards,

P.S. Am I doing something wrong?
HHVM seems to have optimization margins for hash and loop.

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Levi Morrison — view source

unread

Hi all,

I've tried to see how packed array is faster with following code

http://3v4l.org/TQd6c

I confirmed when start index is non-zero, hash is used by
zend_hash_index_find().
I got following result. (with much larger number of elements/loops)

Fedora 22 + current master without --enable-debug
1st "Time" is total execution time.
2nd "Time" is the time spent by "for loop"

Hash
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7903809547424
Time: 1.1529920101166
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.8049499988556
Time: 1.1719739437103

Packed
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7407248020172
Time: 1.1594388484955
[yohgaki@dev php-src]$ ./php-bin ~/tmp/array_bench2.php
Time: 1.7248120307922
Time: 1.1530420780182

Packed array is not so fast, even if zend_hash.c seems much
faster with packed array.

Just FYI.

Regards,

P.S. Am I doing something wrong?
HHVM seems to have optimization margins for hash and loop.

--
Yasuo Ohgaki
yohgaki@ohgaki.net

How are you testing hash vs packed? As far as what you posted I cannot
tell a difference – it looks like you are running the same thing twice
(same binary and same input file).

9 years ago by Yasuo Ohgaki — view source

unread

Hi Levi,

How are you testing hash vs packed? As far as what you posted I cannot
tell a difference – it looks like you are running the same thing twice
(same binary and same input file).

I've modified START index and verified both packed and unpacked array is
used
by using gdb. I didn't analyze whole execution, but only zend_hash.c

I didn't paste slightly different code because it will not give us much
difference
and it's useless services like 3v4l.

I'm a little disappointed by the result because I was expecting much better
result with packed array..

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Dmitry Stogov — view source

unread

I see only the test for "packed" array. You may create similar "hash"
array, initializing it in reverse order.

In my experiments "packed" arrays are slightly (8%) faster.

$ sapi/cli/php packed.php
Time: 0.022471189498901
Time: 0.012310028076172

$ sapi/cli/php hash.php
Time: 0.024425029754639
Time: 0.012874126434326

Thanks. Dmitry.

Hi Levi,

How are you testing hash vs packed? As far as what you posted I cannot
tell a difference – it looks like you are running the same thing twice
(same binary and same input file).

I've modified START index and verified both packed and unpacked array is
used
by using gdb. I didn't analyze whole execution, but only zend_hash.c

I didn't paste slightly different code because it will not give us much
difference
and it's useless services like 3v4l.

I'm a little disappointed by the result because I was expecting much better
result with packed array..

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Yasuo Ohgaki — view source

unread

Hi Dmitry,

I see only the test for "packed" array. You may create similar "hash"
array, initializing it in reverse order.

It's better approach to see the difference because the array content is
basically the same.

In my experiments "packed" arrays are slightly (8%) faster.

$ sapi/cli/php packed.php
Time: 0.022471189498901
Time: 0.012310028076172

$ sapi/cli/php hash.php
Time: 0.024425029754639
Time: 0.012874126434326

It's faster on my PC, too.
8% is good enough to have.
I'm surprised that PHP's hash is super fast :)

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Julien Pauli — view source

unread

Just to throw back another discussion based on this topic, has anyone
considered changing the hash algorithm about string keys (real hashes) ?

I gave MurmurHash2 a try, it was twice faster than DJB33 in my benchs
(64bits platform and 64bits MurmurHash2 variant).
128bits MurmurHash3 however was a little bit slower than DJB33.
I did not analyze collision risks though, but a valgrind/calgrind bench on
many scenarios showed a better response time and a better zend_hash_func()
response time with MurmurHash2.

Julien.P

Hi Dmitry,

I see only the test for "packed" array. You may create similar "hash"
array, initializing it in reverse order.

It's better approach to see the difference because the array content is
basically the same.

In my experiments "packed" arrays are slightly (8%) faster.

$ sapi/cli/php packed.php
Time: 0.022471189498901
Time: 0.012310028076172

$ sapi/cli/php hash.php
Time: 0.024425029754639
Time: 0.012874126434326

It's faster on my PC, too.
8% is good enough to have.
I'm surprised that PHP's hash is super fast :)

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Dmitry Stogov — view source

unread

Hi Julien,

Could you be more specific. From the first look MurmurHash2is more
expensive, but may be it reduces number of collisions.
what implementation(s) did you use (src or patch)? how did you measure the
speed? did you try to embed it into PHP?

Thanks. Dmitry.

Just to throw back another discussion based on this topic, has anyone
considered changing the hash algorithm about string keys (real hashes) ?

I gave MurmurHash2 a try, it was twice faster than DJB33 in my benchs
(64bits platform and 64bits MurmurHash2 variant).
128bits MurmurHash3 however was a little bit slower than DJB33.
I did not analyze collision risks though, but a valgrind/calgrind bench on
many scenarios showed a better response time and a better zend_hash_func()
response time with MurmurHash2.

Julien.P

Hi Dmitry,

I see only the test for "packed" array. You may create similar "hash"
array, initializing it in reverse order.

It's better approach to see the difference because the array content is
basically the same.

In my experiments "packed" arrays are slightly (8%) faster.

$ sapi/cli/php packed.php
Time: 0.022471189498901
Time: 0.012310028076172

$ sapi/cli/php hash.php
Time: 0.024425029754639
Time: 0.012874126434326

It's faster on my PC, too.
8% is good enough to have.
I'm surprised that PHP's hash is super fast :)

Regards,

--
Yasuo Ohgaki
yohgaki@ohgaki.net

9 years ago by Julien Pauli — view source

unread

First of all, I tried it against a PHP5 codebase, not PHP7.

I simply patched it about return type (casted it to our ulong , taking care
of 32/64 platforms), then I very simply #define zend(_inline)_hash_func to
mumurhash2.

Then I ran a callgrind on an extension of mine (closed source), that
heavily makes use of zend_inline_hash_func.

I noticed with callgrind result graph that this latter took twice less time
when the macro was defined to target murmurhash2 than DJB33.
And the zend_hash_quick_****() calls called later with such a hash did not
seem to take longer time, though the collision rate stayed barely the same.

This is a quick test as #defining in an extension is abviously not safe at
all, but as I fully use the quick API, the compiled PHP codebase doesnt
make use of zend_hash_func itself (which would lead to DJB33)

Julien.P

Hi Julien,

Could you be more specific. From the first look MurmurHash2is more
expensive, but may be it reduces number of collisions.
what implementation(s) did you use (src or patch)? how did you measure the
speed? did you try to embed it into PHP?

Thanks. Dmitry.