Re: Questions from a Beginner.
- Posted by mattlewis (admin) May 20, 2009
- 1195 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. 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.
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.
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
