Iterative comparisons #85

vext01 · 2015-01-27T16:09:35Z

In response to #83, this pull request implements an (optimised) iterative comparison.

Prior to this change, I was unable to run deltablue with a parameter of more than about 1650. Now it runs larger numbers fine.

Below are the results before and after on richards and deltablue. Richards is ever so slightly slower, but deltablue is dramatically faster (on par with the same benchmark in python running under pypy).

1: /home/vext01/research/hippyvm.hippyvm/hippy-c-master richards.php
            Mean        Std.Dev.    Min         Median      Max
real        2.201       0.009       2.194       2.198       2.218       
user        2.182       0.014       2.164       2.184       2.204       
sys         0.015       0.008       0.008       0.012       0.028       

1: /home/ltratt/hippy/hippyvm/hippy-c richards.php
            Mean        Std.Dev.    Min         Median      Max
real        2.223       0.007       2.211       2.226       2.230       
user        2.203       0.006       2.192       2.204       2.208       
sys         0.016       0.003       0.012       0.016       0.020       



1: /home/vext01/research/hippyvm.hippyvm/hippy-c-master deltablue.php
            Mean        Std.Dev.    Min         Median      Max
real        3.748       0.007       3.734       3.749       3.756       
user        3.719       0.015       3.692       3.724       3.732       
sys         0.023       0.008       0.012       0.020       0.036       

1: /home/ltratt/hippy/hippyvm/hippy-c deltablue.php
            Mean        Std.Dev.    Min         Median      Max
real        0.317       0.002       0.314       0.318       0.320       
user        0.302       0.004       0.296       0.304       0.308       
sys         0.013       0.003       0.008       0.012       0.016

Note that our method _compare() is not being compiled, probably due to the loop. @cfbolz suggested to add a jit merge point for this loop. This should be a separate unit of work.

Note that hippy does not deal with comparison cycles very well. I will raise an issue for this.

Sorry about the large number of commits, it has been quite a journey, with the algorithm evolving over time.

This needs to be carefully reviewed.

Also remove the dead _compare_object().

This reverts commit 7293476. This slowed down dletablue and made no differenceto richards.

Tiny speedup in deltablue.

No functional change.

This gives roughly a 5% speed increase on DeltaBlue.

Beef up the explanation for what's going on, as otherwise the code makes very little sense.

This and the previous commit speed up object comparison by almost 16x.

Means we don't allocate or iterate over another list.

This reverts commit 788359d. This won't work, as object comparisons need to happen left to right.

No functional change.

This also opens up a couple of opportunities to bypass redundant identity checks.

I got this wrong. We want to inline hippy's default instance object comparison, but allow subclasses to override it. This mechanism is a simpler version of UseFastComparison, but achieves the same effect.

Previously this meant that when we hit the slow case, we needlessly redid all the fast work that we'd already done. This gives about ~8-9% speedup on Deltablue.

We rely on the fact that typically objects of the same type will return attributes in the same order to avoid this.

Often we can expect that their keys follow the same order, which stops us doing lookups in cases where that property holds. Previously, comparisons were particularly annoying as the current array API forced us to do 2 lookups per key on average.

No functional change.

Gives ~4% speedup on Deltablue.

This patch makes two related changes: 1) We only need to push aggregate thingies onto the stack, as we can compare primitive thingies as we're going. If they're definitely equal, they don't need to go on the stack at all. 2) As soon as we encounter primitive thingies which we can tell aren't equal, there's no point pushing anything further onto the stack: what we have will be enough to tell us the answer, so we can then break. Together they give ~17% increase on DeltaBlue.

This allows us to hit all of our fast cases.

vext01 · 2015-01-28T10:35:55Z

The failing tests are orthogonal. See #87.

vext01 · 2015-01-29T10:36:58Z

Merged the regex fixes. Should now pass.

vext01 · 2015-01-29T16:46:59Z

The remaining failing test is a cycle test. This was probably passing by luck before, as hippy does not handle cycles properly. I'm inclined to mark it skip until someone addresses cycles.

https://bugs.php.net/bug.php?id=63882

vext01 · 2015-02-02T13:07:11Z

I have marked the bug 63882 test as skipped, as discussed above.

4 phpt tests will now fail:

bug_41655_2
fread_socket_variation1
fwrite_variation3
get_current_user

These are failing on master already.

vext01 · 2015-02-02T16:19:59Z

Hrm, odd -- the tests I expected to fail did not.

Must be something to do with our test environment. Unrelated to this pull anyhow.

rlamy · 2015-02-03T16:22:06Z

