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

--===============0093861011774027394==
Content-Type: multipart/alternative; boundary=047d7bb709d2651998051b634e45

--047d7bb709d2651998051b634e45
Content-Type: text/plain; charset=UTF-8

On Tue, Jul 21, 2015 at 9:45 AM, ruanbeihong <[email protected]> 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.

--047d7bb709d2651998051b634e45
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra"><br><div class=3D"gmail_quote">=
On Tue, Jul 21, 2015 at 9:45 AM, ruanbeihong <span dir=3D"ltr">&lt;<a href=
=3D"mailto:[email protected]" target=3D"_blank">[email protected]</=
a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I think it&#39;s the=
 last thing to think about when writing codes. You&#39;d expect the compile=
r to do such &#39;update inline&#39; optimization for you.</blockquote></di=
v><br></div><div class=3D"gmail_extra">It is a very true statement. But the=
re 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.<br><br></div><div =
class=3D"gmail_extra">Also, there are limits to a functional programming la=
nguage. 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 ev=
aluation 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 fash=
ion.<br><br></div><div class=3D"gmail_extra">Programming languages which su=
pport linear access for updates usually annotate access in a type/effect sy=
stem (ATS, Rust comes to mind). And thus they have an easier time optimizin=
g since they can rely on the program being well-typed or well-effected.<br>=
<br></div><div class=3D"gmail_extra">All of this said, functional languages=
 commonly have GCs which are extremely good at handling high allocation rat=
es. 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 mode=
rn CPUs: papers from the 90&#39;es show that usually, memory is less of an =
issue than first thought. But here, 20 years later, it is about time to red=
o those old findings.<br><br></div><div class=3D"gmail_extra"><br clear=3D"=
all"><br>-- <br><div class=3D"gmail_signature">J.</div>
</div></div>

--047d7bb709d2651998051b634e45--

--===============0093861011774027394==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--===============0093861011774027394==--