Move functions from sage.matroids.bitset_tools to sage.misc

[sagetrac-Stefan]

There are several bitset tools in the matroid code:

• pickling/unpickling
• rev_lex comparison
• bitset_morph

These should be moved into sage.misc.

apply trac_14668_bitsets.patch

Component: misc

Author: Rudi Pendavingh, Stefan van Zwam

Reviewer: Volker Braun

Merged: sage-5.11.beta1

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

[sagetrac-Stefan]

Changed dependencies from 7477 to none

[sagetrac-Stefan]

comment:2

Just uploaded a patch adding functionality to bitset.pxi and tests to misc_c.pyx. I took the liberty to clean up some of the docstrings and trailing whitespace; I hope that's ok.

[sagetrac-Stefan]

Author: Rudi Pendavingh, Stefan van Zwam

[nathanncohen]

comment:4

Hellooooooooooooooo !!

Just a couple of comments :

I thought at first that your bitset_rev_lex_cmp function was wrong, and I noticed later that I had read "reverse lexicographic order" as "co-lex order" (i.e. the lexicographic order on words when you read them from right to left instead). Turns out that this "reverse lexicographic order" can be obtained by adding a "-" to a call to the previous function.

I personally think that risking this confusion is not worth saving a - in a source code, and that this '-' is not worth the space it takes to store the code of this function in bitset.pxi either. Well, that's just my advice, I don't mind much, I just say it aloud, do as you wish.

I also did not understand from its docstring what bitset_morph does, and so I read the code. First, I think that "function" would be better than "morphism" in this context. And as this actually computes the image of a bitset by a function, renaming it to bitset_image or bitset_function_image would make sense to me... What do you think ?

Anyway, have fuuuuuuuuuuuuuuuuuuuuuuuuuuuunnn !!!

Nathann

[sagetrac-Stefan]

Bitset enhancements

[sagetrac-Stefan]

comment:5

Attachment: trac_14668_bitsets.patch.gz

• bitset_rev_lex_cmp was removed
• bitset_morph is now called bitset_map with hopefully better docstring

[nathanncohen]

comment:6

• bitset_morph is now called bitset_map with hopefully better docstring

Oh right ! Good choice :-)

Nathann

[dcoudert]

comment:7

Hello,

I'm giving here some comments that could either be used to improve this patch or be considered for a future patch.

With path #13352, I tried to speed-up the bitset_len method using popcount. I have not finalized the patch because the solution I have proposed is not satisfactory. In particular, it has been suggested to use the low level __builtin_popcount() method, but my trials were not successful. Another remark was that GMP has functions like mpz_popcount() for mpz_t.

In fact, the mpz_t type of GMP is similar to the bitset_s type we have here, and the bitset_lex_cmp method proposed in this patch corresponds to the mpz_cmp method of GMP.

Since GMP is optimized for most processors (and used for arbitrary length numbers in sage), it would be nice to use it here. But may be this is relevant for (Frozen)Bitset only?

David.

[jasongrout]

comment:8

Indeed. I wonder how much of a speedup it would be to move to mpz_t as the base format. That sounds interesting to look at.

[jasongrout]

comment:9

It looks like polymake has a bitset C++ class based on mpz_t: http://modular.math.washington.edu/home/wstein/www/home/cswiercz/sage-4.6/spkg/build/polymake-2.2.p5/src/lib/PTL/include/Bitset.h

[sagetrac-Stefan]

comment:10

The GMP suggestion is now ticket #14704 . Since there's a big ticket (#7477) depending on this one, I'd prefer this version to go into Sage soon. Our code in #7477 only uses the bitset_pickle and bitset_unpickle functions, so I'd be ok if the other stuff was postponed.

[dcoudert]

comment:11

Sure, it's better to have a dedicated ticket for possibly moving to gmp.

[rbeezer]

comment:12

Replying to @sagetrac-Stefan:

I'd prefer this version to go into Sage soon.

Agreed - no point to hangup #7477 on improvements to this. Get matroids working, then investigate speedups to bitsets.

[vbraun]

Reviewer: Volker Braun

[vbraun]

comment:13

I was hoping that somebody would have set this to positive review by now, come oooon.

And no endless feature request on tickets that obviously improve what we have... can you reimplement all of bitsets using foo? Sure, great idea! :-P

[rbeezer]

comment:14

Replying to @vbraun:

I was hoping that somebody would have set this to positive review by now, come oooon.

Yes, it has been more than 24 hours. I was about to cruise the documentation and code style, etc. But I'm late to the party again, apparently. ;-)

[jdemeyer]

Merged: sage-5.11.beta1