Change binary_matrix data type to use bitset #17665

dcoudert · 2015-01-24T18:13:04Z

This patch changes the data structure binary_matrix_t to use one bitset per row. This enables us to use directly operations on bitsets without casts. It also moves the files to data_structures.
Currently, this data structure is only used for operations on graphs.

CC: @nathanncohen

Component: misc

Author: David Coudert

Branch/Commit: da02c12

Reviewer: Jeroen Demeyer, Nathann Cohen

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

The text was updated successfully, but these errors were encountered:

dcoudert · 2015-01-24T18:13:41Z

Branch: public/17665

videlec · 2015-01-24T18:40:52Z

comment:2

Hello,

You could also consider moving it to sage/data_structures/... no?

Vincent

dcoudert · 2015-01-24T18:44:33Z

comment:3

I will try to ;)
David.

sagetrac-git · 2015-01-24T20:56:57Z

Branch pushed to git repo; I updated commit sha1. New commits:

`a2c836b`	`trac #17665: change the structure binary_matrix`
`cbf8dda`	`trac #17665: update distances_all_pairs`
`1a9851f`	`trac #17665: update static_dense_graph`
`0524fda`	`trac #17665: add bitset_are_disjoint to bitset_t`
`4269af6`	`trac #17665: update independent_set`
`58ae861`	`trac #17665: fix multiple problems but not all`

sagetrac-git · 2015-01-24T20:56:57Z

Commit: 58ae861

dcoudert · 2015-01-24T21:00:28Z

comment:5

I have compilation errors that I don't know how to fix.

It also remains to move the data structure to appropriate directory.

Enough for me for tonight.

David.

sagetrac-git · 2015-01-24T23:36:29Z

Branch pushed to git repo; I updated commit sha1. New commits:

`b4d28b2`	`trac #17665: identation error in generic_graph_pyx.pyx`

sagetrac-git · 2015-01-24T23:36:29Z

Changed commit from 58ae861 to b4d28b2

dcoudert · 2015-01-24T23:38:48Z

comment:7

I also tried to add a file binary_matrix.pxd (not in the commits since I don't remember how to include it), but still not working :(

jdemeyer · 2015-01-25T09:06:39Z

comment:8

Replying to @dcoudert:

I don't remember how to include it

git add FILENAME

dcoudert · 2015-01-25T10:47:02Z

comment:9

I have added file binary_matrix.pxd, but now I'm unable to push my modifications.

confetti:sage dcoudert$ git trac push
Pushing to Trac #17665...
Guessed remote branch: public/17665
Traceback (most recent call last):
  File "/Users/dcoudert/sage/git-trac-command/bin/git-trac", line 18, in <module>
    cmdline.launch()
  File "/Users/dcoudert/sage/git-trac-command/git_trac/cmdline.py", line 210, in launch
    app.push(ticket_number, remote=args.remote, force=args.force)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/app.py", line 194, in push
    self.repo.push(remote, force)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_repository.py", line 181, in push
    self.git.echo.push('trac', refspec)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 341, in meth
    return self.execute(git_cmd, *args, **kwds)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 98, in execute
    popen_stderr=subprocess.PIPE)
  File "/Users/dcoudert/sage/git-trac-command/git_trac/git_interface.py", line 263, in _run
    raise GitError(result)
git_trac.git_error.GitError: git returned with non-zero exit code (1) when executing "git push trac HEAD:refs/heads/public/17665"
    STDERR: error: insufficient permission for adding an object to repository database ./objects
    STDERR: 
    STDERR: fatal: failed to write object
    STDERR: error: unpack failed: unpack-objects abnormal exit
    STDERR: To [email protected]:sage.git
    STDERR:  ! [remote rejected] HEAD -> public/17665 (n/a (unpacker error))
    STDERR: error: failed to push some refs to '[email protected]:sage.git'

Should I use a specific command?

sagetrac-git · 2015-01-25T12:54:28Z

Changed commit from b4d28b2 to 3e7ccc6

sagetrac-git · 2015-01-25T12:54:28Z

Branch pushed to git repo; I updated commit sha1. New commits:

`8dc4967`	`trac #17665: resolve compilation issues`
`3e7ccc6`	`trac #17665: use bitset_t instead of bitset_s is cleaner`

sagetrac-git · 2015-01-25T15:43:57Z

Branch pushed to git repo; I updated commit sha1. New commits:

`cc0cc60`	`trac #17665: move binary_matrix to data_structures`

sagetrac-git · 2015-01-25T15:43:57Z

