#17647: Branch and Bound for vertex separation
-------------------------+-------------------------------------------------
Reporter: | Owner:
dcoudert | Status: needs_review
Type: | Milestone: sage-6.5
enhancement | Resolution:
Priority: major | Merged in:
Component: graph | Reviewers:
theory | Work issues:
Keywords: | Commit:
Authors: David | 0504e8f1946309d9784c4837275c919b047f9829
Coudert | Stopgaps:
Report Upstream: N/A |
Branch: |
public/17647 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by ncohen):
> should be something like that
> {{{
> cdef bitset_t * bitset_pool = <bitset_t *>sage_malloc(5 * n *
sizeof(bitset_t))
> for i from 0 <= i < 5*n:
> bitset_init(bitset_pool[i], n)
> ...
> ...
> for i from 0 <= i < 5*n:
> bitset_free(bitset_pool[i])
> sage_free(bitset_pool)
> }}}
In a design like that there is a problem if some `bitset_init` fails. But
well. Yeah, then it would probably be cleaner anyway. Good idea.
> {{{
> # The intersection of the common neighbors of i and j is a
AND of
> # their respective rows. A popcount then returns its
cardinality.
> inter = 0
> for l in range(m.width):
> inter += __builtin_popcountl(m.rows[i][l] &
m.rows[j][l])
> }}}
>
> Seriously, it would be much cleaner to use bitsets for rows and to call
{{{bitset_len}}}.
With bitsets you cannot do this very computation without allocating a
third bitset.
Okay, let's say that it is not important: could you turn/extend your
`fast_digraph` into a bitset matrix ? You can overwrite the current one if
you like, nobody but me uses it anyway. This way it would work with
bitsets, and you could allocate this matrix of bitsets in one instruction
without having to handle the memory allocation problems in your branch and
bound code.
> As I said previously, my suggestion is more to change the
{{{static_dense_graph}}} data_structure to use directly {{{bitset_t}}} for
rows.
We agree if you actually talk of changing the 'binary_matrix' type, which
is then used by the static dense graph stuff.
> > Run a long command, then type 'perf top' in a console. You'll love it.
>
> Don't have it on OSX :(
`O_o`
Try it on a real machine. That will give you a reason to install some real
OS `:-P`
> According some discussions on the mailing lists, we have some profiling
experts that could be of more help than me. I can have a look anyway to
tell if it is dummy's level ;)
The problem with 'profiling experts' is that they don't review those
patches, and if nobody does it everybody loses.
Nathann
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
