How to deal with the potential “wild pointer" when using the exposed vector?

[Yikai-Liao]

The problem is simple. When we free a vector (e.g., by replacing it with another vector), python objects that refer to elements in that vector become "wild pointers".

I verified my suspicions with the following code. I'd like to know if there's a way to avoid this problem, or at the very least get a warning when I access invalid python objects, because accessing these "wild pointers" has a probability of giving the program a segmentation fault.

Here is the minimal code:

#include <nanobind/nanobind.h>
#include <nanobind/stl/string.h>
#include <nanobind/stl/vector.h>
#include <nanobind/stl/bind_vector.h>
#include <vector>
#include <string>
namespace nb = nanobind;

struct Bar {
    int data;
    explicit Bar (const int data) : data(data) {}
};

struct Foo {
    std::vector<Bar> bars;
    explicit Foo(std::vector<Bar> bars) : bars(std::move(bars)) {}
};



NB_MAKE_OPAQUE(std::vector<Bar>);

NB_MODULE(nanobind_example_ext, m) {
    nb::class_<Bar>(m, "Bar")
        .def(nb::init<int>())
        .def_rw("data", &Bar::data)
        .def("__repr__", [](const Bar& self) { return "Bar(" + std::to_string(self.data) + ")"; });

    nb::bind_vector<std::vector<Bar>>(m, "BarList");

    nb::class_<Foo>(m, "Foo")
        .def(nb::init<std::vector<Bar>>())
        .def_rw("bars", &Foo::bars)
        .def("__repr__", [](const Foo& self) { return "Foo(" + std::to_string(self.bars.size()) + " bars)"; });
}

# in ipython
from nanobind_example.nanobind_example_ext import Foo, Bar, BarList
f = Foo(BarList([Bar(i) for i in range(10000)]))
b = f.bars[-1]
print(b, id(b)


%%timeit
f.bars = BarList(Bar(0) for _ in range(10000))


print(b, id(b)

[wjakob]

Hi @Yikai-Liao,

thank you for report. This was a very bad issue, I almost cannot believe you are the first one to mention it. (I personally don't use the bind_vector/map API and added it just for completeness).

The following commit fixes the implementation to avoid dangling pointers, which does come with a slight decrease of convenience though. (Cannot get an element and then mutate it to affect the vector itself unless a shared ownership model is used.)

f91100b

[Yikai-Liao]

I'm not sure will this commit fix all the problems. I find that even append could cause such problems.

For vectors, if you reached the capacity when pushing back new element, vector would automatically copy all the data into a new block of memory. And this would make all the previous objects in python that pointing to the elements in that vector invalid.

from nanobind_example.nanobind_example_ext import Foo, Bar, BarList

l = BarList([Bar(0)])
b = l[0]
print("old:", b, id(b))
l.append(Bar(1))
new_b = l[0]
print("new:"， new_b, id(new_b))
print("old:", b, id(b))

This can also be observed in pybind11.

I think there are a couple of possible solutions：

1. always copy when modifying the data position, like numpy.append
2. use std::vector<std::shared_ptr<T>> instead of std::vector<T>, i.e. keeping its memory structure similar to a python list and tolerating memory and performance overheads
3. disable saving references to elements in a vector in python (seems impossible)

In fact, we can't demand that a vector with contiguous memory be identical to the interface semantics of a python list.

However, users of these python binding libraries will always expect the interface semantics of vector binding to be identical to python lists, with higher performance

[wjakob]

Dear @Yikai-Liao,

with commit f91100b applied, I get the following output when running a variant of your example:

from test_bind_vector_ext import Foo, Bar, BarList

l = BarList([Bar(123)])
b = l[0]
print("old:", b, id(b))
l.append(Bar(456))
new_b = l[0]
print("new:", new_b, id(new_b))
new_b.data = 1000
print("new:", new_b, id(new_b))
print("old:", b, id(b))
print("cur:", l[0])

old: Bar(123) 4378668656
new: Bar(123) 4378663664
new: Bar(1000) 4378663664
old: Bar(123) 4378668656
cur: Bar(123)

I don't see any obvious problem with this. Because BarList.__getitem__ now copies the referenced element, it is undisturbed by the later call to .append(). In particular, it is safe to continue using the "old" b (which was not the case prior to f91100b). The downside is that changes to b never propagate back to l[0] unless a shared ownership model is used. You are correct that this isn't a good match for the semantics of the builtin list.

[wjakob]

It is quite possible that the pybind11 version is buggy as well. My priority for now is to ensure that we have a working strategy for nanobind, and that can then be communicated back to the pybind11 team.

[Yikai-Liao]

I got it. You choose a similar implementation to pyo3, which always copies the element in a vector. This could lead to more than a convenience issue.

For example, if we are binding an existing lib, we need intrusive modifications (add lots of shared_ptr) to make it possible to modify the element in a vector directly in python, like this:

# with out shared ptr
# Need to modify data in a very unnatural way
l = BarList([xxx])
b = l[0]
b.xxx = xxx # modify b
l[0] = b

# with shared ptr
# Natural but requires intrusive modification of raw data
l[0].xxx = xxx

On the other hand, for library only serves as a back-end of a python package, we need to consider two kinds of situations for efficiency.

• a vector of large objects (much larger than the memory overheads introduced by shared_ptr)
• a vector of small objects (just a few bytes, and locality can drastically affect performance in this case)

For the first case, we can use std::vector<shared_ptr>, without introducing much overheads.

But for second one, I think we may need a new data container to optimize the performance. I now have a basic idea that I'm going to apply to my own library.

template<typename T>
class SharedVec {
    std::shared_ptr<std::vector<std::vector<T>>> resources;
    std::vector<T*> ptrs;
}

we could just store the real data in the resources (the memory would be managed by a shared_ptr of 2d vectors), and store a series of raw pointers in the ptrs. And we can get the shared ptr for each element (std::shared_ptr<T>(resources, ptrs[i]))

Then, it will just perform like a python list. No matter how we insert or remove elements, the location of the data would stay unchanged.
Every time we need space for new data, we could create a new vector with certain capacity. Every time we insert or remove some elements, we are just editing the ptrs, and other references would keep valid. Even if the SharedVec is freed, the resources will wait for the python objects.

Moreover, SharedVec introduces only a pointer-sized memory overhead for each element, which is much smaller than shared ptr and does not create memory fragmentation problems.

Better yet, in the case of no frequent insertions and deletions, SharedVec maintains good locality for high access efficiency.

This data structure is basically good enough for my use, but I'm not sure it's suitable for a more general purpose container.