NIF vs Elixir showdown

[Alexei Sholik]

I compared an Elixir implementation of String.duplicate with the current NIF-based version (the :binary.copy NIF). The results were surprising.

https://gist.github.com/alco/b4f5d1d995005b521986

Graph: https://www.dropbox.com/s/bp52ro47tw2zr7u/Screen%20Shot%202014-07-18%20at%2020.28.34.png

If you ever feel like speeding up String.duplicate, now you know what to do :)

--
Best regards
Alexei Sholik

[Alexei Sholik]

The Elixir version grows the stack, up to log2(n). However, the NIF version would be able to preallocate all the memory up front and then use a similar algorithm with rather small stack on each recursive call. I haven't looked into the NIF's implementation yet.

[Alexei Sholik]

I haven't found the implementation of :binary.copy in the source :/

[Martin Schurrer]

I forked it to also test with chardata (iolists to Erlang people).

Unexpectedly chardata is the fastest as long as it's not turned into a
binary :)

https://gist.github.com/MSch/e16e23ee2d8bae649c86

fyi in order to run this git clone
https://github.com/alco/benchfella.git then check out the develop
branch, mix compile and run:

elixir -pa ~/path/to/benchfella/_build/dev/lib/benchfella/ebin dup_bench.exs

--

Kind regards,
Martin Schurrer

[Robert Virding]

On Friday, July 18, 2014 8:42:07 PM UTC+2, Martin Schuerrer wrote:

I forked it to also test with chardata (iolists to Erlang people).

Unexpectedly chardata is the fastest as long as it's not turned into a
binary :)

https://gist.github.com/MSch/e16e23ee2d8bae649c86

Actually that is not surprising! While lists may not be the common way of representing strings they are for many operations faster than keeping them in some array (binary) format, especially as soon as you start copying. There was a discussion last year on the erlang mailing list about a benchmark which showed this.

Robert

[Alexei Sholik]

Hi Robert,

I think it's fine for lists to be faster than binaries when comparing Elixir/Erlang implementations. But it is not fine for a NIF to be slower than any of them.

I've written a basic implementation in C that compares naive copying with a more efficient algorithm: https://gist.github.com/alco/7d75b87b77bb7c113499#file-results

slow Input size = 100000, time = 1918.361000 µs
fast Input size = 100000, time = 254.149000 µs

Compare this to the Elixir vs :binary.copy measurements:

StringDuplicateBench.strdup 100000:           20000   88.69 µs/op
StringDuplicateBench.binary copy 100000:       5000   546.27 µs/op

Of course, the real binary_copy implementation has to take a lot of things into consideration, but the compiled BEAM code almost always has more run time overhead compared to the native implementation. At the native level you have more ability to optimize things, so these results can't be called satisfactory. It may just be the fact that the code complexity of the C implementation is too high to get it right.

--
You received this message because you are subscribed to the Google Groups "elixir-lang-talk" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elixir-lang-ta...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.