![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Warp wrote:
> It would be less efficient because it would require always deep-copying
> data when it's passed around?
Basically. Deep-copying and duplicating.
If I say
X is a list [1, 2, 3]
Y is a list prepending 0 to X
Z is a list prepending 9 to X
then X is still out there only once, and Y and Z point to it. Lists are
"linked lists" rather than array-like lists.
>> The real situation is of course a bit more complicated than this, but
>> you get the idea.
>
> It looks like a really inefficient way of computing a simple calculation.
It's a lazy calculation. Hopefully the compiler can figure out when it
doesn't actually need to do that.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 11/11/2010 12:38 PM, Darren New wrote:
>
> It's a lazy calculation. Hopefully the compiler can figure out when it
> doesn't actually need to do that.
>
However, as I understand it (keeping in mind that I don't actually know
Haskell) it does have the implication that it can be much harder to
reason about the efficiency of a program, since it depends quite a bit
on what tricks the compiler can use. This is in contrast to a language
like C where the relative simplicity of the compiler means that the
approximate performance is much more obvious.
It seems like a pretty common double-edged sword. Smarter systems often
allow you to do things more easily at the cost of the need for more
mental space required to know when the smart system will fail and how to
correct it.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Kevin Wampler wrote:
> It seems like a pretty common double-edged sword.
Yep.
> Smarter systems often
> allow you to do things more easily at the cost of the need for more
> mental space required to know when the smart system will fail and how to
> correct it.
I think the best model is something SQL-like. Where you express the
semantics of what you want, and then in a separate place say "by the way,
here's hints to make it faster."
It's also the case that, generally speaking, there are on occasion things
you can make more efficient in a higher-level language than a lower-level
language, simply because there's more information about intent there. As in,
it's way easier for C to micro-optimize my call to memcpy() than it is to
micro-optimize my while loop that does semantically the same thing. And it's
way easier for the SQL interpreter to figure out the best access pattern
than it is for my C compiler to analyze my code along with the BDM to figure
out how to optimize access.
Unfortunately, there are relatively few high-level languages that actually
give you the option of telling the system how best to optimize stuff, even
tho the concept has been around for ages.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 11/11/2010 05:19 PM, Warp wrote:
> Invisible<voi### [at] dev null> wrote:
>> I always used to think that creating a data structure who's size is not
>> statically known required handling it by reference. However, C++ somehow
>> manages to do this by value, so it seems my assumptions are incorrect.
>
> No, dynamically allocated objects can only be handled with a pointer.
> You can of course wrap that pointer so that it looks and behaves like
> the allocated object itself, but as if handled by-value (including being
> scope-bound).
>
> For example you can handle an instance of std::vector or std::string
> by value, but internally they contain a pointer to dynamically allocated
> memory (which they manage).
I see. (I think!) So, presumably, when you copy std::vector "by value",
all it's actually copying is the reference to the real data?
>> In fact, thinking about it, you probably /could/ implement Haskell
>> without GC. It would just be far less efficient, that's all.
>
> It would be less efficient because it would require always deep-copying
> data when it's passed around?
That's one reason.
The other reason is that Haskell expressions are not restricted to being
*trees*. They can be general *graphs*. This is how you implement a
common sub-expression such that it only gets computed once - a very
useful thing to be able to do (obviously). I'm not quite sure how this
would interact with a non-GC implementation.
>> The real situation is of course a bit more complicated than this, but
>> you get the idea.
>
> It looks like a really inefficient way of computing a simple calculation.
It is. That's why there's an entire optimiser pass dedicated to removing
all these steps if possible. If a, b and x are just plain ordinary
integers, it's highly likely that the final machine code will just chuck
those variables into machine registers and do the usual binary
arithmetic directly.
Of course, all of this graph reduction /is/ pointless for a simple piece
of arithmetic. But if we choose a less trivial example, it becomes clear
why it's useful. For example, that old chestnut of the Fibonacci
function where the output depends on the output. That's impossible in a
normal language, but trivial in Haskell.
(Obviously no programmer in history has actually /needed/ the Fibonacci
numbers. And if they did, there's a well-known O(1) algorithm for them
anyway. It's just an example.)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
> ...and now I'm reading about Agda, a programming language which has
> MELTED MY MIND! >_<
Idris is similar, with moderately less mind-meltation. Even so, all of
the documentation is clearly written for somebody already familiar with
the idea and just wanting to learn the actual syntax.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Darren New <dne### [at] san rr com> wrote:
> > It looks like a really inefficient way of computing a simple calculation.
> It's a lazy calculation. Hopefully the compiler can figure out when it
> doesn't actually need to do that.
It's provable (no, not a typo of "probable", different thing) that, in
the general case, the problem "will this line of code ever be executed?"
is an unsolvable problem. Hence a compiler can make that decision only
in the most trivial cases.
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> I see. (I think!) So, presumably, when you copy std::vector "by value",
> all it's actually copying is the reference to the real data?
Actually, when you assign an std::vector object to another, whether it
performs a deep-copy of the data or if it uses some copy-on-write mechanism
to perform lazy copying depends on the library implementation, but AFAIK
most if not all library implementations use deep-copying.
Thus, if you assign one std::vector object to another, all the data it
contains will be copied as well.
Of course if you want copy-on-write instead, then you can create your own
"vector" which does that. (I have actually done precisely this for some
projects because of the benefits of this technique.)
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> It's a lazy calculation. Hopefully the compiler can figure out when it
>> doesn't actually need to do that.
>
> It's provable (no, not a typo of "probable", different thing) that, in
> the general case, the problem "will this line of code ever be executed?"
> is an unsolvable problem. Hence a compiler can make that decision only
> in the most trivial cases.
More tractable is "if X is executed then Y is definitely executed". For
example, the arguments to (+) [over integers] will always be executed.
Therefore, any code that calls (+) can just pass two integers, rather
than bothering to build a graph of heap objects to pass.
It would be one thing if the compiler knew about the special properties
of built-in functions like (+). But in fact it performs a "strictness
analysis" pass which infers this information for all user-written code.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |