# Pre-allocate for findall

**URL:** <https://discourse.julialang.org/t/pre-allocate-for-findall/87454>\
**Category:** Performance\
**Created:** [September 18, 2022, 11:53pm UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454 "2022-09-18T23:53:26Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 18, 2022, 11:53pm UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/1 "2022-09-18T23:53:27Z")

</div>

I am absolutely sure something like this has been asked before but I cannot for the life of me find it.

I’m currently working on a memory- and speed-efficient way to access the first 1 billion primes as part of a different project. The way I’m using is a 1.4GB Bitarray, which I then use `findall` to convert back to numbers.

This is acceptably fast (~20 seconds) for my purposes, EXCEPT I need to manually add the number 2 back to the front of the array, which more than quadruples the run time.

Since I know exactly how big the array I need is, is there any way to do something where `findall` stores its answer directly into a pre-allocated array, so that I don’t need to do 1 billion copy operations?

My current code:

```julia
const last_prime = 22801763489

function get_primes()
    # Acquire primes as Bitarray
    io = open("primes_as_bits.bitarray")
    list = BitArray(undef, (Int((last_prime - 1) / 2)))
    read!(io, list)
    close(io)

    # Convert Bitarray into Int[]
    final = [2]
    push!(final, (findall(x -> x == 1, list) .* 2 .+ 1)...)
    return final
end

```

P.S. I’ve got a threaded version as well, which is a little faster, but I feel like it would still be much more efficient if I could just solve this problem.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:23am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/2 "2022-09-19T00:23:43Z")

</div>

First of all, you should use `pushfirst!` instead of `push!`. Most of the extra time comes from splatting. Secondly, you can just use a loop to avoid the extra allocations.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:24am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/3 "2022-09-19T00:24:43Z")

</div>

Also, the bitarray would be 1/3rd smaller if you masked out multiples of 3 as well as 2.

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 12:29am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/4 "2022-09-19T00:29:33Z")

</div>

Do you mean loop through `findnext`? I think I tried that and it was still slower, but I’ll get an actual benchmark here in a second. I assumed `findall` had some hidden optimizations under the hood

Also, thank you. I have like 5 versions I’ve tried and `pushfirst` was among them. That was the one I was actually citing when I said “4x slower”

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:40am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/5 "2022-09-19T00:40:50Z")

</div>

What I mean is just

```julia
function get_primes()
    # Acquire primes as Bitarray
    io = open("primes_as_bits.bitarray")
    list = BitArray(undef, (Int((last_prime - 1) / 2)))
    read!(io, list)
    close(io)

    # Convert Bitarray into Int[]
    final = Vector{Int}(undef, n)
    final[1] = 2
    i = 1;
    for j in 2:length(list)
         if list[j]
            final[i] = list[j]*2 + 1
            i += 1
        end
    end
    return final
end

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:48am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/6 "2022-09-19T00:48:48Z")

</div>

This is also fairly easy to multithread if you also store a couple offsets for the nth prime for various n.

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 12:50am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/7 "2022-09-19T00:50:10Z")

</div>

Well I’ll be danged. I swear I tried that already.

Fwiw, `findnext` seems to be just a bit faster, but they’re both well under 30 seconds

Thank you very much!

P.S. Yeah, multithreading is the next step, I just wanted to have a principled way of getting the solution first

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:52am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/8 "2022-09-19T00:52:08Z")

</div>

If you want to squeeze out some extra performance, you could throw `@inbounds` at it, and @celrod might know of an easy way to get this to vectorize.

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [September 19, 2022, 12:53am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/9 "2022-09-19T00:53:42Z")

</div>

Any reason we shouldn’t have a `findall!` that takes an out array?

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 12:54am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/10 "2022-09-19T00:54:11Z")

</div>

I appreciate it, but I only need this to be less than 30 seconds. This isn’t the project. The next set of calculations is going to take hours. I just needed this to be fast enough to be able to monitor the first step of the next thing without losing my sanity

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 12:55am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/11 "2022-09-19T00:55:08Z")

</div>

What’s the main calculation?

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 1:00am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/12 "2022-09-19T01:00:48Z")

</div>

I’m making heat maps of the final digit of prime p mapped against prime p-1 in different base systems n. It makes pretty pictures.

If I can find a way to sensibly do so, I’m going to try to find a continuous analogue to the idea of

```julia
array[p[i] % n + 1, p[i - 1] % n + 1] += 1

```

That way, I can make a full-blown animation between the different integer bases, as well as have an HD version of each frame.

Like so:

 ![Primes_0002](https://global.discourse-cdn.com/julialang/original/3X/c/3/c39cdcdb7d16f7b3df5c55f4c411c1c3c4dd17bd.png)  
 ![Primes_0010](https://global.discourse-cdn.com/julialang/original/3X/2/4/24d771ca86883d94dc90b261e7bc86e05201b379.png)  
 ![Primes_0100](https://global.discourse-cdn.com/julialang/original/3X/a/4/a4384926b1bcfb4630ceadcaaf334c9585752aad.png)  
 ![Primes_0101](https://global.discourse-cdn.com/julialang/original/3X/f/c/fc880b3495d418ed7e009febecfe1555131fd650.png)

Some cool stuff happens particularly at prime bases and extremely non-prime bases

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 1:09am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/13 "2022-09-19T01:09:19Z")

</div>

Interesting! I think you might be able to compute this efficiently from the bitmap directly. Specifically, I believe that this can be viewed as a convolution-like operation over the reshaped bitmap.

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 1:14am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/14 "2022-09-19T01:14:34Z")

</div>

How do you mean? I had the word “convolution” flash across my mind while thinking about this, but I couldn’t come up with any sensible way to use it.

Also, if you’re interested in playing around with this, I will happily share my code.

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 1:17am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/15 "2022-09-19T01:17:21Z")

</div>

Fwiw, the loop using `findnext` even outperformed `findall` without adding the 2 back in by about 50%.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [September 19, 2022, 1:19am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/16 "2022-09-19T01:19:49Z")

</div>

The idea is that if you define `mask` to be an `n` by `k` bitarray, then `array[i, j] = dot(mask[i, :], mask[j, :])`. I definitely don’t have time to work on this, but it is really cool.

---

<div class="post-metadata">

**Author:** ![MacKenzieHnC](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mackenziehnc/32/16429_2.png) [@MacKenzieHnC](https://discourse.julialang.org/u/MacKenzieHnC)\
**Post date:** [September 19, 2022, 1:24am UTC](https://discourse.julialang.org/t/pre-allocate-for-findall/87454/17 "2022-09-19T01:24:43Z")

</div>

I’ll think on that and report back if I the continuous version I’m looking for.

Thanks again for your help!