we do test readonly arrays, the question is whether they survive all conversions to that point (probably they get copied somewhere).
The tests are not a good benchmark, I think you need to run actual benchmarks on larger datasets both using big and small trees and do full profiling to see if this makes it slower.

It seems at least according to the benchmarks/bench_tree.py, such changes make it faster, and not just by a tiny bit.

Results from the master on my machine:

Results from this branch on my machine:

well that's interesting. Should also be interesting to @NicolasHug

how stable are these curves though, can we get bars? ;)

I know I'm doing something wrong here, but really don't know what. I get this very odd looking cython compile error:

Memoryview 'DOUBLE_t[:, :]' not conformable to memoryview 'DOUBLE_t[:, :]'.

Been trying to figure it out, but any help would be appreciated.

don't ask me why but I think that

from _tree cimport DOUBLE_t

in both splitter and criterion will fix it (also remove ctypedef np.npy_float64 DOUBLE_t).

Very weird that the other dtypes aren't causing the same thing.

Looks similar to this where the fix is similar

don't ask me why but I think that

from _tree cimport DOUBLE_t

in both splitter and criterion will fix it (also remove ctypedef np.npy_float64 DOUBLE_t).

Very weird that the other dtypes aren't causing the same thing.

Looks similar to this where the fix is similar

Ooh, that makes a lot of sense. I wish cython would print the complete type, like, _tree.DOUBLE_t vs. _criterion.DOUBLE_t instead or something. Thanks.

But does it make sense to you that only DOUBLE_t is causing this, and not e.g. DTYPE_t?

It looks like a Cython bug to me.

But does it make sense to you that only DOUBLE_t is causing this, and not e.g. DTYPE_t?

It looks like a Cython bug to me.

I think the difference may be that DOUBLE_t is the only one used in the context of a memoryview while passing between modules. I'd agree that it's a bug or at least an inconsistency that it has stricter type checking for a_t [:] x than a_t* x though. But please read all of that with the hint of "adrin is still learning cython" :D.

Sorry, got confused. Not sure that @NicolasHug is the one most in need of being happy. Rather, if you are happy that this does not make life more difficult with your other work on trees, I'm happy for it.

It sure doesn't make my life harder at least ^^
Like Adrin I'm still learning those Cython features, so I can't give an informed review for this. I'm mostly interested on how thing can be done to get some inspiration for #12807

I made some more reliable benchmarks with error bars (10 repeats each) using the benchmarks/bench_tree.py, under 3 different conditions. In the following plots:

• master: the master
• only_x: uses memoryviews for X in _tree.* and _splitter.*
• criterion_y: also uses memoryviews for y in _criterion.*

Charts for increasing number of rows:
Classifier:

Regressor:

Increasing number of columns:
Classifier:

Regressor:

I guess the conclusion from these charts is that when we use memory views for X, there's little or no overhead. But there's some overhead when we try to apply that for y in criterion. Here are a few points about that:

In the case of using memory views for X, we only do a type cast/conversion when we want to use it, and the memory view is not passed around in functions. This can be done since in all those cases we operate under gil and we can do python stuff.

All the _criterion.* code is under nogil, which means we can't do that type cast. As a result y needs to be passed around as a memory view struct. Now the issue is that the memoryview struct is a rather large one, i.e. the generated C code:

typedef struct {
  struct __pyx_memoryview_obj *memview;
  char *data;
  Py_ssize_t shape[8];
  Py_ssize_t strides[8];
  Py_ssize_t suboffsets[8];
} __Pyx_memviewslice;

And this struct is what's passed around, and not a pointer to it. I couldn't find a way to pass around pointers and then do a cast while keeping gil, and I suspect this is the reason behind the overhead for this case.

WDYT?

What are the units of the axis? You don't just use 10 samples / rows right?

Have you tried removing some of the unnecessary casts in criterion.pyx? For example

    cdef int update(self, SIZE_t new_pos) nogil except -1:
        ...
        cdef DOUBLE_t[:, :] y = self.y
        ...

is probably not needed since self.y has been declared as a memory view already.

I assume looking at the annotated generated code (cython -a) doesn't help since it's all no-gil / no-python interaction code ?

In any case I don't think the overhead of passing the memview struct is causing the slowdown, because this struct is only passed once when building the criterion object right? It's not passed into tons of function calls. Also, I would assume the same overhead occurs for the X view: Cython still has to allocate the memview struct for X, on the heap instead of on the stack.

Like I said above I'm not experienced with advanced Cython so... don't take all this for granted ;)

Another lead might be that the previous code for y knew that y was C-aligned, while now Cython has to generate code for any kind of alignment adding an unnecessary multiplication. It might be worth it to specify that the view is C-aligned to avoid the innermost stride
multiplication. (see section Caring about memory layout in this paper)

here is the doc for C or F contiguous memviews

Nice tips @NicolasHug . Those together bring all tests as shown in these plots, i.e. no overhead (most of it was after I applied your first comment):

Now I need to figure out a way to to handle the read-only input issue (i.e. failing tests).

I guess this looks good for a review now.

My 2 cents is that we should not start caring about non public API changes.

Quoting #10251 (comment)

this interface is not considered public, stable API and should be used at one's own risk.

It's also mostly (if not all) the C API, and not even the python API. I really don't think we should care about backward compatibility of those pieces of the code. That said, I'm happy to have a blog post somewhere (we don't have a blog, do we?) and announce well in advance that there are some C API changes to those parts and explain them.

Personally, I was really confused by the strides and it took me a while to figure they're just there to index the matrices.

I guess we [mostly] agree that this part of the package is not the easiest to get used to, which contributes to inhibiting contributions to it by a wider developer community. FWIW, I personally find memoryviews significantly nicer than what they're replacing here, and much less intimidating.

Generally, I think this PR is not the only thing which can potentially improve readability of the tree code base, and I'd find any contribution towards this goal valuable (the least it does is to ease my life working on trees, and that's why I started this PR). So I would have liked us to follow the "it's not public, therefore we can change the API" principle, at least here.

I understand it's a nice thing to not change APIs, but:

1. If I were a developer using private parts of a package, I wouldn't expect them to keep it as is.
2. Even if it was public, I'd support a deprecation cycle to clean up the code base, cause I feel it helps with the maintainability of the code base.

I don't know, that's all I have I guess.

@jnothman Is it possible to direct the people using the current version of Criterion to this PR and see what they think about it?

As far as I can tell the only change to the Criterion is pretty minimal and only impacts the __init__ signature. Someone with a custom Criterion object would only need to wrap they y pointer into a memory view (EDIT: the other way around actually), and remove the stride argument. That's a pretty minor inconvenience for using a private API, IMHO.

@camilstaps, you opened #10251 and needed custom Criterions, WDYT?

Also @glemaitre , @jmschrei, @glouppe , you've been working a lot on the tree code, maybe you want to weight in?

EDIT: for context: this PR greatly simplifies tree code by using memory views instead of pointer + stride, but breaks the Criterion interface, which is private but apparently used anyway by some users.

Thanks for the persuasive market research, @NicolasHug :D

Maybe we should just make the change.

Regarding custom Criterion, I think that it is a minor issue. If I recall the PR which was exposing the criterion, it was mentioned that we did not want to officially support it but exposed the criterion for convenience instead.

Maybe we should just make the change.

\o/

What did we decide about read only memoryview handling? Are we copying at master? In this PR?

I don't think we're copying. Some tests did actually fail and then I changed them in splitter and criterions to const memoryview instead and now tests are happy.

@jnothman any final verdict on this one?

I'm in favour. Is that final?

It is for this PR. I've found a bit more in the context of the NOCATS PR, but that can stay there.

For future reference, any such changes should go through time performance tests, sometimes what we see is not intuitive and they may actually slow down the run.

@glemaitre review ping :)