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

[Jesper Louis Andersen]

On Tue, Jul 21, 2015 at 9:45 AM, ruanbeihong <ruanbeihong@REDACTED> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-patches/attachments/20150721/b6f0ba7b/attachment.htm>