Programming Corner from Icon Newsletter 26

March 1, 1988; Icon Version 7

Timing Expressions

In the last Newsletter we promised more results from benchmarking Icon expressions to see how fast they execute. The timings that follow were obtained under Version 7 of Icon. In most cases, there should be little difference between Version 6 and Version 7 timings.

Of course, absolute timings vary greatly from computer to computer. The timings that follow are relative to a mythical "Icon execution cycle". Relative timings may vary somewhat depending on the computer used, the C compiler, and so forth. Although we have not collected data on differences in relative timings for different implementations of Icon, such differences usually should be small enough to ignore. (This remains to be shown, however.) For reference, the relative timings that follow were obtained from running Icon on a VAX 8650 under UNIX 4.3bsd.

To provide some values for timings, suppose values are assigned to variables as follows: 
i := 10
j := 20
r1 := 3.0
r2 := 2e10
Addition is about as simple and conventional operation you can imagine. Here are some timings: 
i + j       4.0
r1 + r2     5.6
i + r1      7.3
You probably would expect real (floating-point) arithmetic to take a little longer than integer arithmetic, but that's not what accounts for the difference in timings for the first two expressions. Icon real numbers are stored in small blocks that have to be allocated (12 bytes each). It's the allocation time that accounts for most of the difference above. (The time required for possible garbage collection as a result of this allocation is not included in the figures above.) The reason why the addition of an integer and a real takes even longer is because of conversion of the integer to a real.

Now consider some operations on strings. Suppose 
s1 := "abcdef"
s2 := string(&cset)
One simple operation is computing the size of a string: 
*s1        2.3
*s2        2.3
As these figures suggest, the time it takes to determine the size of a string does not depend on how long the string is. In fact, the size of a string is computed when the string is created and is stored as part of the string value -- it's right there when it's needed.

String comparison illustrates how subtle some operations are and how difficult it is to know much time it takes to perform some operations. We'll use the following strings in lexical comparisons: 
s1 := "abcdef"
s2 := "abc" || "def"
s3 := repl(s1,100)
s4 := repl(s1,100)
The reason for having duplicate strings will become apparent in the timings: 
s1 == s1     3.8
s1 == s2     5.6
s1 == s3     3.8
s3 == s4    60.6
What's going on here? It takes the same amount of time to compare a string to itself as it does to compare a string to a much longer string. But comparing two strings with the same value takes longer! The reason why there is a difference in the first two timings is that s1 and s2 are physically distinct, even though they have the same value. (That's a property of the way Icon is implemented, not of the language itself.) What happens in string comparison is that two checks are made right away. First, are the values physically the same, as in the first expression above? If so, comparison succeeds without even looking at the characters. Second, are the lengths different, as in the third case above? If so, the comparison fails immediately. Only if neither of these cases apply are the characters compared. The comparison is from left to right, character by character, until there is a mismatch (failure) or there are no more characters (success). Consequently, string comparison takes the longest when the two strings are physically different (produced in different computations) and have a long common initial substring.

There's not much you can do about this when programming -- and you probably shouldn't try to -- but this information may keep you from jumping to unwarranted conclusions and doing things that may be counterproductive.

If timings are not intuitive for simple expressions, what about something more complicated, like operations on a set? To begin with, how time consuming is it to construct a set? 
set()        13.9
That's probably less than you'd expect. (The expression above uses a feature of Version 7 which allows the first argument of set to be defaulted rather than requiring an empty list, as in Version 6.) A word of caution, however -- space has to be allocated for a set; while the figure above includes the time for allocation, it does not account for time that this allocation may subsequently incur in possible garbage collections.

The next obvious question is how long does it take to insert a member in a set. If we start with an empty set S, the timing is 
insert(S,1)  15.3
As you might imagine, that figure doesn't mean much, since how long it takes to look up a value in a set must depend on how big the set is and what its members are. Suppose S contains the first 1,000 integers, as in 
S := set()
every set(insert(1 to 1000)
Here are some figures for looking up integers in S, as well as an integer that's not in S: 
member(S,1)     9.2
member(S,500)   7.5
member(S,799)  12.5
member(S,1001) 14.1
To begin with, it should seem reasonable that it takes longer to find out that a value is not in the set -- whatever technique is used for look up, one way or another, everything has to be checked, while if the value is in the set, it it may be found more quickly. But why does it take longer to find 1 than 500? (The difference in timings is real, incidentally.) Can you guess anything about how sets are implemented from these figures? And, much more importantly, is it faster to look up integers than, say, strings?

Without trying to answer all these questions (rather we hope they will make you think and possibly dig deeper into the internal workings of Icon), we'll just comment that timings for a language like Icon with all its features are possible combinations, is not really subject to reduction to a few simple formulas, guidelines, or tables of timings. We hope (someday, if there's ever time) to compile an extensive list of timings, but the result is more likely to be a curiosity than a useful tool for programmers.

Storage Allocation


Another dimension of expression evaluation relates to the storage that may be allocated. The timings above account for the time required for allocation, but they don't give an insight into how much storage is involved or the time that may be needed later on for garbage collection.

There are several factors involved here. The space allocated for an object may be transient and used only temporarily, until another value takes its place. That's true in expressions like 
while line := read() do
    if check(line) then write(line)
where space is allocated for each string that is read and assigned to line, but then is replaced by the next string. On the other hand, a set or table that is used to hold many values may last from the beginning of program execution until the end, tying up storage all the time. Transient allocation, involves "storage throughput", in which space that is no longer needed can be reclaimed by garbage collection.

The interesting thing is that garbage collection spends most of its time working storage that has to be retained; it barely notices storage that is "garbage". For this reason, storage throughput, as exemplified by the loop above, is comparatively cheap in itself, but if there is a lot of it, it does cause garbage collections. Such collections are fast if there is a lot of garbage, but if there are a lot of "permanent" object like sets and tables around, they pay for it each time.

What all this means is that there is no simple formula for associating a timing penalty for garbage collection with storage allocation. It depends on the storage environment, and in a complicated way.

Nonetheless, it may be interesting to know how much space various kinds of objects take in Icon. This is something that can be expressed in formulas and presented in tables (this is done in the Icon implementation book). However, there are some things about storage allocation that you might not expect.

For example, a string takes only as many bytes of storage as there are characters in it (unlike C, Icon's strings are not null-terminated.) For example, 
s := repl("x",100)
takes 100 bytes of storage. But what about the following expression? 
s[1] := "y"
This expression does not actually change the former value of s (another variable might be sharing the value and must not have its value changed as the result of changing the value of s). Instead, the expression above is a shorthand notation for concatenation and assignment of a new value to s: 
s := "y" || s[2:0]
Consequently, you'd expect this operation also to take 100 bytes of storage. It does take 100 bytes of string storage, but it also allocates 20 bytes for a substring trapped variable block that is used to keep track of the substrings involved and the variable to which the assignment is made. Something like this is necessary, since in the general case, a lot might go on between the subscripting operation and the final assignment. For example, in 
s[1] := compute()
there's not telling what compute may do before an assignment is made to s.

Substring trapped variable blocks contribute to storage throughput, since they are needed only until the assignment is made, which usually is right away. Unfortunately, the present implementation of Icon is not smart enough to detect when substring trapped variables are needed -- it even allocates them when no assignment is made, as in 
write(s[i])
Nontheless, such blocks are transient. They may cause garbage collection, but getting rid of them is fast. And the implementation could be improved so that substring trapped variable blocks are allocated only when they are actually needed.
Icon home page