Iterators efficiency and instance tracking

[aldanor]

In the current implementation, the iterator implementation turns out to be very inefficient at times (to the point where it adds overhead that is order of magnitude bigger than the iterator logic itself).

Iterators with internal reference

Consider a hypothetical example (this would be quite typical for stream-like / input ranges):

struct point { int x; int y; };

struct range {
    int n;
    range(int n) : n(n) {}

    struct iterator {
        int i = 0;
        point p {};
        iterator() = default;
        iterator(int n) : i(n), p{n, n} {}
        const point& operator*() const { return p; }
        iterator& operator++() { --i; p.x = i; p.y = i; return *this; }
        bool operator==(const iterator& it) const { return i == it.i; }
    };

    iterator begin() { return {n}; }
    iterator end() { return {}; }
};

Assuming point has a corresponding py::class_ binding, wrapping this range in a py::make_iterator() with default return value policy of reference_internal and iterating over it in Python will do roughly the following for each iteration step:

• advance C++ iterator, check if iteration is over, dereference the C++ iterator
• do the cast to Python point instance:
  • do a runtime check in the map of registered types to get type_info (why isn't this cached per each py::cpp_function?)
  • do a runtime check in the multimap of registered instances to find the instance
  • the instance will always be found
  • incref it and return

Note that this will essentially yield the same Python object on every iteration, but it will still perform two map lookups every time.

In this example, this could be completely avoided if py::iterator_state cached the resulting py::object (whose ->value always points to the same C++ instance in this example, so it doesn't even need to be reallocated) and not just the current state of begin/end iterators. Instead of doing the cast, it could just incref the object and return the handle.

No internal reference or copy r/v policy

If the C++ iterator returns an object with a different address on each dereference, or if we specify the copy return value policy, things get even worse.

The sequence of steps is now:

• advance C++ iterator, check if iteration is over, dereference the C++ iterator
• do the cast to Python point instance:
  • do a runtime check in the map of registered types to get type_info
  • do a runtime check in the multimap of registered instances to find the instance
  • the instance will never be found
  • allocate new Python instance
  • (if copy r/v policy is specified) call C++ object's copy constructor
  • bind the Python instance to the C++ object
  • record the new instance in the registered instances multimap
  • (at some point in future) remove instance from registered multimap

If the downstream Python code doesn't care about yielded values outside of one iteration
cycle and doesn't pass them as arguments to other functions, which is quite often the case,
i.e. if it's something like this:

sum(p.x * p.x + p.y * p.y for p in points_iterable)

or this:

for p in points_iterable:
    # do some computation, don't save p or pass it as argument anywhere

then registering/unregistering instances adds overhead that is completely unneeded. Plus, between the garbage collection cycles, the registered instances multimap will grow quite fast here which will slow things down even further. Here, the sequence of steps might as well just be:

• advance and derefence C++ iterator
• allocate new Python instance
• bind the C++ object to it

Would it make sense to have a return value policy copy_untracked (cast doesn't do registered instance lookup; dealloc calls dtor and doesn't try to unregister)? Or reference_untracked (cast doesn't do registered instance lookup; dealloc doesn't call dtor and doesn't try to unregister) or something like that? The only catch here is that some sort of flag must be stored in the instance itself, so that the deallocator knows not to try and erase it from registered instances multimap when the time comes.

[wjakob]

Hi Ivan,

I agree that there is a lot of fluff. I'm curious if you've faced performance issues due to this?
One minor correction to the first case above: even when copy is used, the object won't be copied if the address matches an existing object.

I'm not sure how the type_info could be cached in a clean way without messing up the separation between type casters and the rest of the codebase. In any case, I suspect that the C++ hashtable lookup is very fast (much faster than a Python dict lookup).

The untracked policies you suggest sound potentially dangerous (though maybe I'm just missing something). Python is free to do whatever it wants with the resulting instances (e.g. stick them into some data structure that persists). How can you ensure correct lifetime management while avoiding leaks in this case?

[aldanor]

@wjakob Yes, the only reason I raised this is because of serious performance issues. I have a C++ codebase that parses some network files and streams parsed data structures (order of tens of millions), with average time spent per packet being around 200ns. When wrapping it in a make_iterator (with the default reference_internal), the performance drops to around 550-600ns, when setting the rvp to copy it drops further to 750-800. All of this time is pybind11 overhead which in this case seems absolutely redundant.

I did a bit of profiling, here's an example of top offenders (this is compiled with something like -O2 -pg):

(pprof) top40
Total: 48298 samples
    2815   5.8%   5.8%     2820   5.8% _int_malloc malloc.c:0
    2480   5.1%  11.0%     2480   5.1% std::_Hash_bytes ??:0
    2301   4.8%  15.7%     6467  13.4% std::_Hashtable::find :0
    1750   3.6%  19.4%     1753   3.6% _int_free malloc.c:0
    1549   3.2%  22.6%     1549   3.2% std::_Hashtable::_M_find_before_node [clone .isra.1086] [clone .lto_priv.2808] :0
    1499   3.1%  25.7%     2519   5.2% std::_Hashtable::equal_range :0
    1408   2.9%  28.6%     2115   4.4% _mcount ??:0
    1369   2.8%  31.4%     2131   4.4% std::vector::vector :0
    1215   2.5%  33.9%     1806   3.7% std::_Hashtable::_M_insert_multi_node :0
    1119   2.3%  36.2%     3939   8.2% __GI___libc_malloc :0
    1054   2.2%  38.4%     1054   2.2% std::_Hashtable::_M_find_before_node [clone .isra.1321] [clone .lto_priv.1320] :0
    1020   2.1%  40.5%     1020   2.1% __memcpy_sse2 :0
    1002   2.1%  42.6%    10985  22.7% StreamAdaptor::adaptor::fetch :0  # <-- C++ iterator "next()"
     899   1.9%  44.5%     1322   2.7% std::_Hashtable::erase :0
     829   1.7%  46.2%    33459  69.3% pybind11::cpp_function::initialize::{lambda#3}::operator [clone .constprop.848] :0
     798   1.7%  47.8%     3763   7.8% cache_next_packet [clone .constprop.1239] :0  # C++ iterator
     792   1.6%  49.5%     2804   5.8% __GI__IO_fread :0

So, out of the top 50% of cumulative time roughly 25% (half) is spent directly in hash maps, but actually it's more than that since a lot of mallocs, frees and memcpys are triggered by hash maps as well.

Hash tables are fast, but not that fast... Multi maps are even worse.

[aldanor]

Re: the untracked data structures, we still attach a deallocator to them though (with the difference being that it wouldn't try to erase from the hash map)? Could you provide a hypothetical example of a leak you were talking about, so we're on the same page?

[aldanor]

Re: caching type_info, wouldn't it be natural for cpp_function to cache it somehow? It knows its own return type, and the types cannot be unregistered => this implies that on the second call (or later), the type_info must already exist, and it may as well be cached for future reuse? It seems a bit wasteful for functions that are executed millions of times to do the same hashmap lookup every time

[jagerman]

Here's a branch with (experimental) return type caching implementation: it passes all the tests, and is indeed being used as intended (it avoids the hash table type lookup for 62/140 return values in the test suite). See how it affects your profiling results; if it looks promising, I'll submit as a PR.

branch / commit

It caches it in function_record rather than cpp_function, and has to do a little intermediate templated class trickery to be able to pass through the cache variable only where we want it (i.e. generic types) without needing to add a cache variable to all type_casters.

[aldanor]

@jagerman Thanks.

I did a bit of testing with a trivial struct with a single int field:

• running c++ loop creating and instance and calling the copy constructor on each iteration
• calling pybind11 (master branch) function that returns a new instance with rvp::copy
• the same as above with @jagerman's branch
• running python loop with same number of elements doing nothing (to exclude pure Python overhead)

This is gcc5, -O3 -DNDEBUG, Python 3.5, Linux, E5 2687W, times per iteration:

C++	28ns
python empty loop	89ns
master	342ns
return-type-caching	324ns

=> pybind11 overhead goes from 225ns to 207ns which is approx 8%.

So the proposed commit seems to work as intended (albeit it's slightly clunky that cast now has a fourth parameter which is an optional double pointer, but I guess there's not many options on how to pass a mutable cache...).

Should we also have copy_untracked? :)

[wjakob]

This speedup seems very small compared to the profiler output mentioned earlier. How come?

[jagerman]

Because return value type lookup is the relatively smaller overhead here. Much of the rest of the hashing cost is in the instance lookup, which, for cast, typically requires two hashes for new instances: one to determine whether the instance is known, and when it isn't, another hash when inserting it.

[jagerman]

Also, just for the record, unordered_multimap vs unordered_map isn't incurring any noticeable difference here: you can switch the definition in common.h (no other code changes needed) and see that timings stay essentially unchanged—it breaks tests, of course, but it shouldn't break your example iterator code. (multimap only gets slower when you have a lot of equal key values, which is unlikely to be the case in pybind11—we only get that when one pybind-registered type is the first member of another pybind-registered type.).

[aldanor]

Yea, there's the instance tracking which takes time. Plus this a very simplified example (I'll have to try and rebuild the code I have with these changes to see how it affects real-world large codebase - but may not be able to do so until Monday).

Here's a simple benchmark ("untracked" code can be commented out, it's my local change; adds "tracked" flag to instance wrapper, skips registering on cast and unregistering on dealloc):

// test_cast.cpp
#include <pybind11/pybind11.h>

struct Foo { int v; Foo(int i) : v(i) {} };

PYBIND11_PLUGIN(test_cast) {
    namespace py = pybind11;
    py::module m("test_cast");
    py::class_<Foo>(m, "Foo");
    m.def("mk_copy", [](int  i) -> Foo { return {i}; },
          py::return_value_policy::copy);
    m.def("mk_untracked", [](int  i) -> Foo { return {i}; },
          py::return_value_policy::copy_untracked);
    m.def("ref", [](int N) {
        for (int i = 0; i < N; i++) {
            Foo f(i); auto f2 = new Foo(f); volatile int y = f2->v; delete f2;
        }
    });
    return m.ptr();
}

from time import time
from test_cast import mk_copy, mk_untracked, ref


def bench(msg, iterable, norm=1):
    n = 0
    t0 = time()
    for _ in iterable:
        n += 1
    t1 = time()
    n *= norm
    print('{:<15s} calls: {:<10d} elapsed: {:.3f}s       ns/call: {:.1f}ns'
          .format(msg + ':', n, t1 - t0, 1e9 * (t1 - t0) / n))


N = 10 * 1000 * 1000

# object is created and copied in a C++ loop
bench('C++', (ref(x) for x in [N]), N)

# empty Python loop that allocates an object and does nothing else
bench('Python', (object() for i in range(N)))

# return_value_policy::copy_untracked
bench('mk_untracked', (mk_untracked(i) for i in range(N)))

# return_value_policy::copy
bench('mk_copy', (mk_copy(i) for i in range(N)))

Using @jagerman's branch:

C++:            calls: 10000000   elapsed: 0.279s       ns/call: 27.9ns
Python:         calls: 10000000   elapsed: 1.587s       ns/call: 158.7ns
mk_untracked:   calls: 10000000   elapsed: 2.573s       ns/call: 257.3ns
mk_copy:        calls: 10000000   elapsed: 3.298s       ns/call: 329.8ns

On master:

mk_copy:        calls: 10000000   elapsed: 3.496s       ns/call: 349.6ns

[jagerman]

@aldanor Re: copy_untracked, how much of an overhead reduction does it give? It ought to be relatively easy to implement (even easier if you just change copy behaviour for testing): skip the instances look-up and emplace in type_caster_generic::cast in cast.h, and delete the if (!found) pybind11_fail(...) from generic_type::dealloc() in pybind11.h. (You might also want to add a bool unregistered to the instance struct so that you can avoid the look-up in dealloc entirely for unregistered types.)

[jagerman]

Okay, there's my answer :)

[aldanor]

@jagerman Yes that exactly what I did :)

[wjakob]

It would be interesting to see a profiler dump for the mk_untracked version in case that is easy to make.

[jagerman]

Something else to think about: would it make more sense applying this do-no-track attribute to the type, rather than the return value? Otherwise I could get into weird behaviour with something like:

p = best(p1, p2)

where best is some sort of max-like function that returns a reference to the better instance. Suppose it returns a reference to p1. I'm going to get different behaviour depending on whether p1 came from a tracked or untracked return value. If p1 was tracked, I'll get p is p1. If untracked, what happens? I think I would get two variables that Python thinks are different, but that are bound to the same C++ instance; is this going to work properly?

If, on the other hand, the don't-track-me is a class property, I'll always get consistent behaviour: every function that returns a Foo (in your example) will be returning untracked copies. (In the best call above, I'd always get a p copied from p1 and p2, regardless of where p1 or p2 came from).