Changed commit from 3e7ccc6 to cc0cc60

sagetrac-git · 2015-01-25T15:47:35Z

Changed commit from cc0cc60 to 5e3d524

sagetrac-git · 2015-01-25T15:47:35Z

Branch pushed to git repo; I updated commit sha1. New commits:

`5e3d524`	`trac #17665: fix binary_matrix doc`

dcoudert · 2015-01-25T15:51:27Z

comment:13

Patch ready to be reviewed.

Many thanks to Volker for solving technical issues.

jdemeyer · 2015-01-26T10:51:57Z

Changed branch from public/17665 to u/jdemeyer/ticket/17665

jdemeyer · 2015-01-26T10:52:25Z

Changed commit from 5e3d524 to 5cc5d22

jdemeyer · 2015-01-26T10:52:25Z

comment:15

Removed some cruft and a compiler warning.

New commits:

`5cc5d22`	`Remove unneeded stuff`

dcoudert · 2015-01-26T12:28:50Z

comment:16

Thank you, it is better now.

nathanncohen · 2015-01-26T13:05:24Z

comment:17

Hello !

I added a small commit at public/17665 that only fixes some doc and a function call. It is not equivalent to do the following change:

-    binary_matrix_set0(m,row,col)
-    m.rows[row][col >> index_shift] |= (<unsigned long>1) << (value & offset_mask)
+    if value:
+        binary_matrix_set1(m,row,col)
+    else:
+        binary_matrix_set0(m,row,col)

The purpose of the first code (and of bitset_set_to is specifically to avoid that 'if').

Nothing else to mention, and only my commit now needs a review!

Nathann

dcoudert · 2015-01-26T13:11:53Z

comment:18

Have you pushed it on top of what Jeroen did? I don't see your commit.

nathanncohen · 2015-01-26T13:12:37Z

comment:19

Yep it is there O_o

Nathann

jdemeyer · 2015-01-26T16:13:16Z

comment:20

Why did you replace

for i in range(m.n_rows):

by

for i from 0 <= i < m.n_rows:

everywhere? The latter is considered legacy syntax.

Also: make sure your types match. n_rows and n_cols are declared as long, then loop indices should also be long (you use int in many places).

dcoudert · 2015-01-26T16:30:31Z

comment:21

Replying to @jdemeyer:

Why did you replace
for i in range(m.n_rows):
by
for i from 0 <= i < m.n_rows:
everywhere? The latter is considered legacy syntax.

I thought it was better this way, but if it's not the correct cython syntax, we can go back to range(n).

Also: make sure your types match. n_rows and n_cols are declared as long, then loop indices should also be long (you use int in many places).

It was already intin many places. So we can try to unify the stuff.
Honestly I doubt that we really need long for n_rows and n_cols. int should be large enough, no?

Why have you changed the path to the branch? I cannot write to u/jdemeyer/ticket/17665 and I'm unable to see what Nathann's pushed.

Best,
David.

jdemeyer · 2015-01-26T17:26:20Z

comment:22

Replying to @dcoudert:

Replying to @jdemeyer:
Why did you replace
for i in range(m.n_rows):
by
for i from 0 <= i < m.n_rows:
everywhere? The latter is considered legacy syntax.
I thought it was better this way, but if it's not the correct cython syntax, we can go back to range(n).

It's technically correct but not recommended.

Also: make sure your types match. n_rows and n_cols are declared as long, then loop indices should also be long (you use int in many places).

It was already intin many places. So we can try to unify the stuff.
Honestly I doubt that we really need long for n_rows and n_cols. int should be large enough, no?

I would personally use long (or even better: Py_ssize_t). There is no reason to artificially restrict to 2^32 rows and columns. Even if you don't see an obvious use-case for this, perhaps other people do.

Given that

sage: Matrix(GF(2), 2^32, 1)
4294967296 x 1 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)

works fine, the same would work for this binary_matrix class.

dcoudert · 2015-01-26T21:08:45Z

Changed branch from u/jdemeyer/ticket/17665 to u/dcoudert/ticket/17665

dcoudert · 2015-01-26T21:13:34Z

comment:24

I have implemented requested changes:

use range(n) instead of for i from 0 <= i < n
use type Py_ssize_t instead of int or long in binary_matrix

Let me know if further changes are needed.

New commits:

`1a1d430`	`trac #17665: Merged with 6.5.beta6`
`74ff5b2`	`trac #17665: reviewer's commit`
`283e45e`	`trac #17665: use type Py_ssize_t and change loops`

