OpenEuphoria

1. Tip of the week - Concetenation

• Posted by ChrisB (moderator) Oct 17, 2010
• 2194 views

This weeks Tip of the week is brought to us by Derek Parnell.

Euphoria makes concatenation so easy, it seems a shame not to use it. However, this simplicity comes with a price. Concatenation is a time consuming thing to do and if your application needs to do lots of it, then it pays to find other ways to do things. So, to get better performance from your application, avoid as much concatenation as possible.

Why is it time consuming? Well, under the hood, whenever you join two objects together, Euphoria makes a new sequence. And if that new sequence is to replace a sequence, the old sequence's memory needs to be deallocated. Consider this...

sequence c 
 
c = "abc" & "def" -- Statement #1 
c &= "xyz" -- Statement #2 
c = append(c, "000") -- Statement #3 

• Statement #1: Memory for 6 items is allocated. "abc" and "def" are copied to the new allocation. 'c' is then made to refer to the new allocation.
• Statement #2: Memory is allocated for 9 items. All of 'c' gets copied and "xyz" gets copied to the new allocation. The memory that 'c' was referring to is deallocated and 'c' is next set to refer to the new allocation.
• Statement #3: Memory is allocated for 12 items. All of 'c' gets copied and "000" gets copied to the new allocation. The memory that 'c' was referring to is deallocated and 'c' is next set to refer to the new allocation.

These is a simplified explanation of what happens because it is a bit more complicated than this (sometimes 'c' already points to enough memory so no extra allocation is needed), but you get the drift.

As you can see, the more you concatenate, the more Euphoria has to allocate RAM, copy stuff around, and in some cases deallocate now unused RAM. One way of preventing all this work is to pre-allocate the result sequence or to use an existing sequence with enough room.

Let's see this in action. Suppose you are writing a function to collect all the vowels in a sentence. (I don't know why but just bear with me for now). Here is a simple way, using concatenation.

function getvowels(sequence text) 
 sequence res 
 
 res = "" 
 for i = 1 to length(text) do 
  if find(text[i], "aeiou") then 
    res &= text[i] 
  end if 
 end for 
 return res 
end function 

That function does a concatenation for every vowel it finds, and each concatenation copies (again) all the vowels found so far.

So here is a faster way...

function getvowels(sequence text) 
 sequence res 
 integer p 
 
 res = repeat(' ', length(text)) 
 p = 0 
 for i = 1 to length(text) do 
  if find(text[i], "aeiou") then 
    p += 1 
    res[p] = text[i] 
  end if 
 end for 
 return res[1 .. p] 
end function 

In this version, we allocate the maximum possible size of the return value (if text were all vowels then the length of text is the maximum size.). This allocation gets done once. Now, as we find a vowel, instead of concatenating, we just copy it to the next available spot in the result sequence. When all is done, we just return everything in the result from 1 up to the last one we copied there. This has a lot less RAM allocation and copying going on, but is a bit more complex. Programming is always an exercise in trade-offs.

By the way, that is not the fastest it could be yet, but that I'll leave that for another Tip-Of-The-Week entry.

--------------------------------------------------------------------------------------------------------------------------------

Things that may seem second nature to you, or if you've ever had an 'aha' moment, let us know, others may see things they have never seen before. Remember, send your tips to totw@openeuphoria.org.

3. Re: Tip of the week - Concetenation

• Posted by petelomax Oct 17, 2010
• 2172 views

Actually, I think this is a bit of an "urban myth".

I heard about this (from Derek) years ago and never really saw any real benefit.

My tests show the maximum gain to be around 15%, normally more like 5%, and that is on a specifically targetted benchmark.

In the real world, very rarely worth it.

Regards, Pete

5. Re: Tip of the week - Concetenation

• Posted by mattlewis (admin) Oct 18, 2010
• 2053 views

Yes, it does typically allocate a little more than it needs, and this can help prevent excess reallocations. It really depends on how many times it will happen, and how many reallocations it will have to do.

When the sequence grows beyond the storage space it has already allocated, we have to realloc to get a bigger space. Sometimes, the OS is able to simply give you more memory starting at the same place. No copying required. But sometimes, it can't do that, and you get a pointer to some other place. At that point, we have to copy the old data into the new memory before we can add the new object to the end of the sequence.

It does only make copies when necessary. However, there are two basic reasons why it's necessary. First, is when you try to change a sequence that has a reference count greater than 1. I think this is the case you're thinking of.

But the other time is when a sequence grows, as described above. It's not the sort of thing a euphoria programmer necessarily thinks about, since it all happens transparently. And in most cases, it's probably not even a major (or noticeable) hit to performance.

But in some situations, where it happens in an inner loop, it can make a significant difference. Like any optimization, it depends on the circumstances.

Matt