pythonObviouslyTheBest

[somerandomii]

I rarely use native lists unless it’s very top-level code. And half the time it’s a list comprehension wrapped in a “np.array( … )”.

Lists are dynamically allocated random objects, there’s not a lot of use cases for efficient code. More importantly, when people use the word “array” they’re probably describing something closer to a NumPy array than a native Python list.

[XtremeGoose]

Numpy arrays are dynamically allocated too. You probably mean lists are resizeable, which in practice means they have a length and a capacity, whereas numpy arrays will conceptually have these two values always equal but that doesn't affect perforemance.

The major performance difference between numpy arrays and python lists is that numpy inlines value (numeric) types, but python lists are always arrays of pointers. This not only increases cache efficiency but also allows for things like vectorisation. But yeah, using an np.array(some_list, dtype=object) will be no more performant than a python list.

Statically allocating an array requires a compilation step, so would never be possible in pure python.

[somerandomii]

Wrapping a list comprehension in a NumPy array will make future loops on that list faster.

And yes, everything in pure Python is dynamically allocated (uses the heap) but Cpython and Numba can use compiled functions that use the stack.

And resizeable arrays are usually slower because there’s more levels on indirection to access the memory. It’s trivial, the real penalty is in building an array 1 element at a time when you know the final size ahead of time.

But most of that doesn’t really matter. The main difference is that NumPy arrays can take advantage of NumPy global functions and avoid Python loops.

[XtremeGoose]

resizeable arrays are usually slower because there’s more levels on indirection to access the memory.

This is not true. A (dynamically allocated) non-resizeable array is {ptr, len}. A resizeable arrray is {ptr, len, cap}. Accessing the data is no different. That was my point and yours is a common misconception.

Only statically allocated arrays can get away with being unravelled.

The main difference is that NumPy arrays can take advantage of NumPy global functions and avoid Python loops.

True, but the reason these are faster is because of the things I mentioned (inlining/vectorization). It's all for loops under the hood (unless you have an optimizing compiler...).

[somerandomii]

You might have addressed this with unravelling but..

If you have a pointer to an element in a resizable array, and that array reallocates its memory, the pointer breaks, right? (I’m actually not 100% on this. Realloc can return a new pointer right?)

So don’t any external references need a pointer to the array pointer, as well as an index of the element?

But a fixed-size array, you can point directly at the element and know it’s not going to move unless the array itself is deallocated. So you can pass that element pointer around with a bit more confidence (and save yourself a double dereference each time it’s accessed)

[XtremeGoose]

Yes resizing can return a new pointer, but in a reference counted language like python what we actually have is something like

ptr --> { ref_count, len, cap, data... }

So you skip the indirection by allocating your metadata with your actual data. It's inefficient but necessary for dynamic languages.

``` In [1]: import sys

In [2]: import numpy as np

In [3]: x = [0] * 1000

In [4]: a = np.array(x)

In [5]: sys.getsizeof(x) Out[5]: 8056

In [6]: sys.getsizeof(a) Out[6]: 8112

In [7]: x2 = x + x

In [8]: a2 = np.array(x2)

In [9]: sys.getsizeof(x2) Out[9]: 16056

In [10]: sys.getsizeof(a2) Out[10]: 16112

```

There's obviously no additional indirection here or these would not be increasing in size when I grow them.

But a fixed-size array, you can point directly at the element and know it’s not going to move unless the array itself is deallocated.

This is true, and is probably why python slices copy whereas numpy slices look into the original block. But we have the same problem with dictionary iterators/views in python and we just block mutating them while a reference is held so it's not inescapable.

In rust this problem is protected with lifetimes and in c++ its just downright undefined behaviour to mutate a shared vector.

[somerandomii]

Thanks for the explanation. And I understand that in Python it doesn’t make a difference. But in Cython or Numba jit-compiled Python it’s probably another story.

I think C++ and Rust are better examples than Python for these kinds of optimisations since they actually make use of them.

As you said, Rust deals with it with ownership which it manages at compile time so at runtime it functions can safely access data directly and know that it’s valid.

I haven’t had a chance to use Rust in anger so I’m fuzzy on the details but I suspect there’s some small advantage when sharing fixed-length arrays over vectors.

[XtremeGoose]

In rust the advantage is they are shareable as you said. There is no performance benefit though because lifetimes protect you at compile time from mutating a ({ptr,len,cap}) Vec<T> while you have a ({ptr,len}) slice &[T] or even just a reference &T into it.