1

In the array library in Python, what's the most efficient way to preallocate with zeros (for example for an array size that barely fits into memory)?

Creating a huge list first would partially defeat the purpose of choosing the array library over lists for efficiency.

Is it possible to preallocate even faster, without spending time on overwriting whatever there was in memory?

(Preallocating is important, because then the code is faster than growing an array iteratively, as discussed here.)

root
  • 1,812
  • 1
  • 12
  • 26
  • The only way to create an `array.array` of nonzero size is to pass it an existing container or iterator with that size. Have you considered the `numpy` module? It gives you the same memory-efficient storage of `array`, extends that to multiple dimensions, and gives you efficient vectorized math operations that apply to the entire array. You can directly create an array of a given size, either initialized to zeros, or left uninitialized. – jasonharper Sep 02 '22 at 18:36
  • @jasonharper How do I make an iterable that produces lots of zeros but doesn't require much memory nor runtime? (This is for a memory- and runtime-critical application where `numpy`, `ulab` etc. aren't available.) – root Sep 02 '22 at 18:41

2 Answers2

2

Use sequence multiplication, just like you would to create a giant list, but with an array:

arr = array.array(typecode, [0]) * size_needed

Note the position of the parentheses. We directly multiply a 1-element array by an element count, rather than multiplying a 1-element list by an element count and then converting to an array.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • 2
    @MadPhysicist: It's [documented](https://docs.python.org/3/library/array.html), but in a way that's easy to miss: "Array objects support the ordinary sequence operations of indexing, slicing, concatenation, and multiplication." – user2357112 Sep 02 '22 at 18:42
  • Is this without unnecessary overhead, for example *reading* the first zero over and over in order to copy it? – root Sep 02 '22 at 18:43
  • @user2357112. Good call. Still neat though :) – Mad Physicist Sep 02 '22 at 18:45
  • @root. This should not have any overhead. It should allocate a buffer that is exactly `size_needed` times the current size (1), and fill it in with repeated copies of the current array. Internally, the data is just a pointer, so there should not be any unnecessary overhead. The internals of the module are written in C: https://github.com/python/cpython/blob/main/Modules/arraymodule.c#L910 – Mad Physicist Sep 02 '22 at 18:51
  • 2
    @root: If you're hoping for something that'll just `calloc` a buffer, there is unfortunately no option to do that. The array multiplication will hit a fast path that uses `memset` if the original array has 1 element and a 1-byte typecode, but otherwise, it'll repeatedly `memcpy` chunks to populate the new buffer. – user2357112 Sep 02 '22 at 18:53
  • @user2357112 Where in the source code is this fast path? – root Sep 02 '22 at 19:15
  • 1
    @root: https://github.com/python/cpython/blob/v3.10.6/Modules/arraymodule.c#L928 – user2357112 Sep 02 '22 at 19:21
  • @user2357112 You linked to the `v3.10.6` tag of the repo. It seems that the `main` branch has replaced that code [here](https://github.com/python/cpython/commit/850687df47b03e98c1433e6e70e71a8921eb4454#diff-a64ccdf7f6d9fe7fbe417fe2d24c7803c152b75640bdc5a6539754aa71bc6a51L931). I don't quite understand how efficient [the new code here](https://github.com/python/cpython/blob/main/Modules/arraymodule.c#L927-L929) is. Do you? – root Sep 02 '22 at 19:34
  • @root: `_PyBytes_Repeat` has the same fast path. They refactored a few similar functions and moved the duplicate code into a new `_PyBytes_Repeat` helper. – user2357112 Sep 02 '22 at 19:39
1

Using the * operator is probably best. A much less efficient method:

from array import array
from itertools import repeat

arr = array(typecode, [])
arr.extend(repeat(0, size_needed))

You can shorten this with the iterable version of the constructor:

arr = array(repeat(0, size_needed))

Or, to avoid the extra import:

arr = array(0 for _ in range(size_needed))

The reason that this is much less efficient is that array.extend (which is what the iterable constructor delegates to) does not use the length or __length_hint__ of the iterable object that is passed in. Consequently, the array will be expanded with multiple reallocations until you reach the target size. This may end up being almost as inefficient as allocating the list. While repeat does define a proper __length_hint__, generator expressions do not, but that is a moot point for the current CPython implementation.

Mad Physicist
  • 107,652
  • 25
  • 181
  • 264
  • if you don't want the `repeat` import, you can do `arr.extend(0 for _ in range(size_needed))` – kindall Sep 02 '22 at 18:48
  • @kindall Is your solution similar to `arr.extend([0] * size_needed)`? The problem is that the fleshed out list would occupy too much memory. (See the question.) – root Sep 02 '22 at 18:52
  • @root. Using a generator is not the same as making a list. The generator is evaluated lazily. While this is much less efficient than using `*` because multiple reallocations may happen a the array is filled, it does not create a list of zeros in memory. – Mad Physicist Sep 02 '22 at 18:54
  • Is that a list comprehension, and omission of brackets is syntactic sugar? So list comprehensions are generators and their elements are *discarded* on the fly? – root Sep 02 '22 at 18:58
  • Another thing: Any idea why the `repeat` solution is "much less efficient"? Its logic does seem similar to the `*` operator: the `array` library gets warned about the final array size, hence can initialize it at once, and then receives zeros from a source that claims to be ["efficient"](https://docs.python.org/3/library/itertools.html). – root Sep 02 '22 at 19:01
  • 1
    @root. It's a generator expression. When used as a function argument, you can omit the parentheses (not brackets). A list comprehension is when you have square brackets around it, which is syntactic sugar for `list()`. A generator expression is evaluated the same way that a similar function with a `yield` function would be: that is, lazily, with only one value stored in memory at the same time. In fact, if `__length_hint__` is implemented for it, and `array` respects it, then this may end up being relatively efficient (not compared to `memcpy` though). – Mad Physicist Sep 02 '22 at 19:01
  • 1
    @root. It's less efficient exactly because generators don't normally report their size. They might not even have a finite size (like `repeat` without the second argument). Some generators *may* implement `__length_hint__`, but that's not guaranteed, and I don't know how it's propagated through the wrappers. – Mad Physicist Sep 02 '22 at 19:02
  • Thanks! If `array.extend` doesn't get warned about the final size, then we have the problem of slow iterative growth of the array, mentioned in the question. But it's good to know these methods. – root Sep 02 '22 at 19:04
  • 1
    @root. I checked. `repeat` does correctly implement `__length_hint__`, but `(0 for i in range(100)).__length_hint__()` does not! – Mad Physicist Sep 02 '22 at 19:05
  • The generator might pass on the `__length_hint__` of `range(100)`, but `range(100).__length_hint__()` isn't implemented. It's a lacking feature in Python that would be meaningful, right? – root Sep 02 '22 at 19:13
  • @root. `range(100)` has `__len__` implemented, which should supersede `__length_hint__` anyway. The real issue is that `array_iter_extend` (C function) does not look for `__len__` or `__length_hint__` before inserting one element at a time from the iterator: https://github.com/python/cpython/blob/main/Modules/arraymodule.c#L993. That being said, it would be useful, in some cases, if generator expressions could pass through a `__length_hint__`. It would fall apart any time you had an `if` filter on it, but it would still be useful for an upper bound, when available. – Mad Physicist Sep 02 '22 at 19:14
  • And another issue is that the generator `(0 for i in range(100))` doesn't look for `__len__` of `range(100)` when we try `(0 for i in range(100)).__length_hint__()`, right? – root Sep 02 '22 at 19:17
  • @root. Generator expressions don't define a `__length_hint__` at all. They don't look for anything. On top of that, `array.fromiter` does not use `__len__` or `__length_hint__` on the iterable. – Mad Physicist Sep 02 '22 at 19:20
  • I withdraw my cgenerator expression suggestion, the length hint is vital. – kindall Sep 02 '22 at 19:22
  • @kindall. Yup. If anything, `repeat` is better, but unfortunately the `array` module does not care. I would submit a PR if I had the time. Until then, this answer only meets the superficial requirement of "not having a list", but actually does something just as bad. – Mad Physicist Sep 02 '22 at 19:25
  • Why is the fact that generator expressions don't implement `__length_hint__` "a moot point for the current CPython implementation"? It can be fixed, right? Maybe I don't quite understand the word "moot". – root Sep 02 '22 at 20:07
  • @root. It doesn't matter that `repeat(0, 100).__length_hint__() == 100`: the *current* implementation of `array.extend` does not use that information. You could fix it, in which case I would have to update my answer, but in the meantime, it's irrelevant that this method exists. – Mad Physicist Sep 02 '22 at 20:32