Opened 8 years ago

Closed 8 years ago

#14668 closed task (fixed)

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

Reported by: Stefan Owned by: jason
Priority: minor Milestone: sage-5.11
Component: misc Keywords:
Cc: Merged in: sage-5.11.beta1
Authors: Rudi Pendavingh, Stefan van Zwam Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by 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

Attachments (1)

trac_14668_bitsets.patch (45.2 KB) - added by Stefan 8 years ago.
Bitset enhancements

Download all attachments as: .zip

Change History (16)

comment:1 Changed 8 years ago by Stefan

  • Dependencies 7477 deleted
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by Stefan

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.

comment:3 Changed 8 years ago by Stefan

  • Authors set to Rudi Pendavingh, Stefan van Zwam

comment:4 Changed 8 years ago by ncohen

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

Last edited 8 years ago by ncohen (previous) (diff)

Changed 8 years ago by Stefan

Bitset enhancements

comment:5 follow-up: Changed 8 years ago by Stefan

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

comment:6 in reply to: ↑ 5 Changed 8 years ago by ncohen

  • bitset_morph is now called bitset_map with hopefully better docstring

Oh right ! Good choice :-)

Nathann

comment:7 Changed 8 years ago by dcoudert

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.

comment:8 Changed 8 years ago by jason

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.

comment:10 follow-up: Changed 8 years ago by Stefan

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.

Last edited 8 years ago by Stefan (previous) (diff)

comment:11 Changed 8 years ago by dcoudert

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

comment:12 in reply to: ↑ 10 Changed 8 years ago by rbeezer

Replying to 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.

comment:13 follow-up: Changed 8 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to positive_review

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

comment:14 in reply to: ↑ 13 Changed 8 years ago by rbeezer

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. ;-)

comment:15 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.11.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.