Elixir - Replace at position in binary

Question

Problem

I'm trying to make a basic image (bitmap) writter in Elixir but I stuck on a point.

I tried to make a function for set a pixel into a binary. I use pattern matching but my function is clearly too slow (more than 10 min to set all pixels to a picture with a size of 1024 * 768).

Currently, I've a binary with a size equals to width * height. Like you can see on the following code, my function take x and y as params and have to modify an int at this location.

Current code

# Function
def replace_by_test(output, width, x, y) do
    out_offset = y * width + x
    <<
        o_before :: binary-size(out_offset),
        _ :: binary-size(4),
        o_after :: binary
    >> = output

    << o_before :: binary, "TEST" :: binary, o_after :: binary >>
end

# Test on a 1024 * 768 resolution image
out_size = 1024 * 768 * 8
output = << 0 :: size(out_size) >>
for x <- 0..(1024*768-1), do: replace_by_test(output, 1024, 0, 0)

Goal

Make this code faster. If possible, run it in less than 10 seconds.

What are you trying to achieve with this? You're creating a copy of a 786 kb string 786k times here. I don't think you can speed this up significantly. Maybe there's a better solution to the problem you're trying to solve? — Dogbert
– Dogbert, Commented Feb 27, 2018 at 20:04
@Dogbert I just want to be able to create an image from a pixel sequence (List<%{ x, y, rgba_as_int }> for example) — DarkyZ
– DarkyZ, Commented Feb 27, 2018 at 20:13
Are the pixels in the list consecutive? E.g. x=0 y=0 then x=0 y=1 then x=0 y=3 and so on? or can they be in random order? — Dogbert
– Dogbert, Commented Feb 27, 2018 at 20:15
Are you attempting to do some sort of steganography? Like @Dogbert I am having a hard time understanding what you're actually trying to do. — Onorio Catenacci
– Onorio Catenacci, Commented Feb 27, 2018 at 21:35

Dogbert · Accepted Answer · 2018-02-27 20:26:11Z

Constructing a new binary like that would result in Erlang having to copy the whole binary on each iteration. Copying 786432 bytes 786432 times is bound to be slow (That's 618GB of memory that needs to be allocated and then soon free'd!). You need to use a different data structure for this.

One option is to use a Map while constructing the binary and then convert it to a binary when you're done modifying:

# Create a blank image.
map = for x <- 1..1024, y <- 1..768, into: %{}, do: {{x, y}, 0}

# Set each pixel once to x * y
map =
  0..1023
  |> Enum.reduce(map, fn x, map ->
    0..767 |> Enum.reduce(map, fn y, map ->
      Map.put(map, {x, y}, 0)
    end)
  end)

# Get back a binary
binary = for x <- 0..1023, y <- 0..767, into: <<>>, do: <<Map.get(map, {x, y})>>

IO.inspect binary
IO.inspect byte_size(binary)

Output:

<<0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...>>
786432

This whole script takes about 2.5 seconds to execute on my machine.

Another option is to use Erlang's array module. It might be faster than maps. It should be easy to implement after reading the documentation of that module once.

Edit: Here's the code converted to array. It runs in almost exactly 1 second on my machine, 2.5 times faster than map.

# Create a blank image.
array = :array.new(size: 1024 * 768, default: 0)

# Set each pixel once to x * y
array =
  0..1023
  |> Enum.reduce(array, fn x, array ->
    0..767 |> Enum.reduce(array, fn y, array ->
      :array.set(y * 1024 + x, 123, array)
    end)
  end)

# Get back a binary
binary = :array.foldl(fn _, x, acc -> <<acc::binary, x>> end, <<>>, array)

Collectives™ on Stack Overflow

Elixir - Replace at position in binary

Problem

Current code

Goal

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem

Current code

Goal

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related