[erlang-questions] data sharing is outside the semantics of Erlang, but it sure is useful
James Hague
resulted in a significant memory savings. I'm talking about a
reduction in heap size from 60MB to under half that. By "enforcing the
sharing of data" I mean making sure that identical elements in a data
structure are actually referencing the same locations in memory.
This is easy to do in Erlang, because the compiler is very literal:
fix_tuple({H, H}) -> {H, H};
...
That ensures that identical looking elements in the tuple are sharing
memory locations. But there is absolutely no reason the compiler has
to do this. It would be perfectly valid to optimize away the entire
function, just returning the original value.
Would any existing standard library functions make this nicer? What I
really want is to have a gb_trees:insert function that returns
{NewTree, InsertedValue} where InsertedValue references existing data
(unless it wasn't already in the tree; in that case, InsertedValue is
exactly what I passed in). Then I can happily use InsertedValue,
knowing data is being shared.
James
________________________________________________________________
erlang-questions mailing list. See http://www.erlang.org/faq.html
erlang-questions (at) erlang.org
James Hague
I meant gb_sets. Something like gb_sets:add_shared(Term, Set).
Robert Virding
> > really want is to have a gb_trees:insert function that...
>
> I meant gb_sets. Something like gb_sets:add_shared(Term, Set).
>
I am missing something here. gb_sets (nor sets, ordsets, rbsets) does not
make a copy of the data which is put into the set. All that is copied is
enough of the *tree* to insert the new element. There is no need to copy the
new data as it is kept within the same process. Only ets makes a copy of the
data.
Robert
James Hague
> make a copy of the data which is put into the set. All that is copied is
> enough of the *tree* to insert the new element. There is no need to copy the
> new data as it is kept within the same process. Only ets makes a copy of the
> data.
Let's say you've got a long list of strings. Many of them duplicates.
You don't just want to remove the duplicates because that will change
the length of the list. The goals is to ensure that identical strings
are shared, so there's only one copy in memory. What's a practical
way of doing that?
This is irrelevant most of the time, but there are some situations
where it's a huge win.
(My solution was to build a new list by adding each element to a
binary tree. If a string is already in the tree, return the version
that's already there (which is not something that gb_sets does). In
the resulting list, elements are shared as much as possible. I'm
clearly taking advantage of how the runtime works, but it shrunk the
heap size by tens of megabytes.)
Robert Virding
misfeature, file a bug report and ask them to change it. (Unnecessary as you
don't really need to put in the new element)
I can just point out that neither sets, ordsets nor rbsets do that, they all
leave the original element in. :-)
Robert
2009/9/14 James Hague <james...@gmail.com>
Mikael Pettersson
> I've run into several cases where enforcing the sharing of data
> resulted in a significant memory savings. I'm talking about a
> reduction in heap size from 60MB to under half that. By "enforcing the
> sharing of data" I mean making sure that identical elements in a data
> structure are actually referencing the same locations in memory.
>
> This is easy to do in Erlang, because the compiler is very literal:
>
> fix_tuple({H, H}) -> {H, H};
> ...
>
> That ensures that identical looking elements in the tuple are sharing
> memory locations. But there is absolutely no reason the compiler has
> to do this. It would be perfectly valid to optimize away the entire
> function, just returning the original value.
>
> Would any existing standard library functions make this nicer? What I
> really want is to have a gb_trees:insert function that returns
> {NewTree, InsertedValue} where InsertedValue references existing data
> (unless it wasn't already in the tree; in that case, InsertedValue is
> exactly what I passed in). Then I can happily use InsertedValue,
> knowing data is being shared.
Sounds like you want "hash consing". A hash table keeps track of all
non-immediate terms seen so far. To "intern" a new term you recurse
down to the leaves and compute hashes, on the way up you check if an
equivalent node (e.g. cons/2 or tuple/N) has been seen, and if so
you use that one otherwise you add the new node to the hash table.
Either way you return the interned node and its hash on the way up.
This may lose sharing with the input term, but interned terms will
share everything's that's sharable.
Erlang's default memory model doesn't allow same-node processes to
share memory(*), so you will lose sharing in message sends.
(*) Except in one binaries-related case which is irrelevant here.
A major downside of hash consing is that it can leak memory:
if an interned term becomes unreferenced in the application, the
hash table will still keep a master copy of it, wasting memory.
VMs with built-in support for hash consing usually also support
"weak references" or "weak hashes" where the referenced data can
be nuked if the GC determines that it should be dead.
Ulf Wiger
>
> Erlang's default memory model doesn't allow same-node processes to
> share memory(*), so you will lose sharing in message sends.
Yes, but there are two levels of sharing here.
1. The sharing of terms across processes, as with large binaries
2. The relative sharing within the term itself.
The latter could be preserved using a sharing-preserving copy.
As this is invariably more expensive than the current copying
algorithm when there is no sharing to preserve (likely a very
common case), it is reasonable that this isn't the default.
The problem today is that you cannot make a sharing-preserving
copy between processes at the Erlang level even if your life
depended on it, and in some cases, this may indeed be the case,
figuratively speaking. Some data structures simply cannot be
passed in a message or in a spawn, since the loss of sharing
leads to a memory explosion.
One problem is of course that if a process that has such a
term crashes, and EXIT messages are propagated that contain
the term, the EXIT propagation will kill the node. Even
without loss of sharing, this can happen, of course. I did
it once by spawn-linking 100,000 processes from the shell
and then mis-spelling length(processes()). This led to an
EXIT message, containing a list of 100,000 pids, that was
copied 100,000 times. My workstation was frozen for 10
minutes while the VM was trying to find a way to cope.
No mystery there, of course, and no sharing either.
All I could do was laugh at my stupidity and take an
extra coffee break.
BR,
Ulf W
--
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com
Mikael Pettersson
> Mikael Pettersson wrote:
> >
> > Erlang's default memory model doesn't allow same-node processes to
> > share memory(*), so you will lose sharing in message sends.
>
> Yes, but there are two levels of sharing here.
>
> 1. The sharing of terms across processes, as with large binaries
> 2. The relative sharing within the term itself.
>
> The latter could be preserved using a sharing-preserving copy.
> As this is invariably more expensive than the current copying
> algorithm when there is no sharing to preserve (likely a very
> common case), it is reasonable that this isn't the default.
>
> The problem today is that you cannot make a sharing-preserving
> copy between processes at the Erlang level even if your life
> depended on it, and in some cases, this may indeed be the case,
> figuratively speaking. Some data structures simply cannot be
> passed in a message or in a spawn, since the loss of sharing
> leads to a memory explosion.
So a sharing-preserving term_to_binary might fix the worst
problems, even if it requires some non-default option and
requires users to explicitly wrap and unwrap parts of messages?
Just trying to see if this is something worth pursuing or not.
/Mikael
James Hague
Hash consing is a heavyweight solution. It's got a fixed cost for
something that's usually irrelevant. What I really want is a function
that takes a data structure and returns a new version with maximal
sharing. I can write special case versions of that in Erlang, but
it's messy and feels like something that should be a general library
service.
Witold Baryluk
> > I am missing something here. gb_sets (nor sets, ordsets, rbsets) does not
> > make a copy of the data which is put into the set. All that is copied is
> > enough of the *tree* to insert the new element. There is no need to copy the
> > new data as it is kept within the same process. Only ets makes a copy of the
> > data.
>
> Let's say you've got a long list of strings. Many of them duplicates.
> You don't just want to remove the duplicates because that will change
> the length of the list. The goals is to ensure that identical strings
> are shared, so there's only one copy in memory. What's a practical
> way of doing that?
>
> This is irrelevant most of the time, but there are some situations
> where it's a huge win.
>
> (My solution was to build a new list by adding each element to a
> binary tree. If a string is already in the tree, return the version
> that's already there (which is not something that gb_sets does). In
> the resulting list, elements are shared as much as possible. I'm
> clearly taking advantage of how the runtime works, but it shrunk the
> heap size by tens of megabytes.)
It looks for me as quite good solution, you depend on memory saving, so
explicitly manages to have shared strings:
Any other way i can see is to have this add/retrivial from binary tree,
to be performed implicitly on every step (via some sort of hashing) of
computation to ensure that identical elements are only once in memory
(of one process). But this have really big performance problems i think,
and most of times you really don't need perfect sharing.
You can limit this "hashing" to only terms which are complex enaugh,
like long lists, or nested tuples. But still this is very costly.
If you want to have some term (or list of many terms) and shrink them,
by some magic, you can using following pseudo code:
maximize_sharing(Term) ->
Tree = tree:new(),
NewTree = iterate_over_every_subterm_and_add_first_to_tree(Term),
NewTerm = iterate_over_every_subterm_and_find_in_tree(Term, NewTree).
Lack of sharing is also problematic when sending term_to_binary data,
because term_to_binary essentially flattens term be repeatedly copying
data. It would be nice to have term_to_binary which doesn't copies data
more than once, which already is in the same term.
Ie.
> erlang:process_info(self(), heap_size).
{heap_size,1597}
> X = {2,2,2,2},
Y1 = {X,X,X,X},
Y2 = {Y1,Y1,Y1,Y1},
Y3 = {Y2,Y2,Y2,Y2},
Y4 = {Y3,Y3,Y3,Y3},
Y5 = {Y4,Y4,Y4,Y4},
Y6 = {Y5,Y5,Y5,Y5},
Y7 = {Y6,Y6,Y6,Y6},
Y8 = {Y7,Y7,Y7,Y7},
Y9 = {Y8,Y8,Y8,Y8},
ok.
> erlang:process_info(self(), heap_size).
{heap_size,4181}
>
In memory Y9 will be pretty small, and whole process memory consumption
will be small, but term_to_binary(Y9) (binary with 2MB of data, but not
counting to the heap_size), or just displaying using io_lib:format("~w",
[Y9]) (2MB of data after flattening resulting list) or sending it to
different node will be disaster.
> erlang:process_info(self(), heap_size). % after io_lib:format(), ok.
{heap_size,9707190}
I don't know how it affects sending Y9 to process on the same node.
As we know Y9 need to be copied to heap of the destination process
(because sharing heaps between process destroy soft real-time semantic
of garbage collection, but improves other performance metrics for big
messages). But is it copied smart enough?
> P = spawn(fun() -> P = receive P2 -> P2 end, io:format("~p ~n ~p ~n",
[erlang:process_info(self(), heap_size), size(P)]), ok end), P ! Y9, ok.
{heap_size,2103540}
>
Unfortunately no.
First good step will be to have version of term_to_binary which
preserves sharing of (already shared) subterms (term_to_binary have
second argument for options, like minorversion or gzip compression), and
binary_to_term which understand how to unpack them preserving sharing
(also across
multiple process in the same node, or compact storage in file/db).
--
Witold Baryluk
Paul Mineiro
this thread caught my attention.
to stimulate discussion i pounded out some code that does hash consing
(hashcons:share/1) and that does encoding and decoding suitable for
composition with erlang:term_to_binary/2 (hashcons:encode/1) and
erlang:binary_to_term/1 (hashcons:decode/1). encoded terms don't
necessarily have a smaller wire footprint even in a very favorable case
(see below), but should decode into a shared data structure (as opposed to
calling hashcons:share/1 after calling erlang:binary_to_term/1, which
could create a temporary which is unacceptably huge).
attached.
-- p
% erl
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]
Eshell V5.6.5 (abort with ^G)
1> hashcons:encode (lists:duplicate (10, wazzup)).
{[0,0,0,0,0,0,0,0,0,0],[{0,wazzup}]}
2> size (erlang:term_to_binary (hashcons:encode (lists:duplicate (10, wazzup)), [ compressed ])).
35
3> size (erlang:term_to_binary (lists:duplicate (10, wazzup), [ compressed ])).
31
4> % not always smaller
4> size (erlang:term_to_binary (hashcons:encode (lists:duplicate (100, wazzup)), [ compressed ])).
38
5> size (erlang:term_to_binary (lists:duplicate (100, wazzup), [ compressed ])).
37
Paul Mineiro
is a bugfix:
-- p
--- hashcons.erl.orig 2009-09-15 14:29:30.000000000 -0700
+++ hashcons.erl 2009-09-15 14:29:32.000000000 -0700
@@ -53,7 +53,7 @@
Ref = dict:size (NewDict),
{ Ref,
NewTerm,
- dict:store (NewTerm, { Ref, NewTerm }, NewDict),
+ dict:store (Term, { Ref, NewTerm }, NewDict),
dict:store (Ref, NewTerm, NewCodec)
}
end.
Witold Baryluk
> Unfortunately no.
>
> First good step will be to have version of term_to_binary which
> preserves sharing of (already shared) subterms (term_to_binary have
> second argument for options, like minorversion or gzip compression), and
> binary_to_term which understand how to unpack them preserving sharing
> (also across
> multiple process in the same node, or compact storage in file/db).
>
>
btw. term_to_binary(Y9, [{compressed, 9}]) have size of about 15KB,
and {compressed, 6} (default one) is about 25KB !
(but anyway after binary_to_term heap_size explodes to 2MB).
--
Witold Baryluk
Michael Turner
I'm a curious about how the subject line on this thread, which seems to
me too-easily generalized from the very specific problem James brings
up: saving space when you have a very long list of strings, with some
strings repeated.
If you're representing items of data of any kind in a very long list, I
can only assume it's because the cost of linear access is a non-issue
for your application. If you want to save space by storing only once
the repeated elements in a long, mostly-serial-access list, well, that
reminds of very much of the very general idea of "data compression",
which is also usually used when linear-search access is not much of an
issue, when memory is an issue, and when the data features significant
repetition.
So why not just use compression, if saving space is an important goal and
reducing random-access time is not?
Not sure that I'm totally sold on the Erlang Way of doing things, being
pretty new to the language. But in this particular case (or even for
generalizations of it), I don't see why the Erlang Way (insofar as I
understand it) is necessarily inferior to anything requiring that the
language break with its general shared-nothing approach. Did I miss
something?
-michael turner
Ulf Wiger
>
> Not sure that I'm totally sold on the Erlang Way of doing things, being
> pretty new to the language. But in this particular case (or even for
> generalizations of it), I don't see why the Erlang Way (insofar as I
> understand it) is necessarily inferior to anything requiring that the
> language break with its general shared-nothing approach. Did I miss
> something?
Again, two kinds of sharing here.
'The share-nothing approach' refers to the fact that
there are no shared data structures between processes
(conceptually, as the VM certainly makes use of the
possibility to share stuff anytime it can do so safely.)
The other type of sharing is the implicit sharing /within
an Erlang term/. Consider:
X = lists:seq(1,1000),
Y = {X,X,X,X,X,X,X,X}.
The runtime system will only allocate 2 words for the
tuple + 8 words for the pointers to X. This is
an extremely efficient way of building what's conceptually
a structure of 8000 integers. This is used deliberately by
certain modules. QuickCheck, for example, builds
intricate structures that rely extensively on this type
of sharing. Passing such a structure to another process,
either by spawn or message passing, is generally fatal.
http://erlang.org/pipermail/erlang-bugs/2007-November/000488.html
(This post also contains a nice little program that could
be used to benchmark different solutions.)
I encountered this problem once in a very subtle way,
where I had deliberately relied on implicit sharing
in the state, but happened to pass the entire state
by mistake inside a message.
http://www.erlang.org/pipermail/erlang-questions/2005-November/017924.html
The bug existed for a while, but wasn't noticeable as long
as everything was on the process heap, since the deeply
recursive data structure didn't take up much space.
BR,
Ulf W
--
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com
________________________________________________________________
Michael Turner
On 9/16/2009, "Ulf Wiger" <ulf....@erlang-consulting.com> wrote:
>Michael Turner wrote:
>>
>> Not sure that I'm totally sold on the Erlang Way of doing things, being
>> pretty new to the language. But in this particular case (or even for
>> generalizations of it), I don't see why the Erlang Way (insofar as I
>> understand it) is necessarily inferior to anything requiring that the
>> language break with its general shared-nothing approach. Did I miss
>> something?
>
>Again, two kinds of sharing here.
[Snip]
Interesting answer, but not an answer to my real question. (Maybe I went
on for a paragraph too long.)
It seems that James is interested in data structure sharing IN THIS
PARTICULAR CASE because it gives him a kind of data compression. Again,
if that's the goal, why is ordinary data compression *not* the answer
here? If compression isn't the goal, what did I miss about the
(implicit) problem statement, to which sharing semantics in Erlang *is*
the answer?
-michael turner
James Hague
> PARTICULAR CASE because it gives him a kind of data compression. Again,
> if that's the goal, why is ordinary data compression *not* the answer
> here?
Can you clarify what you mean by "ordinary data compression?"
Jayson Vantuyl
"Semantic Data Compression".
I don't really think that it's useful to classify data sharing as data
compression. Bottom line, there's an optimization (and a clearly
important one) that Erlang isn't doing. Exporting the term to binary
and compressing it isn't particularly fruitful, I suspect.
In a (horrifying) XML example, I think it's the difference between:
<!-- Semantically Compressed -->
<order>
<address id="home">
123 Any St
Any Town, AS USA
</address>
<shipto href="#home" />
<billto href="#home" />
</order>
<!-- Semantically Uncompressed -->
<order>
<shipto>
123 Any St
Any Town, AS USA
</shipto>
<billto>
123 Any St
Any Town, AS USA
</billto>
</order>
The original poster wants to be able to build structures like the
first. It's possible within a single process, but there's a
technicality in that sending the structure via a message expands it.
The second poster is suggesting that you just GZIP the latter. While
this would undoubtedly work, it's extremely clunky, probably not
actually kinder on memory usage (due to generating lots of binaries),
and doesn't really address the problem that an existing optimization
could be generalized to work between processes.
--
Jayson Vantuyl
kag...@souja.net
Zoltan Lajos Kis
> It seems that James is interested in data structure sharing IN THIS
> PARTICULAR CASE because it gives him a kind of data compression. Again,
> if that's the goal, why is ordinary data compression *not* the answer
> here? If compression isn't the goal, what did I miss about the
> (implicit) problem statement, to which sharing semantics in Erlang *is*
> the answer?
>
> -michael turner
>
>
a file, is not different from copying the file, and then tar.gz'ing the two.
The result might be the same space-wise, but there are certain
differences in usability...
Z.
Richard O'Keefe
On Sep 17, 2009, at 4:43 AM, Jayson Vantuyl wrote:
> I don't really think that it's useful to classify data sharing as
> data compression.
It's very much in the spirit of dictionary-based compression.
> Bottom line, there's an optimization (and a clearly important one)
> that Erlang isn't doing.
And can't reasonably be *expected* to do. It is reasonable
to expect Erlang to *preserve* sharing, as when sending a term
to another process, because failing to do so can make space use
blow up in a rather sickening way which it's hard for a
programmer to detect.
I sometimes think that for every use case there is an equal
and opposite use case. In the case of memory, for example,
we've got *space* issues and *cache* issues. Looking for
existing copies of stuff can save you space, but it can
do terrible things to your cache (bringing in stuff that it
turns out you don't want). The tradeoffs depend on how much
space you may save, how likely the saving is, and how well you
can avoid looking at irrelevant stuff while looking for an
existing copy. The programmer is in a better position to know
these things than the Erlang compiler or runtime system.
One thing I didn't quite understand was why the original data
source is emitting stuff with lots of duplication in the first
place. Fixing the duplication problem at the source has the
added benefit of reducing the cost of getting the data into an
Erlang process to start with.
Jayson Vantuyl
> to expect Erlang to *preserve* sharing, as when sending a term
> to another process, because failing to do so can make space use
> blow up in a rather sickening way which it's hard for a
> programmer to detect.
that it preserves sharing unless requested not to.
> I sometimes think that for every use case there is an equal
> and opposite use case. In the case of memory, for example,
> we've got *space* issues and *cache* issues. Looking for
> existing copies of stuff can save you space, but it can
> do terrible things to your cache (bringing in stuff that it
> turns out you don't want). The tradeoffs depend on how much
> space you may save, how likely the saving is, and how well you
> can avoid looking at irrelevant stuff while looking for an
> existing copy. The programmer is in a better position to know
> these things than the Erlang compiler or runtime system.
I'm not suggesting that we do it for every, single piece of data. We
already sort of do it for atoms, most numbers are small enough that
it's not a big win, so the only real question is for lists / tuples /
binaries.
The win for lists and binaries is pretty huge. Binaries are rarely
small. Lists get huge too. I'm not suggesting a full blown hash-cons
solution, but some way to prevent invisible expansion is pretty
critical.
> One thing I didn't quite understand was why the original data
> source is emitting stuff with lots of duplication in the first
> place. Fixing the duplication problem at the source has the
> added benefit of reducing the cost of getting the data into an
> Erlang process to start with.
I've run into this when working with a simple graph algorithm.
Representing edges as {source,dest} was great for atoms and horrible
for strings. All of my tests used atoms, but at runtime, the strings
were being duplicated (because I was messaging them around). It was
noticeable.
Another problem I had was with a backend for the Linux Network Block
Device. I was tossing around disk blocks (4k binaries) and had
pathological memory usage really quickly.
Real development has real problems with unnecessary data duplication.
This is not a matter of optimization. Someone needs to finish one of
the alternate heap implementations. Really.
--
Jayson Vantuyl
kag...@souja.net
Witold Baryluk
There is also another good aspect of preserving sharing.
If we have X = Y = something(), then testing for equality X == Y
is just simple testing (in VM) for pointer first, if they match return
true, if not then test it deeper, if needed, also using this rule, and
eventually in the end use plain value.
This can speed up many things.
It is quite strange to anybody, that for example time complexity
(and memory also as sharing is lost) of algorithm are different in
situations:
1) we built data structure D, and execute algorithm a(D)
2) we build data structure D, send it to P, which then executes a(D).
Difference between them can be very very big factor, and can depend
on the size of D. In pathological situation your algorithm can change
for example from O(n^2) to O(n^4). And i can imagine even bigger
problems than that.
PS. Beyond the fact that message passing and term_to_binary should be
aware of sharing and preserve as much as possible from it (eventualy
with some optional flag), i am also interested with some experimental
hybrid heap approach in erlang.
--
Witold Baryluk
Richard O'Keefe
On Sep 17, 2009, at 1:02 PM, Jayson Vantuyl wrote:
>I've run into this when working with a simple graph algorithm.
>Representing edges as {source,dest} was great for atoms and
>horrible for strings. All of my tests used atoms, but at runtime,
>the strings were being duplicated (because I was messaging them
>around). It was noticeable.
This sounds to me like a perfect example where duplication
should be avoided at the source. Graphs should be sent as
{graph,{NodeNames},[{F1,T1},...,{Fn,Tn}]}
where the Fi and Ti are indices into the {NodeNames} tuple.
>
> Another problem I had was with a backend for the Linux Network Block
> Device. I was tossing around disk blocks (4k binaries) and had
> pathological memory usage really quickly.
>
> Real development has real problems with unnecessary data
> duplication. This is not a matter of optimization. Someone needs
> to finish one of the alternate heap implementations. Really.
There seem to be two issues confused here.
One of them is the fact that when you send a message,
all sharing within the message is removed (except that
large binaries are not supposed to be copied).
We *agree* that this is a bad thing. My message was explicit
that Erlang should preserve sharing.
But it didn't sound as though that's what the original poster
was talking about. I may well have misunderstood; it would
not be the first time.
It's claimed that preserving sharing would raise the cost of
message sending too high. There's an answer to that. Set a
modest threshold, say 100 cells or so, and try the existing
way of sending. But if that threshold is crossed, give up,
and start over with a method that preserves within-message
sharing.
Richard O'Keefe
On Sep 17, 2009, at 2:46 PM, Witold Baryluk wrote:
> It is quite strange to anybody, that for example time complexity
> (and memory also as sharing is lost) of algorithm are different in
> situations:
>
> 1) we built data structure D, and execute algorithm a(D)
> 2) we build data structure D, send it to P, which then executes a(D).
My message explicitly said that I thought that Erlang should
*PRESERVE* sharing, including in message passing. You didn't
need to persuade me of something I already argued for.
The point at issue, as I understood it, was an "OPTIMIZATION",
namely INTRODUCING sharing. For example, if memory serves me
correctly, whenever the Logix implementation of Flat Concurrent
Prolog successfully executed a test X == Y, it smashed one of
them to refer to the other. That's run-time introduction of
sharing. The reason why Logix did that was that they didn't
_have_ atoms, only strings, in order to avoid having to lock
a centralised symbol table. But they wanted strings to _act_
rather like atoms.
I recommend
within a during message
process passing
preserve sharing YES[1] YES[2]
introduce sharing NO NO
[1] This is what Erlang does now.
[2] This is a change, and it's going to be tricky to do it
without slowing "normal" cases down.
And I'm counting term_to_binary/binary_to_term here,
because of their use when messages are passed over a wire.
Michael Turner
On 9/16/2009, "Richard O'Keefe" <o...@cs.otago.ac.nz> wrote:
>
>On Sep 17, 2009, at 4:43 AM, Jayson Vantuyl wrote:
>> I don't really think that it's useful to classify data sharing as
>> data compression.
>
>It's very much in the spirit of dictionary-based compression.
And just so that everybody's clear: I *didn't* "classify data sharing
as data compression." I *asked* what, exactly, in the problem that
James' code is intended to solve, couldn't be solved in classic Erlang
style with data compression? Did I misunderstand the problem?
Oh, and just to be doubly clear: I've used shared data a lot in data
structure design, from the early 1980s onward, and in some shared-memory
multi-processor applications back as far as the late 1980s. I'm not
religiously opposed to data structure sharing. I actually think it can
be kind of cool, in circumstances where it's justified. I just have a
question here, one I'd like see an answer for. I *don't* like seeing
that question re-written into some questions I never asked, much less
into some statements I never made.
-michael turner
Ulf Wiger
>
> I *asked* what, exactly, in the problem that
> James' code is intended to solve, couldn't be solved in
> classic Erlang style with data compression?
Going back to the OP's actual question is a novel concept,
but not nearly as fun as redefining the question into what
suits your own ambition, and going from there. :)
Having re-read what James initially asked for, it seemed
to me as a pretty clever poor-man's version for answering
the question "are these two objects not just equal, but
the /same/ object?". This cannot be done today in Erlang.
If it could, it would be possible to write your own
sharing-preserving term_to_binary().
The suggestion from James was that an access structure
library could fake that by telling the caller "this is
the object I have", and the caller could use that instead,
and thereby achieving a higher degree of sharing.
(To address your question then, compression seems to not
address this problem, as the idea of having clever helper
functions to help make use of sharing implies extremely
lightweight semantics. Often, making use of sharing not
only reduces memory consumption, but also improves
performance, and James' suggesion really doesn't carry
any overhead in terms of execution time - but compression
definitely does.)
The same effect could be achieved by calling gb_trees:find()
first, and then perhaps calling insert, but I assume James
would prefer to achieve this effect without having to access
the tree twice?
But given that an API change is asked for in a set of core
libraries (since the APIs of the different access structures
are harmonized, it wouldn't be just gb_trees), it begs the
question - do we want to promote the use of sharing (inside
terms)? If yes, what does that imply? The big, ugly problem
that needs to be solved then is the one where you can in fact
kill the entire VM if a term that aggressively uses sharing
happens to get passed in a message (which can happen e.g.
if the process crashes and there are linked processes).
BR,
Ulf W
--
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com
________________________________________________________________
Bjorn Gustavsson
> This is easy to do in Erlang, because the compiler is very literal:
>
> fix_tuple({H, H}) -> {H, H};
> ...
>
> That ensures that identical looking elements in the tuple are sharing
> memory locations. But there is absolutely no reason the compiler has
> to do this. It would be perfectly valid to optimize away the entire
> function, just returning the original value.
We have no intention of introducing "optimizations" that would break
that code.
> Would any existing standard library functions make this nicer? What I
> really want is to have a gb_trees:insert function that returns
> {NewTree, InsertedValue} where InsertedValue references existing data
> (unless it wasn't already in the tree; in that case, InsertedValue is
> exactly what I passed in). Then I can happily use InsertedValue,
> knowing data is being shared.
In Wings3D (which is an application that depends heavily on sharing),
I use a gb_tree to keep track of values that I want to share.
I enter each term as both the key and the value and then I just do
gb_trees:get/2
to retrieve the shared value.
/Bjorn
--
Björn Gustavsson, Erlang/OTP, Ericsson AB
Michael Turner
On 9/17/2009, "Ulf Wiger" <ulf....@erlang-consulting.com> wrote:
>Michael Turner wrote:
>>
>> I *asked* what, exactly, in the problem that
>> James' code is intended to solve, couldn't be solved in
> > classic Erlang style with data compression?
>
>Going back to the OP's actual question is a novel concept,
>but not nearly as fun as redefining the question into what
>suits your own ambition, and going from there. :)
You're saying I have some ambition to use data compression in Erlang for
reducing the amount of space taken by a long list of strings with many
repeated strings?
Really?
Why am I not aware of having any such ambition then?
Oh, I see: you misinterpreted what I wrote. (Unless *I'm*
misinterpreting what *you* wrote. Am I?)
>Having re-read what James initially asked for, ....
I just re-read what James initially asked for. Then he changed it when
somebody pointed out a mistake. THEN it became the concrete problem
that I asked about: a long list of strings, with many of them repeated
-- how to save space?
> .... it seemed
>to me as a pretty clever poor-man's version for answering
>the question "are these two objects not just equal, but
>the /same/ object?".
>
>This cannot be done today in Erlang.
So what? If you have unique identifiers for objects stored in some index
structure for efficiently determining whether you've seen one of them
before, why isn't that enough? If that doesn't give you the lightest
of "lightweight semantics", so what? Just by using the right
algorithm for the problem, you get most of the optimization benefits
you're going to get. So what's really important is (as usual) is
understanding the real problem, and what sort of optimizations are
really necessary. Richard O'Keefe pulls back and asks: Why are you
getting a long stream of strings with many repeated in the first place?
Because that IS a problem, and data-sharing might be just a bandaid over
it.
>If it could, it would be possible to write your own
>sharing-preserving term_to_binary().
Yes, and if there was some way embed self-modifying assembly language
code in Erlang, you could ....
Look, there are always lots of possibilities in software, because that's
its defining characteritic. Relatively few of those possibilities are
wise choices. What's the cost of this choice? (Possible answer: yet
another way to crash Erlang, if I understand your reservation expressed
below.)
>(To address your question then, compression seems to not
>address this problem, as the idea of having clever helper
>functions to help make use of sharing implies extremely
>lightweight semantics. Often, making use of sharing not
>only reduces memory consumption, but also improves
>performance, and James' suggesion really doesn't carry
>any overhead in terms of execution time - but compression
>definitely does.)
As Richard pointed out, there is the memory hierachy to be considered.
(And with RAM access time ratios of around 200-to-1 between off-chip
main memory and L1 cache, these days, you're not being realistic about
optimization unless you're thinking about that fact ALL THE TIME, at
least to be sure that it doesn't matter for your problem.) If the
access pattern is usually that you need decompress a portion of a list,
then you read from that portion extensively before moving on, you might
be better off using compression than anything else, simply because it
saves much more memory. That is, it *would*, in the case of a long
list, with many repeated strings, which was the first concrete example
James brought up. But what IS the access pattern? And why is it like
that? Not enough to go on, here.
>The same effect could be achieved by calling gb_trees:find()
>first, and then perhaps calling insert, but I assume James
>would prefer to achieve this effect without having to access
>the tree twice?
I assume we'd all prefer everything to be fast, all the time. That
seems to be a preference at Ericsson. In the telephony switch at
Ericsson that has the most Erlang code in it (AFAIK), there's a lot of
Erlang code. But as I understand it, also a lot of C code in that same
switch. They don't use Erlang in that system for speed. They use it
for robustness and expressive power for the concurrency-oriented aspect
of the system.
>But given that an API change is asked for in a set of core
>libraries (since the APIs of the different access structures
>are harmonized, it wouldn't be just gb_trees), it begs the
>question - do we want to promote the use of sharing (inside
>terms)? If yes, what does that imply? The big, ugly problem
>that needs to be solved then is the one where you can in fact
>kill the entire VM if a term that aggressively uses sharing
>happens to get passed in a message (which can happen e.g.
>if the process crashes and there are linked processes).
I'm looking at Erlang for implementing a linguist's model of cognition.
The data structures required to do this involve not just a lot of
sharing, but a lot of circularity.
I've decided (I hope wisely) that the best way to represent these data
structures is to have nodes represented by processes, and links between
the nodes represented by process IDs, and have the amount of data at
each node, and in each message, bounded by a small constant. I might
use the digraph library to maintain a map that mirrors the process
structure. But if it turns out I don't have to do that, I might not.
I'm not looking at doing it this way to save memory. Nor am I doing it
to make the thing faster (except perhaps in some very long term view, in
which going concurrency-oriented is the ultimate speedup). I'm taking
this approach because it looks like the best way to make the thing
actually work. Which, interestingly, is also very important in
telephony.
In a paper I can't immediately identify right now, the authors remarked
that Erlang programmers often spend a fair amount of time trying to
measure what's fast in Erlang, then writing stuff using what they
discover is fast. The authors were disturbed, saying that they'd
prefer that Erlang programmers implement things so as to be *clear* in
Erlang, so that maintainers of the Erlang interpreter and compiler would
know what to target for optimization.
And now we have James Hague pointing out that an ambiguity (?) in Erlang
semantics means that he's now got a great optimization, but one that
might go away if Erlang is allowed to optimize it out. Well, C is
really great for optimizing stuff, but I've had my "lightweight
semantics" optimizations in that language optimized out by a subsequent
release of the compiler, and I deserved what I got. One of C's
co-designers contributed the now-famous saying: "Premature optimization
is the root of all evil in software." Probably because, with that
language being what it is, he'd seen a lot more evil than most of us.
It's hard habit to acquire (because optimization can be so much fun),
but it's a good one: the habit of asking yourself, in contemplating an
optimization, "Would this solve the real problem? Or just compensate
for it?" Sometimes (especially in legacy computing environments)
compensation is the best you can do -- there's a black box you can't
get into and fix. But if that's the reason, you should know it. And
if there's a better language for those compensating optimizations, you
should use it.
-michael turner
Michael Turner
On 9/17/2009, "Bjorn Gustavsson" <bgust...@gmail.com> wrote:
>On Mon, Sep 14, 2009 at 6:22 PM, James Hague <james...@gmail.com> wrote:
>> This is easy to do in Erlang, because the compiler is very literal:
>>
>> fix_tuple({H, H}) -> {H, H};
>> ...
>>
>> That ensures that identical looking elements in the tuple are sharing
>> memory locations. But there is absolutely no reason the compiler has
>> to do this. It would be perfectly valid to optimize away the entire
>> function, just returning the original value.
>
>We have no intention of introducing "optimizations" that would break
>that code.
But is James correct in implying that the semantics of Erlang admit of
such interpretations?
-michael turner
Bjorn Gustavsson
>>>
>>> That ensures that identical looking elements in the tuple are sharing
>>> memory locations. But there is absolutely no reason the compiler has
>>> to do this. It would be perfectly valid to optimize away the entire
>>> function, just returning the original value.
>>
>>We have no intention of introducing "optimizations" that would break
>>that code.
>
> But is James correct in implying that the semantics of Erlang admit of
> such interpretations?
Probably. As far as I know, there is no specification or documentation
that explicitly says that an Erlang implementation must preserve
sharing within a process.
/Bjorn
--
Björn Gustavsson, Erlang/OTP, Ericsson AB
________________________________________________________________
Ulf Wiger
>
> On 9/17/2009, "Ulf Wiger" <ulf....@erlang-consulting.com> wrote:
>
>> Michael Turner wrote:
>>> I *asked* what, exactly, in the problem that
>>> James' code is intended to solve, couldn't be solved in
>>> classic Erlang style with data compression?
>> Going back to the OP's actual question is a novel concept,
>> but not nearly as fun as redefining the question into what
>> suits your own ambition, and going from there. :)
>
> You're saying I have some ambition to use data compression in Erlang for
> reducing the amount of space taken by a long list of strings with many
> repeated strings?
No, I'm not saying that. But if you do, I have no
problem with it. :)
> Oh, I see: you misinterpreted what I wrote.
That's what I meant, and pls note the smiley.
I was just jokingly alluding to the fact that discussions
often meander away from what the original poster was
asking for.
>> Having re-read what James initially asked for, ....
>
> I just re-read what James initially asked for. Then he changed it when
> somebody pointed out a mistake. THEN it became the concrete problem
> that I asked about: a long list of strings, with many of them repeated
> -- how to save space?
It basically split into different sub-threads, one being
about the basic issues of implicit sharing within terms
(in which some posters confused this sort of sharing with
the no-shared semantics of concurrent Erlang.)
James also wrote that he wanted a BIF that would find
possibilities of sharing in a term and exploit them.
Some posts refered to the "built-in compression" available
in Erlang in the form of term_to_binary(Term, [compressed]).
I think one could say that compressing using term_to_binary/2
is at the far end of the spectrum in this matter. If you
compress to a binary, you lose every possiblity of pattern
matching (except check for equality), where as "compression"
using implicit sharing is completely transparent to pattern
matching.
That is, through fairly simple means, you can make use of
sharing and still keep to ideomatic Erlang. Depending on the
problem, sharing can give amazing yield with minimal work.
>> .... it seemed
>> to me as a pretty clever poor-man's version for answering
>> the question "are these two objects not just equal, but
>> the /same/ object?".
>>
>> This cannot be done today in Erlang.
>
> So what? [...]
>
>> If it could, it would be possible to write your own
>> sharing-preserving term_to_binary().
>
> Yes, and if there was some way embed self-modifying assembly
> language code in Erlang, you could ....
>
> Look, there are always lots of possibilities in software,
> because that's its defining characteritic. Relatively few
> of those possibilities are wise choices. What's the cost
> of this choice? (Possible answer: yet another way to crash
> Erlang, if I understand your reservation expressed
> below.)
There are several problems where smart data structures
can be used /only/ if one is allowed to rely on implicit
sharing. I'm pretty sure that QuickCheck, for example,
relies heavily on it, and also has a serious problem
with the fact that the 'rule base' cannot be passed
to another process. This has to do with another aspect
of Erlang - if the process controlling a test run receives
an untrappaple exit, the shrinking process won't work,
since all information about the run will be gone.
The simple remedy would be to spawn a process that
executes one run and then reports back, but this can't
be done, since the data structure that needs to be
passed along 'explodes'.
This particular case in itself answers the 'so what'.
If it had been feasible to do it in Erlang, the authors
of QuickCheck surely would have done it by now. Also,
I would not dream to suggest that they should simply
choose another data structure in order to solve the
problem. Their knowledge in that area far exceeds mine.
I've also had discussions with experienced Haskell and
OCaml programmers who felt that the loss of sharing when
sending data from one node to another was sufficient
reason in itself not to use Erlang - since the use of
sharing in functional programming is such a powerful tool.
Obviously, I don't share the view that this disqualifies
Erlang entirely, but at least I'm not alone in thinking
that (a) sharing is a good thing, and (b) the occasional
loss of sharing, partly beyond the programmer's control,
is a bad thing.
> I assume we'd all prefer everything to be fast, all the time. That
> seems to be a preference at Ericsson. In the telephony switch at
> Ericsson that has the most Erlang code in it (AFAIK), there's a lot of
> Erlang code. But as I understand it, also a lot of C code in that same
> switch. They don't use Erlang in that system for speed. They use it
> for robustness and expressive power for the concurrency-oriented aspect
> of the system.
OT, but this is not a correct description.
I assume you refer to the AXD 301? Most of the C code in the AXD 301
is low-level device processor code, written in C mainly for historical
reasons. In the first versions, those device processors did not have
the CPU or memory capacity to run Erlang, and instead ran VRTX - later
OSE Delta. The programming style in that environment led to a lot of
code duplication (there were more than 100 different device boards
produced in the AXD 301 over the years). While it was correct then
that it wouldn't have been possible to use Erlang at all, much less
get sufficient characteristics with it, newer generations of ARM
processors and the cost of RAM changed that. It would have been
possible to use Erlang in the modern device boards of the AXD 301,
and in many ways it would be preferable, but the cost of re-writing
the core device board software made it a fairly uninteresting
alternative at the end - the move to a more homogeneous network
architecture and using IP across the board also changed the
balance between control processor development and device processor
development.
There were other blocks of C code, in the form of 3rd party
applications that were integrated rather than writing everything
from scratch. This was not done for performance, usually,
but more because of market considerations, and sometimes
credibility (it's not necessarily a good idea to start writing
your own BGP stack, for example, as a buggy BGP stack can cause
endless trouble on the Internet).
Indeed, it has been the experience at Ericsson that for
signaling applications, Erlang application often have outstanding
performance, especially when aspects such as load tolerance
and portability to new and more powerful architectures are
taken into account. This was also shown by the Herriott-Watt
studies together with Motorola.
Having said this, it is certainly true that the main reason
for using Erlang is that it offers a very productive way
of reaching a robust and well-working system. As Joe often says,
if the product is /fast enough/, this is much more important
than raw speed.
> In a paper I can't immediately identify right now, the authors remarked
> that Erlang programmers often spend a fair amount of time trying to
> measure what's fast in Erlang, then writing stuff using what they
> discover is fast. The authors were disturbed, saying that they'd
> prefer that Erlang programmers implement things so as to be *clear* in
> Erlang, so that maintainers of the Erlang interpreter and compiler would
> know what to target for optimization.
I don't know which paper you are refering to, but this is an
argument that I have personally put forth several times in various
contexts, on this list and elsewhere. The problem is not
just that people write 'optimized' code at the expense of clarity.
They often end up optimizing things that don't matter, and miss
things, like algorithm optimization that really does.
BR,
Ulf W
--
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com
________________________________________________________________
James Hague
Originally, what I wanted was a way to manually make sure that terms
are shared. This is easy to do by having a data structure function
that works like this:
{New_Tree, Item_in_Tree} = some_tree:insert(Tree, Item)
None of the library functions have this, as far as I can tell. I pass
in a some data item, like a string, and it gets searched for in a tree
(or similar data structure). If it exists, the same tree and a pointer
to the item already in the tree are passed back. I can use the
returned item rather than the original, knowing that sharing is
occurring if it's possible. If the item doesn't exist, then I get back
the new tree and exactly the same item I passed in.
The reason I brought up Erlang semantics here, is that so that the
check for if something is shared or not could be handled at the
runtime level.
A tangential topic is about enforcing sharing across all data
structures--with hash consing, for example--but that's a major change
that doesn't make sense.
Then there's the issue of terms with shared data blowing up when
converted to a binary and back, or sent to another process. This is a
potentially critical flaw in some cases, but it's more easily dealt
with than the previous paragraph. And it's not what I was originally
talking about :)
Ulf Wiger
> I've run into several cases where enforcing the sharing of data
> resulted in a significant memory savings.
BTW, here is an example from OTP, written by Robert Virding,
no less, so it has to be an example of the type of code
that for which Erlang was originally intended. :)
%% expand_segs(Segs, EmptySeg) -> NewSegs.
%% contract_segs(Segs) -> NewSegs.
%% Expand/contract the segment tuple by doubling/halving the number
%% of segments. We special case the powers of 2 upto 32, this should
%% catch most case. N.B. the last element in the segments tuple is
%% an extra element containing a default empty segment.
expand_segs({B1}, Empty) ->
{B1,Empty};
expand_segs({B1,B2}, Empty) ->
{B1,B2,Empty,Empty};
expand_segs({B1,B2,B3,B4}, Empty) ->
{B1,B2,B3,B4,Empty,Empty,Empty,Empty};
expand_segs({B1,B2,B3,B4,B5,B6,B7,B8}, Empty) ->
{B1,B2,B3,B4,B5,B6,B7,B8,
Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty};
expand_segs({B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16},
Empty) ->
{B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16,
Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty,
Empty,Empty,Empty,Empty,Empty,Empty,Empty,Empty};
expand_segs(Segs, Empty) ->
list_to_tuple(tuple_to_list(Segs)
++ lists:duplicate(tuple_size(Segs), Empty)).
It is from dict.erl, and used to expand the hash table.
Very deliberate use of sharing.
BR,
Ulf W
--
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com
________________________________________________________________
Paul Mineiro
> Wow, this discussion has blown up :)
>
> Originally, what I wanted was a way to manually make sure that terms
> are shared. This is easy to do by having a data structure function
> that works like this:
>
> {New_Tree, Item_in_Tree} = some_tree:insert(Tree, Item)
>
> None of the library functions have this, as far as I can tell. I pass
> in a some data item, like a string, and it gets searched for in a tree
> (or similar data structure). If it exists, the same tree and a pointer
> to the item already in the tree are passed back. I can use the
> returned item rather than the original, knowing that sharing is
> occurring if it's possible. If the item doesn't exist, then I get back
> the new tree and exactly the same item I passed in.
I did post a solution to this (hashcons:share/1).
Basically, (as I understand it) any of the standard associative maps you
can insert the same term as key and value and then use the value returned,
and that value will be shared with the associative map. (I'm not sure if
all of the standard *set* implementations have this property).
-- p
Raoul Duke
>> prefer that Erlang programmers implement things so as to be *clear* in
>> Erlang, so that maintainers of the Erlang interpreter and compiler would
>> know what to target for optimization.
> just that people write 'optimized' code at the expense of clarity.
> They often end up optimizing things that don't matter, and miss
> things, like algorithm optimization that really does.
yup, and it ain't just in Erlang. (as already alluded to re: c.) oh
the humanity of all the wasted effort and cpu cycles. :(
James Hague
Yup, and it was nice to see. My code is actually similar to that.
James
James Hague
> I use a gb_tree to keep track of values that I want to share.
> I enter each term as both the key and the value and then I just do
> gb_trees:get/2 to retrieve the shared value.
That is an excellent idea! I was trying to hard to use gb_sets here :)
Michael Turner
On 9/17/2009, "Ulf Wiger" <ulf....@erlang-consulting.com> wrote:
>Some posts refered to the "built-in compression" available
>in Erlang in the form of term_to_binary(Term, [compressed]).
>
>I think one could say that compressing using term_to_binary/2
>is at the far end of the spectrum in this matter. If you
>compress to a binary, you lose every possiblity of pattern
>matching (except check for equality), ...
That's funny. I just unzipped a file, looked at it in an editor, and
did a search.
What you apparently mean is "you lose every possibility of pattern
matching DIRECTLY on the compressed representation". But if you
selectively decompress parts of the long list, with some global
dictionary for the more repeated parts, clearly one can do pattern
matching on it. Will performance necessarily be poorer? It depends on
the data and its access patterns. If you can't characterize those, any
optimization attempt will be a shot in the dark anyway.
>This [case of QuickCheck] case in itself answers the 'so what'.
>If it had been feasible to do it in Erlang, the authors
>of QuickCheck surely would have done it by now. Also,
>I would not dream to suggest that they should simply
>choose another data structure in order to solve the
>problem. Their knowledge in that area far exceeds mine.
Well, I guess I wouldn't dream of asking them to choose another data
structure either. But maybe I would dream of asking them to choose a
different *process* structure. If passing a rules-base around causes
explosions, how about ... well, NOT passing a rules-base around? How
about moderating access to the rules-base via processes and messages?
After all, even if that incurs a performance penalty, it's still a
testing framework, and very likely the code under test will be soaking
up most of the cycles. Maybe they didn't do this because that's not
how they originally designed the whole thing, and they just didn't want
to bother redesigning it to be more loosely coupled in that respect?
>I've also had discussions with experienced Haskell and
>OCaml programmers who felt that the loss of sharing when
>sending data from one node to another was sufficient
>reason in itself not to use Erlang - since the use of
>sharing in functional programming is such a powerful tool.
>Obviously, I don't share the view that this disqualifies
>Erlang entirely, but at least I'm not alone in thinking
>that (a) sharing is a good thing, and (b) the occasional
>loss of sharing, partly beyond the programmer's control,
>is a bad thing.
Again, I'm new to this, but my understanding of Erlang is that it's not
a functional language per se -- it's a concurrency-oriented language in
which processes are specified in functional terms. If you're not used
to that emphasis, you won't consider concurrency at every turn, and you
might have accumulated design and coding habits that don't match the
semantic emphasis of Erlang, even if you come from a functional
programming background.
In any case, Erlang's problem as a small minority language isn't to
please the users of other small minority languages so much that it gains
followers from those camps. It's how to make itself understood -- and
increasingly used for its strengths -- in a much larger software
community, while also becoming more palatable in the process, where it
can do it without compromise of its principle. If I had to choose
between better syntax and semantics for records and better support for
structure sharing, I'd *definitely* ask for better support for records,
at this point.
>> I assume we'd all prefer everything to be fast, all the time. That
>> seems to be a preference at Ericsson. In the telephony switch at
>> Ericsson that has the most Erlang code in it (AFAIK), there's a lot of
>> Erlang code. But as I understand it, also a lot of C code in that same
>> switch. They don't use Erlang in that system for speed. They use it
>> for robustness and expressive power for the concurrency-oriented aspect
>> of the system.
>
>OT, but this is not a correct description.
>
>I assume you refer to the AXD 301? Most of the C code in the AXD 301
>is low-level device processor code, written in C mainly for historical
>reasons. In the first versions, those device processors did not have
>the CPU or memory capacity to run Erlang, and instead ran VRTX - later
>OSE Delta.
[snip]
What it seems to come down to is: Erlang would have overloaded much of
the original hardware, if it would fit at all, so C/real-time-OS was the
better solution at one point. Later, these components came to closely
match my description of "black boxes you can't get into and fix", for
a variety of reasons including the prohibitive cost of doing that.
Except for cases like these ...
>There were other blocks of C code, in the form of 3rd party
>applications that were integrated rather than writing everything
>from scratch.....
which were designed in for other reasons that make them virtual black
boxes that you can't get inside of and fix.
Believe me, I spent some time in the trenches in telecom, I know
first-hand how the spaghetti pile grows.
All of which seems to be drifting away from a point: sure, it's nice to
have things arranged so that you can express things naturally in a
language and it will be guaranteed to be fast, or save memory, or have
some other nice feature. But there's often a hidden or delayed cost.
Remote procedure calls, for example, seemed like the natural
"idiomatic" way to do interprocess communication. *Seemed*. For a
long time. And to some very smart people, too.
-michael turner
Toby Thain
On 17-Sep-09, at 7:05 AM, Michael Turner wrote:
> ...
> In a paper I can't immediately identify right now, the authors
> remarked
> that Erlang programmers often spend a fair amount of time trying to
> measure what's fast in Erlang, then writing stuff using what they
> discover is fast. The authors were disturbed, saying that they'd
> prefer that Erlang programmers implement things so as to be *clear* in
> Erlang, so that maintainers of the Erlang interpreter and compiler
> would
> know what to target for optimization.
This is true of any language, I think, and particularly true of
declarative languages (I am thinking of SQL, for example).
>
> And now we have James Hague pointing out that an ambiguity (?) in
> Erlang
> semantics means that he's now got a great optimization, but one that
> might go away if Erlang is allowed to optimize it out. Well, C is
> really great for optimizing stuff, but I've had my "lightweight
> semantics" optimizations in that language optimized out by a
> subsequent
> release of the compiler, and I deserved what I got. One of C's
> co-designers contributed the now-famous saying: "Premature
> optimization
> is the root of all evil in software."
To be pedantic, I think that was actually Professor Knuth*.
--T
> Probably because, with that
> language being what it is, he'd seen a lot more evil than most of us.
>
> It's hard habit to acquire (because optimization can be so much fun),
> but it's a good one: the habit of asking yourself, in contemplating an
> optimization, "Would this solve the real problem? Or just compensate
> for it?" ...
>
> -michael turner
>
* http://shreevatsa.wordpress.com/2008/05/16/premature-optimization-
is-the-root-of-all-evil/
+ http://www-cs-staff.stanford.edu/~uno/