I didn't really review it, but the tests seem comprehensive. I'd say go ahead!

Iterative comparisons

vext01 and others added 30 commits January 23, 2015 13:28

MOve aggregate comparisons into their own function.

a4770ef

Also remove the dead _compare_object().

Make the array case iterative.

c386584

Add tests from the iterative_cmp branch.

bbe1cce

Hook object comparisons onto _compare_aggregate.

d3fa33f

Avoid repeated array length computations.

7293476

Update WRT get_errno() changes by armin.

5efb7b8

Missing import.

d12a3e8

Revert "Avoid repeated array length computations."

1ab836e

This reverts commit 7293476. This slowed down dletablue and made no differenceto richards.

Typo bug.

e17e766

Restore order of cases in comparison.

c8e5f0c

Tiny speedup in deltablue.

Minor tidy up.

9054507

No functional change.

Chop the number of lists used down.

21e6995

This gives roughly a 5% speed increase on DeltaBlue.

Disequality isn't a word.

49c20e8

Beef up the explanation for what's going on, as otherwise the code makes very little sense.

Fast path comparing arrays with only simple datatypes.

37a9350

Add some "obvious" fast paths in (mostly to do with object identity).

270bc00

Inline the common object comparison case.

14f68a0

NotImplemntedError is not RPython, so make a new exception type.

b01b129

This and the previous commit speed up object comparison by almost 16x.

And kill the remaining dead code in W_InstanceObject.compare().

9bb4b69

Add a fast path. Hope to find no aggregate fields.

2df0624

Remove new_st on object comparisons.

788359d

Means we don't allocate or iterate over another list.

Array comparisons are left to right.

63f1865

Revert "Remove new_st on object comparisons."

f92295b

This reverts commit 788359d. This won't work, as object comparisons need to happen left to right.

Test that checks object comparisons are left to right.

63eadcf

Remove broken test shadowed by another test.

4448d1f

Match Hippy's code style.

5901e57

No functional change.

Try not to allocate a new_st list unless absolutely necessary.

bc0f789

Remove redundant UseFastComparison.

146b7d1

This also opens up a couple of opportunities to bypass redundant identity checks.

Add a big comment and edit another one to reflect reality.

0fe4327

Remove minor redundancy.

085f418

Sort-of restore the "fast" comparison.

99e40ef

I got this wrong. We want to inline hippy's default instance object comparison, but allow subclasses to override it. This mechanism is a simpler version of UseFastComparison, but achieves the same effect.

ltratt and others added 12 commits January 26, 2015 16:55

NotImplementedError isn't RPython.

8f86d79

Only do type checks on dereferenced thingies.

07a15bf

The iterator should not be reset.

5ffa441

Previously this meant that when we hit the slow case, we needlessly redid all the fast work that we'd already done. This gives about ~8-9% speedup on Deltablue.

Avoid (most) dictionary lookups when comparing objects.

6664d04

We rely on the fact that typically objects of the same type will return attributes in the same order to avoid this.

Minor code prettification.

f36d0fc

No functional change.

Avoid doing unnecessary derefs.

d401472

Gives ~4% speedup on Deltablue.

Add minor test variant.

24331f9

When ignore_order is True, make the search breadth-first.

fac8d99

This allows us to hit all of our fast cases.

Add a few more comparison tests.

5220fb4

Add a few more comparison tests.

7fc9523

vext01 mentioned this pull request Jan 27, 2015

Hippy cannot detect cycles in comparisons. #86

Open

Merge branch 'master' into iterative_cmp2

1064d56

Mark a cyclic comparison test as skip.

af6a0c1

vext01 added a commit that referenced this pull request Feb 5, 2015

Merge pull request #85 from hippyvm/iterative_cmp2

80eab66

Iterative comparisons

vext01 merged commit 80eab66 into master Feb 5, 2015

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Iterative comparisons #85

Iterative comparisons #85

vext01 commented Jan 27, 2015

vext01 commented Jan 28, 2015

vext01 commented Jan 29, 2015

vext01 commented Jan 29, 2015

vext01 commented Feb 2, 2015

vext01 commented Feb 2, 2015

rlamy commented Feb 3, 2015

Iterative comparisons #85

Iterative comparisons #85

Conversation

vext01 commented Jan 27, 2015

vext01 commented Jan 28, 2015

vext01 commented Jan 29, 2015

vext01 commented Jan 29, 2015

vext01 commented Feb 2, 2015

vext01 commented Feb 2, 2015

rlamy commented Feb 3, 2015