The Crystal Programming Language Forum

Fastest and iconic way to zero an array

I have an array of integers and need to set each element to zero (0) at times.

I did it like this:

ary.each_with_index { |_, m| ary[m] = 0 }

or

ary.size.times { |m| ary[m] = 0 }

but there’s got to be an easier/prettier (maybe faster) way.

Since this occurs so frequently, what I’d like to do is something like this:

ary.to_zero

https://crystal-lang.org/api/Array.html#fill(value:T)-instance-method

2 Likes

Pointer has a method clear that will set a number of elements to zero (as in zero in all bytes). But it’s in Pointer and “unsafe” because setting, say, a string or a class instance, or in general something that’s not an integer to zero will result in segfault or undefined behavior.

That said, for your program you could add a method for that in your code. And we could add it to the standard library, except that I don’t know how useful/frequent that is.

class Array
  def zero!
    {% unless T < Int::Primitive %}
      {% raise "Can't zero Array(#{T}), only Array of integers can be zeroed" %}
    {% end %}
    to_unsafe.clear(size)
  end
end

ary = (1..1_000).to_a

Benchmark.ips do |x|
  x.report("[]=") do
    ary.each_index do |i|
      ary[i] = 0
    end
  end
  x.report("zero!") do
    ary.zero!
  end
end

Output:

  []=   1.21M (825.38ns) (± 5.20%)  0.0B/op  20.87× slower
zero!  25.29M ( 39.54ns) (± 5.60%)  0.0B/op        fastest

Actually, now I remember there’s Array#fill so this should work:

ary.fill(0)

However, I believe that’s not optimized to use clear, but I’ll send a PR to do that soon :-)

6 Likes

With fill the benchmark output is:

  []=   1.24M (804.15ns) (± 4.25%)  0.0B/op  22.13× slower
 fill   2.52M (397.51ns) (± 3.77%)  0.0B/op  10.94× slower
zero!  27.53M ( 36.33ns) (± 3.01%)  0.0B/op        fastest
2 Likes

Wow @asterite I’m impressed!

So will you add zero! to the stdlib since it’s clearly the most performant, and iconic?

BTW, i guess zero! should work for floats and other numeric arrays too.

FYI, this operation is frequently done in many numeric algorithms.

I won’t add zero!. I will optimize fill(0) to do that trick. For now you could patch Array#fill with this:

class Array(T)
  def fill(value : T)
    {% if Int::Primitive.union_types.includes?(T) %}
      if value == 0
        to_unsafe.clear(size)
      else
        fill { value }
      end
    {% else %}
      fill { value }
    {% end %}
  end
end
1 Like

Is zero in floats always represented as a stream of zero bytes?

I don’t know what other numeric arrays are there.

Also, this trick won’t work for BigInt/BigFloat of course.

By the way, did you want a more succinct way to write it or a more performant way to execute it?

Because ary.fill(0) is the way to go. If it’s not as optimized as doing Pointer#clear maybe it’s not worth making the method more complex for now.

I actually need the fastest way to do it (how it looks is irrelevant).

This operation takes place inside an inner loop in an algorithm.
I have to initialize the array to zero before its operated on.
Given the huge performance difference you showed between zero! and fill(0)
this will have a tangible performance effect on the total algorithm.

(I’m translating this particular algorithm from D|Nim|Rust into Crystal. Currently the
Rust version is fastest, and Nim second. This particular operation is a bottleneck,
because you can’t get around doing it, so doing it the fastest way possible is desirable.
When I finish the full translation, and benchmarking, I’ll release the results to the forum.)

Is zero in floats always represented as a stream of zero bytes?

Never mind, I was thinking of their values not about their physical representation.
However, I think its still worth it in stdlib if just for integer arrays, for the reasons given.

OK, now I understand why.

I benchmarked all your changes, in file zero-test.cr below

require "benchmark"

class Array
  def zero!
    {% unless T < Int::Primitive %}
      {% raise "Can't zero Array(#{T}), only Array of integers can be zeroed" %}
    {% end %}
    to_unsafe.clear(size)
  end
end

class Array(T)
  def fill(value : T)
    {% if Int::Primitive.union_types.includes?(T) %}
      if value == 0
        to_unsafe.clear(size)
      else
        fill { value }
      end
    {% else %}
      fill { value }
    {% end %}
  end
end

ary = (1..1_000).to_a

Benchmark.ips do |x|
  x.report("[]=") do
    ary.each_index do |i|
      ary[i] = 0
    end
  end
  x.report("fill(0)") do
    ary.fill(0)
  end
  x.report("zero!") do
    ary.zero!
  end
end

and got these results:

➜  crystal-projects crystal build zero-test.cr --release
➜  crystal-projects ./zero-test           
    []= 884.80k (  1.13µs) (±22.34%)  0.0B/op  16.63× slower
fill(0)  14.49M ( 69.02ns) (±15.82%)  0.0B/op   1.02× slower
  zero!  14.72M ( 67.94ns) (±15.42%)  0.0B/op        fastest
➜  crystal-projects ./zero-test
    []=   1.02M (984.89ns) (±18.05%)  0.0B/op  15.36× slower
fill(0)  15.60M ( 64.11ns) (±15.08%)  0.0B/op        fastest
  zero!  14.81M ( 67.52ns) (±16.25%)  0.0B/op   1.05× slower

So zero! and fill(0) have sameish performance, so don’t really need zero!

Thanks for jumping on this immediately.

1 Like

No, if nothing else, there is both positive and negative 0.

edit: Looked it up. Those are the two cases that exist. The sign bit can be set for zero, or not. But they must still compare as equal to each other.

And according to IEEE754 positive zero (that looks like a sane default for float numbers) is represented as a stream of zero bytes.

Yes, but what should happen if you want to fill an array with negative zero? The code as pasted above doesn’t work as it would fill with positive zero instead.

Then you could do arr.fill(-0.0f64). But zero! method will be faster and would work for most usecases, because usually people want to fill array with 0.0, that is positive zero.

Hey @asterite I just want to be clear that you’re still doing the PR for fill(0) for integer arrays, which is what I need. Will that be available in next release?

From the discussion on zeroing floating point arrays, I want to be sure on which method will exist for my usecase.

Sorry, I won’t have time to do this right now. Feel free to open a PR. Otherwise, if zero! or that patch are working in your code, maybe there’s no need to add this extra logic to the standard library.

Proposed a PR for this here (integers only for the time being):

1 Like

Excellent work! :+1:

Will this PR be included in the next release (0.34)?