Re: Immutable Datastructures with good Sharing

On 11-11-05 09:20 PM, markspace wrote:
On 11/5/2011 1:41 PM, Jan Burse wrote:
Arne Vajhøj schrieb:

How do you know that the clone solution use more CPU than
the solution you are looking for now??

It has been proven for the stack.


I'd like to see that proof. I think this is the fundamental disconnect
most people are having on this thread. What is an immutable stack
actually good for? There's nothing that comes to my mind.

Concurrency. Immutable data structures help in that environment -
nothing special about stacks in that regard.

But a friend of mine implemented the same application,
and he has a different solution for the queue and
is orders of magnitude faster.

Cloning or copying has got to be slow. I'd bet this is why your
solution is slow, even if you don't realize it.

If you are actually really cloning, or copying everything. If you are
looking to implement efficient persistent data structures then the only
bits you copy are the modified bits. The unmodified bits are shared, and
are still immutable.

AHS
--
You should know the problem before you try to solve it.
Example: When my son was three he cried about a problem with his hand. I
kissed it several times and asked him about the problem. He peed on his
hand.
-- Radia Perlman, inventor of spanning tree protocol
.

Relevant Pages

  • Forth Frustrations
    ... I was working on an interface to my new window system in Ficl. ... have more than 3 or 4 items on the stack at once. ... Now unmotivated and realizing that the structure really sucks in my Ficl ... Data structures, not algorithms, are central to ...
    (comp.lang.forth)
  • Re: Human stack shufflers ?
    ... The problem with using locals in this example is that they're ... usefully and efficiently as properly used persistent data structures. ... The choice, IMO, isn't between locals and stack thrashing, it's ... The low-level word was DRAW, which took a desired y,x position on the stack and moved the beam from CURRENT to that position. ...
    (comp.lang.forth)
  • Re: Forth Frustrations
    ... I found it extremely frustrating to juggle around data on the stack, such as 2 RGBA color components when building a gradient. ... Data structures, not algorithms, are central to programming. ... In the Windows environment, you often have to put together immense lists of parameters for an OS call. ... I'm not at all familiar with Ficl, but the products from FORTH, Inc. as well as other modern Forths I'm familiar with have excellent facilities for setting up application-specific data structures. ...
    (comp.lang.forth)
  • Re: interesting problem
    ... Are you going to use a stack, queue, ... > of those data structures, as long as you're allowed to use ... This depend on what you understand under "recursion". ... this sense syntactical recursion still uses "stack". ...
    (comp.lang.c)
  • Re: difference between stack & heap (general, for a newbie)
    ... understand how these two data structures are implemented when your C++ ... What I should've asked is "what is the scope of data when allocated ... stack (where ``heap'' and ``stack'' are not standards, ... allocated on the stack versus those allocated on the heap, ...
    (comp.lang.cpp)