Changes between Version 4 and Version 8 of Ticket #13352
 Timestamp:
 08/18/13 15:08:25 (8 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

Ticket #13352
 Property Cc ncohen added

Property
Milestone
changed from
sage5.11
tosage5.12

Ticket #13352 – Description
v4 v8 1 This patch improves the running time of the {{{bitset_len}}} method by using fast methods for counting bits in 32 and 64 bits integers (popcount). It 2  adds file {{{bitcount.pxi}}} to {{{sage/misc/}}}. This file contains the functions for counting bits in 32 or 64 bits integers 3  adds corresponding tests to file {{{misc_c.pyx}}} 4  modifies the {{{bitset_len}}} function accordingly 1 This patch improves the running time of the {{{bitset_len}}} method by using {{{__builtin_popcount()}}}. 5 2 6 3 Before: 7 4 {{{ 8 sage: x = FrozenBitset('10'*1003002); len(x) 9 1003002 10 sage: %timeit len(x) 11 125 loops, best of 3: 5.27 ms per loop 12 sage: x = FrozenBitset('10'*10705); len(x) 13 10705 14 sage: %timeit len(x) 15 625 loops, best of 3: 56.3 µs per loop 5 sage: B = Bitset('10'*10000) 6 sage: len(B) 7 10000 8 sage: %timeit len(B) 9 1000 loops, best of 3: 245 us per loop 16 10 }}} 17 11 18 12 After: 19 13 {{{ 20 sage: x = FrozenBitset('10'*1003002); len(x) 21 1003002 22 sage: %timeit len(x) 23 625 loops, best of 3: 865 µs per loop 24 sage: x = FrozenBitset('10'*10705); len(x) 25 10705 26 sage: %timeit len(x) 27 625 loops, best of 3: 9.39 µs per loop 14 sage: B = Bitset('10'*10000) 15 sage: len(B) 16 10000 17 sage: %timeit len(B) 18 100000 loops, best of 3: 2.52 us per loop 28 19 }}} 29 30 The ``popcount_32`` method is the same than the function used in patch #12371.31 32 The alternative would be to use functions {{{__builtin_popcount()}}} and {{{__builtin_popcountll()}}}. They are extremely fast but they required to add flag ``mpopcnt`` or ``msse4.2`` to the gcc compiler. Can we do that? how?33 20 34 21 35 22 APPLY: 36 23 37 * [attachment:trac_13352_bitset_len .patch]24 * [attachment:trac_13352_bitset_len_v2.patch] 38 25