realloc() error for test_make_undirected on Python 3.6

Thanks for the report.

I'm not sure how 6d6be7b1 could have introduced this bug, but in any case we should probably remove all C-level memory allocations from kwant.graph, following the reorganisation of kwant.graph.CGraph in 6d6be7b1.

The stated reasoning for use of C-level memory allocation (in comments at the start of graph/core.pyx) are:

There are no efficient arrays that allow appending
Cython extensions cannot have typed buffers as members

It seems that the answer to (1) was to use realloc, however I can't see how this is any better than using array.resize on an array.array. As for (2), we can just store an array.array, the same way as we now do for the CGraph.

Hi, it looks to me that edges is no longer initialized to 0. No idea why. @slavoutich, can you try this:

diff --git a/kwant/graph/core.pyx b/kwant/graph/core.pyx
index 1f9c15f..607f5ad 100644
--- a/kwant/graph/core.pyx
+++ b/kwant/graph/core.pyx
@@ -41,6 +41,7 @@ cdef class Graph:
 
     def __init__(self, allow_negative_nodes=False):
         self.allow_negative_nodes = allow_negative_nodes
+        print("hola", <unsigned long int>self.edges)
 
     def __dealloc__(self):
         free(self.edges)

And then run

./setup.py test -a -s

For me, with Python 3.5, this prints only zeros.

If my guess is true, this bug can be fixed by

diff --git a/kwant/graph/core.pyx b/kwant/graph/core.pyx
index 1f9c15f..9de139a 100644
--- a/kwant/graph/core.pyx
+++ b/kwant/graph/core.pyx
@@ -41,6 +41,7 @@ cdef class Graph:
 
     def __init__(self, allow_negative_nodes=False):
         self.allow_negative_nodes = allow_negative_nodes
+        self.edges = NULL
 
     def __dealloc__(self):
         free(self.edges)

@jbweston, what array.resize do you refer to? The stdlib array module doesn’t seem to have such an operation. I don’t mind if the graph module gets modernized, but given that it is time-tested and we do not exactly know yet by what we will eventually replace it, I’m for concentrating our efforts on other parts of Kwant.

@jbweston, another thing: I noticed that ./setup.py test -a -s outputs a lot of zeros from the operator tests. Is this on purpose, or you just forgot to remove the call to print?

you just forgot to remove the call to print?

Yes it's this -- I'll push a fix

what array.resize do you refer to?

This is some Cython-level interface to array: from cpython cimport array. In any case, if self.edges = Null fixes this then we can just do that

@cwg I have tried, I also have zeros, and then it fails.

test_with_hola.log

Correspondingly, proposed patch does nothing.

test_with_fix0.log

Hi, can you try this?

diff --git a/kwant/graph/core.pyx b/kwant/graph/core.pyx
index 1f9c15f..7b3afdd 100644
--- a/kwant/graph/core.pyx
+++ b/kwant/graph/core.pyx
@@ -43,6 +43,7 @@ cdef class Graph:
         self.allow_negative_nodes = allow_negative_nodes
 
     def __dealloc__(self):
+        print("freeing", <unsigned long int>self.edges)
         free(self.edges)
 
     property num_nodes:
@@ -69,7 +70,11 @@ cdef class Graph:
         """
         if capacity <= self.capacity:
             return
-        self.edges = <Edge*>realloc(self.edges, capacity * sizeof(Edge))
+        nbytes = capacity * sizeof(Edge)
+        print("reallocing", <unsigned long int>self.edges, nbytes, "bytes",
+              end=" -> ")
+        self.edges = <Edge*>realloc(self.edges, nbytes)
+        print("new pointer:", <unsigned long int>self.edges)
         if not self.edges:
             raise MemoryError
         self.capacity = capacity

Here it works correctly, one gets output like:

.reallocing 0 64 bytes -> new pointer: 94119872580944
reallocing 94119872580944 128 bytes -> new pointer: 94119863826336
reallocing 94119863826336 256 bytes -> new pointer: 94119873092448
reallocing 94119873092448 512 bytes -> new pointer: 94119870475184
reallocing 94119870475184 1024 bytes -> new pointer: 94119873093008
reallocing 94119873093008 2048 bytes -> new pointer: 94119859404160
reallocing 94119859404160 4096 bytes -> new pointer: 94119867972352
reallocing 94119867972352 8192 bytes -> new pointer: 94119869917520
freeing 94119869917520

Here's the output.

test1.log

This is a realloc that causes a problem.

https://gitlab.kwant-project.org/kwant/kwant/blob/1fbcace81264ad7f04550accf8fe5c8d23701a56/kwant/graph/utils.pyx#L178

Commenting it out allows tests to run smoothly. I suppose it can occasionally appear to be statically allocated array, not dynamically. @cwg, can you check with more experienced eye?

Proposed patch:

diff --git a/kwant/graph/utils.pyx b/kwant/graph/utils.pyx
index 1ecb143..c61da5f 100644
--- a/kwant/graph/utils.pyx
+++ b/kwant/graph/utils.pyx
@@ -16,6 +16,8 @@ cimport numpy as np
 from libc.stdlib cimport malloc, realloc, free
 from libc.string cimport memset
 cimport cython
+from cpython cimport array
+import array
 from .defs cimport gint
 from .defs import gint_dtype
 from .core cimport CGraph, CGraph_malloc
@@ -176,7 +178,8 @@ def remove_duplicates(CGraph gr, np.ndarray[gint, ndim=1] edge_weights=None):
     gr.num_edges = nnz
 
     # Release memory that is not needed any more.
-    gr.heads = <gint *>realloc(gr.heads, nnz * sizeof(gint))
+    array.resize(gr._heads, nnz * sizeof(gint))
+    gr.heads = <gint *>gr._heads.data.as_ints
     if not gr.heads:
         raise MemoryError

Hah, looks good. Are there any other realloc's that we should replace with array.resize?

OK, I see now, I missed the other realloc() in utils.pyx. So this is indeed a bug, introduced by Anton’s commit that uses array.array: there is no guarantee that array.array buffers can be realloced, and if they are, one would have to update the pointer as well.

@slavoutich, your fix looks good, except that nnz should not be multipied by the size of an integer. The argument to resize is the new size of the array in items, not in bytes.

@anton-akhmerov, I don’t see anything else that should be fixed. BTW, since when do you have a dash in your gitlab user name?

Another thing: realloc no longer needs to be imported in utils.pyx

@slavoutich care to make an MR?

mentioned in merge request !67 (closed)

closed via commit c7252f6e

mentioned in commit slavoutich/kwant@c7252f6e

realloc() error for test_make_undirected on Python 3.6

Child items ...

Activity