[Pyrex] Question, plus suggestions for improvement?

[Josiah Carlson]

"Giovanni Bajo" <rasky at develer.com> wrote:
> Josiah Carlson wrote:
> >> If you need to perform many accesses, it's better to convert it to a
> >> standard C array of integers/floats, allocated with malloc() (and
> >> freed with free()). You can index it with any "cdef int" variable,
> >> and this will provide C-like performance. This is especially useful
> >> if the same data is used many times (eg: convert the data to C array
> >> in the constructor, and then use it in all the methods).
> >
> > In my experience, malloc and free are horrible from a performance
> > perspective.  The highest performing code I've produced never uses
> > either of them (or really, never uses free).
> >
> > If one assumes a maximum fixed size of the input sequence, you can use
> > stack allocation, which is both far faster, and impervious to "oops, I
> > forgot to free" bugs.
> 
> Depends. What if you have an unbounded size, and it's often going to be
> larger than Python standard pools so PyMem_Malloc won't help?

PyMem_Malloc isn't any better than malloc.  What I meant by 'stack
allocation', and "a maximum fixed size" is something like...

int fcn(...) {
    int stack_memory[maximum_fixed_size];
    ...
}

> It also depends on how many times you access the list. If you do it many
> times, it's much better to pay for the penalty of malloc once, rather than
> going through PyList_GetItem + PyFloat_AsFloat thousands of times.

I'm not familliar with the algorithm that the OP has chosen to implement
for permutations, but I wasn't speaking directly to the OP's particular
application with regards to performance.  I was stating that generally
malloc/free tends to have some performance gotchas that most people
don't realize until they stop using it.

Why would malloc/free not be as fast as stack allocation?  Easy;
malloc/free needs to check the various memory heaps for a suficiently
sized block of memory, chop a bit off, etc.  It's some nontrivial data
structure manipulation, nevermind that free doesn't always actually
free[1]. On the other hand, using the function call stack is
functionally free, it's merely a larger increment on call and decrement
on return.

 - Josiah

[1] If you want to have some fun, write a program that mallocs, trivially
manipulates the allocated memory (to bypass your optimizer), then freesthe
memory.  Compare its performance, memory use, etc., to repeatedly
calling a function that does the same trivial manipulation to its
stack-based memory.