gmane.comp.python.cython.devel

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-22T13:16:44

That's a valid point, but my experience has been that any worthy C
compiler will do common subexpression elimination for the outer
dimensions and not recompute the offset every time. It actually
generated marginally faster code for scalar assignment than a
"cascaded pointer assignment", i.e. faster than

p0 = data;
for (...) {
    p1 = p0 + i * strides[0]
    for (...) {
        p2 = p1 + j * strides[1]
        ...
    }
}

(haven't tried manual strength reduction there though).

_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] 0.17

mark florisson — 2012-05-22T13:08:07

I think we have enough stuff in to go for a 0.17 release, I have a few
more fixes and a refactoring that I'll finish tonight that might be
useful to get in as well. Currently Jenkins is yellow though, as the
reduce_pickle test fails in Python 3.
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-22T07:13:17

Sorry for being an such an annoying know-it-all, it just seemed from 
your comment like you didn't know :-)

Dag
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Robert Bradshaw — 2012-05-22T07:06:15

On Mon, May 21, 2012 at 11:57 PM, Dag Sverre Seljebotn
<d.s.seljebotn< at >astro.uio.no> wrote:

Yes, I understand this. Truly element-wise arithmetic with arrays of
the same memory layout (or even size) is not that uncommon though, and
should be optimized for as well. Fortunately, I feel pretty
comfortable sitting back and watching 'cause you've both thought about
these issues far more than I and I don't see you both getting it wrong
:).

- Robert
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-22T06:57:51

I meant, "throws away a lot of memory *bandwidth*".

Dag


_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-22T06:57:04

The point isn't only being clever about the *order*...you need "copy-in, 
copy-out".

The point is that the NumPy iterator is not good enough (for 
out-of-cache situations). Since you grab a cache line (64 bytes) each 
time from main memory, a plain NumPy broadcasted iterator throws away a 
lot of memory for "A + A.T", since for ndim>1 there's NO iteration order 
which isn't bad (for instance, you could iterate in the order of A, and 
the result would be that for each element of A.T you fetch there is 64 
bytes transferred).

So the solution is to copy A.T block-wise to a temporary scratch space 
in cache so that you use all the elements in the cache line before 
throwing it out of cache.

In C, I've seen a simple blocking transpose operation be over four times 
faster than the brute-force transpose for this reason.

Dag


_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Robert Bradshaw — 2012-05-22T06:48:23

On Mon, May 21, 2012 at 11:36 PM, Dag Sverre Seljebotn
<d.s.seljebotn< at >astro.uio.no> wrote:

Yes, being clever about the order in which to iterate over the indices
is the hard problem to solve here. I was thinking more in terms of the
inner loop iterating over the innermost dimension only to do the
indexing (retrieval and assignment), similar to how the generic NumPy
iterator works.


Linear transformations of the index variables could probably be
handled, but that's certainly not v1 (and not too difficult for the
user to express manually).

- Robert
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-22T06:36:25

Ideally, there is a lot more magic going on, though I don't know how far 
Mark wants to go.

Imagine "nditerate(A, A.T)", in that case it would have to make many 
small tiles so that for each tile being processed, A has a tile in cache 
and A.T has another tile in cache (so that one doesn't waste cache line 
transfers).

So those array lookups would potentially look up in different memory 
buffers, with the strides known at compile time.

Which begs the question: What about this body?

if i < 100:
     continue
else:
     A[i, j, k] += B[i - 100, j, k]

I guess just fall back to a non-tiled version? One could of course do 
some shifting of which tiles of B to grab etc., but there's a limit to 
how smart one should try to be; one could emit a warning and say that 
one should slice and dice the memoryviews into shape before they are 
passed to nditerate.

Dag
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Robert Bradshaw — 2012-05-22T06:11:55

On Mon, May 21, 2012 at 3:34 AM, Dag Sverre Seljebotn
<d.s.seljebotn< at >astro.uio.no> wrote:

I'm assuming the index computations would not be re-done in this case
(i.e. there's more magic going on here than looks like at first
glance)? Otherwise there is an advantage to ndenumerate.

- Robert
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-21T11:21:33

Indeed, my initial idea was to make it optional, but since Theano
would also give execution on the GPU as well as generate BLAS calls
where appropriate, it makes sense to push for making it optimal for
the CPU as well memory-access wise and vectorization-wise.


Yeah, I've been digging a bit through the code, I'm not sure yet how
much work that would require, but I think it is non-trivial.
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-21T11:14:26

Still, if this is all Theano provides, I question structuring the 
project around reusing Theano. It's the sort of things that are 
nice-to-have but not fundamental (like memory access patterns).

Put another way, it sounds like Theano could easily be made an optional 
dependency currently.

Another question is of course whether it is better to work on Theano to 
implement tiling etc. for the CPU (and even compile all the 
specializations and select between them).

You could perhaps even have Theano use PEP 3118 rather than NumPy too.

I guess I should subscribe to the Theano list.

Dag
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-21T11:11:49

(Where of course the nditerate loop striding pattern would be patched
accordingly.)

_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-21T11:08:33

As for this, I don't think CSE is important for scalar computations,
since if they are objects, you have to go through a Python layer since
you have no idea what the code does, and if they are C objects, the C
compiler will readily optimize that out. You want this for vector
expressions since the computations may be  expensive and the C
compiler may not optimize them. E.g. consider the silly example of v1
* sum(A) + v2 * sum(A). It's more convenient to write than to
introduce a new variable manually.


I don't think so, since I think we want to try explicit vectorization.
I think the iteration and tiling mechanism etc will be shared by both,
but we wouldn't provide that direct mapping (I think). Although maybe
we could insert a VectorAssignment with VectorScalars... let's see, in
any case both will be optimized in the same way, except that with
vector expressions you know you're always getting the best the
compiler can do.

