Re: [erlang-questions] How to Update List Elements A Lot

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: [erlang-questions] How to Update List Elements A Lot

ruanbeihong

I think it's the last thing to think about when writing codes. You'd expect the compiler to do such 'update inline' optimization for you.

 

I'm not quite sure that the compiler do does that kind of optimization, but I will consider to use C port when performance is really critical problem when profile test proved it.

 

 

On Tuesday 21 July 2015 12:00:04 Hugo Wang wrote:

Hi all,


I'm writing an encrypt/decrypt stuff in Erlang, the input and output are both lists (or binary). In other words, I need to generate a list of bytes based on another list of bytes. During the generating there are a lot of band, bor, bxor, bsl, bsr, etc operations. Every element in the new list (the output) would be updated many times.


In other language, like C or Python, we can init an output list and then update its elements inline. In Erlang, what I currently do, would make a copy of the list every time when an element need to update. This looks not quite right.


Any comments/ideas on this? I want to use pure Erlang to implement it, rather than making a C port.


Thanks,

Hugo



--

 

James Ruan


_______________________________________________
erlang-patches mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-patches
Reply | Threaded
Open this post in threaded view
|

Re: [erlang-questions] How to Update List Elements A Lot

Jesper Louis Andersen-2

On Tue, Jul 21, 2015 at 9:45 AM, ruanbeihong <[hidden email]> wrote:
I think it's the last thing to think about when writing codes. You'd expect the compiler to do such 'update inline' optimization for you.

It is a very true statement. But there are limits to what kind of transformations you can expect of a compiler. If you have used lists with lots of lists:keyreplace/4 for instance, then the compiler is not clever enough to transform this to a list comprehension, which turns an O(n^2) algorithm into a O(n) algorithm.

Also, there are limits to a functional programming language. In-place updates requires the compiler to prove that access to the data is truly linear. If you have lots of cross-module calls, the Erlang evaluation model somewhat constrains you, because if a module is loaded while the cross-module calls are being done, then you expect the code to jump to the new version. And the new version may use the data in a non-linear fashion.

Programming languages which support linear access for updates usually annotate access in a type/effect system (ATS, Rust comes to mind). And thus they have an easier time optimizing since they can rely on the program being well-typed or well-effected.

All of this said, functional languages commonly have GCs which are extremely good at handling high allocation rates. Non-live data on the heap has 0 reclamation cost in the Erlang BEAM VMs GC for instance. The primary problem here is the memory bottleneck in modern CPUs: papers from the 90'es show that usually, memory is less of an issue than first thought. But here, 20 years later, it is about time to redo those old findings.



--
J.

_______________________________________________
erlang-patches mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-patches