Changes between Version 2 and Version 6 of Ticket #31117


Ignore:
Timestamp:
Dec 28, 2020, 1:38:01 AM (2 years ago)
Author:
David Coudert
Comment:

I had to remove last commit because method next_out_neighbor_unsafe is not implemented in static_sparse_backend.pyx, and I don't know yet how to add such method to this backend.

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #31117

    • Property Commit changed from a19e27645d4c621f223a93245347a2472ee21a56 to e56743ba1d0274bfca69e91a01cbaad6af8973ba

  • Ticket #31117 – Description

    v2 v6  
    5959}}}
    6060
    61 Another improvement is to avoid using `in_neighbors` and `out_neighbors` since these methods return lists of vertices and behind we have some mallocs of arrays. So a lot of operations that could be avoided. We get significant speed up even on small graphs.
    62 {{{
    63 sage: comp()                                                                                                                                       
    64 2D Grid Graph for [5, 5]
    65 9.93 µs ± 350 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
    66 57.3 µs ± 1.62 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    67 2D Grid Graph for [10, 10]
    68 31.3 µs ± 1.67 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    69 230 µs ± 11.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
    70 2D Grid Graph for [50, 50]
    71 881 µs ± 22.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
    72 7.26 ms ± 269 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    73 2D Grid Graph for [100, 100]
    74 3.84 ms ± 203 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    75 31.3 ms ± 1.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
    76 2D Grid Graph for [500, 500]
    77 120 ms ± 2.65 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
    78 1.05 s ± 25.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    79 2D Grid Graph for [1000, 1000]
    80 644 ms ± 18.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    81 5.26 s ± 279 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    82 }}}
     61Another improvement is to avoid using `in_neighbors` and `out_neighbors` since these methods return lists of vertices and behind we have some mallocs of arrays. So a lot of operations that could be avoided.