#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 dcoudert):
> > > I am not done with the review, but I worry a bit about the fact that
you allocate memory in a recursive function. They can cost a lot, these
things. Do you see a clean way to avoid that ?
> > I already though about it and I don't have a "clean" method to
propose. I could for instance allocate one for all 5 arrays of n bitsets
each and access to the bitsets of level *level* since the BAB has depth at
most n. This way we avoid multiple allocations.
> > If you think it is OK, I can implement it.
>
> Using bitsets that would mean dozens of allocations lines again.
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)
}}}
> What is it that you use in those fast digraphs of yours that are not in
the 'binary matrix' type ? Possibly the best is to implement it there and
use the binary matrices?
I'm using extensively {{{bitset_union, bitset_difference, bitset_discard,
bitset_add, bitset_len, bitset_first}}}.
What you propose is to recode what has already been properly implemented
for bitsets into the binary matrix type. For instance, in module
{{{static_dense_graph.pyx}}}, we have code like that:
{{{
# 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}}}.
As I said previously, my suggestion is more to change the
{{{static_dense_graph}}} data_structure to use directly {{{bitset_t}}} for
rows.
> > What's the magic commande to profile this code? %prun is not working
here.
>
> Run a long command, then type 'perf top' in a console. You'll love it.
Don't have it on OSX :(
> > The speed of the {{{bitset_len}}} method depends on the system. Since
patch #13352, we use the mpn methods for popcount which is expected to use
{{{__builtin_popcount}}}. I don't know how fast it is on my laptop. I'll
check as soon as you give me the magic command ;)
>
> I will probably write a "profiling tutorial" soon. It would be cool if
you were willing to review it. That will be helpful, along with the
"interface C code with Sage" tutorial.
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 ;)
David.
--
Ticket URL: <http://trac.sagemath.org/ticket/17647#comment:14>
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.
