# Too many allocations for this couple of small functions

**URL:** <https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170>\
**Category:** Performance\
**Created:** [October 3, 2022, 4:47pm UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170 "2022-10-03T16:47:29Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![daviddoij](https://avatars.discourse-cdn.com/v4/letter/d/87869e/32.png) [@daviddoij](https://discourse.julialang.org/u/daviddoij)\
**Post date:** [October 3, 2022, 4:47pm UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170/1 "2022-10-03T16:47:29Z")

</div>

Hi there, newbie here

solved Project Euler #4 problem with Julia and, althogh the timing is good, I got too many allocations (around 100k) for such a small program.  
I’ve tried with explicit types in the variables and didn’t get any improvements, so obviously I’m doing something wrong.

Here is the code

```julia
> function ispalindrome(n)
> for i in zip(digits(n), reverse!(digits(n)))
> if i[1] ≠ i[end]
> return false
> end
> end
> return true
> end
> 
> 
> function Problem4()
> #=
> A palindromic number reads the same both ways. The largest palindrome made
> from the product of two 2-digit numbers is 9009 = 91 x 99.
> 
> Find the largest palindrome made from the product of two 3-digit numbers. 
> =#
> 
> ans = 10_001
> for i = 100:999, j = i:999
> if (i*j > ans) && ispalindrome(i*j)
> ans = i*j
> end
> end
> return ans
> 
> end
>
> @btime Problem4()
> println("Result: ", Problem4())

```

---

<div class="post-metadata">

**Author:** ![Krastanov](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krastanov/32/6817_2.png) [@Krastanov](https://discourse.julialang.org/u/Krastanov)\
**Post date:** [October 3, 2022, 5:05pm UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170/2 "2022-10-03T17:05:19Z")

</div>

The `digits` function creates an array each time you call it. That storage space requires the expensive allocation.

And you perform it twice for each n, which is an additional expense.

I would suggest:

1. If you create such an array, create it only once and use something like `digit_array[index] != digit_array[end+1-index]` when traversing it.
2. Try to not even create the array, rather make your own “get\_nth\_digit” function that uses modulo division and remainders.
3. If you prefer to create such an array in advance (because it is much simpler than creating a “get\_nth\_digit”), create a “scratch space” buffer array that gets overwritten and reused on each iteration. Such buffers are a common way to minimize allocations, because overwriting an already allocated array is drastically faster than searching for enough free space on the heap to allocate a new array. You might need to write a new function `digits!(buffer,n)` which writes the digits of `n` in the already allocated array `buffer`.

3 would probably be my preferred solution over 2.

A side note: explicit types in the arguments of functions do not provide speedup in Julia (with some caveats to that statement). Types in function signatures mainly serve to organize how multiple dispatch would be happening (when you have multiple definitions of the same function with different type signatures). If the type signature is not specified, Julia would still compile a specific implementation for the type being encountered, so things will still be fast.

On the other hand, types specified in the definition of structs can be very important for performance, as having a full type specification at compile time permits the compiler to not use “boxed” objects (objects with unknown type that needs to be checked at runtime).

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 3, 2022, 9:24pm UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170/3 "2022-10-03T21:24:39Z")

</div>

I would go with a `get_first_digit` and `get_last_digit`, compare them, and then recurse on the remaining digits. If you use `divrem` and precalculate the length of the number (in digits), you can do this with zero allocations. It will also bail out early, so if the first and last digits are different, `ispalindrome` runs in nearly zero time.

Furthermore, in the main loop of `Problem4`, make sure to iterate from large numbers to small ones instead of from small to large. Then bail out early from each loop.

---

<div class="post-metadata">

**Author:** ![nilshg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nilshg/32/2283_2.png) [@nilshg](https://discourse.julialang.org/u/nilshg)\
**Post date:** [October 4, 2022, 8:21am UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170/4 "2022-10-04T08:21:06Z")

</div>

You’ve already got everything you need I believe but just a small addition to make the issue obvious:

```julia
julia> f(x) = (digits(x); reverse!(digits(x)))
f (generic function with 1 method)

julia> @btime f(12345)
  72.485 ns (2 allocations: 192 bytes)

```

That’s often how I go about performance tuning - start with the smallest, simplest bit of the code that you can isolate, benchmark it, think about whether it can be improved/allocations reduced.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 4, 2022, 9:00am UTC](https://discourse.julialang.org/t/too-many-allocations-for-this-couple-of-small-functions/88170/5 "2022-10-04T09:00:49Z")

</div>

Here’s an implementation of `ispalindrome` for comparison

```julia
ispalindrome(x::Integer, numdigits=ndigits(x)) = _ispalindrome(x, 10^(numdigits-2))
function _ispalindrome(x::Integer, divider)
    x < 10 && return iszero(x) || iszero(divider)
    (x, digit1) = divrem(x, 10)
    (digit2, x) = divrem(x, divider)
    return digit1 == digit2 && _ispalindrome(x, div(divider, 100))
end

```

If I try that on `12345` I get

```julia
julia> @btime ispalindrome(12345)
  9.710 ns (0 allocations: 0 bytes)
false

```

Trying it on an actual palindrome, it’s a bit slower:

```julia
julia> @btime ispalindrome(12321)
  21.386 ns (0 allocations: 0 bytes)
true

```

But if you know the length of your number (which you actually do in your application), there’s a significant speedup:

```julia
julia> @btime ispalindrome(12321, 5) # actual palindrome
  10.711 ns (0 allocations: 0 bytes)
true

julia> @btime ispalindrome(12345, 5) # early bailout
  1.900 ns (0 allocations: 0 bytes)
false

```

The vast majority of your tests will be `false`, and you can bail out early, meaning that you can do palindrome testing very fast indeed. One caveat: Benchmark results around ~1ns can be unreliable, but I think it’s safe to say we are close to optimal.

**Edit:** For longer integers, using the longest possible `Int64` palindrome:

```julia
julia> @btime ispalindrome(1234567890987654321)
  74.743 ns (0 allocations: 0 bytes)
true

julia> @btime ispalindrome(1234567890987654321, 19) # supplying numdigits
  60.183 ns (0 allocations: 0 bytes)
true

```

With early bailout for non-palindrome:

```julia
julia> @btime ispalindrome(1234567890987654327)
  16.000 ns (0 allocations: 0 bytes)
false

julia> @btime ispalindrome(1234567890987654327, 19) # supplying numdigits
  1.200 ns (0 allocations: 0 bytes)
false

```