Re: Questions from a Beginner.
- Posted by jimcbrown (admin) May 20, 2009
- 1234 views
No, you're right. But you still misrepresent the issue somewhat: In EU this O(n) vs. O(1) is not a deliberate design tradeoff that can be made by the programmer, because often O(1) cannot be achieved at all with the given semantics. It seems not even a consious tradeoff by the language designer, but a big design flaw that has been overlooked for years.
I don't know what you and Matt are specifically referring to now about the O(n) issue
I believe he's referring to copy on write when assigning to a sequence element. At least, that's the assumption I've been making in my responses.
Ok. So then basically, what he is saying when he says "the design of Euphoria is worse than I realized", is that he thinks COW is bad design. Hmm.
I don't think this (your assumption) is right, see below.
Consider the following code:
function set_element( sequence s, integer element, object value ) s[element] = value return s end function sequence foo = {"a","b", "c"} foo = set_element( foo, 1, "A" )
When the assignment to s happens, it must first be copied, since there are multiple references on the sequence. The copying itself is O(n), because it depends upon the length of the sequence.
Derek provided a way to achieve the O(1) result, by storing the sequence in some other container, and using what is effectively a pointer, which implements passing by reference.
And Critic posted a modified version which was suppose to be slower, but Derek proved was faster.
(He did have a valid point about Derek's version being able to cause a memory leak, but with the new delete and delete_routine functionality that issue has been solved.)
Anyways, my understand was that it was the differences between Derek's original, Critic's modified, and Derek's later optimized versions that Critic was arguing about.
I seriously doubt that this is really an overlooked design flaw. I think it's a deliberate part of the design, and one that seems to have worked out rather well. The O(n) nature of COW doesn't appear to have dominated the performance of euphoria code, certainly not in the subjective view of its users, nor, apparently in most or all benchmarking that's been done to date.
Agreed. COW is used in a lot of other places (e.g. Linux-the-kernel and WinNT's kernel's implementation of virtual memory).
In most actual live code, I believe the usual practice is to do "foo[1] = set_element(foo[1], 'A')" instead of "foo = set_element(foo, 1, 'A')". (If one needs to change a majority of elements in the sequence, then even PBR would not be able to improve the algorithm from O(n) to O(1).)
There are some things that can be done to eliminate this without changing anything about the current syntax. I've had a plan for a while to detect situations like the above when inlining code, and avoiding the extra reference altogether.
There's probably more that can be easily done on the translator side, even in cases where we're not inlining. Some of those same tricks might slow the interpreter down unacceptably, which is why I mention the translator, where translation speed isn't terribly important in the same way that parsing and runtime speed is important for the interpreter.
There has been talk about adding a way to pass by reference to euphoria, but that won't happen before 4.1 (if, ultimately, it happens at all).
Matt
So basically, if your assumption is right, then Critic is complaining about the O(n)-ness of "foo = set_element(foo, 1, 'A')", going as far as to state that it is an obvious design flaw that has been overlooked with no O(1) alternative, even though a) Derek already showed a possible O(1) alternative, b) PBR in 4.1 will also give another O(1) alternative, and c) the reasoning for the original design trade-off has been explained (showing that it is a trade-off, not an overlooked flaw), and d) even though he has been shown that the trade-off improved the very code he wrote, that he still claims that the trade-off makes "the design of Euphoria worse than [he] realized".
Actually, after writing the above, I think I am starting to believe your assumption (about Critic) may be right after all.