_______________________________________________
cython-devel mailing list
cython-dev

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-21T10:56:10

Ah, I guess, because we can reduce thead-local results manually in a
specified (elementwise) order (I was thinking of generating OpenMP
annotated loops, that can be enabled/disabled at the C level, with an
'if' clause with a sensible lower bound of iterations required).


Yeah, definitely.


Yes, it does those kind of things, and it also eliminates common
subexpressions, and it transforms certain expressions to BLAS/LAPACK
functionality. I'm not sure we want that specifically. I'm thinking it
might be more fruitful to start off with a theano-only specialization,
and implement low-level code generation in Theano, and use that from
Cython by either directly dumping in the code, or deferring that to
Theano. At this point I'm not entirely sure.


I think it does so for the CUDA backend, but not for the C++ backend.
I think we need to discuss this stuff on the theano mailing list.

_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/lis

Re: [Cython] gsoc: array expressions

Dag Sverre Seljebotn — 2012-05-21T10:34:40

Only associative, right?

Sounds good to me.



I think this sounds good; I guess don't see a particular reason for 
"ndenumerate", I think code like the above is clearer.

It's perhaps worth at least thinking about how to support "for idx in 
...", "A[idx[2], Ellipsis] = ...", i.e. arbitrary number of dimensions. 
Not in first iteration though.

Putting it in "parallel" is nice because prange already have 
out-of-order semantics.... But of course, there are performance benefits 
even within a single thread because of the out-of-order aspect. This 
should at least be a big NOTE box in the documentation.


Can you enlighten us a bit about what Theano's optimizations involve? 
You mention doing the iteration specializations yourself below, and also 
the tiling..

Is it just "scalar" optimizations of the form "x**3 -> x * x * x" and 
numeric stabilization like "log(1 + x) -> log1p(x)" that would be 
provided by Theano?

If so, such optimizations should be done also for our scalar 
computations, not just vector

Re: [Cython] N-d arrays, without a Python object

mark florisson — 2012-05-20T21:19:49

Hey Pauli,

Thanks for the feedback, that's actually really something I wanted as
well, along with variable sized C arrays while we're at it. We think
we can definitely make this work, probably with a syntax like 'cdef
double[:10, :10] myview' for memoryviews. I'm not sure when I'll have
the time to implement this, as I'm first going to focus on the gsoc,
so I can't promise anything for 0.17.

Cheers,

Mark
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

[Cython] N-d arrays, without a Python object

Pauli Virtanen — 2012-05-20T20:59:58

Hi,


# OK, but slow
cdef double[:,:] a = np.zeros((10, 10), float)

# OK, fast (no Python object)
cdef double[10] a

# OK, but slow, makes Python calls (-> cython.view array)
cdef double[10*10] a_
cdef double[:,:] a = <double[:10,:10]>(<double*>a_)

# not allowed
cdef double[10,10] a

Small N-d work arrays are quite often needed in numerical code, and I'm
not aware of a way for conveniently getting them in Cython.

Maybe the recently added improved memoryviews could allow for
Python-less N-dim arrays? This may be reinveinting a certain language,
but such a feature would find immediate practical use.

Re: [Cython] gsoc: array expressions

mark florisson — 2012-05-20T14:10:53

This does not address code reuse yet, I believe Theano does not
implement explicit vectorization or tiling for the CPU, correct? From
that perspective, it makes more sense to implement this in Theano and
reuse the code generation part (although it seems Theano is an even a
larger beast than Cython). I sincerely believe that the larger part
here would be code generation, so if another code backend is targeted
(e.g. Numba), it may make more sense for such a project to reuse
Theano's optimization pipeline, but not the code generation backend.
_______________________________________________
cython-devel mailing list
cython-devel< at >python.org
http://mail.python.org/mailman/listinfo/cython-devel

[Cython] gsoc: array expressions

mark florisson — 2012-05-20T14:03:09

Hey,

For my gsoc we already have some simple initial ideas, i.e.
elementwise vector expressions (a + b with a and b arrays with
arbitrary rank), I don't think these need any discussion. However,
there are a lot of things that haven't been formally discussed on the
mailing list, so here goes.

Frédéric, I am CCing you since you expressed interest on the numpy
mailing list, and I think your insights as a Theano developer can be
very helpful in this discussion.

User Interface
===========
Besides simple array expressions for dense arrays I would like a
mechanism for "custom ufuncs", although to a different extent to what
Numpy or Numba provide. There are several ways in which we could want
them, e.g. as typed functions (cdef, or external C) functions, as
lambas or Python functions in the same module, or as general objects
(e.g. functions Cython doesn't know about).
To achieve maximum efficiency it will likely be good to allow sharing
these functions in .pxd files. We have 'cdef inline' functions, but I
would

Re: [Cython] [cython] Python array support (#113)

Robert Bradshaw — 2012-05-20T08:07:42

I've merged this and fixed it up somewhat. I didn't realize anonymous
union members are a gnu (and now C11) extension, which this uses, so
there's that caveat. I think it's good enough (and useful enough) go
go in, we can continue to improve things from here.

- Robert

Re: [Cython] [Python-Dev] C-level duck typing

Dag Sverre Seljebotn — 2012-05-18T08:30:14

This seems right on target. I could make a utility code C header for 
such a metaclass, and then the different libraries can all include it 
and handshake on which implementation becomes the real one through 
sys.modules during module initialization. That way an eventual PEP will 
only be a natural incremental step to make things more polished, whether 
that happens by making such a metaclass part of the standard library or 
by extending PyTypeObject.

Thanks,

Dag