dcoudert · 2015-01-26T21:13:34Z

Changed commit from 5cc5d22 to 283e45e

jdemeyer · 2015-01-27T05:03:15Z

comment:26

Given that bitsets are initialized with zeros, replace

binary_matrix_init(m, n, n)
binary_matrix_fill(m, 0)

by

binary_matrix_init(m, n, n)

In bitset_are_disjoint, replace

We assume ``a.limbs == b.limbs``.

by

We assume ``a.limbs <= b.limbs``.

sagetrac-git · 2015-01-27T07:35:59Z

Branch pushed to git repo; I updated commit sha1. New commits:

`da02c12`	`trac #17665: fix reviewer's comments`

sagetrac-git · 2015-01-27T07:35:59Z

Changed commit from 283e45e to da02c12

dcoudert · 2015-01-27T07:36:25Z

comment:28

done.

nathanncohen · 2015-01-28T10:21:12Z

comment:29

Jeroen? Have your remarks been correctly addressed? If so, can you set this ticket to positive_review?

Thanks,

Nathann

jdemeyer · 2015-01-28T19:51:26Z

comment:30

I give positive_review to all changes which are not in sage/graphs. If somebody else can review the graphs stuff, that would be perfect.

nathanncohen · 2015-01-28T20:38:55Z

Reviewer: Jeroen Demeyer, Nathann Cohen

nathanncohen · 2015-01-28T20:38:55Z

comment:31

I give positive_review to all changes which are not in sage/graphs. If somebody else can review the graphs stuff, that would be perfect.

Then it can go. I already reviewed the graph changes.

Nathann

dcoudert · 2015-01-28T22:15:33Z

comment:32

Thank you for your help.
David.

vbraun · 2015-01-29T13:26:01Z

Changed branch from u/dcoudert/ticket/17665 to da02c12

dcoudert added this to the sage-6.5 milestone Jan 24, 2015

dcoudert added p: major / 3 labels Jan 24, 2015

This comment has been minimized.

Sign in to view

dcoudert added the s: needs review label Jan 25, 2015

jdemeyer added s: needs work and removed s: needs review labels Jan 26, 2015

dcoudert added s: needs review and removed s: needs work labels Jan 26, 2015

nathanncohen mannequin added s: positive review and removed s: needs review labels Jan 28, 2015

vbraun removed the s: positive review label Jan 29, 2015

vbraun closed this as completed in b38de51 Jan 29, 2015

dcoudert mentioned this issue Feb 17, 2015

Branch and Bound for vertex separation #17647

Closed

sagetrac-gouezel mannequin mentioned this issue Feb 18, 2015

Sublinking of static_dense_graph #17772

Closed

Change binary_matrix data type to use bitset #17665

Change binary_matrix data type to use bitset #17665

Comments

dcoudert commented Jan 24, 2015

dcoudert commented Jan 24, 2015

videlec commented Jan 24, 2015

dcoudert commented Jan 24, 2015

sagetrac-git mannequin commented Jan 24, 2015

sagetrac-git mannequin commented Jan 24, 2015

dcoudert commented Jan 24, 2015

sagetrac-git mannequin commented Jan 24, 2015

sagetrac-git mannequin commented Jan 24, 2015

dcoudert commented Jan 24, 2015

jdemeyer commented Jan 25, 2015

dcoudert commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

sagetrac-git mannequin commented Jan 25, 2015

dcoudert commented Jan 25, 2015

This comment has been minimized.

jdemeyer commented Jan 26, 2015

jdemeyer commented Jan 26, 2015

jdemeyer commented Jan 26, 2015

dcoudert commented Jan 26, 2015

nathanncohen mannequin commented Jan 26, 2015

dcoudert commented Jan 26, 2015

nathanncohen mannequin commented Jan 26, 2015

jdemeyer commented Jan 26, 2015

dcoudert commented Jan 26, 2015

jdemeyer commented Jan 26, 2015

dcoudert commented Jan 26, 2015

dcoudert commented Jan 26, 2015

dcoudert commented Jan 26, 2015

jdemeyer commented Jan 27, 2015

sagetrac-git mannequin commented Jan 27, 2015

sagetrac-git mannequin commented Jan 27, 2015

dcoudert commented Jan 27, 2015

nathanncohen mannequin commented Jan 28, 2015

jdemeyer commented Jan 28, 2015

nathanncohen mannequin commented Jan 28, 2015

nathanncohen mannequin commented Jan 28, 2015

dcoudert commented Jan 28, 2015

vbraun commented Jan 29, 2015