faster hashs for Matrix_mod2_dense

[malb]

Simon King requested faster hashing for matrices over GF(2). This patch implements it, but depends on #3324 and an updated M4RI.

CC: @simon-king-jena

Component: linear algebra

Keywords: m4ri, hash, matrix

Issue created by migration from https://trac.sagemath.org/ticket/3724

[malb]

implements faster hashing

[malb]

comment:1

Attachment: m4ri_hash.patch.gz

it seems, the patch is independent of the PNG fix.

[malb]

comment:2

Simon, can you review my patch?

[simon-king-jena]

comment:3

The patch applies to sage-3.1.1

Consider a little test:

sage: M=MatrixSpace(GF(2),10000,10000).random_element()
sage: M.set_immutable()
sage: time M.__hash__()

Without the patch, i had to interrupt sage after few minutes since it ate pretty much of my computer's memory.

With the patch, we get

sage: time M.__hash__()
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.00 s
-2570088162955604276

Well done, Martin! I give a positive review.

The patch contains a doc-test. One problem for me: Typing M.__hash__?, i don't see them. What is the user supposed to do in order to see the doc-string of the respective hash method?

I know that the following should be another ticket. But here are two items on my wish list:

1. Can similar things be done with the hash of matrices over GF(p), p>2?
2. Please also improve pickling of matrices! Example:

sage: M=MatrixSpace(GF(2),1000,1000).random_element()
sage: timeit('x=loads(dumps(M))')
5 loops, best of 3: 2.33 s per loop

which is somehow slowish.

[sagetrac-mabshoff]

comment:4

Simon,

please open a thread on sage-devel. I assume the discussion will conclude that speed up is warranted and then we can open tickets for the new issues.

Cheers,

Michael

[sagetrac-mabshoff]

comment:5

Merged in Sage 3.1.2.alpha1

[malb]

comment:6

Replying to @simon-king-jena:

The patch contains a doc-test. One problem for me: Typing M.__hash__?, i don't see them. What is the user supposed to do in order to see the doc-string of the respective hash method?

That could be a bug for introspection (or however that thingy is called). Could you open a ticket?

1. Can similar things be done with the hash of matrices over GF(p), p>2?

Yes it can, please open a Trac ticket and I'll do it as soon as I find some time.

2. Please also improve pickling of matrices! Example:

sage: M=MatrixSpace(GF(2),1000,1000).random_element()
sage: timeit('x=loads(dumps(M))')
5 loops, best of 3: 2.33 s per loop

which is somehow slowish.

That is #3324 which is blocked by a problem on OSX 10.4 and libpng.

[simon-king-jena]

comment:7

Sorry, but i think i should re-open the ticket:

sage: M = MatrixSpace(GF(2),10000,10000).random_element()
sage: M.is_mutable()
True
sage: M.__hash__()
354973654957594997

A mutable object is not allowed to have a hash, AFAIK.
On the other hand, the hash-value seems not to be cached:

sage: M[0,0]
1
sage: M[0,0]=0
sage: M.__hash__()
-8868398381897180811

So, the hash value has changed (i.e., was re-computed) by changing the matrix...

sage: N=copy(M)
sage: N.__hash__()
-8868398381897180811

... and has not changed by copying the matrix.

By consequence, it may be that everything is alright.

However, I re-open the ticket, because I think this should be addressed -- either by a new patch raising an exception when M is mutable, or by the assertion that "mutable objects have no hash" is a rule but no law, and that it is fine since the hash is not cached.

Cheers
Simon

[malb]

address review

[malb]

comment:8

Attachment: m4ri_hash2.patch.gz

You're right, good catch. The attached patch addresses that issue.

[sagetrac-mabshoff]

comment:9

m4ri_hash2.patch looks good to me. Positive review.

[sagetrac-mabshoff]

comment:10

Merged m4ri_hash2.patch in Sage 3.1.2.alpha1

[malb]

comment:11

The new hash-ing method does not obey Sage's hashing rules. See Robert's comment at #3956. Obeying this rule however would come with a considerable speed penalty compared to m4ri_hash.patch.

[sagetrac-mabshoff]

comment:12

Martin,

can we move the latest issue to a new ticket? As is this ticket is getting rather messy, i.e. in HISTORY.txt as well as here.

Cheers,

Michael

[malb]

comment:13

your wish is my command.