[m-dev.] Equality and pointer equality

[Ralph Becket]

Ralph Becket, Friday,  8 October 2004:
> It just occurred to me to wonder whether the Mercury equality tests
> first test for word/pointer equality before doing anything more
> complicated?

It turns out that we don't.  Each of these runs repeatedly tests a value
against itself (see the attached file):

1000000 equality tests of string length 2^ 5:  199ms
1000000 equality tests of string length 2^ 6:  320ms
1000000 equality tests of string length 2^ 7:  580ms
1000000 equality tests of string length 2^ 8: 1080ms
1000000 equality tests of string length 2^ 9: 2080ms
1000000 equality tests of string length 2^10: 4090ms
1000000 equality tests of list length 2^ 5: 1140ms
1000000 equality tests of list length 2^ 6: 2250ms
1000000 equality tests of list length 2^ 7: 4390ms
1000000 equality tests of list length 2^ 8: 8740ms
1000000 equality tests of list length 2^ 9: 17470ms
1000000 equality tests of list length 2^10: 34830ms

This is running on ceres with the default compilation options.  Things
are faster at -O6, but the equality tests are still linear in the size
of the input.

Oops!

-- Ralph
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------